самый быстрый способ сравнить строки в Python

Question

Я пишу скрипт на Python, который позволит пользователю вводить строку, которая будет командой, которая инструктирует скрипт для выполнения определенного действия. Ради аргумента я скажу, что мой список команд:

lock
read
write
request
log

Теперь я хочу, чтобы пользователь мог ввести слово «журнал», и оно выполнит определенное действие, которое очень просто. Тем не менее, я хотел бы сопоставить частичные слова. Так, например, если пользователь вводит «lo», он должен совпадать с «блокировкой», так как он находится выше в списке. Я пытался использовать strncmp из libc, используя ctypes, чтобы выполнить эту задачу, но мне еще не хватало голов или хвостов.

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]

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» и «читают», когда думают, что получат «запрос». Сведение к минимуму нажатий клавиш пользователем с риском ошибок - это так 1960-е годы, что это не смешно. Что они используют? ASR33 телетайпы? По крайней мере, вы можете настаивать на уникальном совпадении - «rea» для чтения и «req» для запроса.

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,
}

Answer 4

Я предлагаю вам взглянуть на использование библиотеки Python readline, а не изобретать велосипед. Чтобы завершить слово, пользователю нужно будет нажать «Tab», но вы можете настроить «readline up» так, чтобы вкладка соответствовала, насколько это возможно, или циклически проходила все слова, начиная с текущей заглушки.

Это довольно приличное введение в readline в python http://www.doughellmann.com/PyMOTW/readline/index.html

Answer 5

вы можете использовать старты с

например

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

Answer 6

jaro_winkler() в Python-Levenshtein может быть то, что вы ищете.

Answer 7

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

Итак, по моему мнению, вы спрашиваете, как оптимизировать операцию, которая не требует измеримого времени или процессора.Я использовал 10 000 команд, и тестовая строка совпадает с каждой из них, чтобы показать, что даже в экстремальных обстоятельствах у вас все еще могут быть сотни пользователей, которые никогда не увидят никакой задержки.

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

Answer 9

Это адаптировано из реализации Trie J.Tauber в Python , которую вы можете сравнить и / или адаптировать к любым дополнительным функциям, которые вам нужны. Смотрите также запись Википедии о попытках .

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')
>>>

Answer 10

Замените на вашу любимую функцию сравнения строк. Довольно быстро и точно.

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