python - 在未排序列表的字符串列表中查找字符串索引

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 倍。

编辑

对于进一步调整，数据对齐很重要，numpy 数组是实现这一点的好方法。不幸的是，从列表的转换成本很高，因此如果可以以数组形式提供数据，这是有意义的:

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)