Оптимизируйте поиск в длинном списке строк

Question

У меня есть следующий MWE, где я использую понимание списка для поиска в списке ls для строк, которые содержатся strings:

import numpy as np

strings = ["ASD", "DSA", "ABC", "ABQ"]
ls     = np.asarray(["ASD", "DSA", "ASD", "ABC", "ABQ","ASD", "DSA", "ASD", "ABC", "ABQ","ASD", "DSA", "ASD", "ABC", "ABQ"])

for string in strings:
    print(len(ls[[string in s for s in ls]]))  

Это работает, как задумано - однако проблемав том, что мой ls -лист очень длинный (10 ^ 9 записей), а его понимание занимает значительное время.

Есть ли способ оптимизировать приведенный выше код?

---

РЕДАКТИРОВАТЬ: Я ищу решение, которое позволит мне записывать отдельные случаи, то есть 6, 3, 3 и 3

Answer 1

Предлагаю вам использовать идеи, предложенные в этом посте ;наилучшим подходом может быть использование collections.Counter.

. Это позволяет построить Counter один раз, и тогда вы можете легко найти отдельные элементы, для которых вы хотите рассчитывать.

Это может выглядеть такэто:

import collections
import numpy as np
import timeit

def _get_data(as_numpy):
    data = []
    for _ in range(10**6):
        data.extend(["ASD", "DSA", "ASD", "ABC", "ABQ"])

    if as_numpy:
        data = np.asarray(data)

    return data

def f1(data):
    search_list = ["ASD", "DSA", "ABC", "ABQ"]
    result_list = []

    for search_str in search_list:
        result_list.append(
            len(data[[search_str in s for s in data]]))

    return result_list

def f2(data):
    search_list = ["ASD", "DSA", "ABC", "ABQ"]
    result_list = []

    c = collections.Counter(data)
    for search_str in search_list:
        result_list.append(
            c[search_str])

    return result_list

def f3(data):
    search_list = ["ASD", "DSA", "ABC", "ABQ"]
    result_list = []

    c = collections.Counter(data)
    for search_str in search_list:
        result_list.append(
            data.count(search_str))

    return result_list

def f4(data):
    # suggestion by user 'nixon' in another answer to this question
    search_list = ["ASD", "DSA", "ABC", "ABQ"]

    l, counts = np.unique(data, return_counts=True)
    # 'l' and 'counts' are in different order than 'search_list'
    result_list = [
        counts[np.where(l == search_str)[0][0]]
        for search_str in search_list]

    return result_list

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

data1 = _get_data(as_numpy=True)
data2 = _get_data(as_numpy=False)
assert f1(data1) == f2(data2) == f3(data2) == f4(data1)

И сравнивая время, я получаю:

print(timeit.timeit(
    'f(data)',
    'from __main__ import f1 as f, _get_data; data = _get_data(as_numpy=True)',
    number=10))
print(timeit.timeit(
    'f(data)',
    'from __main__ import f2 as f, _get_data; data = _get_data(as_numpy=False)',
    number=10))
print(timeit.timeit(
    'f(data)',
    'from __main__ import f3 as f, _get_data; data = _get_data(as_numpy=False)',
    number=10))
print(timeit.timeit(
    'f(data)',
    'from __main__ import f4 as f, _get_data; data = _get_data(as_numpy=True)',
    number=10))

# f1 48.2 sec
# f2  1.7 sec
# f3  3.8 sec
# f4  9.7 sec

Как вы можетевидите, есть разница в разнице во времени.

Это работает для вашего случая?

---

РЕДАКТИРОВАТЬ: добавлен подход с использованием numpy.unique, аналогичный предложенному @Никсон в другом ответе на этот вопрос;кажется, что он все еще медленнее, чем collections.Counter.

Answer 2

Используйте np.unique с return_counts=True и используйте np.in1d для выполнения логической индексации и сохраняйте только значения в ls, которые присутствуют в strings на обоихуникальные значения и количество:

l, counts = np.unique(ls, return_counts=True)
mask = np.in1d(l,strings)

l[mask]
#array(['ABC', 'ABQ', 'ASD', 'DSA'], dtype='<U3')

counts[mask]
array([3, 3, 6, 3], dtype=int64)