Geek asks and answers

Python: fast int bigkey dictionary

I have a list of> 10.000 int items. The values ​​of the elements can be very high, up to 10 ^ 27. Now I want to create all pairs of elements and calculate their sum. Then I want to look for different pairs with the same amount.

For instance:

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)]
...

Content pairs[7]is what I'm looking for. This gives me two pairs with the same sum of values.

I implemented it as follows - and I wonder if this can be done faster. Currently, 10,000 items require more than 6 hours in a fast car. (As I said, values land therefore keys pairsare ints up to 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: I want to add a little background, as requested by Simon Stelling.

The goal is to find formal analogies, for example

lays : laid :: says : said


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

analogy(a,b,c,d), True, a : b :: c : d. , , , O ((n ^ 4)/2).

, char -count. , char (a, d) (b, c). , "layssaid" 2 a, "laidsays"

,

  • , " char" ( l)
  • pairs , " ", .. count char.

, . O ((n ^ 2)/2), , .

+3
4

, , .

: , n ^ 2 , . . .

:

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)
0

, xrange 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))

, , . , ? , ? - ? ?

+4

. itertools.combinations.

, ( , ), :

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

SimonStelling ; , , . itertools - product; , , O (n ^ 2). :

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))
0

More articles:


All Articles