Как, найдя значения в одном списке, сосчитать количество тех же самых значений во втором?

Question

[Timebird]

Пример:
Допустим, есть список: lst1 = [a, b, c]. И второй список: lst2 = [d, a d, e, a, f, a, d, b, b, c, a, b, k, e, a, c, c, b].
Надо на каждое из значений lst1 найти количество тех же a, b, c в lst2, чтобы вывод был такой:
a: 5
b: 4
c: 3
Как это реализуется при помощи словаря? Может, есть какое-то изящное решение, чтобы не городить счётчики на каждое из значений lst1?

Answer 1

[Максим Мосейчук]

from collections import Counter

lst1 = ["a", "b", "c"]
lst2 = ["d", "a" "d", "e", "a", "f", "a", "d", "b", "b", "c", "a", "b", "k", "e", "a", "c", "c", "b"]

counter = Counter(lst2)
for key in lst1:
    print(f'{key}: {counter[key]}')

Comments

[Andrey Dugin]

Поправлю: следует обойтись без проверки 'k in lst1':

counter = Counter(lst2)
for key in lst1:
    print(f'{key}: {counter[key]}')

Answer 2

[Hrabryi]

Используй генератор словарей - получишь самое изящное решение (и главное быстрое):
print({key: lst2.count(key) for key in lst1})

Comments

[Максим Мосейчук]

Это самое медленное решение, его сложность O(n*m).
Эффективное решение требует O(n) операций.

[Hrabryi]

fshp, а теперь запускаем тест на производительность:

from collections import Counter

import datetime

lst1 = ["a", "b", "c"]
lst2 = ["d", "a" "d", "e", "a", "f", "a", "d", "b", "b", "c", "a", "b", "k", "e", "a", "c", "c", "b"]

time_start = datetime.datetime.now()
for k,v in {key: lst2.count(key) for key in lst1}.items():
    print("{}: {}".format(k,v))
print('Время2: ', datetime.datetime.now()-time_start)

time_start = datetime.datetime.now()
for k,  v in Counter(lst2).items():
    if k in lst1:
        print(f"{k}: {v}")
print('Время: ', datetime.datetime.now()-time_start)

И получаем результат, что вариант с генератором словаря в 2-3 раза быстрее твоего. Не веришь - можешь сам проверить.

[Максим Мосейчук]

Hrabryi, потому что объём данных маленький, создание объекта дольше, чем проход по списку.
Константы сложности разные: k1*O(n*m) и k2*O(n), где k1 < k2.

from collections import Counter
import string

import datetime

lst1 = list(string.ascii_lowercase)
lst2 = list(string.ascii_lowercase)*1000

time_start = datetime.datetime.now()
for k,v in {key: lst2.count(key) for key in lst1}.items():
    print("{}: {}".format(k,v))
print('Время2: ', datetime.datetime.now()-time_start)


time_start = datetime.datetime.now()
counter = Counter(lst2)
for k in lst1:
    print(f"{k}: {counter.get(k, 0)}")
print('Время: ', datetime.datetime.now()-time_start)

Если увеличить количество элементов, то ваш способ уже на порядок отстаёт. Counter проходит по списку всегда один раз. Ваш способ проходит по списку столько раз, сколько есть элементов в lst1.

[Игорь Иванов]

fshp, Ваш алгоритм быстрее только на сортированных данных.
Возьмите любой большой текстовый файл в качестве "lst2" (мегабайт на 50) и повторите измерения.

import timeit
from collections import Counter
import string

with open("book.txt", "r") as f_in:
    lst1 = list(string.ascii_uppercase)
    
    lst2 = f_in.read().upper()
    #lst2 = list(string.ascii_lowercase) * 100000
        
    t = timeit.default_timer()
    counter = {i: lst2.count(i) for i in lst1}
    for k in lst1:
        print(f"{k} : {counter.get(k, 0)}")
    print("\nCode execution time: {0:.4} sec.\n".format(timeit.default_timer() - t))

    t = timeit.default_timer()
    counter = Counter(lst2)
    for k in lst1:
        print(f"{k} : {counter.get(k, 0)}")
    print("\nCode execution time: {0:.4} sec.\n".format(timeit.default_timer() - t))

[Максим Мосейчук]

Игорь Иванов, сортировка не имеет к этому отношения. К тому же list(string.ascii_lowercase)*1000 не сортированный.

У вас код неверный. lst2 у вас не список, а строка. count на строках это совсем не то, что count на списках, т.к. строка в памяти непрерывным куском данных хранится. Counter же работает с iterable.

lst2 = list(f_in.read().upper())
И уже цифры не такие радужные.

[Максим Мосейчук]

Игорь Иванов, для строк лучше defaultdict использовать.