Простое автозаполнение слов, предназначенное для использования в оболочке

Aug 19 2020

Проблема

Я пишу простую оболочку, и я хочу иметь приятную функцию автозаполнения, которая есть в 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)]

Ответы

3 Peilonrayz Aug 19 2020 at 03:46
  1. Вы можете использовать, dict.setdefaultа не изменять дерево условно. Это дает преимущество поиска ключа только один раз, а не максимум 3 раза с вашим текущим кодом.

  2. Я не фанат вашей терминологии:

    • 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, {})
  1. В _extract_stringsя бы двигаться acc = []после определения функции , так что код не повсюду.

  2. В рекурсивной функции я использую строки, чтобы отслеживать слово «пока», и передаю сцепленные копии дочерним элементам для использования. Изначально я использовал списки, поэтому я мог просто добавлять, не создавая каждый раз новый объект, но совместное использование изменяемого списка между рекурсиями оказалось проблематичным. Я также возвращаю только окончания из функции поиска, а затем восстанавливаю полное слово в 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)
    
  3. Функция поиска _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)
    
  4. Я не фанат ваших пустых строк. Они кажутся случайными и ненужными.

  5. Это дерево лучше было бы описать в классе. Класс, даже без сахара, упростит понимание вашего кода, поскольку тогда вам не нужно будет думать «что есть _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)
    
  6. Пока что план состоит в том, чтобы вызвать make_lookup_table_from_pathодин раз при загрузке оболочки, сохранить таблицу в переменной за пределами основного цикла, а затем выполнить поиск в сохраненной таблице (чем больше я пишу «таблицу», тем больше я ' я понимаю, что это, наверное, не то слово).

    Использование Trie здесь - хорошее решение.
    Если бы вы перестраивали таблицу каждый раз, когда звонили, find_matchingто простой str.startswith, вероятно, не справился бы с этим на много миль.

В целом

Стиль вашего кода кажется немного странным. Но в остальном это хорошо. Я бы предложил больше всего использовать класс.