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

Question

Учитывая, что у меня есть два списка, например:

l1 = ['a', 'c', 'b', 'e', 'f', 'd']
l2 = [
    'x','q','we','da','po',
    'a', 'el1', 'el2', 'el3', 'el4',
    'b', 'some_other_el_1', 'some_other_el_2',
    'c', 'another_element_1', 'another_element_2',
    'd', '', '', 'another_element_3', 'd4'
]

, и мне нужно создать словарь, в котором ключи - это те элементы из второго списка, которые находятся в первом, а значения - это списки элементов, найденных между«ключи», такие как:

result = {
    'a': ['el1', 'el2', 'el3', 'el4'],
    'b': ['some_other_el_1', 'some_other_el_2'],
    'c': ['another_element_1', 'another_element_2'],
    'd': ['', '', 'another_element_3', 'd4']
}

Какой более питонный способ сделать это?

В настоящее время я делаю это:

# I'm not sure that the first element in the second list
# will also be in the first so I have to create a key
k = ''
d[k] = []
for x in l2:
    if x in l1:
        k = x
        d[k] = []
    else:
        d[k].append(x)

Но я довольноположительно, что это не лучший способ сделать это, и это также не выглядит красиво :)

Редактировать: я также должен упомянуть, что нет необходимости упорядочивать список, и ни второй список не должен начинаться с элементас первого.

Answer 1

Даже чище, чем превращать l1 в set, используйте ключи словаря, который вы строите. Как это

d = {x: [] for x in l1}
k = None

for x in l2:
    if x in d:
        k = x
    elif k is not None:
        d[k].append(x)

Это потому, что (в худшем случае) ваш код будет перебирать все значения в l1 для каждого значения в l2 в строке if x in l1:, потому что проверяет, является ли значение in список занимает линейное время . Проверка, является ли значение in ключами словаря, является постоянным временем в среднем случае ( то же самое с set s , как уже , предложенный Эриком Думинил ).

Я установил k на None и проверил его, потому что ваш код возвратил бы d с '': ['x','q','we','da','po'], что, вероятно, не то, что вы хотите. Предполагается, что l1 не может содержать None.

Мое решение также предполагает, что в результирующем словаре можно использовать ключи с пустыми списками, если в l1 есть элементы, которые никогда не появляются в l2. Если это не хорошо, вы можете удалить их в конце с помощью

final_d = {k: v for k, v in d.items() if v}

Answer 2

Ваш код читабелен, выполняет свою работу и достаточно эффективен.Не нужно много менять!

Вы можете использовать более описательные имена переменных и заменить l1 на set для более быстрого поиска:

keys = ('a', 'c', 'b', 'e', 'f', 'd')
keys_and_values = [
    'x','q','we','da','po',
    'a', 'el1', 'el2', 'el3', 'el4',
    'b', 'some_other_el_1', 'some_other_el_2',
    'c', 'another_element_1', 'another_element_2',
    'd', '', '', 'another_element_3', 'd4'
]

current_key = None
result = {}
for x in keys_and_values:
    if x in keys:
        current_key = x
        result[current_key] = []
    elif current_key:
        result[current_key].append(x)

print(result)
# {'a': ['el1', 'el2', 'el3', 'el4'],
#  'c': ['another_element_1', 'another_element_2'],
#  'b': ['some_other_el_1', 'some_other_el_2'],
#  'd': ['', '', 'another_element_3', 'd4']}

Answer 3

 def find_index():
    idxs = [l2.index(i) for i in set(l1).intersection(set(l2))]
    idxs.sort()
    idxs+= [len(l2)+1]
    res = {l2[idxs[i]]: list(l2[idxs[i]+1: idxs[i+1]]) for i in range(len(idxs)-1)}
    return(res)

Сравнение методов с использованием теста Юстенгеля:
justengel
run_comp: .455
run_other: .244
mkrieger1
group_by_keys: .160
me
find_index: .068

Обратите внимание, что мой метод игнорирует ключи, которые не отображаются l2, и необрабатывать случаи, когда ключи появляются более одного раза в l2.Добавление в пустые списки ключей, которые не отображаются в l2, можно выполнить с помощью {**res, **{key: [] for key in set(l1).difference(set(l2))}}, что увеличивает время до .105.

Answer 4

Вы можете использовать itertools.groupby:

import itertools
l1 = ['a', 'c', 'b', 'e', 'f', 'd']
l2 = ['x', 'q', 'we', 'da', 'po', 'a', 'el1', 'el2', 'el3', 'el4', 'b', 'some_other_el_1', 'some_other_el_2', 'c', 'another_element_1', 'another_element_2', 'd', '', '', 'another_element_3', 'd4']
groups = [[a, list(b)] for a, b in itertools.groupby(l2, key=lambda x:x in l1)]
final_dict = {groups[i][-1][-1]:groups[i+1][-1] for i in range(len(groups)-1) if groups[i][0]}

Выход:

{'a': ['el1', 'el2', 'el3', 'el4'], 'b': ['some_other_el_1', 'some_other_el_2'], 'c': ['another_element_1', 'another_element_2'], 'd': ['', '', 'another_element_3', 'd4']}

Answer 5

Для развлечения вы также можете сделать это с itertools и третьей стороной numpy:

import numpy as np
from itertools import zip_longest, islice

arr = np.where(np.in1d(l2, l1))[0]
res = {l2[i]: l2[i+1: j] for i, j in zip_longest(arr, islice(arr, 1, None))}

print(res)

{'a': ['el1', 'el2', 'el3', 'el4'],
 'b': ['some_other_el_1', 'some_other_el_2'],
 'c': ['another_element_1', 'another_element_2'],
 'd': ['', '', 'another_element_3', 'd4']}

Answer 6

Вот версия, использующая itertools.groupby. Это может быть или не быть более эффективным, чем простая версия из вашего поста, в зависимости от того, как реализован groupby, потому что цикл for имеет меньше итераций.

from itertools import groupby
from collections import defaultdict, deque

def group_by_keys(keys, values):
    """
    >>> sorted(group_by_keys('abcdef', [
    ...          1, 2, 3,
    ...     'b', 4, 5,
    ...     'd',
    ...     'a', 6, 7,
    ...     'c', 8, 9,
    ...     'a', 10, 11, 12
    ... ]).items())
    [('a', [6, 7, 10, 11, 12]), ('b', [4, 5]), ('c', [8, 9])]
    """
    keys = set(keys)
    result = defaultdict(list)
    current_key = None
    for is_key, items in groupby(values, key=lambda x: x in keys):
        if is_key:
            current_key = deque(items, maxlen=1).pop()  # last of items
        elif current_key is not None:
            result[current_key].extend(items)
    return result

Это не различает ключи, которые вообще не встречаются в values (например, e и f), и ключи, для которых нет соответствующих значений (например, d). Если эта информация необходима, возможно, лучше подойдет одно из других решений.

Answer 7

Обновлено ... Снова

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

Я собираюсь использовать два списка понимания.

idxs = [i for i, val in enumerate(l2) if val in l1] + [len(l2)+1]
res = {l2[idxs[i]]: list(l2[idxs[i]+1: idxs[i+1]]) for i in range(len(idxs)-1)}
print(res)

Результаты:

{'a': ['el1', 'el2', 'el3', 'el4'],
 'b': ['some_other_el_1', 'some_other_el_2'],
 'c': ['another_element_1', 'another_element_2'],
 'd': ['', '', 'another_element_3', 'd4']}

Тестирование скорости для больших списков:

import collections


l1 = ['a', 'c', 'b', 'e', 'f', 'd']
l2 = [
    'x','q','we','da','po',
    'a', 'el1', 'el2', 'el3', 'el4', *(str(i) for i in range(300)),
    'b', 'some_other_el_1', 'some_other_el_2', *(str(i) for i in range(100)),
    'c', 'another_element_1', 'another_element_2', *(str(i) for i in range(200)),
    'd', '', '', 'another_element_3', 'd4'
]


def run_comp():
    idxs = [i for i, val in enumerate(l2) if val in l1] + [len(l2)+1]
    res = {l2[idxs[i]]: list(l2[idxs[i]+1: idxs[i+1]]) for i in range(len(idxs)-1)}


def run_other():
    d = collections.defaultdict(list)
    k = ''

    for x in l2:
        if x in l1:
            k = x
        else:
            d[k].append(x)


import timeit
print('For Loop:', timeit.timeit(run_other, number=1000))
print("List Comprehension:", timeit.timeit(run_comp, number=1000))

Результаты:

For Loop: 0.1327093063242541
List Comprehension: 0.09343156142774986

старые вещи ниже

Это довольно просто для списочных представлений.

{key: [val for val in l2 if key in val] for key in l1}

Результаты:

{'a': ['a', 'a1', 'a2', 'a3', 'a4'],
 'b': ['b', 'b1', 'b2', 'b3', 'b4'],
 'c': ['c', 'c1', 'c2', 'c3', 'c4'],
 'd': ['d', 'd1', 'd2', 'd3', 'd4'],
 'e': [],
 'f': []}

Код ниже показывает, что происходит выше.

d = {}
for key in l1:
    d[key] = []
    for val in l2:
        if key in val:
            d[key].append(val)

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

Ссылки:

• http://www.pythonforbeginners.com/basics/list-comprehensions-in-python
• https://docs.python.org/3.6/tutorial/datastructures.html#list-comprehensions

Answer 8

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

import collections

d = collections.defaultdict(list)
k = ''

for x in l2:
    if x in l1:
        k = x
    else:
        d[k].append(x)