Найти признаки строки в списке строк для несортированного списка

Question

Постановка задачи

Если вам дана строка, давайте назовем ее target, вы можете вернуть мне ВСЕ признаки, в которых target находится в некотором входном списке строк (это важно, этоэто список строк, а не чисел), давайте назовем его input_list.Пример ввода:

target = '1234'
input_list = [str(x) for x in range(30000)] + [str(x) for x in range(30000)]

Вы не можете предполагать, что input_list отсортирован, если вы хотите отсортировать список, вам нужно будет добавить его в свою собственную версию benchmarkFind().Простое решение состоит в том, чтобы просто сделать следующее, но это может быть очень неэффективно:

def benchmarkFind(target,input_list):
    out = []
    for i in range(len(input_list)):
        if input_list[i] == target:
            out.append(i)
    return out

Ответ здесь будет следующим:

idx = [1234, 31234]

Результаты теста

>>> %timeit benchmarkFind(target,input_list)
100 loops, best of 3: 3.07 ms per loop

Результаты комментариев пользователей

От @trincot и @Abhinav Sood - Немного лучше, но не очень.

def enumerateFind(target,input_list):
    return [i for i, e in enumerate(input_list) if e == target]

>>> %timeit enumerateFind(target,input_list)
100 loops, best of 3: 2.96 ms per loop

От @B.M - Это, похоже, лучший ответ на данный момент !

def primitiveFind(target ,input_list):
    try :
        l=[]
        u=-1
        while True:
            u = input_list.index(target,u+1)
            l.append(u)
    except ValueError:
        return l

>>> %timeit primitiveFind(target,input_list)
1000 loops, best of 3: 577 µs per loop

Answer 1

Петли Python, как известно, медленные, но примитивы в списке быстрые.list.index быстро.

def find2(target ,input_list):
    try :
        l=[]
        u=-1
        while True:
        u= input_list.index(target,start=u+1)
        l.append(u)
    except ValueError:
        return l

работает:

In [32]: find2(target,input_list)
Out[32]: [1234, 31234]

In [33]: %timeit find2(target,input_list)
2.8 ms ± 255 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [34]: %timeit benchmarkFind(target,input_list)
12 ms ± 1.35 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [35]: %timeit [i for i, e in enumerate(input_list) if e == target]
14.2 ms ± 1.79 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

в 4 раза быстрее на моем компьютере сегодня утром.

РЕДАКТИРОВАТЬ

Для дальнейшей настройки, выравнивание данных важно, массивные массивы - хороший способ добиться этого.К сожалению, преобразование из списка является дорогостоящим, поэтому имеет смысл, если данные могут быть представлены в виде массива:

input_arr=np.array(input_list)

(input_arr==target).nonzero()
(array([ 1234, 31234], dtype=int64),)

%timeit input_arr=np.array(input_list)
10.6 ms ± 414 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit (input_arr==target).nonzero()
1.56 ms ± 123 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Answer 2

Перечисление выполняется намного быстрее:

python -m timeit -s "\
    target = '1234';\
    input_list = [str(x) for x in range(30000)] + [str(x) for x in range(30000)];\
    idx = [i for i, e in enumerate(input_list) if e == target]"

100000000 циклов, лучше всего 3: 0,00582 usec на цикл