Эффективно проверьте, если элемент встречается не менее n раз в списке

Как лучше написать функцию Python (check_list) для эффективного тестирования, если элемент (x) встречается не менее n раз в списке (l)?

Моя первая мысль была:

def check_list(l, x, n):
    return l.count(x) >= n

Но это не короткое замыкание, когда x было найдено n раз и всегда O (n).

Простой подход, который делает короткое замыкание:

def check_list(l, x, n):
    count = 0
    for item in l:
        if item == x:
            count += 1
            if count == n:
                return True
    return False

У меня также есть более компактное короткое замыкание с генератором:

def check_list(l, x, n):
    gen = (1 for item in l if item == x)
    return all(next(gen,0) for i in range(n))

Есть ли другие хорошие решения? Каков наилучший эффективный подход?

Спасибо

Ответ 1

Вместо того, чтобы налагать дополнительные накладные расходы на установку объекта range и используя all, который должен проверить правдоподобие каждого элемента, вы можете использовать itertools.islice выполнить предварительный шаг генератора n, а затем вернуть следующий элемент в срезе, если существует срез, или по умолчанию False, если нет:

from itertools import islice

def check_list(lst, x, n):
    gen = (True for i in lst if i==x)
    return next(islice(gen, n-1, None), False)

Обратите внимание, что как list.count, itertools.islice также работает со скоростью C. И это имеет дополнительное преимущество в обработке итераций, которые не являются списками.

Некоторое время:

In [1]: from itertools import islice

In [2]: from random import randrange

In [3]: lst = [randrange(1,10) for i in range(100000)]

In [5]: %%timeit # using list.index
   ....: check_list(lst, 5, 1000)
   ....:
1000 loops, best of 3: 736 µs per loop

In [7]: %%timeit # islice
   ....: check_list(lst, 5, 1000)
   ....:
1000 loops, best of 3: 662 µs per loop

In [9]: %%timeit # using list.index
   ....: check_list(lst, 5, 10000)
   ....:
100 loops, best of 3: 7.6 ms per loop

In [11]: %%timeit # islice
   ....: check_list(lst, 5, 10000)
   ....:
100 loops, best of 3: 6.7 ms per loop

Ответ 2

Вы можете использовать второй аргумент index, чтобы найти последующие индексы вхождений:

def check_list(l, x, n):
    i = 0
    try:
        for _ in range(n):
            i = l.index(x, i)+1
        return True
    except ValueError:
        return False

print( check_list([1,3,2,3,4,0,8,3,7,3,1,1,0], 3, 4) )

О `index` arguments

Официальная документация не упоминает в своем Python Tutuorial, раздел 5 метод второй или третий аргумент, но вы можете найти его в более всеобъемлющий Стандартная библиотека Python, раздел 4.6:

s.index(x[, i[, j]]) индекс первого вхождения x в s (с или после индекса я и перед индексом j) ⁽⁸⁾

⁽⁸⁾index вызывает ValueError, когда x не найден в s. При поддержке дополнительные аргументы метода индекса позволяют эффективно искать подразделы последовательности. Передача дополнительных аргументов примерно эквивалентна использованию s[i:j].index(x), только без копирования каких-либо данных, а возвращаемый индекс относится к началу последовательности, а не к началу среза.

Сравнение производительности

При сравнении этого метода list.index с методом islice(gen) наиболее важным фактором является расстояние между найденными вхождениями. Когда это расстояние составляет в среднем 13 или более, list.index имеет лучшую производительность. Для более низких расстояний самый быстрый метод также зависит от количества найденных случаев. Чем больше случаев для поиска, тем быстрее метод islice(gen) превосходит list.index по среднему расстоянию: это усиление исчезает, когда число вхождений становится действительно большим.

Следующий график рисует (приблизительную) линию границы, при которой оба метода работают одинаково хорошо (ось X логарифмическая):

Ответ 3

В конечном итоге короткое замыкание - это путь, если вы ожидаете, что значительное число случаев приведет к досрочному прекращению. Позвольте изучить возможности:

Возьмем случай метода list.index по сравнению с методом list.count (это были самые быстрые в соответствии с моим тестированием, хотя ymmv)

Для list.index, если список содержит n или более x, и метод вызывается n раз. Хотя в методе list.index выполнение выполняется очень быстро, что позволяет ускорить итерацию, чем пользовательский генератор. Если происхождение x достаточно далеко друг от друга, будет видно большое ускорение с нижнего уровня выполнения index. Если экземпляры x находятся близко друг к другу (более короткий список/более распространенные x), гораздо больше времени будет потрачено на выполнение более медленного кода на Python, который опосредует остальную часть функции (переключение по n и увеличение i)

Преимущество list.count заключается в том, что он выполняет весь тяжелый подъем за пределами медленного выполнения python. Это гораздо более простая функция для анализа, поскольку это просто случай сложности времени O (n). Проводя почти почти никогда не в интерпретаторе python, однако он почти готов к более быстрым вычислениям для коротких списков.

Сводка критериев выбора:

более короткие списки предпочитают list.count
списки любой длины, которые не имеют высокой вероятности использования короткого замыкания list.count
списки, которые являются длинными и вероятными для короткого замыкания list.index

Ответ 4

Я бы рекомендовал использовать Counter из модуля collections.

from collections import Counter

%%time
[k for k,v in Counter(np.random.randint(0,10000,10000000)).items() if v>1100]

#Output:
    Wall time: 2.83 s
    [1848, 1996, 2461, 4481, 4522, 5844, 7362, 7892, 9671, 9705]

Ответ 5

Это показывает другой способ сделать это.

Сортировка списка.
Найдите индекс первого вхождения элемента.
Увеличить индекс на единицу меньше количества раз, когда элемент должен произойти. (n - 1)

Найти, если элемент в этом индексе совпадает с элементом, который вы хотите найти.

def check_list(l, x, n):
    _l = sorted(l)
    try:
        index_1 = _l.index(x)
        return _l[index_1 + n - 1] == x
    except IndexError:
        return False

Ответ 6

Другая возможность может быть:

def check_list(l, x, n):
    return sum([1 for i in l if i == x]) >= n