在Python中比较字符串的最快方法

Question

我正在用Python编写一个脚本，允许用户输入一个字符串，这个字符串是一条指令，指示脚本执行特定的操作。举个例子，我会列出我的指令列表：

lock
read
write
request
log

现在，我希望用户能够输入单词“log”，然后进行特定的操作，这非常简单。但是，我希望能够匹配部分单词。例如，如果用户输入“lo”，它应该匹配“lock”，因为它在列表中更高。我尝试使用ctypes从libc中的strncmp来完成这个任务，但是我还没有搞清楚。

- Mike Trpcic

---

速度到底有多重要？假设这只在用户输入命令时运行一次，并在少于1000个命令的小集合上运行，即使是最低效（实用）的实现也会在不到一毫秒的时间内返回结果 - 这对用户来说几乎是瞬间完成的。 - Frank Farmer

这是一个运行在Twisted框架上的网络应用程序，最多可能有50个用户同时输入命令，如果所有50个用户都在输入命令并且我没有有效地解析它们，那么可能会出现潜在的延迟。 - Mike Trpcic

Twisted是线程化的。你仍然不会注意到任何影响。大多数计算机可以在你按下一个键的时间内比较10,000个或更多的字符串。这被称为过早优化，你正在浪费时间在琐事上。 - SpliFF

简单构建，然后测量您的性能问题所在。似乎很不可能是命令解析。 - Ned Batchelder

@SpliFF 我同意信息的精神，然而 Twisted 并不是线程化的。除非你自己去实现（例如 deferToThread）。 - Devin Jeanpierre

Mike，这是某种终端服务器吗（考虑到你之前关于ANSI转义序列的问题）？如果它是一种具有实时交互响应的大规模多用户服务器，您可能有理由专注于性能，以至于几毫秒的差异实际上会很重要。在这种情况下，用户将注意到50ms的延迟。您可能已经知道了...让这里的人们清楚地知道什么时间范围对您很重要，可能会帮助您获得直截了当的回复，而不需要所有可能不需要的建议。 - Peter Hansen

Answer 1

如果你正在接受用户输入，那么为什么要担心比较速度？即使是最慢的技术也比用户感知到的要快得多。使用最简单易懂的代码，并将效率问题留给紧密的内部循环。

cmds = [
    "lock",
    "read",
    "write",
    "request",
    "log",
    ]

def match_cmd(s):
    matched = [c for c in cmds if c.startswith(s)]
    if matched:
        return matched[0]

- Ned Batchelder

---

真希望我能给那个点赞10倍。这就是为什么我非常喜欢UI开发 - 时间尺度绝对（嗯，相对而言）非常巨大。你可以悠闲地花费100毫秒来完成某些事情，而没有人会注意到。 - Bryan Oakley

Answer 2

这将实现您想要的功能：

def select_command(commands, user_input):
    user_input = user_input.strip().lower()
    for command in commands:
        if command.startswith(user_input):
            return command
    return None

然而：

你似乎过于担心了错误的事情。因此，50个用户意味着50毫秒的延迟 - 您不会因这种“滞后”而被开除。要担心的是低效的数据库访问或由用户输入“r”并得到“read”而他们以为会得到“request”引起的问题。在冒险出错的情况下最小化用户击键，这种做法早已过时。他们使用的是什么？ASR33电传打字机吗？至少您可以坚持唯一匹配 - “rea”表示read，“req”表示request。

- John Machin

Answer 3

这是根据您的要求在运行时进行优化的…（虽然大多数情况下并不需要）

以下是一个简单的代码示例，它将接受一个输入字典，其中命令映射到函数，并生成一个输出字典，其中所有非重复的子命令都映射到同一个函数。

因此，当您启动服务时运行此代码，然后您就拥有了100％优化的查找功能。我相信还有更聪明的方法可以实现这一点，所以请随意编辑。

commands = {
  'log': log_function,
  'exit': exit_function,
  'foo': foo_function,
  'line': line_function,
  }

cmap = {}
kill = set()
for command in commands:
  for pos in range(len(1,command)):
    subcommand = command[0:pos]
    if subcommand in cmap:
      kill.add(subcommand)
      del(cmap[subcommand])
    if subcommand not in kill:
      cmap[subcommand] = commands[command]

#cmap now is the following - notice the duplicate prefixes removed?
{
  'lo': log_function,
  'log': log_function,
  'e': exit_function,
  'ex': exit_function,
  'exi': exit_function,
  'exit': exit_function,
  'f' : foo_function,
  'fo' : foo_function,
  'foo' : foo_function,
  'li' : line_function,
  'lin' : line_function,
  'line' : line_function,
}

- gahooa

Answer 4

您可以使用startswith函数。

例如：

myword = "lock"
if myword.startswith("lo"):
   print "ok"

如果您想查找单词中的“lo”，而不考虑位置，请使用“in”运算符

if "lo" in myword

因此，您可以采取以下方法来实现这一点：

for cmd in ["lock","read","write","request","log"]:
    if cmd.startswith(userinput):
        print cmd
        break

- ghostdog74

---

@ghostdog74，建议更详细地阅读：“我想匹配部分单词。例如，如果用户输入“lo”，它应该匹配“lock”，因为它在列表中较高。” - Peter Hansen

Peter Hansen 是正确的。为了让系统更易于使用，部分单词需要匹配。我将（最终）有一些复杂的命令，能够将它们缩写成一个字母非常方便。 - Mike Trpcic

Answer 5

我建议您考虑使用Python的readline库，而不是重复造轮子。 用户将必须按Tab键以完成单词，但您可以设置readline，使其在可能的范围内匹配Tab或循环遍历所有以当前存根开头的单词。

这似乎是一个相当不错的Python readline入门http://www.doughellmann.com/PyMOTW/readline/index.html。

- Michael Anderson

Answer 6

jaro_winkler() 在 python-Levenshtein 中可能是你正在寻找的。

- Ignacio Vazquez-Abrams

Answer 7

这是从J.Tauber的Python Trie实现改编而来，您可以将其与您需要的任何额外功能进行比较和/或重新适应。另请参阅Trie的维基百科条目。

class Trie:
    def __init__(self):
        self.root = [None, {}]

    def add(self, key):
        curr_node = self.root
        for ch in key:
            curr_node = curr_node[1].setdefault(ch, [key, {}])
        curr_node[0] = key

    def find(self, key):
        curr_node = self.root
        for ch in key:
            try:
                curr_node = curr_node[1][ch]
            except KeyError:
                return None
        return curr_node[0]

设置（添加顺序很重要！）：

t = Trie()
for word in [
   'lock',
   'read',
   'write',
   'request',
   'log']:
   t.add(word)

然后像这样调用：

>>> t.find('lo')
'lock'
>>> t.find('log')
'log'
>>> t.find('req')
'request'
>>> t.find('requiem')
>>>

- Peter Hansen

---

不开玩笑，但又一次的“使用startswith()迭代列表”看起来真的很无聊。;-) - Peter Hansen

至少我的startswith尝试通过在第一次匹配时退出来解决了OP（无意义的）效率问题 :-) - John Machin

@John，啊，你认为如果“lo”也出现在列表中，但在“lock”之后，输入“lo”将返回“lock”作为匹配项是可以接受的吗？我没有考虑到这一点。 - Peter Hansen

@Peter Hansen：本月最佳“非”“顺序不当”的评论。你没有理由认为我认为那是可以接受的。显然，那是不可接受的。但这是OP所说他想要的自然结果。他显然知道列表中的顺序很重要。人们需要相信(a)他不会在“lock”或“log”之后放置“lo”，(b)如果失败，他会测试他的代码并发现用户无法访问“lo”功能。 - John Machin

@John，这很难是一个“自然的结果”，因为我的解决方案没有遇到这个问题。我还要指出，“在整体解决方案仍然较慢的情况下放弃第一次匹配”，因为它正在遍历一长串命令，这几乎不是解决性能问题的好方法。（当然，在我们讨论之前，我们需要更多关于性能需求和实际列表大小的背景信息。） - Peter Hansen

@Peter：你的解决方案并没有因为偶然事件或者（更加宽容地说）因为你在OP的隐含从左到右的顺序上额外添加了一个限制而受到问题的困扰。在第一次匹配失败时就放弃：你错过了我评论中的笑脸 :-) - John Machin

Answer 8

如果我正确理解了你的问题，你想要一个代码片段，在它拿到答案后立即返回，而不需要继续遍历你的“命令列表”。以下代码应该可以满足你的需求：

from itertools import ifilter

def check_input(some_string, code_book) :
    for q in ifilter(code_book.__contains__, some_string) :
        return True
    return False

- doug

Answer 9

import timeit

cmds = []
for i in range(1,10000):
    cmds.append("test")

def get_cmds(user_input):
    return [c for c in cmds if c.startswith(user_input)]

if __name__=='__main__':
    t = timeit.Timer("get_cmds('te')", "from __main__ import get_cmds")
    print "%0.3f seconds" % (t.timeit(number=1))

#>>> 0.008 seconds

基本上，根据我的评论，您正在询问如何优化一个不需要测量时间或CPU的操作。我在这里使用了10,000个命令，并且测试字符串与每个命令都匹配，只是为了表明即使在极端情况下，您仍然可以有数百个用户执行此操作，他们永远不会看到任何延迟。

- SpliFF

Answer 10

使用你最喜欢的字符串比较函数进行替换。相当快速，且简洁明了。

matches = ( x for x in list if x[:len(stringToSearchFor)] == stringToSearchFor )
print matches[0]

- Bear

---

(1) 请查看http://docs.python.org/library/stdtypes.html#str.startswith (2) 不要使用list，它会掩盖内置的list()函数。 - John Machin