m****r 发帖数: 6639 | 1 我有一个40个entry的string array。 现在需要implement contains。 不知道直接
scan快还是放在map里面快。 谁来说说? 感觉还是放在map里面快点。 但是这个
threshold到底在哪里? |
b**l 发帖数: 25 | |
S**********C 发帖数: 161 | 3 40 entries? It doesn't make any difference, don't bother.
【在 m****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我有一个40个entry的string array。 现在需要implement contains。 不知道直接 : scan快还是放在map里面快。 谁来说说? 感觉还是放在map里面快点。 但是这个 : threshold到底在哪里?
|
m****r 发帖数: 6639 | 4 at the end of the day, it probably doesn't matter. but i was just wondering
since the issue came up.
【在 S**********C 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 40 entries? It doesn't make any difference, don't bother.
|
g*****g 发帖数: 34805 | 5 Suffix tree最快,但你这数量级,是吃饱了撑的。到4M级别,差别就很大。
【在 m****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我有一个40个entry的string array。 现在需要implement contains。 不知道直接 : scan快还是放在map里面快。 谁来说说? 感觉还是放在map里面快点。 但是这个 : threshold到底在哪里?
|
m****r 发帖数: 6639 | 6 我日。
我的问题就是, 在这个数量级, 那个快?
如果只有三个, 肯定直接scan快。 对吧。 如果4m, suffix tree快?hashmap快?
反正比linear scan快。
但是中间, 有个时候, linear scan 变成不快了。 对吧? 这个时候在那里?
【在 g*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Suffix tree最快,但你这数量级,是吃饱了撑的。到4M级别,差别就很大。
|
g*****g 发帖数: 34805 | 7 40个都是suffix tree快,只不过差不了太多。
【在 m****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我日。 : 我的问题就是, 在这个数量级, 那个快? : 如果只有三个, 肯定直接scan快。 对吧。 如果4m, suffix tree快?hashmap快? : 反正比linear scan快。 : 但是中间, 有个时候, linear scan 变成不快了。 对吧? 这个时候在那里?
|
p****i 发帖数: 6135 | 8 答案是: depends
姐给你分析一下:
先说linear scan, 这个容易
空间: one table with 40 entries. 40*sizeof (yourobject)
时间:
如果查找不成功, 你需要40 个 index++ 操作 外加40个比较操作: 40 ++
operations and 40 compare operations
如果成功, averagely 你需要 40/2 =20 个index ++ operations and 20 compare
operations
【在 m****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我日。 : 我的问题就是, 在这个数量级, 那个快? : 如果只有三个, 肯定直接scan快。 对吧。 如果4m, suffix tree快?hashmap快? : 反正比linear scan快。 : 但是中间, 有个时候, linear scan 变成不快了。 对吧? 这个时候在那里?
|
g*****g 发帖数: 34805 | 9 This is wrong. Both the hotspot JDK and OpenJDK implementation uses a native
O(nm) algorithm for contains operation. Not a Boyer–Moore string which is
O(n).
So worst case can be 40 * sizeof(search key) * average_sizeof(keys)
compare
【在 p****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 答案是: depends : 姐给你分析一下: : 先说linear scan, 这个容易 : 空间: one table with 40 entries. 40*sizeof (yourobject) : 时间: : 如果查找不成功, 你需要40 个 index++ 操作 外加40个比较操作: 40 ++ : operations and 40 compare operations : 如果成功, averagely 你需要 40/2 =20 个index ++ operations and 20 compare : operations
|
p****i 发帖数: 6135 | 10 然后来看hashmap
hashmap的特点就是用空间换时间
重点就是你准备用多大的空间来换你的时间呢?
而且这个也跟你的key密切相关
举个简单的例子, 如果你的key是integer, range 1-100
那最简单的hash就是建立一个空间为100个entry 的hash table
直接用key作index
这样你的查找时间无论是miss还是hit, 都只有一个compare operation而已
稍微变化一下这个例子, 如果你key的range是1-10000呢?
你是否还会愿意用一个空间为10000个entry的hashtable来储存你仅仅40个的数据?
如果说,你不愿意, 那你需要在hash function上下功夫,
generally speaking, hash function通常的形势是: Key part 1 * prime number A
+ Key part 2 * prime number B +...
通过认真设计hash function来达到节约一定空间的目的
但是, 不是没有代价的, 代价就是这个hash function的复杂度。
不考虑collision
这时候查找的cost, 无论miss还是hit都是: 一次hash function的运算 cost + 一
次compare 的cost
在这个简单的例子里: 通常一个hashfunction的运算cost已经超过了你的20次++
and 20 次compare的cost
compare
【在 p****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 答案是: depends : 姐给你分析一下: : 先说linear scan, 这个容易 : 空间: one table with 40 entries. 40*sizeof (yourobject) : 时间: : 如果查找不成功, 你需要40 个 index++ 操作 外加40个比较操作: 40 ++ : operations and 40 compare operations : 如果成功, averagely 你需要 40/2 =20 个index ++ operations and 20 compare : operations
|
|
|
p****i 发帖数: 6135 | 11 我Java不熟, 就是high level, theoretical的给他分析一下
而且我不太理解: 你的这个说的是空间还是时间?
native
is
【在 g*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : This is wrong. Both the hotspot JDK and OpenJDK implementation uses a native : O(nm) algorithm for contains operation. Not a Boyer–Moore string which is : O(n). : So worst case can be 40 * sizeof(search key) * average_sizeof(keys) : : compare
|
p****i 发帖数: 6135 | 12 上面是general speaking,
回到你的问题本身, 如果object本身是string的话,
重点就是看hash string --》 index 的cost
和compare two strings的cost了
这个对java熟的人可以具体分析下
好了, 我也要问个问题了, 大家帮忙看下
【在 p****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 然后来看hashmap : hashmap的特点就是用空间换时间 : 重点就是你准备用多大的空间来换你的时间呢? : 而且这个也跟你的key密切相关 : 举个简单的例子, 如果你的key是integer, range 1-100 : 那最简单的hash就是建立一个空间为100个entry 的hash table : 直接用key作index : 这样你的查找时间无论是miss还是hit, 都只有一个compare operation而已 : 稍微变化一下这个例子, 如果你key的range是1-10000呢? : 你是否还会愿意用一个空间为10000个entry的hashtable来储存你仅仅40个的数据?
|
r*****s 发帖数: 985 | 13 要考虑节约空间的话
用bloom filter
还是要看具体要求。
【在 p****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 然后来看hashmap : hashmap的特点就是用空间换时间 : 重点就是你准备用多大的空间来换你的时间呢? : 而且这个也跟你的key密切相关 : 举个简单的例子, 如果你的key是integer, range 1-100 : 那最简单的hash就是建立一个空间为100个entry 的hash table : 直接用key作index : 这样你的查找时间无论是miss还是hit, 都只有一个compare operation而已 : 稍微变化一下这个例子, 如果你key的range是1-10000呢? : 你是否还会愿意用一个空间为10000个entry的hashtable来储存你仅仅40个的数据?
|
w**z 发帖数: 8232 | 14 试一下,不就知道了?用啥hash ,存啥value 都有关系。
【在 m****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我日。 : 我的问题就是, 在这个数量级, 那个快? : 如果只有三个, 肯定直接scan快。 对吧。 如果4m, suffix tree快?hashmap快? : 反正比linear scan快。 : 但是中间, 有个时候, linear scan 变成不快了。 对吧? 这个时候在那里?
|
m****r 发帖数: 6639 | 15 contains() for what?
native
is
【在 g*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : This is wrong. Both the hotspot JDK and OpenJDK implementation uses a native : O(nm) algorithm for contains operation. Not a Boyer–Moore string which is : O(n). : So worst case can be 40 * sizeof(search key) * average_sizeof(keys) : : compare
|
g*****g 发帖数: 34805 | 16 说的是JDK里 String.contains是一个O(nm)时间复杂度的实现,不是最好的算法。
【在 m****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : contains() for what? : : native : is
|
m****r 发帖数: 6639 | 17 yes. i understand all this. but again, the question i am asking is, at how
many strings does the linear scan becomes slower.
【在 p****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 然后来看hashmap : hashmap的特点就是用空间换时间 : 重点就是你准备用多大的空间来换你的时间呢? : 而且这个也跟你的key密切相关 : 举个简单的例子, 如果你的key是integer, range 1-100 : 那最简单的hash就是建立一个空间为100个entry 的hash table : 直接用key作index : 这样你的查找时间无论是miss还是hit, 都只有一个compare operation而已 : 稍微变化一下这个例子, 如果你key的range是1-10000呢? : 你是否还会愿意用一个空间为10000个entry的hashtable来储存你仅仅40个的数据?
|
m****r 发帖数: 6639 | 18 why do i need contains()? i would used equals.
【在 g*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 说的是JDK里 String.contains是一个O(nm)时间复杂度的实现,不是最好的算法。
|
g*****g 发帖数: 34805 | 19 你自己说 "现在需要implement contains"。
完全匹配简单,hashmap性能就不错。
【在 m****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : why do i need contains()? i would used equals.
|
m****r 发帖数: 6639 | 20 我再日。 contains 是针对这个40个string的list说的。 不是per string。
【在 g*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你自己说 "现在需要implement contains"。 : 完全匹配简单,hashmap性能就不错。
|
|
|
m****r 发帖数: 6639 | 21 看来我的语言障碍很大。 不适合xiecode。
【在 m****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我再日。 contains 是针对这个40个string的list说的。 不是per string。
|
p****i 发帖数: 6135 | 22 你去研究一下java default string hash function
然后回来update我们一下吧
how
【在 m****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : yes. i understand all this. but again, the question i am asking is, at how : many strings does the linear scan becomes slower.
|
c*********e 发帖数: 16335 | 23 恩,我也觉得hashmap可以解决楼主的问题,既然楼主要快的那个。hashmap其实是
hashtable,就是o(1),這個速度绝对快。
【在 p****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 然后来看hashmap : hashmap的特点就是用空间换时间 : 重点就是你准备用多大的空间来换你的时间呢? : 而且这个也跟你的key密切相关 : 举个简单的例子, 如果你的key是integer, range 1-100 : 那最简单的hash就是建立一个空间为100个entry 的hash table : 直接用key作index : 这样你的查找时间无论是miss还是hit, 都只有一个compare operation而已 : 稍微变化一下这个例子, 如果你key的range是1-10000呢? : 你是否还会愿意用一个空间为10000个entry的hashtable来储存你仅仅40个的数据?
|
f**r 发帖数: 865 | 24 想要知道的话写个benchmark test试试呗。:-) |
F****n 发帖数: 3271 | 25 Depends. Usually a Map uses hash table and thus depends on how you calculate
the hashcode for a string.
Therefore, your map's performance will vary for different values in your
array because the default String.hashCode depends on the char sequence.
【在 m****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我有一个40个entry的string array。 现在需要implement contains。 不知道直接 : scan快还是放在map里面快。 谁来说说? 感觉还是放在map里面快点。 但是这个 : threshold到底在哪里?
|
F****n 发帖数: 3271 | 26 Again, the answer is "depend on what specific strings"
{"1", "2", "3"....} is different from {"one", "two", "three"...}
how
【在 m****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : yes. i understand all this. but again, the question i am asking is, at how : many strings does the linear scan becomes slower.
|
m****r 发帖数: 6639 | 27 ok. what i have is a list of locale strings, such as "en_US", "nl_BE", etc.
【在 F****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Again, the answer is "depend on what specific strings" : {"1", "2", "3"....} is different from {"one", "two", "three"...} : : how
|