Простое автозаполнение слов, предназначенное для использования в оболочке
Проблема
Я пишу простую оболочку, и я хочу иметь приятную функцию автозаполнения, которая есть в bash, когда вы частично вводите слово и нажимаете tab:

Сейчас он может работать независимо от оболочки, но у него есть функции, которые позволяют ему находить команды в системе. Примеры:
>>> table = make_lookup_table_from(["hell", "water", "help", "air", "hello", "fire", "earth"])
>>> find_matching(table, "hel")
['hell', 'hello', 'help']
>>> table = make_lookup_table_from_path()
>>> find_matching(table, "gcc-")
['gcc-ar', 'gcc-ar-8', 'gcc-ar-9', 'gcc-nm', 'gcc-nm-8', 'gcc-nm-9', 'gcc-ranlib', 'gcc-ranlib-8', 'gcc-ranlib-9', 'gcc-8', 'gcc-9']
>>> find_matching(table, "pyth")
['python3.8', 'python3.8-config', 'python3', 'python3-qr', 'python3-futurize', 'python3-pasteurize', 'python3-tor-prompt', 'python3-config', 'python3-wsdump', 'python', 'python-argcomplete-check-easy-install-script', 'python-argcomplete-check-easy-install-script3', 'python-argcomplete-tcsh', 'python-argcomplete-tcsh3', 'python-config', 'python-faraday', 'python2-config', 'python2-futurize', 'python2-pasteurize', 'python2-pbr', 'python2', 'python2.7-config', 'python2.7']
Как это устроено:
Каждое слово по буквам помещается во вложенный словарь, а затем заканчивается нулевым символом, обозначающим конец слова:
>>> make_lookup_table_from(["hell", "water", "help", "air", "hello", "fire", "earth"])
{'h': {'e': {'l': {'l': {'\x00': {}, 'o': {'\x00': {}}}, 'p': {'\x00': {}}}}}, 'w': {'a': {'t': {'e': {'r': {'\x00': {}}}}}}, 'a': {'i': {'r': {'\x00': {}}}}, 'f': {'i': {'r': {'e': {'\x00': {}}}}}, 'e': {'a': {'r': {'t': {'h': {'\x00': {}}}}}}}
Чтобы выполнить поиск для поиска совпадений, дерево просматривается до тех пор, пока не будет найден общий под-словарь, затем каждое слово рекурсивно реконструируется.
Фокус:
Честно говоря, я учился в школе, уделяя внимание другим вещам, помимо кода, так что я немного подзабыл. Я использую пару неидеальных техник, поэтому любые рекомендации приветствуются:
Функция поиска
_extract_strings
использует рекурсию, потому что это казалось болезненной проблемой, которую нужно решать итеративно. Если мне не хватает очевидного альтернативного способа, я был бы признателен за любые советы.В рекурсивной функции я использую строки, чтобы отслеживать слово «пока», и передаю сцепленные копии дочерним элементам для использования. Изначально я использовал списки, поэтому я мог просто
append
каждый раз не создавать новый объект, но совместное использование изменяемого списка между рекурсиями оказалось проблематичным. Я также возвращаю только окончания из функции поиска, а затем восстанавливаю полное словоfind_matching
. Однако это требуетstring +
каждой найденной строки, что не очень хорошо.
Эти функции действительно работают на удивление быстро. Я собирался настроить систему кеширования, загрузку с диска при запуске, чтобы избежать необходимости постоянно восстанавливать таблицу, но это так быстро, что это не стоит того. В результате обе мои проблемы, упомянутые выше, вероятно, подпадают под «преждевременную оптимизацию», но мне все равно нужны предложения по ним или что-то еще, от стиля до других передовых методов.
Код:
import os
from typing import List, Iterable, Dict
_TERMINATOR = "\0"
_PATH_KEY = "PATH"
_PATH_DELIM = ":"
Table = Dict[str, "Table"]
def _get_paths() -> List[str]:
return os.environ[_PATH_KEY].split(_PATH_DELIM)
def _find_filenames_in(paths: List[str]) -> Iterable[str]:
return (fname
for path in paths
for _, _, fnames in os.walk(path)
for fname in fnames)
def _add_string(table: Table, string: str) -> None:
term_string = string + _TERMINATOR
cur_level = table
for c in term_string:
if c not in cur_level:
cur_level[c] = {}
cur_level = cur_level[c]
def make_lookup_table_from(strings: Iterable[str]) -> Table:
table = {}
for string in strings:
_add_string(table, string)
return table
def make_lookup_table_from_path() -> Table:
paths = _get_paths()
fnames = _find_filenames_in(paths)
return make_lookup_table_from(fnames)
def _extract_strings(table: Table) -> Iterable[str]:
acc = []
def rec(cur_path: str, cur_level: Table):
for char, child in cur_level.items():
if char == _TERMINATOR:
acc.append(cur_path)
else:
rec(cur_path + char, child)
rec("", table)
return acc
def find_matching(table: Table, string: str) -> Iterable[str]:
cur_level = table
for c in string:
try:
cur_level = cur_level[c]
except KeyError:
return []
return [string + end for end in _extract_strings(cur_level)]
Ответы
Вы можете использовать,
dict.setdefault
а не изменять дерево условно. Это дает преимущество поиска ключа только один раз, а не максимум 3 раза с вашим текущим кодом.Я не фанат вашей терминологии:
table
заставляет меня думать, что 2d массив, а не дерево.- Я предпочел бы ,
node
чтобыcur_level
. - Что
c
значит? - Почему бы просто не назвать это
_add_value
?
def _add_value(root: Table, string: str) -> None:
node = root
for char in string + _TERMINATOR:
node = node.setdefault(char, {})
В
_extract_strings
я бы двигатьсяacc = []
после определения функции , так что код не повсюду.-
В рекурсивной функции я использую строки, чтобы отслеживать слово «пока», и передаю сцепленные копии дочерним элементам для использования. Изначально я использовал списки, поэтому я мог просто добавлять, не создавая каждый раз новый объект, но совместное использование изменяемого списка между рекурсиями оказалось проблематичным. Я также возвращаю только окончания из функции поиска, а затем восстанавливаю полное слово в find_matching. Однако для каждой найденной строки требуется строка +, что не очень хорошо.
При получении одного значения ваш код запускается в \$O(l^2)\$где \$l\$- максимальная длина строки. Это потому, что каждый
cur_path + char
является \$O(l)\$операция и вы делаете это \$l\$ раз.С текущим алгоритмом я бы посоветовал следовать подходу «ага, к черту» и быть счастливым, что он достаточно быстрый. Поскольку вручную работать со стеком неинтересно .
Лично я не фанат
acc.append
, вместо этого я бы использовалyield
иyield from
.def _extract_strings(table: Table) -> Iterator[str]: def rec(cur_path: str, cur_level: Table): for char, child in cur_level.items(): if char == _TERMINATOR: yield cur_path else: yield from rec(cur_path + char, child) return rec("", table)
-
Функция поиска _extract_strings использует рекурсию, потому что это казалось болезненной проблемой для итеративного решения. Если мне не хватает очевидного альтернативного способа, я был бы признателен за любые советы.
Хотя создание стека вручную возможно, это не очень просто. Учитывая, что trie вряд ли превысит ограничение стека Python в 1000, вы, вероятно, можете игнорировать это.
Как уже упоминалось ранее при построении стека, мы могли бы легко построить результат одновременно, изменив \$O(l^2)\$производительность просто \$O(l)\$.Однако, как вы должны видеть, это мерзость. Не думаю, что кто-то хочет это поддерживать.
def _extract_strings(table: Table) -> Iterator[str]: stack = [iter(table.items())] stack_value = [] while stack: try: key, value = next(stack[-1]) except StopIteration: stack.pop() if stack_value: stack_value.pop() continue if key == '\0': yield ''.join(stack_value) stack_value.append(key) stack.append(iter(value.items())) table = { 'b': {'a': {'r': {'\0': {}}, 'z': {'\0': {}}}}, 'f': {'o': {'o': {'\0': {}}}}, } for path in _extract_strings(table): print(path)
Я не фанат ваших пустых строк. Они кажутся случайными и ненужными.
Это дерево лучше было бы описать в классе. Класс, даже без сахара, упростит понимание вашего кода, поскольку тогда вам не нужно будет думать «что есть
_add_string
» и «как мне поступитьtable
».
За эти годы я написал несколько попыток , они могут помочь, если вы решите сделать это классным.trie = Trie() trie.add('foo') trie.add('bar') trie.add('baz') # Could use the following to add instead if you need a value # trie['foo'] = ??? key = 'ba' for value in trie[key]: print(key + value)
-
Пока что план состоит в том, чтобы вызвать
make_lookup_table_from_path
один раз при загрузке оболочки, сохранить таблицу в переменной за пределами основного цикла, а затем выполнить поиск в сохраненной таблице (чем больше я пишу «таблицу», тем больше я ' я понимаю, что это, наверное, не то слово).Использование Trie здесь - хорошее решение.
Если бы вы перестраивали таблицу каждый раз, когда звонили,find_matching
то простойstr.startswith
, вероятно, не справился бы с этим на много миль.
В целом
Стиль вашего кода кажется немного странным. Но в остальном это хорошо. Я бы предложил больше всего использовать класс.