J'ai des gros fichiers (centaines de MB) que j'ai besoin de rechercher plusieurs cordes uniques à 20 caractères.
J'ai trouvé que l'utilisation de l'alternance de tuyaux métacaracter pour assortir des expressions régulières comme Quelle est la limite à la taille de cette taille? Combien d'expressions puis-je chaîner ensemble comme ça? Cela causera-t-il une sorte de débordement à un moment donné? Y a-t-il une meilleure façon de faire cela?
Dans un effort pour garder ma question à garder ma question, je n'ai pas souligné le fait que j'ai déjà mis en œuvre du code à l'aide de cette approche d'alternance et je l'ai trouvé utile: sur un étui à essai avec un ensemble de données typique, heure de fonctionnement a été réduit de 87 minutes à 18 secondes - une vitesse de 290x, apparemment avec O (n) au lieu de O (n * m).
Ma question concerne la manière dont cette approche peut être censée fonctionner lorsque d'autres utilisateurs exécutent ce code dans le futur en utilisant les ensembles de données beaucoup plus importants avec des fichiers plus gros et plus de termes de recherche. Le code d'origine O (N * M) était le code existant qui a été utilisé depuis 13 ans et sa lenteur a été signalée récemment à mesure que les ensembles de données liés au génome qu'il fonctionne ont récemment obtenu beaucoup plus grand. (string1 | string2 | string3) accélère le processus de recherche beaucoup (contre la recherche de une corde à la fois).
3 Réponses :
Si vous allez simplement avoir une expression régulière du formulaire (Word1 | Word2 | .... | Wordn), pourquoi ne pas simplement créer un tableau associé de booléens. Cela devrait être très rapide.
EDIT STRY> P> # before the loop, set up the hash
%words = (
cat => 1,
dog => 1,
apple => 1,
.... etc
);
# A the loop to check a sentence
foreach $aword (split(/ /, $sentence))
if ($words{$aword}) print "Found $aword\n";
Je pense que cette approche fonctionnerait bien pour les plus petits ensembles de données qui sont entièrement chargés dans la mémoire avant la recherche.
Si vous avez une expression régulière simple comme (Word1 | Word2 | ... | Wordn), le moteur Regex construira une machine à états capable de passer une fois sur l'entrée une fois pour déterminer si la chaîne correspond à si la chaîne correspond à.
Note latérale: En informatique théorique, les «expressions régulières» sont définies de manière à ce qu'un seul passage soit toujours suffisant. Toutefois, la mise en œuvre pratique de la regex ajoutez des fonctionnalités permettant la construction de modèles de regex qui ne peuvent pas être toujours implémentés comme une seule passe ( Voir cet exemple ).
Encore une fois, pour votre modèle d'expressions régulières, le moteur utilisera presque certainement un seul passage. Cela va probablement être plus rapide que la lecture des données de la mémoire plusieurs fois ... et presque certainement beaucoup plus rapidement que la lecture des données plusieurs fois à partir du disque.
Il n'y a pas de limite théorique dans l'ampleur d'une expression régulière, mais pratiquement, il doit s'adapter dans les limites d'une plate-forme et d'une installation spécifiques. Vous devez découvrir de manière empiriquement si votre plan fonctionnera, et je serai ravi de voir vos résultats.
Une chose que je dirais, c'est que vous devriez compiler l'expression séparément avant de continuer à l'utiliser. Soit cela ou appliquer l'option / o pour compiler une seule fois (c'est-à-dire promettre que le contenu de l'expression ne changera pas). Quelque chose comme ça
C'est étrange: mes résultats étaient exactement opposés, c'était beaucoup plus rapide pour faire plusieurs recherches séparées que d'une seule avec une alternance. Puis-je vous suggérer de dire un peu plus de votre code?
Utilisez-en un de REGEXP :: Assemblez , regexp :: trie , Regex :: présuf pour assembler des altérations plus efficaces
Non nécessaire: p3rl.org/...
Oui, comme Daxim le dit, la meilleure approche dépendra de la manière dont les préfixes communs courants de vos chaînes sont. En général, le moteur Regex est plus intelligent que vous, et ces jours n'explosent pas, alors vous êtes préférable d'essayer et de voir ce qui se passe.