海量游戏ROM去重

    我是个游戏迷，经常会下载各种游戏ROM，有的时候从不同网站会下载到相同的ROM，但是文件名称会略有不同（有的区别也非常大），因为ROM非常多，有上万个，如果要手动使用diff命令比较的话非常浪费时间，所以我决定使用脚本写一个，刚好我安装了cygwin，刚好上面的perl可以拿来用:-)

    一个最直观的想法是将每一个ROM分别与其他ROM进行比较，这种方法的时间复杂度想当可观：O(n!)，我在简单的尝试一下就放弃了。大概每次调用diff需要0.1秒（这是比较两个40k的ROM需要的时间，大部分的rom都远大于此），有兴趣的可以算一下2000个ROM需要执行多久。

    显然，diff是一个非常消耗时间的操作，如果能尽可能的减少其调用次数的话，就可以显著的提高效率。并不是每两个rom都需要进行比较的，我们可以从这些rom中提取某些属性，并且认为具有相似或相同属性的rom才值得我们去比较。

    基于这种思路，我们可以使用文件的大小作为hash的key，这样一来，只有大小相同的ROM才会进行比较。这种说法并不十分准确，因为hash可能会将不同的key映射到同一个bucket，但是perl中没有map，所以只好退而求其次了。好在在我使用的过程中这种情况出现的不多。

代码如下，注释已经相当详细了。

#!/usr/bin/perl -w

use strict;
use warnings;

use lib "$ENV{'HOME'}/bin/lib/";

# 个人使用的cmd库，提供了cmd函数用来执行一个shell命令，并将执行结果和输出返回
use cmd;

# 将命令行传入的文件名末尾的\n去掉
map(chomp($_), @ARGV);

# 将文件按照不同的大小放入哈希表
my %size_hash;

# 处理命令行传入的每一个文件
foreach my $file (@ARGV) {
    # 获取文件大小
    my $size = sizeof($file);

    # 与size大小的文件列表逐一比较
    foreach my $same_size (@{$size_hash{$size}}) {
        my ($rv, @outs) = cmd("diff \"$file\" \"$same_size\"");
        if ($rv == 0) {
            # 找到大小相同且内容一致的文件
            print("$file & $same_size are the same!\n");
        }
    }

    # 将文件放入对应size的文件列表
    push(@{$size_hash{$size}}, $file);
}

sub sizeof {
    my ($file) = @_;

    # 利用du -b获取文件大小，-b参数会返回文件的字节数
    my ($rv, @outs) = cmd("du -b \"$file\"");
    if ($rv != 0) {
        print("@outs\n");
    }

    # 去掉多余的空白字符，将结果保存到size中
    $outs[0] =~ /(.+)\s/;
    my $size = $1;

    return $size;
}

BTW: 有些游戏ROM本身比较大，而且大小常常比较固定，比如FC ROM的典型大小：40K/128K/256K/512K，这可能会造成我们以大小为key的哈希出现较多碰撞，其实解决方法也非常简单：压缩一下。这不仅仅使得碰撞次数减少，而且因为文件本身小了，diff也会进一步提高效率。再者，一般模拟器都会支持压缩格式的ROM。真是一举多得啊！