Как сделать этот поиск и считать намного быстрее?

Question

def count_occurrences(string):
    count = 0
    for text in GENERIC_TEXT_STORE:
        count += text.count(string)
    return count

GENERIC_TEXT_STORE - список строк. Например:

GENERIC_TEXT_STORE = ['this is good', 'this is a test', 'that's not a test']

Учитывая строку 'text', я хочу узнать, сколько раз текст, то есть 'this', встречается в GENERIC_TEXT_STORE. Если мой GENERIC_TEXT_STORE огромен, это очень медленно. Какие способы сделать этот поиск и считать намного быстрее? Например, если я разделю большой список GENERIC_TEXT_STORE на несколько небольших списков, это будет быстрее?

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

Answer 1

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

In [2]: GENERIC_TEXT_STORE = ['this is good', 'this is a test', 'that\'s not a test']

In [3]: def count_occurrences(string):
   ...:     count = 0
   ...:     for text in GENERIC_TEXT_STORE:
   ...:         count += text.count(string)
   ...:     return count

In [6]: import re

In [7]: def count(_str):
   ...:     return len(re.findall(_str,''.join(GENERIC_TEXT_STORE)))
   ...:
In [28]: def count1(_str):
    ...:     return ' '.join(GENERIC_TEXT_STORE).count(_str)
    ...:

---

Теперь используйте timeit для анализа времени выполнения.

, когда размер GENERIC_TEXT_STORE равен 3.

In [9]: timeit count('this')
1.27 µs ± 57.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [10]: timeit count_occurrences('this')
697 ns ± 25.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [33]: timeit count1('this')
385 ns ± 22.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

, если размер GENERIC_TEXT_STORE равен 15000.

In [17]: timeit count('this')
1.07 ms ± 118 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [18]: timeit count_occurrences('this')
3.35 ms ± 279 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [37]: timeit count1('this')
275 µs ± 18.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

, если размер GENERIC_TEXT_STORE равен 150000

In [20]: timeit count('this')
5.7 ms ± 2.39 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [21]: timeit count_occurrences('this')
33 ms ± 3.26 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [40]: timeit count1('this')
3.98 ms ± 211 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

при размере из GENERIC_TEXT_STORE превышает миллион (1500000)

In [23]: timeit count('this')
50.3 ms ± 7.21 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [24]: timeit count_occurrences('this')
283 ms ± 12.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [43]: timeit count1('this')
40.7 ms ± 1.09 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

count1

Когда размер GENERIC_TEXT_STORE большой count и count1 почти в 4-5 раз быстрее count_occurrences.

Answer 2

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

any((word==string for word in text.split()))

Многопроцессорная обработка, вероятно, поможет, поскольку вы можете разбить список на меньшие списки (по одному на ядро), а затем сложить все результаты после завершения каждого процесса (избегать процесс общения во время исполнения). В ходе тестирования я обнаружил, что мультипроцессорная обработка в Python в разных операционных системах довольно сильно отличается, Windows и Ma c могут на самом деле занимать довольно много времени, чтобы порождать процессы, тогда как Linux, кажется, делает это очень сильно. Быстрее. Некоторые люди говорят, что установка соответствия процессоров для каждого процесса с использованием pstools важна, но я не нашел, чтобы это имело большое значение в моем случае.

Другой ответ - посмотреть на использование Cython для компиляции * 1011. * в C программу или, в качестве альтернативы, переписать все это на более быстром языке, но, как вы пометили этот ответ Python Я полагаю, вы не очень заинтересованы в этом.