Python - 查找字符串列表中包含的唯一子字符串的索引，而无需遍历所有项目

Question

我有一个问题，听起来像是已经问过的问题，但实际上我找不到一个真正好的答案。每天我都有一个列表，里面有几千个字符串。我也知道这个字符串将始终包含一个包含单词“other”的项目。例如，有一天我可能有：a = ['mark','george', .... , " ...other ...", "matt','lisa', ... ]另一天我可能会得到：a = ['karen','chris','lucas', ............................., '...other']如您所见，包含子字符串“other”的项的位置是随机的。我的目标是尽快获得包含子字符串“other”的项目的索引。我在这里找到了其他答案，大多数人建议列出对寻找的理解。例如：在Python中查找列表中的子字符串并检查Python列表项是否在另一个字符串中包含字符串它们对我不起作用，因为它们太慢了。此外，其他解决方案建议使用“any”来简单地检查列表中是否包含“other”，但我需要索引而不是布尔值。我相信正则表达式可能是一个很好的潜在解决方案，即使我很难弄清楚如何。到目前为止，我只是设法做了以下事情：# any_other_value_available  will tell me extremely quickly if 'other' is contained in list.any_other_value_available = 'other' in str(list_unique_keys_in_dict).lower()从这里开始，我不太清楚该怎么办。有什么建议吗？谢谢

Answer 1

探索的方法

1. 生成器方法

next(i for i,v in enumerate(test_strings) if 'other' in v)

2. 列表理解法

[i for i,v in enumerate(test_strings) if 'other' in v]

3. 将索引与生成器一起使用（由@HeapOverflow建议）

test_strings.index(next(v for v in test_strings if 'other' in v))

4. 带生成器的正则表达式

re_pattern = re.compile('.*other.*')next(test_strings.index(x) for x in test_strings if re_pattern.search(x))

结论

索引方法具有最快的时间（@HeapOverflow在注释中建议的方法）。

测试代码

使用使用timeit的Perfplot

import random 

import string

import re

import perfplot

def random_string(N):

    return ''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(N))

def create_strings(length):

    M = length // 2

    random_strings = [random_string(5) for _ in range(length)]

    front = ['...other...'] + random_strings

    middle = random_strings[:M] + ['...other...'] + random_strings[M:]

    end_ = random_strings + ['...other...']

    return front, middle, end_

def search_list_comprehension(test_strings):

    return [i for i,v in enumerate(test_strings) if 'other' in v][0]

def search_genearator(test_strings):

    return next(i for i,v in enumerate(test_strings) if 'other' in v)

def search_index(test_strings):

    return test_strings.index(next(v for v in test_strings if 'other' in v))

def search_regex(test_strings):

    re_pattern = re.compile('.*other.*')

    return next(test_strings.index(x) for x in test_strings if re_pattern.search(x))

# Each benchmark is run with the '..other...' placed in the front, middle and end of a random list of strings.

out = perfplot.bench(

    setup=lambda n: create_strings(n),  # create front, middle, end strings of length n

    kernels=[

        lambda a: [search_list_comprehension(x) for x in a],

        lambda a: [search_genearator(x) for x in a],

        lambda a: [search_index(x) for x in a],

        lambda a: [search_regex(x) for x in a],

    ],

    labels=["list_comp", "generator", "index", "regex"],

    n_range=[2 ** k for k in range(15)],

    xlabel="lenght list",

    # More optional arguments with their default values:

    # title=None,

    # logx="auto",  # set to True or False to force scaling

    # logy="auto",

    # equality_check=numpy.allclose,  # set to None to disable "correctness" assertion

    # automatic_order=True,

    # colors=None,

    # target_time_per_measurement=1.0,

    # time_unit="s",  # set to one of ("auto", "s", "ms", "us", or "ns") to force plot units

    # relative_to=1,  # plot the timings relative to one of the measurements

    # flops=lambda n: 3*n,  # FLOPS plots

)

out.show()

print(out)

结果

length list   regex    list_comp  generator    index

     1.0     10199.0     3699.0     4199.0     3899.0

     2.0     11399.0     3899.0     4300.0     4199.0

     4.0     13099.0     4300.0     4599.0     4300.0

     8.0     16300.0     5299.0     5099.0     4800.0

    16.0     22399.0     7199.0     5999.0     5699.0

    32.0     34900.0    10799.0     7799.0     7499.0

    64.0     59300.0    18599.0    11799.0    11200.0

   128.0    108599.0    33899.0    19299.0    18500.0

   256.0    205899.0    64699.0    34699.0    33099.0

   512.0    403000.0   138199.0    69099.0    62499.0

  1024.0    798900.0   285600.0   142599.0   120900.0

  2048.0   1599999.0   582999.0   288699.0   239299.0

  4096.0   3191899.0  1179200.0   583599.0   478899.0

  8192.0   6332699.0  2356400.0  1176399.0   953500.0

 16384.0  12779600.0  4731100.0  2339099.0  1897100.0

Answer 2

如果你正在寻找一个子字符串，正则表达式是找到它的好方法。

在你的情况下，你正在寻找所有包含“other”的子字符串。正如您已经提到的，列表中的元素没有特殊顺序。因此，对所需元素的搜索是线性的，即使它是有序的。

可能描述您的搜索的正则表达式是 。关于文档query='.*other.*'

.（点。在默认模式下，这将匹配除换行符以外的任何字符。如果已指定 DOTALL 标志，则此标志将匹配任何字符，包括换行符。

*使生成的 RE 与前一个 RE 的 0 次或更多次重复匹配，并尽可能多地重复。ab* 将匹配 “a”、“ab”或 “a”，后跟任意数量的 “b”。

在之前和之后，任何字符都可以有0个或更多次重复。.*other

例如

import re

list_of_variables = ['rossum', 'python', '..other..', 'random']

query = '.*other.*'

indices = [list_of_variables.index(x) for x in list_of_variables if re.search(query, x)]

这将返回包含 .在此示例中，将是 ，因为 是列表中的第三个元素。queryindices[2]'...other...'