z***m
发帖数: 1602 | 1 如果有1M个数，每个数大概是100,0000,0000这样的整数，是不是hash table的size也
要很大啊，比如说等于数组中的最大数。最近做coursera上的algorithm，被这道题卡
住了。如果数组小或者里面的数值小，还行。但是如果是1M个数，每个都很大，就算得
很慢。有没有什么好的实现方法啊？
详细题目在：
http://blog.csdn.net/neostar2008/article/details/7782858
考虑的区间是[-10000,10000]而非[2500, 4000]. |
z****e
发帖数: 54598 | 2 那就是string了，而非integer
string是二维变量，所以会有hashcode碰撞的问题
所以会出现大量equals判断，所以效率自然会下降
那最常见的做法就是分解步骤
比如针对前三位做一个hashmap
然后中间三位再单独存一个hashmap，最后四位再存一个hashmap
这样通过一级一级找下去，搜索效率就高了
自然空间复杂度也会相应升高 |
R******1
发帖数: 58 | 3 刚好之前上过这课。是Homework6.1吗？ hash table完全可以做呀。LZ卡在哪里呀？
【在 z***m 的大作中提到】
: 如果有1M个数，每个数大概是100,0000,0000这样的整数，是不是hash table的size也
: 要很大啊，比如说等于数组中的最大数。最近做coursera上的algorithm，被这道题卡
: 住了。如果数组小或者里面的数值小，还行。但是如果是1M个数，每个都很大，就算得
: 很慢。有没有什么好的实现方法啊？
: 详细题目在：
: http://blog.csdn.net/neostar2008/article/details/7782858
: 考虑的区间是[-10000,10000]而非[2500, 4000].
|
A***o
发帖数: 358 | 4 Linear hashing, extensible hashing
如果有1M个数，每个数大概是100,0000,0000这样的整数，是不是hash table的size也
要很大啊，比如说等于数组中的最大数。最近做coursera上的algor........
【在 z***m 的大作中提到】
: 如果有1M个数，每个数大概是100,0000,0000这样的整数，是不是hash table的size也
: 要很大啊，比如说等于数组中的最大数。最近做coursera上的algorithm，被这道题卡
: 住了。如果数组小或者里面的数值小，还行。但是如果是1M个数，每个都很大，就算得
: 很慢。有没有什么好的实现方法啊？
: 详细题目在：
: http://blog.csdn.net/neostar2008/article/details/7782858
: 考虑的区间是[-10000,10000]而非[2500, 4000].
|
z***m
发帖数: 1602 | 5 我python code是这样写的:
def TwoSum_HashTable(lst, target):
hashTable = dict()
for x in lst:
hashTable[x] = True
for x in lst:
y = target-x
if y in hashTable and x != y:
return (x, y)
return None
lines = open('2sum.txt').read().splitlines()
data = map(lambda x: int(x), lines)
count = 0
for t in range(-10000, 10000+1):
if(TwoSum_HashTable(data, t)):
count +=1 # # find if there exists such pair
print count
----------------------
这个2sum.txt有1M的integer，最大的接近1，000，0000，0000，我运行几个小时都不
出结果啊。
【在 R******1 的大作中提到】
: 刚好之前上过这课。是Homework6.1吗？ hash table完全可以做呀。LZ卡在哪里呀？
|
f*******b
发帖数: 520 | |
z***m
发帖数: 1602 | 7 是的，问题是算太慢了，几个小时不出结果啊
【在 R******1 的大作中提到】
: 刚好之前上过这课。是Homework6.1吗？ hash table完全可以做呀。LZ卡在哪里呀？
|
B*****g
发帖数: 34098 | 8 那就别用hash, lol
【在 z***m 的大作中提到】
: 是的，问题是算太慢了，几个小时不出结果啊
|
r*********n
发帖数: 4553 | |
R******1
发帖数: 58 | 10 我之前做的时候是【2500， 4000】，所以很快， 7s左右
刚试了试这个新的range，本来以为是线性增加，时间应该也不不大；
但是，很多target无法满足，就要遍历hash table一次。
【2500， 4000】 用时 7s 命中率1477/1500 绝大多数都很快break了
【0， 1000】 用时 1m56s 命中率445/1000 多于一半要遍历完
建议楼主试试先sort（O（NlogN)), 然后binary search （O（logN)).
2sum.txt ～4MB 所以建设1M个ints
range是【-10000， 10000】， 20000
用hashtable worst case 20000*1M
用sort然后binary search， worst case 1M*log（1M） + 20000*log（1M） ～ 20*1M |
R******1
发帖数: 58 | 11 折腾了一会儿 用C++ 15m搞定【-10000， 10000】
关键的优化其实只有一个： -10000 ～ 56 都没有match的…… 因为最小的两个数和是
56
left = min(sorted[0]+sorted[1], -10000)
LZ可以试试看 |
