N***m
发帖数: 4460 | 1 大量的URL字符串，如何从中去除重复的，优化时间空间复杂度。
我只想到了最笨的办法。 |
D*******a
发帖数: 3688 | 2 hash
【在 N***m 的大作中提到】
: 大量的URL字符串，如何从中去除重复的，优化时间空间复杂度。
: 我只想到了最笨的办法。
|
g*********s
发帖数: 1782 | 3 trie
【在 D*******a 的大作中提到】
: hash
|
g*****g
发帖数: 34805 | 4 Practically, people will put it in DB, using a b-tree index.
And in the scale of 10s of millions, use DB segment.
【在 N***m 的大作中提到】
: 大量的URL字符串，如何从中去除重复的，优化时间空间复杂度。
: 我只想到了最笨的办法。
|
c*****t
发帖数: 1879 | 5 用 DB 的最根本问题是，importing 很痛苦。没必要。query 倒是简单。
前面说的 hash 就不错。文件太大的话，可以用 hash 先 partition 一下。
再把同一 hash 里的 sort / unique 搞定。
这题有点 Map/Reduce 的意思。完全可以平行计算。
【在 g*****g 的大作中提到】
: Practically, people will put it in DB, using a b-tree index.
: And in the scale of 10s of millions, use DB segment.
|
D*******a
发帖数: 3688 | 6 db里面的deduplication实际上也是用hash。
【在 c*****t 的大作中提到】
: 用 DB 的最根本问题是，importing 很痛苦。没必要。query 倒是简单。
: 前面说的 hash 就不错。文件太大的话，可以用 hash 先 partition 一下。
: 再把同一 hash 里的 sort / unique 搞定。
: 这题有点 Map/Reduce 的意思。完全可以平行计算。
|
l********f
发帖数: 149 | 7 With Hash, the complexity will be O(n) and will take O(n) space as well.
O(n) space maybe too much, is there any better way? |
l********f
发帖数: 149 | 8 Sorting is O(nlgn) but with zero space.
【在 l********f 的大作中提到】
: With Hash, the complexity will be O(n) and will take O(n) space as well.
: O(n) space maybe too much, is there any better way?
|
