磁盘的碎片整理有什么好的算法实现?
一般的磁盘工具整理速度慢，效率不高，
能否通过分析磁盘的文件结构，提出某种最优原则，
建立切实可行的数学模型，找到一种高效的整理文件的算法!
问题可以如下描述:
给出一个很大的棋盘,上面摆放有很多颜色的棋子,
其中各个颜色的棋子都有号码表示,从1到n.
每个棋子占用一个格子.如果棋盘按行来给予每一格子编号,
那么对棋子来说,其顺序是杂乱无章的,
现在需要做一件事,就是把同颜色的棋子放到一块去,
并且同颜色的棋子按顺序摆放.
试给出一种算法,移动最少的棋子使得棋盘上棋子顺序化!
其实如果理解有些问题的话,想想这个题目原是磁盘碎片整理的另一种描述,
各位大师应该就能看懂题目了吧,颜色则表示文件,棋子编号应该是文件
块的号码,而棋盘号码则是硬盘分区号码.
希望大家可以讨论讨论!
提供一个好的解法
问题点数：100、回复次数：32Top
1 楼chenhu_doc（^0^纯一狼^0^ 看书看到大笑，直到不能自已）回复于 2006-08-30 20:53:23 得分 0
顶先Top
2 楼lofe811（）回复于 2006-08-30 21:07:37 得分 0
markTop
3 楼lann64（昆仑大鹏＠迦楼罗）回复于 2006-08-30 21:17:21 得分 0
我理解磁盘整理工具速度慢，不是算法问题，而是需要防意外中断和防意外加解锁等问题导致的额外开销。不过作为算法讨论，LZ的问题也有点意思。Top
4 楼hawkjxr（子陵仲）回复于 2006-08-31 20:38:02 得分 0
LZ是什么东西?Top
5 楼lann64（昆仑大鹏＠迦楼罗）回复于 2006-08-31 20:47:50 得分 0
LZ就是楼主，在这就是说你了。至于是什么东西？我不知道，我没说.... ：－）Top
6 楼LS_Winson（风飘隐侠(-_-)）回复于 2006-09-02 14:20:44 得分 0
呵呵，有趣的题目，关注，似乎要很好的数学根基Top
7 楼Kenmark（fenix）回复于 2006-09-02 14:23:11 得分 0
mark一下不太了解Top
8 楼hawkjxr（子陵仲）回复于 2006-09-02 20:40:14 得分 0
我是数学系的,可是拿他没辙,
Top
9 楼hawkjxr（子陵仲）回复于 2006-09-02 20:42:34 得分 0
所以希望在这里得到大家的帮助,看看有什么好办法啊Top
10 楼hawkjxr（子陵仲）回复于 2006-09-02 20:44:37 得分 0
我先有一个思路就是:在内存里面整理好文件分配表在对比分配表的不同移动外存.
至于内存里面移动,次数多点没有关系,关键是如何让前后对比差别不大
而且感觉这个问题象是一个多关键字排序问题Top
11 楼tanta（tanta）回复于 2006-09-06 20:06:50 得分 0
要看内存和空余磁盘空间的大小.Top
12 楼DentistryDoctor（不在无聊中无奈，就在沉默中变态）回复于 2006-09-06 20:34:19 得分 0
要想与现在流行的工具比较高下可能不大容易吧。Top
13 楼hawkjxr（子陵仲）回复于 2006-09-06 22:21:27 得分 0
要是能找到市面上软件的算法也不错,关键是我们连这个算法都找不出来如何
去优化比流行的工具的算法更好?Top
14 楼AFIC（A Fool In China）回复于 2006-09-07 09:34:54 得分 0
我只看过win自带的磁盘碎片整理
他的规律是
1他是利用你磁盘最后的剩余空间来做临时存放的
比如你100m的磁盘，用了80m都在前边
那整理的时候他全都利用最后20m来操作
2磁盘整理和你说的棋盘不同
首先，磁盘整理的时候，一些文件是不能移动的，
就是系统文件拉之类的，红色的
其次，磁盘整理并不是达到完全排序的效果，
磁盘整理以后只会使碎片达到百分之几以下，
并不是说，整理完就没有碎片了
3磁盘整理存在连续操作，
如果比喻成你的棋盘，那么如果棋盘
是100有80个子，都在最前边
那么磁盘整理相当于可以一次移动20个子。
具体的算法我觉得有必要知道碎片到底是怎么存放的
他和文件是怎么连接的，才好往下考虑。Top
15 楼hawkjxr（子陵仲）回复于 2006-09-07 16:11:00 得分 0
回答AFIC(AFIC)的几个问题:
1.同意你的见解,不过这样就很慢,我们需要找到好一点的移动方式,因为这样的话,那么几乎所有的文件都经过了移动,我们要做的就是尽可能减少移动,尽可能快的移动,因为很多文件是不需要移动的.
不然的话,不管文件有多么复杂,只要我们有一个空白的文件块,就可以把整个磁盘给整理好,只是这样时间效率很低.
2.在win里是考虑到安全问题而不能移动系统文件,但是如果你真的想移动,是可以的,在注册表里面修改一个键值就可以了.所以完全排序的效果虽然是理想化的问题,但是换句话说,如果我们不仅仅把这个算法应用在磁盘整理，那么完全排序的算法是需要考虑的.
3.就是因为考虑到算法的健壮性才需要我们通过分析棋子或者说文件的存放规律，也就是说我们做的是一个模型,而不是具体问题,对于可能出现的问题在程序中需要考虑到,那么才能满足算法的健壮性
我的见解就是这样了
Top
16 楼hawkjxr（子陵仲）回复于 2006-09-07 16:19:40 得分 0
前不久和我的一个学计算机的同学讨论了一下有了一个大概的想法,但是还不是很好,希望得到大家的一些看法
1.我们标记A1,A2,B1,B2,......虽然存放的时候没有顺序的概念,但是文件里面本身是有顺序的,我们给以这个标记,并记为list1,
2.我们假设要排成A1,A2,......;B1,B2,......;C1,C2,......;......;N1,N2,......;......
记为list2.
3.假设list1的第一块不是A1,那么在list1,和list2的同一个空白位置,假设在list的最后一格,
4.移动方式:我们先把list1的棋子x移到listend,然后在list1中找到A1,移动到list1_1,然后A1的位置得到一个空格,对比list1,list2.
list2(position(A1,list1))是y,那么在list1中找到y,把y移动到A1腾挪出来的空格.......
如此移动,我们可以满足所有块仅移动一次得到完全排序.
Top
17 楼AFIC（A Fool In China）回复于 2006-09-08 09:46:18 得分 0
我觉得你忽略了一个问题，
我们先简化以下问题，比如棋盘只有40个格子
a1到a8占前八个格子，b1到b10占9到38这30个格子
a9占到39这个格子，那么你觉得最好的挪动是怎样的？
其实如果是磁盘整理，那他直接就告诉你不需要整理了。
因为磁盘整理并不相当于你提出的棋盘模型，
他之所以要整理，是碎块太多，影响访问（访问一个文件的操作需要增加挪动磁头了），
所以，我猜测他根本的算法只是简单的比较碎块数量，以及要挪动的相关文件快的比例即可
比如上边的只挪1个碎片，但开销是30个格子（a8后没有空各，b本身要保持连续），
换一下a1到a7占前七个格子，b1到b10占8到37这30个格子
a8占到39这个格子，a9占到38这个格子，这样要是挪动后，
好处是消除了2个碎片，开销是30，虽然比上边提高了一倍，
但是，还有一种方法是a8,a9交换，
这样也是消除了1个碎片，开销只有1
只要能判断了，可以根据经验，算出一个开销的临界值
大于这个开销不做，小于的作，我觉得这是一个解决办法吧？Top
18 楼lann64（昆仑大鹏＠迦楼罗）回复于 2006-09-08 10:35:46 得分 0
还在讨论呐，看来楼主真要写个磁盘整理程序。
象楼上说的那样，磁盘整理确实不同于lz的棋盘。磁盘整理主要是为了减少磁头移动次数。大家知道磁头只有一个维的移动，也就是说在同一磁道上读写，磁头是不移动的，推理出，同一柱面上磁头也是不移动的。因此，文件存放如果在同一柱面上，即使不连续，也不需要整理。其实文件连续存放读取速度不是更快，而是可能更慢。因为读写磁盘控制，往往是按块发向控制器的指令，当前一个指令完成，下一个指令写控制器的时候，磁盘可能已经转过了起始位置，那磁头就要等位置再转回来时，也就是等磁盘转一圈后再读，这样，比文件在同一柱面均匀分散放置可能读的更慢。
还有，现在磁盘逻辑处理后保存在cmos里的柱面，磁道信息不一定是真实的磁盘信息，如何找到真实的磁盘柱面信息也是一个问题。
从整个盘来说，尽量将文件集中存放在盘的前端，也是同样目的，使本次读和下次读之间，使磁头移动尽量少距离。Top
19 楼hawkjxr（子陵仲）回复于 2006-09-08 16:57:47 得分 0
这个连续在计算机内部指的就是同一柱面上面连续啊,不然按一个上面上的磁道来连续，那还真得不如不移动呢Top
20 楼hawkjxr（子陵仲）回复于 2006-09-08 17:05:01 得分 0
AFIC(AFIC) ,
我觉得你说的临界值是可以采用的,但是我们在这里讨论的并不是可不可移动,而是肯定要移,但是怎么移最好,
比如这里究竟应该选择排成A1..A9B1..B30好还是B1..B30A1..A9比较好,哪种顺序下移动次数少
我们需要文件内连续，但是并不需要文件间也连续，也就是说B30与A1或者说A9与B1之间可以存在空格.
正因为空格的存在而减免了移动的可能,不然真要和磁盘整理完全一样,那么
不可避免的要把所有的空白块移动硬盘的最后才行!~Top
21 楼supercow（超级牛）回复于 2006-09-09 16:09:02 得分 0
小弟在这里有个想法~~~ 如果先分析程序的调用文件 把他们放到靠近的位置这样 有利于提高系统速度吧..Top
22 楼hawkjxr（子陵仲）回复于 2006-09-09 22:48:59 得分 0
问题是如何评价分析呢?
而且如果这些靠近的位置互相冲突重叠呢?
比如A,B两个文件混合在一块交错Top
23 楼hawkjxr（子陵仲）回复于 2006-09-12 12:20:39 得分 0
请大家帮忙想想啊Top
24 楼hawkjxr（子陵仲）回复于 2006-09-13 23:28:22 得分 0
????????????????????????????Top
25 楼supercow（超级牛）回复于 2006-09-15 18:52:13 得分 0
交错~~~ 那就要用贪婪算法来权衡孰重孰轻了~~~ 比如优先大文件.或者带S属性的系统文件.
把与之交错的其他文件移除范围然后组合以后,找空间放入. 也就是有这个问题: 在权衡上,左右为难.导致象windows自带的整理工具 老是整理不彻底吧. 考虑得越多 速度越慢 而且出现 进退维谷的现象就更多. 还有就是如果整理范围太大 意外中止程序....后果.....Top
26 楼DelphiGuy（）回复于 2006-09-15 19:08:21 得分 0
碎片整理使用空闲磁盘做临时交换用，而不使用内存，是为了防止数据丢失。
另外，文件连续其实就是按柱面排列的。因为逻辑扇区的编号就是按柱面顺序排列，而不是一个面之内的道顺序排列。文件系统的设计者已经考虑到了访问效率的问题。
Top
27 楼programfanny（）回复于 2006-09-16 06:25:50 得分 0
Mark and learn.Top
28 楼lxface（公主）回复于 2006-09-16 12:39:10 得分 0
不错呀Top
29 楼hawkjxr（子陵仲）回复于 2006-09-22 16:45:50 得分 0
超级牛的意思还是不明白?
是说选择并不一定是最优或者说只是一种规则而不是较优的考虑Top
30 楼majia777（我不是随便的人,我随便起来的不是人）回复于 2006-09-23 19:19:03 得分 0
LZ是什么东西?
lz,就是盖大楼的民工Top
31 楼hai1039（天下）回复于 2006-09-26 10:53:59 得分 0
其实最快的整理方法是把所有文件拷到另一硬盘，全部删除前一个硬盘，再拷回来。Top
32 楼hai1039（天下）回复于 2006-09-26 10:55:46 得分 0
整理硬盘主要是DOS和FAT系统下用。
在NTFS系统下一般就没有必要去整理碎片。Top
