recherche efficace sur un php iterator

Question

J'ai un itérateur personnalisé (TokenIterator pour être précis, qui le compare, bien, le code php sous forme de jeton). Les articles sont des objets simples ( « sacs de propriété » avec certaines méthodes de normalisation ajoutée)

Je dois implémenter la fonctionnalité de recherche, qui doivent trouver si  1. une itérateur contient un autre ou  2. deux (ou plus) itérateurs se chevauchent (avec quelques paramétrisation).

À l'heure actuelle j'utilise l'approche naïve de (1) -. O (NxM) recherche double boucle, et (2) ne sont pas encore mis en œuvre

Avant de commencer à ré-écrire vraiment algorithmes chaîne de recherche intelligente, je voudrais savoir s'il existe une mise en œuvre effective de cela? Peut-être quelque chose enfoui au plus profond dans un certain cadre ou d'une bibliothèque générique de réutiliser? Et quel algorithme sera ici le plus approprié?

Answer 1

La première chose qui vient à l'esprit est que vous parlez des opérations ensemble, pour lesquelles itérateurs sont sans doute pas la meilleure solution.

Je ne sais pas s'il y a une solution existante pour votre problème, mais comme une solution générale, j'utiliser des tables de hachage. Par exemple, construire une table de hachage en utilisant les jetons de la première série (je vais l'appeler fixé à partir de maintenant, puisque je me sens Iterator est pas le meilleur mot) et vous pouvez le faire en Theta (N), puis essayer de insérer l'autre ensemble dans la même table de hachage. La première fois que vous obtenez une collision, vous saurez qu'il ya un chevauchement. Bien sûr, cela fonctionne bien si l'espace de hachage est large et la fonction de hachage garantit une quantité négligeable de collisions, mais il est toujours possible de coder une sorte de solution de contournement.

Compte tenu de PHP a des tableaux associatifs (qui sont une forme de tables de hachage), vous pouvez également créer un tableau comportant les symboles comme les clés, qui encore une fois peut être fait dans Theta (N), puis utilisez array_key_exists. Il est tout à fait possible que array_key_exists est rien de plus qu'un balayage linéaire de la liste des clés, comme je ne suis pas familier avec les internes de PHP, mais je suis tout à fait confiant que si les tableaux associatifs sont mis en œuvre sous forme de tables de hachage, il devrait être mis en œuvre beaucoup plus efficacement qu'un balayage linéaire.

Answer 2

Si vos itérateurs peuvent être casté en tableaux, vous pouvez utiliser array_diff et array_intersect. Sinon, vous devez mettre en œuvre ce que ces fonctions font sous le capot - promenade sur vos structures et de comparer. Parce que les données que vous itérer ne sont pas triées, ni ne le savez-vous quoi que ce soit d'autre à ce sujet, vous avez pas d'autre choix.