大量字串的排序问题。可能不一定有解 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

大量字串的排序问题。可能不一定有解

大量字串的排序问题。可能不一定有解# JobHunting - 待字闺中

e*92013-02-15 08:02

1 楼

假设有1M个字串，字串的平均长度1MB，需要对这些字串做排序。
因为字串会有变动，而且对排序速度有要求，所以基于写文件的merge sort不适用。
如果直接load到内存，至少需要1TB的内存。
之前想到的是算每个字串的hash值，然后直把hash load到内存中做树或者堆排序，这
样可以减少内存的消耗。但是一般的hash函数会改变原来的排序，所以这个地方会有问题
有没有什么比较好的排序方式？

p*22013-02-15 08:02

2 楼

问题
distributed?

【在 e****9 的大作中提到】

: 假设有1M个字串，字串的平均长度1MB，需要对这些字串做排序。
: 因为字串会有变动，而且对排序速度有要求，所以基于写文件的merge sort不适用。
: 如果直接load到内存，至少需要1TB的内存。
: 之前想到的是算每个字串的hash值，然后直把hash load到内存中做树或者堆排序，这
: 样可以减少内存的消耗。但是一般的hash函数会改变原来的排序，所以这个地方会有问题
: 有没有什么比较好的排序方式？