Autocompleter kata sederhana yang dimaksudkan untuk digunakan di shell

Aug 19 2020

Masalah

Saya sedang menulis shell sederhana, dan saya ingin memiliki fitur pelengkapan otomatis yang bagus yang dimiliki bash saat Anda mengetik sebagian kata lalu tekan tab:

Sekarang ini dapat bekerja secara independen dari shell, tetapi memiliki fitur yang memungkinkannya menemukan perintah pada sistem. Contoh:

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

Bagaimana itu bekerja:

Setiap kata dimasukkan ke dalam kamus bersarang huruf demi huruf, lalu diakhiri dengan karakter nol untuk menandai akhir kata:

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

Untuk melakukan pencarian untuk menemukan kecocokan, pohon dijalankan sampai sub-kamus umum ditemukan, kemudian setiap kata direkonstruksi secara rekursif.

Fokus:

Sejujurnya, saya pernah di sekolah fokus pada hal-hal lain selain kode, jadi saya menjadi sedikit berkarat. Saya menggunakan beberapa teknik yang kurang ideal, jadi semua rekomendasi diterima:

  • Fungsi pencarian _extract_stringsmemanfaatkan rekursi, karena ini tampak seperti masalah yang menyakitkan untuk diselesaikan secara berulang. Jika saya melewatkan cara alternatif yang jelas, saya akan menghargai tip apa pun di sana.

  • Dalam fungsi rekursif, saya menggunakan string untuk melacak kata "sejauh ini", dan meneruskan salinan yang digabungkan ke anak-anak untuk digunakan. Saya awalnya menggunakan daftar jadi saya bisa saja appendtanpa membuat objek baru setiap kali, tetapi berbagi daftar yang bisa berubah di antara pengulangan terbukti bermasalah. Saya juga mengembalikan hanya akhiran dari fungsi pencarian kemudian merekonstruksi kata lengkapnya dalam find_matching. Ini diperlukan string +untuk setiap string yang ditemukan, yang tidak bagus.

Fungsi ini sebenarnya bekerja sangat cepat. Saya akan menyiapkan sistem caching, memuat-dari-disk-on-start untuk menghindari kebutuhan untuk merekonstruksi tabel terus-menerus, tetapi itu sangat cepat sehingga sepertinya tidak sepadan. Akibatnya, kedua kekhawatiran saya di atas mungkin termasuk dalam "pengoptimalan prematur", tetapi saya masih menginginkan saran tentang hal itu atau apa pun, dari gaya hingga praktik terbaik lainnya.

Kode:

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

Jawaban

3 Peilonrayz Aug 19 2020 at 03:46
  1. Anda dapat menggunakan dict.setdefaultdaripada mengubah trie secara bersyarat. Ini memiliki keuntungan hanya dengan mencari kunci sekali dibandingkan maksimal 3 kali dengan kode Anda saat ini.

  2. Saya bukan penggemar terminologi Anda:

    • table membuat saya berpikir array 2d daripada pohon.
    • Saya lebih suka nodeuntuk cur_level.
    • Apa cmaksudnya
    • Mengapa tidak menyebutnya saja _add_value?
def _add_value(root: Table, string: str) -> None:
    node = root
    for char in string + _TERMINATOR:
        node = node.setdefault(char, {})
  1. Dalam _extract_stringsAku akan pindah acc = []setelah definisi fungsi sehingga kode ini tidak di semua tempat.

  2. Dalam fungsi rekursif, saya menggunakan string untuk melacak kata "sejauh ini", dan meneruskan salinan yang digabungkan ke anak-anak untuk digunakan. Saya awalnya menggunakan daftar sehingga saya bisa menambahkan tanpa membuat objek baru setiap kali, tetapi berbagi daftar yang bisa berubah di antara pengulangan terbukti bermasalah. Saya juga hanya mengembalikan akhiran dari fungsi pencarian kemudian merekonstruksi kata lengkapnya di find_matching. Ini memerlukan string + untuk setiap string yang ditemukan, yang tidak bagus.

    Saat mendapatkan satu nilai, kode Anda dijalankan \$O(l^2)\$dimana \$l\$adalah panjang maksimal sebuah string. Ini karena masing cur_path + char- masing adalah \$O(l)\$operasi dan Anda melakukannya \$l\$ waktu.

    Dengan algoritme saat ini, saya sarankan mengikuti pendekatan 'eh, sekrup itu' dan cukup senang bahwa itu cukup cepat. Karena menangani tumpukan secara manual tidaklah menyenangkan .

    Secara pribadi saya bukan penggemar acc.append, saya malah menggunakan yielddan 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. Fungsi pencarian _extract_strings menggunakan rekursi, karena ini tampak seperti masalah yang menyakitkan untuk dipecahkan secara berulang. Jika saya melewatkan cara alternatif yang jelas, saya akan menghargai tip apa pun di sana.

    Meskipun membangun tumpukan secara manual dimungkinkan, itu tidak super sederhana. Mengingat bahwa trie tidak mungkin melebihi batas 1000 stack Python, Anda mungkin dapat mengabaikan ini.
    Seperti yang telah disinggung sebelumnya saat membangun tumpukan, kita dapat dengan mudah membuat hasilnya pada saat yang sama, mengubah \$O(l^2)\$kinerja menjadi hanya \$O(l)\$.

    Namun karena Anda harus dapat melihat ini adalah kekejian. Saya tidak berpikir ada yang mau mempertahankan ini.

    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. Saya bukan penggemar banyak baris kosong Anda. Mereka tampak acak dan tidak dibutuhkan.

  5. Trie akan lebih baik dijelaskan di kelas. Kelas, bahkan tanpa gula, akan membuat kode Anda lebih mudah dipahami, karena Anda tidak perlu memikirkan "apa itu _add_string" dan "bagaimana cara saya menangani table".
    Saya telah menulis beberapa percobaan selama bertahun-tahun , mereka mungkin membantu jika Anda memutuskan untuk menjadikannya sebuah kelas.

    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. Rencananya sejauh ini akan memiliki panggilan ke make_lookup_table_from_pathsekali ketika shell dimuat, simpan tabel dalam variabel di luar loop utama, kemudian lakukan pencarian pada tabel yang disimpan (semakin saya menulis "tabel", semakin banyak saya ' Saya menyadari bahwa itu mungkin bukan kata yang tepat).

    Menggunakan Trie di sini adalah solusi yang bagus.
    Jika Anda membangun kembali tabel setiap kali Anda menelepon find_matchingmaka orang yang sederhana str.startswithmungkin akan melakukannya sejauh bermil-mil.

Secara keseluruhan

Gaya kode Anda tampak sedikit aneh. Tapi sebaliknya itu bagus. Saya sarankan untuk menggunakan kelas.