Можно ли уменьшить сложность от O (n ^ 2) до O (n) при сравнении двух больших наборов данных? - PullRequest
Новая
       6

Можно ли уменьшить сложность от O (n ^ 2) до O (n) при сравнении двух больших наборов данных?

1 голос
/ 13 марта 2020

У меня есть большой набор элементов (~ 2 миллиона), в котором мне нужно сравнить каждый элемент с каждым другим элементом в этом наборе.

Каждый элемент сам по себе представляет собой набор строк, которые объединяются в одна строка Поэтому строка a будет сравниваться со всеми другими строками b с использованием difflib.

В долгосрочной перспективе я хочу переключиться на библиотеку, отличную от difflib, но даже 100-кратное ускорение не будет достаточно быстрым. Элементы хранятся не в базе данных, а непосредственно в памяти. Я использую два цикла for, что явно не является удовлетворительным решением.

Код выглядит примерно так: 

for a in data:
    for b in data:
        # calculate similarity of a and b

Есть ли лучший способ сравнить все элементы по отдельности?

1 Ответ

0 голосов
/ 13 марта 2020

Если предположить, что a и b имеют одинаковую длину, мы можем просто перебрать их длину: 

#if length not equal then items not equal and we can save time.
if len(a) != len(b):
   return False 

for i in range(len(a)):
    if a[i] != b[i]:
        return False

return True

РЕДАКТИРОВАТЬ:

Я неправильно понял, поэтому мой первоначальный ответ: Неправильно.

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

Делая это перед любым сравнением, вы можете добавить две проверки, a похож на элементы, подобные b, или похож на элементы, отличающиеся от b

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

Простой пример PUESDO: 

similar_buckets = {}
different_buckets = {}

def func():
    for string in data:
        if string not in similar_buckets:
            similar_buckets[string] = set()
        if string not in different_buckets:
            different_buckets[string] = set()

        for string2 in data:
            # these occur in O(1)
            if string2 in similar_buckets[string]:
                continue #true
            elif string2 in different_buckets[string]:
                continue #false

            #expensive
            if string == string2:
                similar_buckets[string].add(string2)
                different_buckets[string2] = similar_buckets[string]
                continue
            else:
                different_buckets[string].add(string2)
                similar_buckets[string2] = different_buckets[string]
                continue

func()

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

...