Python: быстрый словарь больших int ключей - PullRequest
Новая
       15

Python: быстрый словарь больших int ключей

3 голосов
/ 06 мая 2011

У меня есть список из> 10.000 int предметов.Значения предметов могут быть очень высокими, до 10 ^ 27.Теперь я хочу создать все пары предметов и рассчитать их сумму.Затем я хочу найти разные пары с одинаковой суммой.

Например: 

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

Содержимое pairs[7] - это то, что я ищу.Он дает мне две пары с одинаковой суммой значений.

Я реализовал это следующим образом - и мне интересно, можно ли это сделать быстрее.В настоящее время на 10 000 единиц товара требуется более 6 часов на быстрой машине.(Как я уже говорил, значения l и, следовательно, ключи pairs являются целыми числами до 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)]}

Редактировать: Я хочудобавить некоторый фон, как попросил Саймон Стеллинг.

Цель состоит в том, чтобы найти формальные аналогии, такие как 

lays : laid :: says : said

, в списке слов, таких как 

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

Iуже есть функция analogy(a,b,c,d), дающая True, если a : b :: c : d.Тем не менее, мне нужно будет проверить все возможные четверки, созданные из списка, что будет сложность около O ((n ^ 4) / 2).

В качестве предварительного фильтра, я хочу использоватьсвойство char-count.Это говорит о том, что каждый символ имеет одинаковое количество в (a, d) и в (b, c).Например, в "layssaid" у нас есть 2 a, и мы делаем в "laidsays"

Так что до сих пор идея была

  • для каждого слова, чтобы создать "charсчитать вектор "и представить его как целое число (элементы в списке l)
  • создать все пары в pairs и посмотреть, есть ли" парные кластеры ", т.е. более одной пары для конкретногосумма символов вектора.

И это работает, это просто медленно.Сложность примерно равна O ((n ^ 2) / 2), но это все еще много, и особенно часто выполняется поиск и вставка в словарь.

Ответы [ 4 ]

4 голосов
/ 06 мая 2011

Существуют тривиальные оптимизации, такие как кэширование значений констант в локальной переменной и использование 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))

Однако, вероятно, гораздо более разумно не рассчитыватьперечислить и вместо этого оптимизировать метод на уровне концепции.Какую внутреннюю цель вы хотите достичь?Вы действительно просто хотите рассчитать, что вы делаете?Или вы собираетесь использовать этот результат для чего-то другого?Что это что-то еще?

1 голос
/ 06 мая 2011

Просто подсказка. Загляните на itertools.combinsk .

Это не совсем то, что вы ищете (потому что в нем хранится пара значений, а не индексов), но это может быть начальный код: 

from itertools import combinations
for (a, b) in combinations(l, 2):
    pairs.setdefault(a + b, []).append((a, b))
0 голосов
/ 22 июня 2011

Наконец, я пришел к собственному решению, просто взяв в среднем половину времени вычислений.

Основная идея: вместо чтения и записи в растущий словарь 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 голосов
/ 07 мая 2011

Приведенный выше комментарий от 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))
...