logo标签列表

高效地在字符串列表中检查字符串是否存在

pythonalgorithmlist-comprehension
3
我有一个很长的字符串，假设为astr = "I am a very long string and I could contain a lot of text, so think of efficiency here"。我还有一个列表alist = ["I", "am a", "list", "of strings", "and each string", "could be made up of many words", "so think of efficiency here"]。现在，我的字符串列表还有一个对应的整数列表alist_ofints = [1, 2, 3, 4, 5, 6, 7]，表示此列表中每个字符串等于多少个点数。

我需要创建一个函数，找出在列表alist中出现的单词在astr中出现了多少次，并使用相应的点数列表alist_ofints创建一个“点数”计数器。因此，在这个例子中，“I”，“am a”和“so think of efficiency here”各出现一次。这将给我们1*2 + 2*1 + 7*1 = 11分。

我想出了两种简单的解决方案。第一种是创建一个函数，查看此字符串列表alist并检查每个项是否在astr中，如果是，则应用明显的以下逻辑。这是低效的，因为我将在astr中查找len(alist)次。这是一种浪费，不是吗？它很简洁明了，但效率低下。

第二个解决方案是将astr变为单词列表，并检查从索引i到索引j的每个单词，其中i是我在列表中的位置，j是我正在寻找的alist短语的长度。因此，“am a”是长度为2的短语（因为它有两个单词），所以我会查看i =某个数字，j =某个数字+1。如果我正在寻找短语"and each string"，则i =某个数字，j =某个数字+3。因此，在测试此短语时，我正在查看三个单词。现在，我认为这也具有相同的时间复杂度。虽然我没有一次循环遍历astr列表，但我要循环遍历我的单词列表alistlen(list(astr))次。而且，我必须创建一个astr列表，这增加了一些复杂性，我想。

因此，到目前为止，我更喜欢第一种解决方案，因为它最容易，最简单，最干净。有更好的方法吗？如果您可以找到一个列表理解方式，那就额外加分了...

谢谢

注意：我知道list(astr)不会返回单词列表。在这个例子中，请想象它会返回。

简而言之：我有两个列表。我需要检查列表中的每个元素是否等于另一个列表中的元素，并创建一个计数器来记录它们出现的次数。除了逐个检查列表1中的每个元素与列表2中的其他元素是否相等（我认为这是O(n^2)），还有更有效的方法吗？

你应该发布你的“天真”的解决方案。 - asongtoruin
1
@asongtoruin 我有个习惯，在实现编码之前，我会先确立一个清晰的算法。 - John Lexus
@Chris_Rands 只需阅读前三段即可...我试图向社区提供尽可能多的信息，以展示我的思考过程。如果您认为这与您想出解决方案的方式无关，那么这并不重要。 - John Lexus
@SaiBot 我将在列表中搜索什么？ - John Lexus
2
谢谢您用语言而不是代码来描述您的思考方式。我认为这很棒。 - גלעד ברקן
显示剩余8条评论
5个回答
2

我已经写了这一行代码，看起来正是你想要的：

print sum([str.count(s) * i for (s,i) in zip(alist, alist_ofints)])

这更像是您的第一种方法，但我并不认为它很低效。

需要注意的一件事是，str.count(s) 只计算 str 中 s 的非重叠出现次数。

这看起来不错，但正如你所提到的，这恰好是我第一次尝试时会做的方式。难道没有其他更有效的方法吗？ - John Lexus
你能告诉我们为什么效率在你的情况下如此重要吗？你的列表大小是一百万吗？@JohnLexus - Arpit Solanki
@JohnLexus 你需要明白的一件事是如何衡量性能。你说你正在处理神经网络相关的东西，所以你的单个字符串大小可能会变化，你的列表大小也会变化，你的机器的功率、RAM等等也会变化。因此，有太多的变量来衡量性能。我建议你实现你的算法，并使用时间命令或一些分析工具来衡量性能，如果性能显著缓慢，那么你可以提问。我没有看到你的任何解决方案中性能变差的情况。还有一个建议，先尝试再问问题。 - Arpit Solanki
@ArpitSolanki 你说得完全正确；这并不是完整的问题，只是一个非常类似我所面临的问题。我真正面临的问题太复杂而难以解释 - 这个问题更容易理解...但还是谢谢你的建议。 - John Lexus
2
不要在stackoverflow上提问，可以去codereview.stackexchange.com上发帖。把你的两个实现方案都放出来，并询问是否有更好的解决方案。因为从技术上讲，你已经有了一个可用的解决方案，没有任何错误，所以这个问题不应该在stackoverflow上提问。 - Arpit Solanki
显示剩余4条评论
2
一种更高效的算法可以使用字符串索引（例如后缀数组）来索引长字符串astr。然后在索引中搜索alist中的每个条目，并在找到结果时相应地增加点数。
索引astr的运行时间为O(n)，其中n是astr的长度。
在索引中搜索长度为m的alist中的条目的时间复杂度为O(log n)。
总体而言，您应该得到O(p log n)的效率，其中p是alist中的条目数。
例如，假设长字符串astr为“我是一个非常长的字符串”，则相应的后缀数组（全部小写）将是SA = [1 4 6 11 16 5 2 8 22 15 0 20 12 3 21 14 13 19 9 17 18 7 10]。
这些都是 astr 的后缀（以它们的起始索引表示），按字典顺序排序。例如，SA[9] = 15 表示从位置 15 开始的字符串（"g string"）。

现在假设您有一个短语列表

alist = ["我是", "非常长",...]

然后对于每个条目，您想在后缀数组中搜索出现次数。这是使用二分查找在后缀数组上完成的。对于 "我是"，这将如下所示：

首先，您查看后缀数组的中间条目（SA[11] = 20）。然后，您查看由该索引表示的后缀（"ing"）。由于此后缀大于您的搜索短语 "我是"，因此您要在后缀数组的左半部分查找。继续进行二分查找，直到找到该短语或确定它不存在为止。

这是一个非常有趣的答案。你能给我举个例子吗？那么，我有我的后缀数组表示我的astr。我如何在后缀数组中搜索alist中的每个单词？ - John Lexus
这可能是最有效的方法，但如果您想要在O(log n)中搜索，您需要添加实际排序列表所需的时间。 - ChatterOne
@ChatterOne，您能解释一下我如何使用后缀数组在我的列表中搜索项目吗？ - John Lexus
@ChatterOne 如果您使用基于比较的排序，则此内容是正确的。对于后缀数组，由于您知道使用了哪些符号，因此可以做得更好。因此，排序实际上是O（n）（请参见后缀数组的构建）。 - SaiBot
@SaiBot 那么，计数排序？看起来你可以立即存储计数，对吧？ - ChatterOne
1
@SaiBot 经过深思熟虑，我发现这是最酷的答案。 - John Lexus
1

（我认为这与thebenman的答案类似。）根据alist中重叠的类型，您可以将alist转换为字典（或嵌套字典，即树形结构）：

{
  I: [(None, 1)],
  am: [(a, 2)],
  list: [(None, 3)],
  of: [(strings,4)],
  and: [(each, 0), (string, 5)],
  could: [(be, 0), (made, 0)...,(words, 6)],
  so: [(think, 0), (of, 0)...,(here, 7)]
}

现在，我们可以遍历 astr ，将其作为单词而不是索引，并保留对所有当前打开的累积匹配的引用并更新。
1
你还可以生成所有可能的子序列，对其使用计数器，然后查找时间几乎为O(1)。
这将需要更多的内存来生成字典（或索引），但在需要多次查找相同长字符串的情况下，它将更加高效。
类似于这样：
from collections import Counter


def get_all_counts(input_string):
    cnt = Counter()
    length = len(input_string)
    alist = []
    s = input_string.split()
    for i in range(0, len(s)):
        current_subsequence = ''
        for j in range(i, len(s)):
            current_subsequence += ' ' + s[j]
            cnt[current_subsequence.strip()] += 1 # I've put 1 here, but you could easily replace it with a lookup of your "points"
    return cnt


counts = get_all_counts(
    'I am a very long string and I could contain a lot of text, so think of efficiency here')

print(counts['am'])
print(counts['of'])

也许使用itertools会更好，但你应该能理解这个想法。

另一个优点是你可以将其转换为Pandas数据框并对其进行查询。

例如像这样的内容：

df = pd.DataFrame.from_dict(counts, orient='index').reset_index()

print(df[df[0] > 1])

会给你所有出现次数大于1的子字符串。
1
你可以为单词列表构建一个Trie数据结构，其中的终端节点包含点数组的索引。
从维基百科得知，输入为["A","to", "tea", "ted", "ten", "i", "in", and "inn"]的trie结构如下所示。 

<p><a href="https://commons.wikimedia.org/wiki/File:Trie_example.svg#/media/File:Trie_example.svg"><img src="https://upload.wikimedia.org/wikipedia/commons/b/be/Trie_example.svg" alt="Trie example.svg" height="145" width="155"></a><br>By <a href="https://en.wikipedia.org/wiki/User:Booyabazooka" class="extiw" title="en:User:Booyabazooka">Booyabazooka</a> (based on PNG image by <a href="https://en.wikipedia.org/wiki/User:Deco" class="extiw" title="en:User:Deco">Deco</a>). Modifications by <a href="//commons.wikimedia.org/wiki/User:Superm401" class="mw-redirect" title="User:Superm401">Superm401</a>. - own work (based on PNG image by <a href="https://en.wikipedia.org/wiki/User:Deco" class="extiw" title="en:User:Deco">Deco</a>), Public Domain, <a href="https://commons.wikimedia.org/w/index.php?curid=1197221">Link</a></p>

所以我们可以遍历整个输入字符串，每当遇到一个单词结尾节点时，就将其分数加起来并继续前进。
因此，整个单词的搜索可以在线性时间内完成。
但是，在存在重叠列表项的情况下，例如["ab", "cd", "abcd"]，分数为[3, 4, 1]，单词为abcd。在预处理后，我们将无法拥有线性时间解决方案，因为每次遇到单词结尾时，最大分数可能来自以下两种情况之一：
1. 将字符串扩展到目前为止的单词，并继续向前查找。 2. 开始将剩余字符串作为列表中的单独单词进行查找。
构建Trie结构的时间和空间复杂度为O(w * m)，其中w是单词数量，m是列表中单词的最大长度。
搜索的时间复杂度为O(m)，其中m是要搜索的单词长度。
你应该添加更多的上下文或一些例子，说明为什么trie树在OP的情况下会很有用。目前并不是非常清楚为什么OP应该使用trie数据结构。 - Arpit Solanki
如果这是真的，我认为这也是一个不错的解决方案，我需要进一步研究一下。 - John Lexus
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接