Um autocompletador de palavras simples para uso em um shell

Question

Problema

Estou escrevendo um shell simples e quero ter o bom recurso de preenchimento automático que o bash oferece quando você digita parcialmente uma palavra e pressiona tab:

No momento, ele pode funcionar independentemente de um shell, mas possui recursos que permitem localizar comandos no sistema. Exemplos:

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

Como funciona:

Cada palavra é colocada em um dicionário aninhado, letra por letra, e terminada por um caractere nulo para marcar o final de uma palavra:

>>> 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': {}}}}}}}

Para fazer uma pesquisa para encontrar correspondências, a árvore é percorrida até que o subdicionário comum seja encontrado, então cada palavra é recursivamente reconstruída.

Foco:

Honestamente, estive na escola focando em outras coisas além de código, então fiquei um pouco enferrujado. Estou usando algumas técnicas menos do que ideais, portanto, quaisquer recomendações são bem-vindas:

• A função de pesquisa _extract_stringsfaz uso da recursão, porque parecia um problema doloroso de resolver iterativamente. Se estou perdendo uma alternativa óbvia, gostaria de receber dicas.

• Na função recursiva, estou usando strings para controlar a palavra "até agora" e passando cópias concatenadas para os filhos usarem. Eu estava originalmente usando listas para que pudesse apenas appendsem criar um novo objeto a cada vez, mas compartilhar a lista mutável entre as recorrências provou ser problemático. Também estou retornando apenas terminações da função de pesquisa e, em seguida, reconstruindo a palavra completa em find_matching. No string +entanto, isso é necessário para cada string encontrada, o que não é ótimo.

Na verdade, essas funções têm um desempenho surpreendentemente rápido. Eu estava planejando configurar um sistema de cache e carregamento do disco na inicialização para evitar a necessidade de reconstruir a tabela constantemente, mas é tão rápido que não parece valer a pena. Como resultado, minhas duas preocupações acima provavelmente se enquadram em "otimizações prematuras", mas ainda gostaria de sugestões sobre elas ou qualquer outra coisa, de estilo a outras práticas recomendadas.

Código:

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

Answer 1

1. Você pode usar em dict.setdefaultvez de modificar condicionalmente o teste. Isso tem a vantagem de procurar a chave apenas uma vez, em vez de no máximo 3 vezes com o código atual.

2. Não sou fã da sua terminologia:

   • table me faz pensar em 2d array em vez de uma árvore.
   • Eu prefiro nodea cur_level.
   • O que isso csignifica?
   • Por que não ligar _add_value?

def _add_value(root: Table, string: str) -> None:
    node = root
    for char in string + _TERMINATOR:
        node = node.setdefault(char, {})

1. Em seguida, _extract_stringsmoveria acc = []após a definição da função para que o código não esteja em todo o lugar.

2. Na função recursiva, estou usando strings para controlar a palavra "até agora" e passando cópias concatenadas para os filhos usarem. Eu estava originalmente usando listas para que pudesse apenas anexar sem criar um novo objeto a cada vez, mas compartilhar a lista mutável entre as recorrências provou ser problemático. Também estou retornando apenas terminações da função de pesquisa e, em seguida, reconstruindo a palavra completa em find_matching. Isso requer string + para cada string encontrada, o que não é ótimo.

   Ao obter um valor, seu código é executado em \$O(l^2)\$onde \$l\$é o comprimento máximo de uma string. Isso ocorre porque cada cur_path + charum é um \$O(l)\$operação e você faz isso \$l\$ vezes.

   Com o algoritmo atual, sugiro seguir uma abordagem do tipo 'eh, dane-se' e ficar feliz por ser suficientemente rápido. Como lidar manualmente com a pilha não é divertido .

   Pessoalmente, não sou fã de acc.append, em vez disso, usaria yielde 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. A função de pesquisa _extract_strings faz uso de recursão, porque parecia um problema difícil de resolver iterativamente. Se estou perdendo uma alternativa óbvia, gostaria de receber dicas.

   Embora seja possível construir manualmente a pilha, não é muito simples. Dado que é improvável que o trie exceda o limite de 1000 pilhas do Python, você provavelmente pode ignorar isso.
   Conforme mencionado antes ao construir a pilha, poderíamos facilmente construir o resultado ao mesmo tempo, mudando o \$O(l^2)\$desempenho para apenas \$O(l)\$.

   No entanto, como você deve ser capaz de ver, isso é uma abominação. Não acho que alguém queira manter isso.

   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. Não sou fã de muitas das suas falas vazias. Eles parecem aleatórios e desnecessários.

5. O trie seria melhor descrito em uma aula. Uma classe, mesmo sem açúcar, tornaria seu código mais fácil de entender, pois assim você não teria que pensar "o que é _add_string" e "como faço para manusear table".
   Eu escrevi algumas tentativas ao longo dos anos , elas podem ajudar se você decidir fazer disso uma aula.

   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. O plano até agora será fazer uma chamada para make_lookup_table_from_pathuma vez quando o shell for carregado, salvar a tabela em uma variável fora do loop principal e fazer pesquisas na tabela salva (quanto mais eu escrevo "tabela", mais eu ' estou percebendo que essa provavelmente não é a palavra certa).

   Usar um Trie aqui é uma boa solução.
   Se você estivesse reconstruindo a mesa cada vez que ligar find_matching, um simples str.startswithprovavelmente faria isso por quilômetros.

No geral

O estilo do seu código parece um pouco estranho. Mas por outro lado é bom. Eu sugiro usar uma classe acima de tudo.