c# - 大集合Server和Path的排序算法

Question

在 C# 中工作，我想编写一个高效的排序算法，它将包含未排序的服务器和路径组合列表的文本文件作为输入，并输出一个已排序的文件。

作为练习，我在假设输入数据大小将超过可用内存的情况下工作，因此我正在考虑一次将文件一个 block 读入内存，进行快速排序(或者堆排序，也许？ )，将排序后的 block 输出到临时文件，然后进行合并排序以产生最终输出。

输入文件的格式由我决定。它可以只是 UNC 路径列表(服务器和路径作为单个字符串)，也可以是 CSV，其中服务器和路径作为单独的字段。

我的问题是，让服务器和路径成为我的数据结构中的独立实体并分别对其进行评估是否有任何好处？

将服务器和路径分开将消除在路径比较运行期间比较服务器名称的必要，但需要额外运行以按服务器排序，并且考虑到可用内存限制，将需要我以某种方式缓存排序的服务器列表，增加磁盘 IO 开销。

是否有一些技术可以通过在我的输入中提供服务器和路径作为单独的字段来优化此类应用程序的性能？

鉴于数据集的性质，我可能会考虑其他任何优化技术吗？

编辑:这是一项一次性任务。我不需要稍后查找条目

Answer 1

I am thinking of reading the file into memory a chunk at a time, doing a Quick sort (or a Heap sort, maybe?), outputting sorted chunks to temporary files, then doing a merge sort to produce the final output.

这是一个非常合理的计划。

另一种解决方案是:创建一个磁盘上的 b 树，然后将所有数据一次一条记录插入到 b 树中。你永远不需要在内存中拥有超过几页的 b-tree，你可以从未排序的列表中一次读取一条记录。一旦它在 b 树中，就按顺序读回它。

Having server and path separate would eliminate having to compare the server names during the path comparison run, but require additional run to sort by server and, given the available memory constraint, would require me to somehow cache the sorted server lists, increasing disk IO overhead.

好的。

My question is whether there is any benefit to be had from having server and path be separate entities in my data structure and evaluating them separately?

你刚才说了优缺点是什么。您已经列出了它们。如果您已经知道答案，为什么还要问这个问题？

Is there some technique I can leverage to optimize performance of such an application by providing server and path as separate fields in my input?

可能是的。

How can I know for sure?

两种方式编写代码并运行它。更好的将被观察到更好。

Any other optimization techniques that I might consider given the nature of the dataset?

您的问题和推测还为时过早。

首先设定一个绩效目标。

然后尽可能清楚和正确地实现代码。

然后仔细测量，看看您是否达到了目标。

如果你这样做了，早点下类去海滩。

如果没有，请获取分析器并使用它来分析您的程序以找出性能最差的部分。然后优化那部分。

继续这样做，直到您达到目标或放弃。