Python: dictionnaire rapide des grandes touches int

Question

J'ai une liste de> 10.000 éléments int. Les valeurs des articles peuvent être très élevées, jusqu'à 10^27. Maintenant, je veux créer toutes les paires d'objets et calculer leur somme. Ensuite, je veux chercher différentes paires avec la même somme.

Par exemple:

l[0] = 4 
l[1] = 3 
l[2] = 6 
l[3] = 1 
... 

pairs[10] = [(0,2)] # 10 is the sum of the values of l[0] and l[2] 
pairs[7] = [(0,1), (2,3)] # 7 is the sum of the values of l[0] and l[1] or l[2] and l[3] 
pairs[5] = [(0,3)] 
pairs[9] = [(1,2)] 
... 

Le contenu de pairs[7] est ce que je cherche. Cela me donne deux paires avec la même somme de valeur.

Je l'ai implémenté comme suit - et je me demande si cela peut être fait plus rapidement. Actuellement, pour 10.000 articles, il faut> 6 heures sur une machine rapide. (Comme je l'ai dit, les valeurs de l et que les clés de pairs sont ints jusqu'à 10^27.)

l = [4,3,6,1] 
pairs = {} 
for i in range(len(l ) ): 
    for j in range(i+1, len(l)): 
     s = l[i] + l[j] 
     if not s in pairs: 
      pairs[s] = [] 
     pairs[s].append((i,j)) 

# pairs = {9: [(1, 2)], 10: [(0, 2)], 4: [(1, 3)], 5: [(0, 3)], 7: [(0, 1), (2, 3)]} 

---

Edit: Je veux ajouter un peu de fond, comme demandé par Simon Stelling .

L'objectif est de trouver Analogies formelles comme

lays : laid :: says : said 

dans une liste de mots comme

[ lays, lay, laid, says, said, foo, bar ... ] 

J'ai déjà une fonction analogy(a,b,c,d) donnant True si a : b :: c : d. Cependant, je devrais vérifier tous les quadruples possibles créés à partir de la liste, ce qui serait une complexité autour de O ((n^4)/2).

En tant que pré-filtre, je souhaite utiliser la propriété char-count. Il est dit que chaque char a le même nombre en (a, d) et en (b, c). Par exemple, dans « layssaid » nous avons 2 A, et nous le faisons dans « laidsays »

L'idée était jusqu'à présent

• pour chaque mot pour créer un « nombre omble chevalier vecteur » et représentent en entier (les éléments de la liste l)
• créer tous les appariements en pairs et de voir s'il y a des «groupes de paires», c'est-à-dire plus d'une paire pour une somme de vecteur de compte de caractères particulière.

Et ça marche, c'est juste lent. La complexité est proche de O ((n^2)/2) mais c'est encore beaucoup, et surtout la recherche de dictionnaire et l'insertion se font souvent.

Answer 1

Enfin, j'ai trouvé ma propre solution, en prenant juste la moitié du temps de calcul en moyenne.

L'idée de base: Au lieu de lire et écrire dans le dictionnaire croissant n^2 fois, je collectionne d'abord toutes les sommes dans une liste. Ensuite, je trier la liste. Dans la liste triée, je cherche ensuite les mêmes éléments voisins.

Voici le code:

from operator import itemgetter 

def getPairClusters(l): 

    # first, we just store all possible pairs sequentially 
    # clustering will happen later 
    pairs = [] 

    for i in xrange(len(l) ): 
     for j in xrange(i+1, len(l)): 
      pair = l[i] + l[j] 
      pairs.append((pair, i, j)) 
    pairs.sort(key=itemgetter(0)) 

    # pairs = [ (4, 1, 3), (5, 0, 3), (7, 0, 1), (7, 2, 3), (9, 1, 2), (10, 0, 2)] 
    # a list item of pairs now contains a tuple (like (4, 1, 3)) with 
    # * the sum of two l items: 4 
    # * the index of the two l items: 1, 3 

    # now clustering starts 
    # we want to find neighbouring items as 
    # (7, 0, 1), (7, 2, 3) 
    # (since 7=7) 

    pairClusters = [] 

    # flag if we are within a cluster 
    # while iterating over pairs list 
    withinCluster = False 

      # iterate over pair list 
    for i in xrange(len(pairs)-1): 
     if not withinCluster: 
      if pairs[i][0] == pairs[i+1][0]: 
       # if not within a cluster 
       # and found 2 neighbouring same numbers: 
       # init new cluster 
       pairCluster = [ (pairs[i][1], pairs[i][2]) ] 
       withinCluster = True 
     else: 
      # if still within cluster 
      if pairs[i][0] == pairs[i+1][0]: 
       pairCluster.append((pairs[i][1], pairs[i][2])) 
      # else cluster has ended 
      # (next neighbouring item has different number) 
      else: 
       pairCluster.append((pairs[i][1], pairs[i][2])) 
       pairClusters.append(pairCluster) 
       withinCluster = False 

    return pairClusters 

l = [4,3,6,1] 

print getPairClusters(l) 

Answer 2

Juste un indice. Jetez un oeil sur itertools.combinations.

Ce n'est pas exactement ce que vous cherchez (car il stocke paire de valeurs, pas d'index), mais il peut être un code de départ:

from itertools import combinations 
for (a, b) in combinations(l, 2): 
    pairs.setdefault(a + b, []).append((a, b)) 

Answer 3

Il y a des optimisations triviales comme la mise en cache des valeurs constantes dans une variable locale et à l'aide xrange au lieu de range:

pairs = {} 
len_l = len(l) 
for i in xrange(len_l): 
    for j in xrange(i+1, len_l): 
     s = l[i] + l[j] 
     res = pairs.setdefault(s, []) 
     res.append((i,j)) 

Cependant, il est probablement beaucoup plus sage de ne pas pré-calculer la liste et au lieu d'optimiser la méthode sur un niveau de concept. Quel est le but intrinsèque que vous voulez atteindre? Voulez-vous vraiment juste calculer ce que vous faites? Ou allez-vous utiliser ce résultat pour autre chose? Qu'est-ce que c'est autre chose?

Answer 4

Le commentaire ci-dessus de SimonStelling est correct; générer toutes les paires possibles est fondamentalement lent, et il n'y a rien que vous puissiez faire à part modifier votre algorithme. La bonne fonction à utiliser de itertools est product; et vous pouvez obtenir quelques améliorations mineures de ne pas créer des variables supplémentaires ou faire des index de liste inutiles, mais sous le capot ce sont toujours tous O (n^2). Voici comment je le ferais:

from itertools import product 
l = [4,3,6,1] 
pairs = {} 
for (m,n) in product(l,repeat=2): 
    pairs.setdefault(m+n, []).append((m,n))