Je dois reconnaître une grande liste d'URL (peu de millions de lignes) comme appartenant à une catégorie particulière ou non. J'ai une autre liste qui a des sous-chaînes que si présentes dans l'URL appartient à cette catégorie. Dire, catégorie A.
La liste des sous-strings à vérifier a environ 10 000 sous-chaînes. Ce que j'ai fait était simplement d'allumer la ligne par ligne dans le fichier Sous-String et recherchez le match et si l'URL appartient à la catégorie A. J'ai trouvé dans des tests qu'il fallait beaucoup beaucoup de temps.
Je ne suis pas un étudiant en informatique, je n'ai donc pas beaucoup de connaissances sur l'optimisation des algorithmes. Mais y a-t-il un moyen de rendre cela plus rapide? Juste des idées simples. Le langage de programmation n'est pas un gros problème, mais Java ou Perl seraient préférables.
La liste des sous-chaînes au match ne changera pas beaucoup. Je recevrai toutefois différentes listes d'URL afin de faire fonctionner cela chaque fois que je l'obtiens. Le goulot d'étranglement semble être les URL comme ils peuvent être très longs.
9 Réponses :
Vous pouvez compresser les sous-chaînes en classes partageant le même préfixe. Cela devrait réduire le temps par une marge importante.
Si vous recherchez des allumettes en déplaçant la chaîne de 1 chaque itération, vous pouvez améliorer votre vitesse tout à fait en utilisant un meilleur algorithme (comme avec des expressions régulières).
L'optimisation du préfixe est effectuée automatiquement si vous mettez toutes les sous-chaînes dans une expression régulière, au moins par un moteur d'expression régulier raisonnablement optimisé.
Je suggère d'utiliser la vénérable Grep au lieu d'utiliser une langue de programmation pour cette tâche. Il utilise le fast Boyer-Moore String Recherche d'algorithme , qui devrait être suffisant pendant quelques millions de lignes.
Je ne suis pas sûr que le GREP serait efficace ici, l'algorithme saute à l'avance s'il n'est pas possible de faire correspondre ce qui fonctionne bien pour un petit nombre de mots, si vous avez 10k mots grep aura probablement du mal à sauter à l'avance (ou de retour sur l'optimisation) car il y aura de nombreux préfixes communs (ou suffixes)
Différentes approches sont bien sûr possibles d'optimiser cela. En ce qui concerne vos antécédents, je vais vous dessiner un simple. Qui supposent que la liste des sous-chaînes ne change pas très souvent.
Je parierais cela va jouer très mal, avez-vous essayé de faire quelque chose comme ça avec des cordes de 10k? BUNLET (1) serait très difficile à tirer efficace et à empêcher que le reste se retrouvera presque aussi inefficace que la mise en œuvre naïve
@ASAF: Il fonctionnera mal si vous avez un mauvais moteur Regexp ou si vous ne précompilez pas la Regexp. Mais sinon il devrait créer un automate presque aussi bon que l'un des algorithmes de KMP. Je voulais donner une approche qui est applicable sans savoir la connaissance de l'informatique profonde. Sinon, KMP est la solution évidente.
@JMG, je suis d'accord KMP est un peu complexe, je voulais dire Aho-Corasick et corrigé ma réponse en conséquence (j'ai utilisé KMP pour quelque chose de différent). Aho-corasick a beaucoup prêt fabriqué implémentations et je ressens est relativement facile à comprendre. En outre, en supposant que vous construisiez une manière d'une manière ou d'une manière ou d'une autre, vous construiriez la regenge «parfaite» sur les cordes 10k que je pense est un problème algorithmique plus difficile que l'original, je ne vois pas comment la solution ne sera pas dépendante (complexité sage) par le nombre des sous-chaînes
@ASAF: Construire l'optimal Regexp ou Meilleure Automaton est une tâche pour le compilateur REGEXP, qui sera probablement mal effectué par les implémentations RegexP basées sur la réaction.
@Asif @jmg Merci gars, je vais tester ces méthodes et voir lequel fonctionne pour moi.
@ASAF: Perl Regex utilise Aho-Corasick
@ASAF: Pourquoi, oui, je avez fait quelque chose comme ça avec ~ 13k Cordes. Fonctionne comme un champion, bien que je l'ai fait dans Perl et Ponthed Step 1 sur le module REGEXP :: Assemblez plutôt que de tenter de construire / optimiser la regex moi-même.
@Dave, je comprends que le Perl :: Assemblez (n'était pas familier avec cet emballage) utilise en fait Aho-Corasick comme implémentation de la même solution. Je choisirais toujours la mise en œuvre Java simplement parce que c'est un code simple et je peux l'optimiser davantage à mes besoins, mais c'est la préférence personnelle.
@Af, @Dave Sherohman: Perl a utilisé Nativement aho-Corasick pour plusieurs chaînes fixes depuis plusieurs années; Regexp :: Assemblez est l'un des nombreux modules similaires qui l'antérieurs et ne sont désormais utiles que pour combiner plus de regex complexes.
@ysth: par "depuis plusieurs années", ai-je raison de supposer que vous voulez dire "depuis Perl 5.10"? Je sais que l'opérateur Smart Match gère ce genre de chose assez bien pour ne pas avoir besoin de r :: A, mais je ne suis pas au courant de quelque chose de similaire ayant été dans le Perl 5.8 Core.
Rien à voir avec la correspondance intelligente; De retour en 2006, c'était en 5.9.4 et en 2007 au 5.10.0: perdoc.perl.org/...
Oui, j'ai implémenté le algorithme Aho-Corasick algorithme en Java Pour le problème que vous suggérez et il a montré une amélioration constante d'environ X180 sur la mise en œuvre naïve (ce que vous faites). Il existe plusieurs implémentations disponibles en ligne, même si je les modifierais pour une meilleure performance. Notez que la complexité des solutions est délimitée par la longueur du mot (dans votre cas l'URL) et non le nombre de sous-chaînes. En outre, cela n'exige qu'un seul passage en moyenne pour la correspondance.
P.S - Nous donnions cette question aux personnes dans des entretiens d'embauche, il existe donc de nombreuses façons de le résoudre. Celui que j'offre est celui que nous utilisons dans le code de production, qui (pour l'instant) bat toutes les autres solutions.
Edit: a écrit le mauvais nom d'algorithme précédemment, fixe ...
Hé, merci, l'algorithme Aho-Corasick a travaillé comme un charme. obtenu environ x50 amélioration de la mise en œuvre naïve. Une plus grande curiosité, quelle était la performance de l'algorithme KMP? cela serait-il encore plus rapide? :)
Nah, oublie environ KMP. C'était une erreur que j'ai faite (copié le nom du mauvais email) L'algorithme Aho-Corasick est linéaire dans la longueur de l'entrée et simple à comprendre / mettre en œuvre je ne me dérangerais pas avec plus d'optimisation à moins que ce soit vraiment nécessaire. Ce que j'ai fait pour accélérer, il suffit d'utiliser des matrices partout pour représenter les bords entre les nœuds (par opposition aux cartes) et l'algorithme d'origine renvoie l'emplacement du match. Vous pouvez accélérer encore plus si vous faites signe cette capacité.
Perl est très bon pour optimiser les longues listes de chaînes alternatives dans une expression régulière (jusqu'à une certaine longueur globale de regex compilée, où elle revient à un mécanisme moins efficace).
Vous devriez être capable de construire une regex pour correspondre à une certaine catégorie comme:
Pour les bibliothèques Java qui mettent en œuvre des algorithmes de recherche de chaîne commune voir les réponses à https: // stackoverflow. com / Questions / 5564610 / Fast-ALERNATIVE-FOR-STRONTINEDEXSHING-STR . Couplé à la parallélisation, vous devriez pouvoir analyser les millions d'URL équitablement rapidement. C'est assez facile de faire; Vous devriez probablement l'essayer et voir si le temps est acceptable ou non avant d'avoir trop besoin de plus en plus en optimisation.
Je l'ai d'abord écrit comme commentaire, mais ensuite je me suis rendu compte, je pense que c'est plus approprié comme une réponse
Vous pouvez utiliser un système de récupération d'informations (comme Apache Lucene en Java) et utiliser Il doit indexer les URL en tant que documents.
Ensuite, après indexation - vous pouvez itérer sur les questions et recherchez chacun d'eux, le résultat sera l'URL correspondante.
Avantages:
* La recherche ne nécessitera pas d'itération sur toute l'URL pour chaque requête.
* Si vous avez plus tard besoin d'intersection ou d'union de sous-chaînes / requêtes - la bibliothèque vous donne cette fonctionnalité
contre:
* L'indexation prendra un certain temps ...
* Vous pourriez avoir besoin d'un espace supplémentaire sur RAM / Disk pour l'Index.
Je pense que c'est une méthode qui mérite d'être explorée, peut-être que le temps consumé tout en indexation vaut le gain de recherche.
J'ai déjà fait ce genre de chose auparavant dans Perl, en comparant une liste de mots-clés ~ 13K contre un flux de données entrant de Twitter pour trouver tous les tweets correspondant à tous ces mots-clés (et quelles mots-clés chaque correspondance). En termes bruts, le code ressemble à: Notez que cela utilise REGEXP :: Assemblez Pour construire la regex, qui ne fait pas partie de la distribution de Core Perl, vous devez donc installer si de CPAN si vous souhaitez adapter ce code. Si vous utilisez Perl 5.10 ou plus tard, il existe également l'opérateur "Smart Match" ( ~~~ ) qui peut faire quelque chose de similaire sans nécessiter de modules supplémentaires.
Je travaille actuellement sur ce problème. Je suis venu à cette conclusion:
Aho-Corasick consommera plus de mémoire tout en faisant de l'arbre. S'il n'y a pas de problème de mémoire que son bien. Mais regarde le chapeau trie une fois. C'est la combinaison de hachage et de trie (arbre). Il fera un arbre à un certain niveau et les caractères restants formeront une valeur de hachage qui doit être marquée dans la table de hachage.
Désolé pour plus de langage technique. Mais je pense que Hat Trie est une meilleure option si vous recherchez une URL spécifique dans la liste de l'URL. (J'ai formé une trie de chapeau qui consommera 12 Mo pour stocker 6lacks d'URL.)
Et même vous pouvez l'accorder selon vos besoins. (Pour la mémoire de la loi ou pour des performances plus rapides)
Vous pouvez utiliser un système de récupération d'informations (c.-à-d. Lucene - en Java) pour indexer les URL, puis rechercher la chaîne, l'indexation prendra du temps, mais il gagnera du temps pour chaque "requête" - ne pas avoir à itération sur le Toute la liste.
10K fois, disons, 10 millions est de quoi, 100 milliards? Ouais, ça prendra du temps, peu importe la langue. Si quelque chose est dans la catégorie A, cela signifie-t-il qu'ils ne peuvent être dans aucune autre catégorie? Si tel est le cas, vous pouvez tout supprimer de la grande liste qui est assignée à une catégorie
La liste des sous-chaînes est constante Il n'y a aucune raison de prendre beaucoup de temps, voir ma réponse La longueur de la liste n'affecte que la taille prise en mémoire de l'automate et même ce sera probablement petit
La parallélisation vous aiderait-elle? En plus des autres optimisations bien sûr.
Bien que j'ai répondu à cela avant de vérifier, il s'agit d'un duplicata de http: / /Stackoverflow.com/questions/1765579/fast-algorithm-fo R-Recherche à la recherche-sous-sous-bornes-in-a-string