硬件DV 关于systemverilog 的associative array

associative array 的exits()， 求教function的复杂度为什么是O(1)
按照小伙伴的说法是一个entry瞅一眼， 那不是O(n)吗？还是说因为一起瞅？

谢谢

akajin 发表于 2019-4-14 07:26
这个解释非常给力，谢谢！

后来查了一下发现我的说法其实不严谨，hash table 是其中一种 implementation（https://en.wikipedia.org/wiki/As ... ble_implementations），只有这种实现的时候才是 O(1) ，其他情况LZ有兴趣可以看看~

associate array 其实是 hash table，指定 key 去访问/查看是否存在是 O(1)，不需要遍历

半吊子水平盲猜一个，别当真
associative array大概使用hash实现？所以对search(exist)来说是O(1) average, O(n) worst case？

转码版居然有人问硬件问题。。

adh360 发表于 2019-4-14 06:54
associate array 其实是 hash table，指定 key 去访问/查看是否存在是 O(1)，不需要遍历

这个解释非常给力，谢谢！

kts1mg 发表于 2019-4-14 07:11
转码版居然有人问硬件问题。。

这不是学习版吗？w(ﾟДﾟ)w。。。。

这玩意又不能综合，只是给你仿真验证的时候省事用的。讨论他的“复杂度”没啥意义吧，都是仿真的时候模拟出来的。

补充内容 (2019-4-15 00:11):
另外哪怕是模拟这块 ，这玩意内部多半是平衡树……毕竟他还维护有序。。

yangff 发表于 2019-4-14 23:10
这玩意又不能综合，只是给你仿真验证的时候省事用的。讨论他的“复杂度”没啥意义吧，都是仿真的时候模拟出 ...

复杂度在simulation的时候影响solver的快慢 =）
- 考虑到block designer start from feature ramp up 到regression clean 需要run 50+次
- 考虑到block level verification在SoC可能会被re-use

adh360 发表于 2019-4-14 08:20
后来查了一下发现我的说法其实不严谨，hash table 是其中一种 implementation（https://en.wikipedia.org ...

谢谢！ 我仔细读一下