Самый быстрый алгоритм поиска перекрытия между двумя очень большими списками?

Я пытаюсь создать алгоритм на Python для фильтрации большого блока данных RDF.

У меня есть один список, состоящий примерно из 70 тысяч элементов, отформатированных как <"datum">.

Затем у меня есть около 6 ГБ элементов (троек), отформатированных как <"A"> <"B"> <"C">

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

Я не смог придумать отличный алгоритм для этого (не помогает тот факт, что у меня нет формального обучения CS).

Лучшее, что я пока придумал, это начать с разделения троек в большом списке на список из трех списков элементов [<"A">, <"B">, <"C">]. Затем я разбиваю это на куски и использую многопроцессорность для создания процессов, которые берут полный маленький список и часть большого списка и...

for line in big list:
    for item in small list:
      if item in line:
       bucket.append(line)

Этот алгоритм занимает довольно много времени.

Есть ли более быстрый способ сделать это? Если есть конкретный алгоритм, вы можете просто дать мне имя, и я придумаю, как его реализовать.

Спасибо!

Уточнения по комментариям:

  1. Все элементы данных являются строками. Таким образом, маленький список может содержать ["Mickey", "Mouse", "Minny", "Cat"], а большой список может быть [["Mickey","Pluto","Bluto"],["John", "Jane", "Jim]...].

  2. Только один элемент в каждой тройке большого списка должен совпадать с элементом в маленьком списке, чтобы это учитывалось.

  3. Все элементы в маленьком списке на самом деле уникальны, поэтому я все равно не подумал преобразовать их в набор. Но я попробую это.

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


python list algorithm rdf
person rogueleaderr    schedule 03.05.2012    source источник
comment
Разрешено ли вам создавать промежуточные структуры на диске? Кажется, вы могли бы извлечь выгоду из «инвертированных индексов», т.е. что-то вроде {'A': [('A', B', 'C), ('A', 'X', 'Y')],... }   -  person spinlok    schedule 03.05.2012
comment
Просто для ясности, каковы точные критерии соответствия записи на каждом этапе? Все ли <A><B><C> должны совпадать? Или только один из <A>, <B> или <C>? И второй этап вашей фильтрации тоже немного расплывчатый. Некоторые примеры данных могут помочь здесь?   -  person Li-aung Yip    schedule 03.05.2012
comment
Вы должны предоставить сокращенный пример того, что содержит первый список, и что вы хотели бы, чтобы итоговый список содержал.   -  person Joel Cornett    schedule 03.05.2012
comment
Что такое данные? Числа? Струны?   -  person user545424    schedule 03.05.2012

Ответы (1)


arrow_upward
5
arrow_downward

Вероятно, вам следует сначала сохранить небольшой список в наборе, чтобы поиск выполнялся быстрее. Это предотвращает выполнение 70 000 итераций для каждого элемента в big_list.

small_list_set = set(small_list)
for line in big_list:
    for item in line:
        if item in small_list_set:
            bucket.append(line)
person happydave    schedule 03.05.2012
comment
Очень хорошее предложение. Скорее всего, это будет намного быстрее, потому что поиск в хорошо реализованном set (с использованием хешированных ключей) занимает O(1) времени, в отличие от поиска по списку за O(n) времени. - person Li-aung Yip; 03.05.2012
comment
Обратите внимание, что это (как и код OP) будет добавлять line несколько раз, если есть несколько совпадений, что, возможно, нежелательно (я не совсем понимаю, какая фильтрация требуется). Этого можно легко избежать, добавив break после bucket.append(line). - person Danica; 03.05.2012
comment
Я согласен - я действительно не совсем понял, чего хотел ОП. Основное предложение состояло в том, чтобы использовать набор для сокращения времени выполнения примерно в 70 000 раз. - person happydave; 03.05.2012
comment
Несмотря на то, что элементы в маленьком списке уже уникальны, использование set() работает НАМНОГО быстрее. Я думаю, что в конечном итоге я собираюсь построить инвертированный индекс, потому что он упрощает второй шаг поиска троек, содержащих элемент из любой из троек, соответствующих первому проходу. Создание индекса занимает довольно много времени, но после его создания поиск выполняется очень быстро. - person rogueleaderr; 03.05.2012
comment
@rogueleaderr: Здесь мы используем set не потому, что элементы в нем гарантированно уникальны, что является одним из свойств set, а потому, что поиск в нем выполняется намного быстрее. (Это возможно, поскольку каждый элемент может встречаться только один раз.) - person Li-aung Yip; 03.05.2012