有效搜索php迭代器

发布时间：2020-12-13 17:05:29 所属栏目：PHP教程来源：网络整理

导读：我有一个自定义迭代器(准确的TokenIterator,迭代,好,标记化的 PHP代码).项目是简单的对象(添加了一些规范化方法的“属性包”) 我必须实现搜索功能,必须找到if ?1.一个迭代器包含另一个或 ?2.两个(或更多)迭代器重叠(有一些参数化). 目前我使用朴素的方法(1)

我有一个自定义迭代器(准确的TokenIterator,迭代,好,标记化的 PHP代码).项目是简单的对象(添加了一些规范化方法的“属性包”)

我必须实现搜索功能,必须找到if
?1.一个迭代器包含另一个或
?2.两个(或更多)迭代器重叠(有一些参数化).

目前我使用朴素的方法(1) – O(NxM)双循环搜索,(2)尚未实现.

在开始重新实现真正的智能字符串搜索算法之前,我想知道是否存在一些有效的实现呢？也许深埋在某些框架或通用库中的东西可以重用？哪种算法最适合这里？

解决方法

首先想到的是你在讨论set操作,迭代器可能不是最好的解决方案.

我不知道你的问题是否有任何解决方案,但是,作为一般解决方案,我会使用哈希表.例如,使用第一组的标记构造一个哈希表(我将从现在开始调用它,因为我觉得Iterator不是最好的词),你可以在Theta(N)中进行,然后尝试将另一组插入同一个哈希表中.第一次碰撞时,你会发现有重叠.当然,如果哈希空间很宽并且哈希函数保证可忽略不计的冲突量,这种方法很有效,但是总是可以编写某种变通方法.

鉴于PHP具有关联数组(它是一种散列表的形式),您还可以创建一个以令牌作为键的数组,这也可以在Theta(N)中完成,然后使用array_key_exists. array_key_exists绝对有可能只是对键列表的线性扫描,因为我不熟悉PHP的内部结构,但我非常有信心,如果将关联数组实现为哈希表,它应该实现得更多比线性扫描有效.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!