m******9
发帖数: 968 | 1 问题1： 2个超大file，memory容不下，都是unsorted，假设里面全是integer。如何找
出2个文件
中的重复部分？
我看到的一个答案是：
step 1: external merge sort F1 (file 1): 将原文件分成若干个temporary
smaller
files, 对每个temporary small file进行quicksort，然后对所有smaller files 进行
multiple-way merge sort, 重新合并成一个sorted big file.
step 2: traverse F2, binary search F2's each element in F1,
step 3: 能找则是common element，如果找不到则继续读取判断下一个element
问题2： 1个超级大文件，unsorted，里面都是string。如何找出所有的anagram？
这个题没什么思路
求教了，谢谢 |
g*******y
发帖数: 1930 | 2 在一个超大的file里面做binary search太费时间了
一般找重复的，用hash最好了，可以minimize disk I/O |
m*****f
发帖数: 1243 | 3 en.
1. hash or bitmap
2. trie
【在 g*******y 的大作中提到】
: 在一个超大的file里面做binary search太费时间了
: 一般找重复的，用hash最好了，可以minimize disk I/O
|
g*******y
发帖数: 1930 | 4 第二个用trie，到底能不能比hash更省空间，我一直有个疑惑
【在 m*****f 的大作中提到】
: en.
: 1. hash or bitmap
: 2. trie
|
m*****f
发帖数: 1243 | 5 这个我也没有真的实现过....不过string题用trie直观, 好处应该更容易吹
【在 g*******y 的大作中提到】
: 第二个用trie，到底能不能比hash更省空间，我一直有个疑惑
|
s***t
发帖数: 49 | 6 hash talbe 放在什么地方呢？
【在 g*******y 的大作中提到】
: 在一个超大的file里面做binary search太费时间了
: 一般找重复的，用hash最好了，可以minimize disk I/O
|
a****n
发帖数: 1887 | |
m******9
发帖数: 968 | 8 hash应该也有memory的限制，这个文件太大，不能全部放到hash table中，能不能解释
一下，怎么
hash呀，谢谢
【在 g*******y 的大作中提到】
: 在一个超大的file里面做binary search太费时间了
: 一般找重复的，用hash最好了，可以minimize disk I/O
|
g*******y
发帖数: 1930 | 9 存在disk上吧，内存肯定存不下
【在 a****n 的大作中提到】
: hash 和 trie都有内存问题吧？
|
m******9
发帖数: 968 | 10 长牙的羊： 我没有跟上你的第2题答案的思路，能不能解释一下，trie如何找anagram
，是不是还要
将每个word都事先sort一遍呀？谢谢
【在 m*****f 的大作中提到】
: en.
: 1. hash or bitmap
: 2. trie
|
m*****f
发帖数: 1243 | 11 是呀
【在 m******9 的大作中提到】
: 长牙的羊： 我没有跟上你的第2题答案的思路，能不能解释一下，trie如何找anagram
: ，是不是还要
: 将每个word都事先sort一遍呀？谢谢
|
m******9
发帖数: 968 | 12 另外问一下，如果用trie，把每个words都sort，（假设是升序）。 在trie中也可以判
断出是
anagram了，但是到时该如何将这些words还原呢？谢谢
【在 m*****f 的大作中提到】
: 是呀
|
v*****t
发帖数: 127 | 13 one idea might be：
store complete words at leaf node, or you can store dictionary indexes of
the words if you want to save some space
【在 m******9 的大作中提到】
: 另外问一下，如果用trie，把每个words都sort，（假设是升序）。 在trie中也可以判
: 断出是
: anagram了，但是到时该如何将这些words还原呢？谢谢
|
