Autocompleter kata sederhana yang dimaksudkan untuk digunakan di shell
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_strings
memanfaatkan 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
append
tanpa 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 dalamfind_matching
. Ini diperlukanstring +
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
Anda dapat menggunakan
dict.setdefault
daripada mengubah trie secara bersyarat. Ini memiliki keuntungan hanya dengan mencari kunci sekali dibandingkan maksimal 3 kali dengan kode Anda saat ini.Saya bukan penggemar terminologi Anda:
table
membuat saya berpikir array 2d daripada pohon.- Saya lebih suka
node
untukcur_level
. - Apa
c
maksudnya - 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, {})
Dalam
_extract_strings
Aku akan pindahacc = []
setelah definisi fungsi sehingga kode ini tidak di semua tempat.-
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 menggunakanyield
danyield 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)
-
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)
Saya bukan penggemar banyak baris kosong Anda. Mereka tampak acak dan tidak dibutuhkan.
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 menanganitable
".
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)
-
Rencananya sejauh ini akan memiliki panggilan ke
make_lookup_table_from_path
sekali 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 meneleponfind_matching
maka orang yang sederhanastr.startswith
mungkin akan melakukannya sejauh bermil-mil.
Secara keseluruhan
Gaya kode Anda tampak sedikit aneh. Tapi sebaliknya itu bagus. Saya sarankan untuk menggunakan kelas.