x*******i
发帖数: 26 | |
w********s
发帖数: 214 | |
b*******e
发帖数: 123 | 3 指点下为什么要排序？ 直接往dictionary里加是O(n)，排序是O(nlog(n))。直接加不
是要快点？ |
a******e
发帖数: 710 | 4 我觉得按文件大小排序和读硬盘的时间相比基本可以忽略不计。
不过Hash在这里确实比排序更快点儿。
【在 b*******e 的大作中提到】
: 指点下为什么要排序？ 直接往dictionary里加是O(n)，排序是O(nlog(n))。直接加不
: 是要快点？
|
b**********5
发帖数: 7881 | 5 按size排序， 和dictionary hash，这两个N， 不一样。 如果size不一样， 你根本
就不需要hash， 就知道这两个文件不一样了
【在 b*******e 的大作中提到】
: 指点下为什么要排序？ 直接往dictionary里加是O(n)，排序是O(nlog(n))。直接加不
: 是要快点？
|
b*******e
发帖数: 123 | 6 倆dictionary,hash size 分类先，hash内容再分类。还是比O(nlog(n))要快。而且如
果相同size文件不多的话，这个会很快。 |
u*****o
发帖数: 1224 | 7 觉得题有点眼熟呢，原来是我的帖子。。
我被VMWARE拒掉了，不知是思路不对还是题没答完的原因，可能两者都有吧。
不过发现这种hot startup实在是难啊，1个小时满满一页的题！都是做ACM出身的吧才
能答出来吧。。不适合挫人练手呀。 |
d***n
发帖数: 832 | |
h**o
发帖数: 548 | 9 文件怎么hash？谁是key谁是value?
【在 b*******e 的大作中提到】
: 倆dictionary,hash size 分类先，hash内容再分类。还是比O(nlog(n))要快。而且如
: 果相同size文件不多的话，这个会很快。
|
A***o
发帖数: 358 | 10 看MD5 digest，相当于做个hash join
【在 x*******i 的大作中提到】
: 原题是 http://www.mitbbs.com/article_t/JobHunting/32549243.html。
: 里面提到的思路是 先排序文件大小，然后比较文件内容hash.
: 大家有没有别的思路呀？
|
|
|
b*******e
发帖数: 123 | |
c***d
发帖数: 26 | 12 hash 能判断两文件是否完全相同。
如果改一下题目，在一批文件中找相似（但不完全相同）文件呢？有什么好想法？
【在 x*******i 的大作中提到】
: 原题是 http://www.mitbbs.com/article_t/JobHunting/32549243.html。
: 里面提到的思路是 先排序文件大小，然后比较文件内容hash.
: 大家有没有别的思路呀？
|
s********u
发帖数: 1109 | 13 还是类似的吧。
其实这个就是下面这个题的变种：
两个数组，找最接近的一对数字。解法就是分别排序，然后用两个指针，i =0； j = 0
;开始往后遍历。如果j对应的数字偏大，那么就i++；反之j++。
对文件的话，应该就是将hash值以某种方法排序，比如数值序或者词典序。
【在 c***d 的大作中提到】
: hash 能判断两文件是否完全相同。
: 如果改一下题目，在一批文件中找相似（但不完全相同）文件呢？有什么好想法？
|
c***d
发帖数: 26 | 14 这就不是正常的hash了。
传统意义上的hash要求即使源做很小的改动，目标hash值也有巨大变化，尽量要求hash
值与源不相关。
对hash值进行排序没意义呀。
0
【在 s********u 的大作中提到】
: 还是类似的吧。
: 其实这个就是下面这个题的变种：
: 两个数组，找最接近的一对数字。解法就是分别排序，然后用两个指针，i =0； j = 0
: ;开始往后遍历。如果j对应的数字偏大，那么就i++；反之j++。
: 对文件的话，应该就是将hash值以某种方法排序，比如数值序或者词典序。
|
s********u
发帖数: 1109 | 15 那就只好找能够反映源的变化程度的hash办法了。
hash
【在 c***d 的大作中提到】
: 这就不是正常的hash了。
: 传统意义上的hash要求即使源做很小的改动，目标hash值也有巨大变化，尽量要求hash
: 值与源不相关。
: 对hash值进行排序没意义呀。
:
: 0
|
p*****3
发帖数: 488 | 16
两种算法对每个文件做hashing, 不同内容的如果两个hash值还能一样赶快去买彩票了
【在 x*******i 的大作中提到】
: 原题是 http://www.mitbbs.com/article_t/JobHunting/32549243.html。
: 里面提到的思路是 先排序文件大小，然后比较文件内容hash.
: 大家有没有别的思路呀？
|
e*******8
发帖数: 94 | 17 local sensitive hashing...
【在 c***d 的大作中提到】
: hash 能判断两文件是否完全相同。
: 如果改一下题目，在一批文件中找相似（但不完全相同）文件呢？有什么好想法？
|
