在PHP中是否存在替代数据结构而不是数组,我可以从不同的索引技术中受益？

Question

最近我遇到了一个包含数十万个值的数组的问题,我唯一想做的就是检查一个值是否已经存在.在我的例子中,这是来自网络服务器日志的IP.所以基本上是这样的:

in_array(ip2long(ip),$myarray) 做了这个工作

然而,查找时间急剧增加,10k的查找大约需要17秒左右.

所以在这种情况下,我并不关心我是否有重复,我只需要检查是否存在.所以我可以将IP存储在索引中,如下所示:

isset($myarray[ip2long($ip)])

并且繁荣,查找时间从17秒(或更多)下降到静态时间0.8秒,进行10k查找.作为我刚使用的数组条目的值int 1.

我认为数组索引可能基于一些b-tree,它应该有log(n)查找时间和hashmap上的索引.

在我的情况下使用索引工作正常,但有没有任何数据结构,我可以使用哈希映射作为值索引,其中多个值也可能会出现(我意识到这只有意义,如果没有太多的重复,我不能使用范围/搜索请求有效,这是树结构的主要好处)？

Answer 1

在与PHP捆绑的SPL库中,除了简单数组之外,还有一系列替代数据结构,包括链表,堆栈,堆,队列等.

但是,我怀疑如果你翻转你的数组,你可以使你的逻辑效率更高,允许你对键进行查找(使用array_key_exists()函数)而不是搜索值.数组索引是散列而不是btree,可以通过密钥进行非常快速的直接访问.

但是,如果您正在使用数组中的10k条目,则可能更好地利用数据库,您可以在其中定义自己的索引.