Le moyen le plus rapide de rechercher 1 Go + une chaîne de données pour la première occurrence d'un motif de Python

Je ne sais pas définitivement si la méthode () code> est plus rapide que la méthode de recherche code> fourni par Python's re code> (expressions régulières) module, mais il n'y a qu'un seul moyen de savoir.

Si vous recherchez une chaîne, ce que vous voulez, c'est ceci: p>

import re
def findit(1_gb_string):
    yield re.search(1_kb_pattern, 1_gb_string)

http://www.youtube.com/watch?v=v5HZOJ6UK-S Sera de la plus utile pour vous. C'est une conférence mit sur la programmation dynamique

Autant que je sache, Standard Trouver Algorithme est un algorithme naïf avec une complexité sur les comparaisons N * M, car Il vérifie les modèles contre chaque décalage possible. Il existe des algoithmes plus efficaces nécessitant des comparaisons N + M. Si votre chaîne n'est pas une chaîne de langue naturelle, vous pouvez essayer algorithme Knuth-Morris-Pratt . Boyer-Moore Rechercher Algorithme est assez rapide et assez simple.

Si les motifs sont assez aléatoires, vous pouvez précomputer l'emplacement des n-préfixes de chaînes.

au lieu de passer sur toutes les options pour N-préfixes, utilisez simplement les réelles dans la chaîne 1GB - il y aura moins que 1gig de ceux-ci. Utilisez comme gros préfixe comme convient à votre mémoire, je n'ai pas 16 Go de RAM pour vérifier, mais un préfixe de 4 pourrait fonctionner (au moins dans une structure de données efficace de la mémoire), sinon essayer 3 ou même 2. P >

Pour une chaîne aléatoire de 1 Go et des motifs de 1kb aléatoires, vous devez obtenir quelques emplacements 10 par préfixes si vous utilisez des préfixes de 3 octets, mais les préfixes de 4 octets devraient vous procurer une moyenne de 0 ou 1. Sois rapide. P>

Emplacements précalcompute strong> p>

def find_pattern(pattern):
  prefix = pattern[:PREFIX_SIZE]
  # optimization - big prefixes will result in many misses
  if prefix not in precomputed_indices:
    return -1
  for loc in precomputed_indices[prefix]:
    if big_string[loc:loc+CHUNK_SIZE] == pattern:
        return loc
  return -1

Lorsque vous précisez que le prétraitement ISH de longue date est acceptable, je suggérerais une variante de Rabin- Karp : "Un algorithme de choix pour la recherche de modèles multiples", comme le dit Wikipedia.

Définir une fonction "Rolling Hash", c'est-à-dire une telle sorte que, lorsque vous connaissez le hachage pour HayStack [ x: x + n] , calculant le hachage pour haunstack [x + 1: x + n + 1] est O (1). (Fonctions de hachage normales telles que l'intégrée intégrée de Python ne possède pas cette propriété, c'est pourquoi vous devez écrire votre propre, sinon le prétraitement devient épuréement long plutôt que simplement assez long;-). Une approche polynomiale est fructueuse et vous pourriez utiliser, disons des résultats de hachage 30 bits (en masquant si nécessaire, vous pouvez faire le calcul avec plus de précision et stockez simplement les 30 bits de choix masqués). Appelons cette fonction de hachage roulante RH pour la clarté.

Ainsi, calculez 1 g de RH Résultats lorsque vous roulerez le long de la chaîne de foin 1GB; Si vous venez de stocker ceux-ci, cela vous donnerait un tableau H de valeurs 1G 30 bits (4 Go) de mappage Index-in-Haystack-> RH Valeur. Mais vous souhaitez que la mappage inverse, utilisez plutôt un tableau A de 2 ** 30 entrées (entrées 1G) que pour chaque valeur RH vous donne tous les indices d'intérêt dans les foines de foin (indices au cours de la mesure de la valeur RH); Pour chaque entrée, vous stockez l'indice du premier indice de fointstack potentiellement intéressant dans un autre tableau B d'indices 1G dans la grille de foin, qui est condamné à conserver tous les indices dans de la botte de foin avec des valeurs HR identiques ("collisions" en hachage) adjacentes. H, A et B ont tous les deux des entrées 1G de 4 octets chacun, donc 12 Go total.

Maintenant pour chaque aiguille 1K entrante, calculez son HR, appelez-le k et utilisez-le comme index dans A; A [K] vous donne le premier index B en B auquel cela vaut la peine de comparer. Donc, faire: xxx

avec un bon rh, vous devez avoir peu de collisions, le moment devrait donc s'exécuter très peu de fois jusqu'à ce qu'il soit renvoyé d'une manière ou d'une autre. Donc, chaque recherche d'aiguille devrait être vraiment très rapide.