4

我有一个自定义迭代器（准确地说是 TokenIterator，它可以迭代，好吧，标记化的 php 代码）。项目是简单的对象（添加了一些规范化方法的“属性包”）

我必须实现搜索功能，它必须查找 1. 一个迭代器是否包含另一个或 2. 两个（或更多）迭代器重叠（带有一些参数化）。

目前我对 (1) - O(NxM) 双循环搜索使用天真的方法，并且 (2) 尚未实现。

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

4

2 回答 2

3

首先想到的是你在谈论集合操作，迭代器可以说不是最好的解决方案。

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

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

于 2010-12-27T00:15:42.240 回答
1

如果您的迭代器可以转换为数组，则可以使用array_diffand array_intersect。否则，您必须实现这些功能在后台执行的操作 - 遍历您的结构并进行比较。因为你迭代的数据没有排序，你也对它一无所知，所以你别无选择。

于 2010-12-24T10:01:53.177 回答