Упорядоченный поиск в Python по сравнению с поисковыми наборами для списка объектов

У меня есть два списка объектов. Давайте назовем списки а и б. Объекты (для наших намерений и целей) определены следующим образом:

class MyObj:
    def __init__(self, string: str, integer: int):
        self.string = string
        self.integer = integer

    def __eq__(self, other):
        if self.integer == other.integer:
            pass
        else:
            return False

        if fuzz.ratio(self.string, other.string) > 90: # fuzzywuzzy library checks if strings are "similar enough"
            return True
        else:
            return False

Теперь я хочу проверить, какие объекты в списке a находятся в списке b (верните true = = по сравнению с некоторым объектом в списке b).

В настоящее время я просто перебираю их следующим образом:

for obj in a:
    for other_obj in b:
        if a == b:
            <do something>
            break

Я сильно подозреваю, что есть более быстрый способ реализовать это. Списки длинные. До 100 000 объектов каждый. Так что это большое узкое место в моем коде.

Я посмотрел на этот ответ Самый быстрый способ поиска списка в python и это говорит о том, что наборы работают намного лучше. Я немного смущен этим, хотя:

  • Насколько важно ускорение удаления дубликатов? Я не ожидаю, что в моих списках будет много дубликатов.

  • Могут ли наборы удалять дубликаты и правильно хэшировать, когда я определил eq , как у меня?

  • Как это можно сравнить с предварительным упорядочением списка и использованием чего-то вроде бинарного поиска? Набор неупорядочен ...

Итак, каков наилучший подход здесь? Пожалуйста, предоставьте рекомендации по реализации в ответе.

4 голоса | спросил Neil 7 PM00000030000003631 2018, 15:44:36

1 ответ


0
TL; DR , при использовании методов нечеткого сравнения, наборы и сортировка могут быть очень сложными без какого-либо метода нормализации.Вы можете постараться максимально сократить количество поисковых пространств, но следует соблюдать осторожность, чтобы делать это последовательно.Если класс определяет ---- +: = 0 =: + ----, а не ---- +: = 1 =: + ---- , он не может быть хешируемым.Например, рассмотрим следующий классТеперь, если вы попытаетесь создать набор с этими элементамиТаким образом, в случае ---- +: = 4 =: + ---- , вы просто определили бы метод ---- +: = 5 =: + ---- .Однако в вашем случае это сложнее, поскольку у вас есть нечеткая семантика равенства.Единственный способ обойти это, как я могу придумать, - это иметь функцию нормализации, которая, как вы можете доказать, будет непротиворечивой, и использовать нормализованную строку вместо фактической строки как часть вашего хэша.Возьмем Float в качестве ключей словаря в качестве примера необходимости нормализации, чтобы использовать «нечеткий» тип, такой как float, в качестве ключей.Для сортировки и двоичного поиска, поскольку вы нечеткий поиск, вам все равно нужно быть осторожным с такими вещами, как бинарный поиск.В качестве примера предположим, что вы говорите, что равенство определяется тем, что оно находится в определенном диапазоне расстояний Левенштейна.Тогда ---- +: = 6 =: + ---- и ---- +: = 7 =: + ---- будут похожи друг на друга (расстояние = 1), но ---- +:= 8 =: + ---- с расстоянием 2, будет ближе к ---- +: = 9 =: + ---- .Так как же определить хороший алгоритм сортировки для нечеткого поиска в этом случае?Одна вещь, которую можно попробовать, это использовать некоторую форму группировки по группам, например, словарь типа ---- +: = 10 =: + ---- , где экземпляры ---- +: = 11=: + ---- классифицируются по одной константе, поле ---- +: = 12 =: + ---- .Затем вы можете попробовать сравнить меньшие подсписки.Это по крайней мере уменьшит пространство поиска путем кластеризации.
ответил Edward Minnix 7 PM00000040000004231 2018, 16:12:42

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132