关联数组,又称为哈希表(hash table),是一种非常好用的数据结构。
在程序中,我们可能会遇到需要消重的问题,举一个最简单的模型:
有一份用户名列表,存储了 10000 个用户名,没有重复项;
还有一份黑名单列表,存储了 2000 个用户名,格式与用户名列表相同;
现在需要从用户名列表中删除处在黑名单里的用户名,要求用尽量快的时间处理。
这个问题是一个小规模的处理量,如果实际一点,2 个表都可能很大,比如有 2 亿条记录。
我最开始想到的方法,就是做一个嵌套的循环,设用户名表有 M 条记录,黑名单列表有 N 条记录,那么,循环的次数是 M * N 次!
PHP 版代码:
foreach($arrayN as $nameN) {
if ($nameM == $nameN) {
// 本行执行了 M * N 次!
unset($arrayM[$keyM]);
}
}
}
return $arrayM;
?>
另一种方式,利用数组索引。
PHP 是一种弱类型的语言,不像 C 语言那样有严格的变量类型限制。C 语言的数组,每一个元素的类型必须一致,而且索引都是从 0 开始。
PHP 的数组,可以用字符串作为索引,也称为关联数组。
数组索引,有一个天然的限制就是不会重复,而且访问的时候不需要查找,可以直接定位。
还是刚才的那个问题,我们采用另一种办法。
把黑名单列表的用户名组织到一个数组里,数组的索引就是用户名。
然后,遍历用户列表的时候,只需直接用 isset 查询那个用户名是否存在即可。
PHP 版代码:
if (isset($arrayHash[$nameM])) {
// 本行执行了 M 次!
unset($arrayM[$keyM]);
}
}
return $arrayM;
?>
可以看到,优化过的代码,循环次数是 M + N 次。
假如 M 和 N 都是 10000,优化前,循环了 1 亿次;优化后,只循环了 20000 次,差了 5000 倍!
如果第二个程序耗时 1 秒,则第一个程序需要将近一个半小时!
最近在做 Perl 的开发,Perl 在处理文本的时候有很高的效率,同样,它也支持关联数组!
只是语法和 PHP 的那种类 C 的方式有很大不同,以第二段代码为例,Perl 版的实现:
#!/usr/bin/perl
my %arrayHash;
for(my $i = 0; $i < @arrayN; ++$i) {
$arrayHash{$arrayN[$i]} = 1;
}
for(my $i = 0; $i < @arrayM; ++$i) {
if ($arrayHash{$arrayM[$i]}) {
$arrayM[$i] = undef;
}
}
Perl 的数组是 @ 开头,哈希是以 % 开头,unset 实际上就是 undef。
Perl 的哈希和数组都是有具体类型的,而且向函数传递变量的时候要传引用,我刚学时间不长,快被搞晕了。
不过,现在刚刚实现了一个以 hash 方式进行 IP 位置查找的算法,平均比较次数大概在 3 次左右,比传统的折半查找方式少了很多次,它大概需要 8 次以上的比较。
刚刚做了一个小的性能测试,对 10 万个 IP 进行查找,在我的台式机上,耗时 15 秒,平均每秒 7500 次,感觉还不错,呵呵。
不过,还是喜欢 PHP 的数组,真的很强大!
God Bless PHP!
虽然我对Perl忘得差不多了,但是映像中Perl遍历散列表应该用while循环,然后配合current keys each等等进行遍历
PHP里面也有类似的用于遍历的函数,当然效率最高的是foreach
PHP的方式虽然好,也有缺点,比如把两种混在一起,使得纯粹作为数组的时候效率不高
用in_array只要循环m次