您的位置：程序门 -> .net技术 -> c#

请教如何对文本文件内容进行排序，请提供一个比较有效率的设计思路

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

请教如何对文本文件内容进行排序，请提供一个比较有效率的设计思路

发表于：2007-01-24 10:13:39 楼主

我是c#的初学者，现在碰到个问题要对文本文件的内容进行排序，生成新的文件
考虑过讲文件每行读入数组，但如果文件很大，肯定会很耗内存，有什么其他方法比较有效率的对文本文件排序吗？就像unix的sort命令一样（暂不考虑使用数据库排序）

发表于：2007-01-24 10:24:441楼得分:0

关注一下

你是指所有的方块字按拼音排序？？

发表于：2007-01-24 11:27:332楼得分:0

我指的是字符串（不管是数字，还是方块字）的比较方法已经实现，根据这个比较方法，将文件中的每行按升序或降序排列重新生成一个文件

发表于：2007-01-24 11:40:193楼得分:0

你的文件有多少大?不用内存的话,只能用硬盘存放临时的数据,那会频繁的读写硬盘,得不偿失啊,即使几百兆的文件全部读到内存中也不多花多少时间的

发表于：2007-01-24 11:44:364楼得分:0

还有就是通过算法,把文件分成几块,每块分别排序,然后再是块与块之间的排序
具体的代码去找本 < <数据结构> > ,当中的排序算法中好像有一个快速算法可以这样用的。

发表于：2007-01-24 11:47:275楼得分:0

全部读到内存中不可以的，会用到虚存，会更加频繁读写硬盘，而且效率极低~

发表于：2007-01-24 11:47:296楼得分:0

用内存是最好的办法
unix下的sort似乎是写到/tmp下的缓存里面

发表于：2007-01-24 12:12:147楼得分:0

sort命令也是很耗内存的...

如果你想最大限度的节约内存.

那么streamreader,每次只用读两行.进行冒泡排序...

发表于：2007-01-24 13:42:568楼得分:0

其实问题跟文本不文本已经不重要了,问题的真正意义如下:

因为排序无非是2个操作,一个是比较,一个是移位（或称交换~~);
效率无非也是2个,一个是时间复杂度一个是空间复杂度.

在这个具体问题上空间复杂度远比时间复杂度重要（就是宁可多耗10倍比较时间也不该多耗1倍空间------因为显然内存比硬盘的速度快千倍,可以把空间节约起来只用内存操作那操作多100倍也无所谓了)

另外一方面比较的花费远比读写要少.

这个问题在于解决空间和读写次数之间的矛盾~~~ 有意思,先记号着,想到再来

发表于：2007-01-24 13:54:289楼得分:0

我有个思路如下,首先先确定文件的大致大小和可以使用内存而不占用虚拟页面文件的内容大小

假设文件是500m, 可以在此使用的内存是150兆, 那么把文件分割为5份,每次读取一份以后在内存中排序（因为在内存中进行,其实排序时交换内容使用的内存量可以忽略---只有1行数据)

然后写入一个临时文件.最后得到5个临时文件

用5个读取器分别按行读5个文件,每读1行就比较5个的大小（当然,才5个,也是在内存里比了),然后最大的写入目标文件,再从最大的那个的源临时文件读下一行.以此循环到读完为止.

这样总的读取硬盘记录数为2n（假设原文件共n行),写硬盘记录数也是2n,总io记录数是4n

因为可能比较100次的时间也没一次io操作久,所以最大限度减少io操作,多比较几次问题不大了.

发表于：2007-01-24 14:03:4810楼得分:0

其实不管分多少块只要超过1块,那么最后的io记录总数都是4n, 所以在这里分成10和分成5分成100都一样,但是分得越细需要的内存最少但需要的额外操作也越多（比如创建文件的io操作)这里需要取一个合理的值,上面说的5个有点偏小了,其实可以更多.理论上,理想状态下（只有io操作费时间,其他操作都是假设瞬间完成), 应该是总记录数开平方.就是假设文件里有一亿行记录,分开成1万个文件是最省内存的,而且总的读写操作也一样是4n （不过多了10000次创建文件的操作..)

为什么是开平方呢,因为这样可以使前面分组时的内存比较和后面循环读取时的比较的规模一样大,最大限度节约了内存,如果分再细,在后面循环读取时会费更多内存,分再少,则前面费更多内存.

但是具体情况毕竟不是理想状态,还要根据比较算法的耗时和其他具体上下文环境来判断.但有一点是肯定的就是主要矛盾是在io操作上,在其他地方去追求极致也不如io省点,其他地方多花点,毕竟写内存比写硬盘快1000倍.

发表于：2007-01-24 14:07:2611楼得分:0

shrinerain（圣影雨) 说的读2行进行冒泡排序,内存是省了,但是io次数绝对不可接受,总需要的io记录数是

读取记录次数: （n*n+n)/2
写记录次数: n*n - n

总合远大于 4n （n很大)

发表于：2007-01-24 14:13:0212楼得分:0

to syeerzy（快乐永远*先天下之乐而乐*后天下之忧而忧*)

每次150兆肯定会用虚存的，不管你内存有多大
不信你试一下

//那么streamreader,每次只用读两行.进行冒泡排序
我倒认为这个方案可行，相邻行的读写，其实是缓冲区的内容
操作系统不会傻到读一行就把内部缓冲区清掉

写的过程恐怕要用临时文件

发表于：2007-01-24 14:16:5113楼得分:0

你用一个150兆的文本文件，一次性读到一个字符串，然后以\r\n分隔split到字符串数组
与readline到数组
两种方式比较一下，哪个快，就知道了~

发表于：2007-01-24 14:51:0914楼得分:0

syeerzy说的有点道理
我总结了一下思路：
1.如果文件大小低于某个值（比如小于物理可用内存)，可以全部读入物理内存进行排序
我的想法是定制一个结构，并实现icomparable接口，用array.sort（)方法进行排序。
2.如果文件大于某个值，全部读入内存会造成频繁使用虚拟内存。则将文件分割成几快，读入内存进行排序后形成几个临时文件。同时读取这几个临时文件，对几个文件中的内容进行排序，写入最后的结果文件。确实这样做“读取硬盘记录数为2n（假设原文件共n行),写硬盘记录数也是2n”，硬盘io是最耗资源。
3.最后实现还是要考虑不少问题，比如内存使用大小和产生临时文件多少的平衡点。
欢迎大家继续讨论，找出更好的处理方法

发表于：2007-01-24 14:55:0915楼得分:0

//那么streamreader,每次只用读两行.进行冒泡排序

能再具体点说明一下实现方式吗？

发表于：2007-01-24 18:50:3516楼得分:0

顶一下，还有谁有好的方法吗

其他资讯