Блог

Главная - Вопросы по программированию - Python3: сопоставление элементов между двумя списками на основе подстрок

Python3: сопоставление элементов между двумя списками на основе подстрок

#python #python-3.x #list-comprehension #dictionary-comprehension

#python #python-3.x #понимание списка #понимание по словарю

Вопрос:

Этот вопрос касается сопоставления строк в одном списке с соответствующими строками в другом списке. Я пытался найти наилучший способ выполнить такое сопоставление. Мой приведенный ниже пример невелик, но я должен применить ту же идею к гораздо большему списку. Итак, у меня есть набор имен файлов и путей в одном списке, а затем у меня есть список частичных имен файлов в другом списке, например:

     list1 = ['/../../abc_file1.txt',
             '/../../abc_extrafile1.txt',
             '/../../abc_file2.txt',
             '/../../abc_file3.txt',
             '/../../abc_extrafile3.txt']

И тогда у меня получается другой список

     ['file1', 'extrafile1', 'file2', 'file3', 'extrafile3']

Итак, что я хотел бы сделать, это получить сопоставление, которое генерирует словарь типа:

     {'file1': '/../../abc_file1.txt',
     'extrafile1': '/../../abc_extrafile1.txt',
     'file2': '/../../abc_file2.txt',
     'file3': '/../../abc_file3.txt',
     'extrafile3': '/../../abc_extrafile3.txt'}

Итак, есть некоторые совпадения между именами файлов, и мне нужно
будьте осторожны с этим.

Существует несколько способов сделать что-то подобное, но я не был уверен, какой из них наиболее эффективен для сопоставления списков порядка 1000 или 10000 записей. Похоже, это можно было бы сделать с помощью понимания по словарю или лямбда-выражения, но кажется немного сложным. Я мог бы написать необработанный цикл, но это не кажется особенно эффективным.

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

Ответ №1:

Вы могли бы запустить dict comprehension , как вы предложили, и проверить по a split первого элемента списка (чтобы учесть перекрытия) и удалить расширения:

 list1 = ['/../../abc_file1.txt',
             '/../../abc_extrafile1.txt',
             '/../../abc_file2.txt',
             '/../../abc_file3.txt',
             '/../../abc_extrafile3.txt']

list2 = ['file1', 'extrafile1', 'file2', 'file3', 'extrafile3']

my_dict = {k: v for v in list1 for k in list2 if k == v.split('_')[1][:-4]}

вывод:

 {'file1': '/../../abc_file1.txt', 'extrafile1': '/../../abc_extrafile1.txt', 'file2': '/../../abc_file2.txt', 'file3': '/../../abc_file3.txt', 'extrafile3': '/../../abc_extrafile3.txt'}

Комментарии:

1. Хорошо, это очень полезно. Здорово, что здесь может сработать понимание по словарю. Считаете ли вы, что сортировка list1 или list2 имеет какую-либо выгоду? Другими словами, находит ли условный оператор первое или последнее совпадение и т.д.?

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

3. Хорошо, понял. Таким образом, он в основном всегда найдет последнее совпадение. Имеет смысл. Спасибо за вашу помощь.

4. В понимании скрыты два цикла. Пожалуйста, проверьте мой ответ ниже для альтернативы.

Ответ №2:

Понимания — это просто более простой способ написания циклов построения коллекции. Проще для глаз, не обязательно эффективно.

В ответе @matt-b dict comprehension скрывается двойной for цикл, что делает понимание больших списков довольно медленным (сложность n в квадрате).

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

С помощью этого ввода:

 size = 1000
list1 = [ '/../../abc_file'   str(i)   '.txt' for i in range(size) ]
list2 = [ 'file'   str(i) for i in range(size) ]

dict comprehension На моей машине требуется около 500 мс:

 my_dict = {k: v for v in list1 for k in list2 if k == v.split('_')[1][:-4]}

# 1 loop, best of 3: 516 ms per loop

Следующая версия работает быстрее, примерно на 1 мс:

 res = { k: None for k in list2 }
for v in list1:
    name = v.split('_')[-1][:-4]
    if name in res:
        res[name] = v

# 100 loops, best of 3: 1.15 ms per loop

С помощью этой структуры легко сохранить несколько совпадений, если это необходимо:

 res = { k: [] for k in list2 }
for v in list1:
    name = v.split('_')[-1][:-4]
    if name in res:
        res[name].append(v)

# 100 loops, best of 3: 1.54 ms per loop

Вы также могли бы сохранить первое совпадение, сверив текущие res[name] значения с None .