我面临着以下问题:
我有一个巨大的文件(假设为 30 GB)，它使用特定的 API 在内存中流式传输。
此 API 仅允许我向前阅读(而不是向后阅读)。但是文件可以无限次读取。
文件包含几乎所有排序的数据，如 99% 的数据已排序，但可能会发生记录不在正确位置的情况，如果所有内容都已排序，则记录应该早于插入.
我正在尝试创建此文件的拷贝，但需要对其进行排序。
有没有一种优雅的方式来做到这一点？
我能想到的唯一方法是最通用的方法:
- 阅读文件
- 创建一批几 GB 的内存，对它们进行排序，将它们写入 HDD 上的文件
- 使用外部合并将所有这些临时文件合并到最终输出中
然而，这并没有使用数据“几乎”排序的特性。会有更好的方法吗？例如不使用 HDD 上的外部文件？
最佳答案
你可以这样做(Python 中的示例)
last = None
special = []
for r in records:
if last is None or r > last:
last = r
else:
special.append(r)
if len(special) > max_memory:
break
if len(special) > max_memory:
# too many out of sequence records, use a regular sort
...
else:
sort(special)
i = 0
for r in records:
while i < len(special) and special[i] < r:
write(special[i])
i += 1
write(r)
while i < len(special):
write(special[i])
i += 1
关于c++ - 排序几乎已排序的大文件，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29288110/