Сглаживание вложенных циклов / уменьшение сложности - алгоритм подсчета дополнительных пар - PullRequest
Новая
       13

Сглаживание вложенных циклов / уменьшение сложности - алгоритм подсчета дополнительных пар

6 голосов
/ 13 января 2012

Я недавно пытался решить какую-то задачу в Python, и я нашел решение, которое, кажется, имеет сложность O (n log n) , но я считаю, что оно очень неэффективно для некоторых входных данных (например, первый параметр 0 и pairs - очень длинный список нулей).

Он также имеет три уровня циклов for.Я верю, что это можно оптимизировать, но в настоящий момент я не могу оптимизировать его больше, я, вероятно, просто упускаю что-то очевидное;)

Итак, в принципе, проблема заключается в следующем:

При заданном списке целых чисел (values) функция должна возвращать количество пар индексов, которые соответствуют следующим критериям:

  • позволяет предположить, что единичная пара индексов является кортежем типа (index1, index2),
  • , тогда values[index1] == complementary_diff - values[index2] равно true,

Пример : если задан список типа [1, 3, -4, 0, -3, 5] как values и 1 как complementary_diff, функция должна возвращать 4 (это длина следующего списка пар индексов: [(0, 3), (2, 5), (3, 0), (5, 2)]).

Это то, что я до сих пор, она должна прекрасно работать большинствовремя, но - как я уже сказал - в некоторых случаях он может работать очень медленно, несмотря на приблизительную сложность O (n log n) (похоже, пессимистическая сложность равна O (n ^2) ). 

def complementary_pairs_number (complementary_diff, values):
    value_key = {} # dictionary storing indexes indexed by values
    for index, item in enumerate(values):
        try:
            value_key[item].append(index)
        except (KeyError,): # the item has not been found in value_key's keys
            value_key[item] = [index]
    key_pairs = set() # key pairs are unique by nature
    for pos_value in value_key: # iterate through keys of value_key dictionary
        sym_value = complementary_diff - pos_value
        if sym_value in value_key: # checks if the symmetric value has been found
            for i1 in value_key[pos_value]: # iterate through pos_values' indexes
                for i2 in value_key[sym_value]: # as above, through sym_values
                    # add indexes' pairs or ignore if already added to the set
                    key_pairs.add((i1, i2))
                    key_pairs.add((i2, i1))
    return len(key_pairs)

Для данного примера он ведет себя так: 

>>> complementary_pairs_number(1, [1, 3, -4, 0, -3, 5])
4

Если выо том, как код может быть «сплющен» или «упрощен», пожалуйста, дайте мне знать.

Я не уверен, что лучший способ - просто проверить complementary_diff == 0 и т. д. - если вы так думаете, пожалуйста,дайте мне знать.

РЕДАКТИРОВАТЬ: Я исправил пример (спасибо, unutbu!).

Ответы [ 5 ]

4 голосов
/ 13 января 2012

Я думаю, что это улучшает сложность до O(n):

  • value_key.setdefault(item,[]).append(index) быстрее, чем при использовании try..except блоки. Это также быстрее, чем при использовании collections.defaultdict(list). (Я проверил это с помощью ipython% timeit.)
  • Оригинальный код посещает каждое решение дважды. За каждый pos_value в value_key существует уникальный sym_value, связанный с pos_value. Есть решения, когда sym_value также находится в value_key. Но когда мы перебираем ключи в value_key, pos_value в конечном итоге присваивается значение sym_value, которое заставить код повторить вычисление, которое он уже сделал. Так что вы можете сократить работу пополам, если вы можете остановить pos_value от выравнивания старый sym_value. Я реализовал это с seen = set(), чтобы сохранить Трек увиденного sym_value с.

  • Код касается только len(key_pairs), а не самих key_pairs. Таким образом, вместо отслеживания пар (с set), мы можем просто отслеживать количество (с num_pairs). Таким образом, мы можем заменить два внутренних цикла for на 

    num_pairs += 2*len(value_key[pos_value])*len(value_key[sym_value])

    или вдвое меньше, чем в случае "уникальной диагонали", pos_value == sym_value. 

def complementary_pairs_number(complementary_diff, values):
    value_key = {} # dictionary storing indexes indexed by values
    for index, item in enumerate(values):
        value_key.setdefault(item,[]).append(index)
    # print(value_key)
    num_pairs = 0
    seen = set()
    for pos_value in value_key: 
        if pos_value in seen: continue
        sym_value = complementary_diff - pos_value
        seen.add(sym_value)
        if sym_value in value_key: 
            # print(pos_value, sym_value, value_key[pos_value],value_key[sym_value])
            n = len(value_key[pos_value])*len(value_key[sym_value])
            if pos_value == sym_value:
                num_pairs += n
            else:
                num_pairs += 2*n
    return num_pairs
2 голосов
/ 13 января 2012

Возможно, вы захотите изучить идиомы функционального программирования, такие как уменьшение и т. Д.

Часто логику вложенных массивов можно упростить с помощью таких функций, как уменьшение, отображение, отклонение и т. Д.

Для примера (в javascript) ознакомьтесь с подчеркиванием js. Я не очень умен в Python, поэтому я не знаю, какие библиотеки у них есть.

0 голосов
/ 15 января 2012

Изменено решение, предоставляемое @unutbu:

Проблема может быть сведена к сравнению этих 2 словарей:

  1. значение

  2. предварительно вычисленный словарь для (plementary_diff - values ​​[i]) 

    def complementary_pairs_number(complementary_diff, values):
    value_key = {} # dictionary storing indexes indexed by values
    for index, item in enumerate(values):
        value_key.setdefault(item,[]).append(index)

    answer_key = {} # dictionary storing indexes indexed by (complementary_diff - values)
    for index, item in enumerate(values):
        answer_key.setdefault((complementary_diff-item),[]).append(index)

    num_pairs = 0
    print(value_key)
    print(answer_key)
    for pos_value in value_key: 
        if pos_value in answer_key: 
            num_pairs+=len(value_key[pos_value])*len(answer_key[pos_value])
    return num_pairs
0 голосов
/ 13 января 2012

Я думаю, вы можете улучшить это, отделяя часть алгебры от поиска и используя более умные структуры данных.

  1. Просмотрите список и вычтите из дополнительного различий для каждого элемента всписок.

    resultlist[index] = complementary_diff - originallist[index]

    Вы можете использовать карту или простой цикл.-> Принимает O (n) времени.

  2. Проверьте, существует ли число в результирующем списке в исходном списке.

    • Здесь, с наивным списком, вы на самом деле получите O (n ^ 2) , потому что вы можете в конечном итоге искать весь исходный список для элемента в результирующем списке.

    • Однако существуют более разумные способы организации ваших данных, чем эта.Если у вас есть исходный список , отсортированный , время поиска сокращается до O (nlogn + nlogn) = O (nlogn) , nlogn для сортировки и nlogn для бинарного поиска по элементу.

    • Если вы хотите быть еще умнее, вы можете сделать свой список в словаре (или хэш-таблице) , а затем этот шаг становится O (n + n) = O (n) , n для построения словаря и 1 * n для поиска каждого элемента в словаре.(* РЕДАКТИРОВАТЬ: * Поскольку вы не можете предполагать уникальность каждого значения в исходном списке. Возможно, вы захотите сохранить счет того, сколько раз каждое значение появляется в исходном списке.)

Итак, теперь вы получаете O (n) общее время выполнения.

Используя ваш пример: 

1, [1, 3, -4, 0, -3, 5],

  1. Generateсписок результатов: 

    >>> resultlist
[0, -2, 5, 1, 4, -4].

  2. Теперь мы ищем:

    • Свести исходный список в словарь.Я выбрал в качестве значения индекс исходного списка, так как он выглядит как побочные данные, которые вас интересуют. 

      >>> original_table
{(1,0), (3,1), (-4,2), (0,3), (-3,4), (5,5)}

    • Для каждого элемента в списке результатов выполните поиск вхеш-таблицу и сделайте кортеж: 

      (resultlist_index, original_table[resultlist[resultlist_index]])

      Это должно выглядеть как пример решения, которое вы имели.

  3. Теперь вы просто найдете длинуиз результирующего списка кортежей.

Теперь вот код: 

example_diff = 1
example_values = [1, 3, -4, 0, -3, 5]
example2_diff = 1
example2_values = [1, 0, 1]

def complementary_pairs_number(complementary_diff, values):
    """
        Given an integer complement and a list of values count how many pairs
        of complementary pairs there are in the list.
    """
    print "Input:", complementary_diff, values
    # Step 1. Result list
    resultlist = [complementary_diff - value for value in values]
    print "Result List:", resultlist

    # Step 2. Flatten into dictionary
    original_table = {}
    for original_index in xrange(len(values)):
        if values[original_index] in original_table:
            original_table[values[original_index]].append(original_index)
        else:
            original_table[values[original_index]] = [original_index]
    print "Flattened dictionary:", original_table

    # Step 2.5 Search through dictionary and count up the resulting pairs.
    pair_count = 0
    for resultlist_index in xrange(len(resultlist)):
        if resultlist[resultlist_index] in original_table:
            pair_count += len(original_table[resultlist[resultlist_index]])
    print "Complementary Pair Count:", pair_count

    # (Optional) Step 2.5 Search through dictionary and create complementary pairs. Adds O(n^2) complexity.
    pairs = []
    for resultlist_index in xrange(len(resultlist)):
        if resultlist[resultlist_index] in original_table:
            pairs += [(resultlist_index, original_index) for original_index in
                original_table[resultlist[resultlist_index]]]
    print "Complementary Pair Indices:", pairs

    # Step 3
    return pair_count

if __name__ == "__main__":
    complementary_pairs_number(example_diff, example_values)
    complementary_pairs_number(example2_diff, example2_values)

Вывод: 

$ python complementary.py
Input: 1 [1, 3, -4, 0, -3, 5]
Result List: [0, -2, 5, 1, 4, -4]
Flattened dictionary: {0: 3, 1: 0, 3: 1, 5: 5, -4: 2, -3: 4}
Complementary Pair Indices: [(0, 3), (2, 5), (3, 0), (5, 2)]
Input: 1 [1, 0, 1]
Result List: [0, 1, 0]
Flattened dictionary: {0: [1], 1: [0, 2]}
Complementary Pair Count: 4
Complementary Pair Indices: [(0, 1), (1, 0), (1, 2), (2, 1)]

Спасибо!

0 голосов
/ 13 января 2012

Я думаю (некоторые или все из них) это помогло бы, но я не уверен, как я это докажу.

1) Возьмите значения и уменьшите их до отдельного набора значений, записав количество каждого элемента (O (n))

2) Сортировать полученный массив. (n log n)

3) Если вы можете выделить много памяти, я думаю, вы могли бы заполнить разреженный массив значениями - поэтому, если диапазон значений составляет -100: +100, выделите массив [201] и любой значение, которое существует в сокращенном наборе, выводит единицу на индекс значения в большом разреженном массиве.

4) Любое значение, которое вы хотите проверить, соответствует ли оно вашим условиям, теперь должно посмотреть на индекс в разреженном массиве в соответствии с отношением x - y и посмотреть, существует ли там значение.

5) как указал unutbu, он тривиально симметричен, поэтому, если {a, b} - пара, то и {b, a}.

...