Bir kabukta kullanılmak üzere tasarlanmış basit bir kelime otomatik tamamlayıcı
Sorun
Basit bir kabuk yazıyorum ve bash'ın bir kelimeyi kısmen yazıp ardından tuşuna bastığınızda sahip olduğu güzel otomatik tamamlama özelliğine sahip olmak istiyorum tab:

Şu anda bir kabuktan bağımsız olarak çalışabilir, ancak sistemdeki komutları bulmasına izin veren özelliklere sahiptir. Örnekler:
>>> 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']
Nasıl çalışır:
Her kelime iç içe geçmiş bir sözlüğe harf harf yerleştirilir, ardından bir kelimenin sonunu işaretlemek için boş karakterle sonlandırılır:
>>> 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': {}}}}}}}
Eşleşmeleri bulmak üzere bir arama yapmak için, ortak alt sözlük bulunana kadar ağaçta gezdirilir, ardından her sözcük yinelemeli olarak yeniden oluşturulur.
Odaklanma:
Dürüst olmak gerekirse, okulda kodun yanı sıra başka şeylere odaklanıyordum, bu yüzden biraz paslandım. İdeal olmayan birkaç teknik kullanıyorum, bu nedenle herhangi bir öneriye açığız:
Arama işlevi
_extract_strings
özyinelemeden yararlanır, çünkü bu yinelemeli olarak çözülmesi zor bir sorun gibi göründü. Bariz bir alternatif yolu kaçırıyorsam, oradaki tüm ipuçlarını takdir ederim.Özyinelemeli işlevde, "şimdiye kadar" sözcüğünü takip etmek için dizeleri kullanıyorum ve birleştirilmiş kopyaları kullanmaları için çocuklara iletiyorum. Başlangıçta listeleri kullanıyordum, böylece
append
her seferinde yeni bir nesne oluşturmadan yapabiliyordum , ancak değiştirilebilir listeyi yinelemeler arasında paylaşmanın sorunlu olduğu ortaya çıktı. Ayrıca arama işlevinden yalnızca sonları döndürüyorum ve ardından tam kelimeyi yeniden oluşturuyorumfind_matching
. Bustring +
, bulunan her ip için gerekli olsa da, bu harika değil.
Bu işlevler aslında şaşırtıcı derecede hızlı işliyor. Tabloyu sürekli olarak yeniden yapılandırmak zorunda kalmamak için bir önbelleğe alma, başlangıçta diskten yükleme sistemi kuracaktım, ancak o kadar hızlı ki buna değmiyor gibi görünüyor. Sonuç olarak, yukarıdaki her iki endişem de muhtemelen "erken optimizasyonlar" kapsamına giriyor, ancak yine de onlar hakkında öneriler veya stilden diğer en iyi uygulamalara kadar her şeyi istiyorum.
Kod:
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)]
Yanıtlar
dict.setdefault
Trieyi koşullu olarak değiştirmek yerine kullanabilirsiniz . Bu, mevcut kodunuzla maksimum 3 kez değil, anahtarı yalnızca bir kez arama avantajına sahiptir.Terminolojinizin hayranı değilim:
table
bir ağaçtan çok 2d dizisini düşünmemi sağlıyor.- Ben tercih ediyorum
node
içincur_level
. - Ne anlama
c
geliyor? - Neden onu aramıyorsun
_add_value
?
def _add_value(root: Table, string: str) -> None:
node = root
for char in string + _TERMINATOR:
node = node.setdefault(char, {})
Gelen
_extract_strings
Hareket ediyorumacc = []
kodu biryere değil böylece fonksiyon tanımından sonra.-
Özyinelemeli işlevde, "şimdiye kadar" sözcüğünü takip etmek için dizeleri kullanıyorum ve birleştirilmiş kopyaları kullanmaları için çocuklara iletiyorum. Başlangıçta listeleri kullanıyordum, böylece her seferinde yeni bir nesne oluşturmadan ekleyebiliyordum, ancak değiştirilebilir listeyi yinelemeler arasında paylaşmanın sorunlu olduğu ortaya çıktı. Ayrıca arama işlevinden yalnızca sonları döndürüyorum ve ardından bul_matching'de tam sözcüğü yeniden oluşturuyorum. Bu, bulunan her dizge için string + gerektirir, bu harika değildir.
Bir değer alırken kodunuz çalışır \$O(l^2)\$nerede \$l\$bir dizenin maksimum uzunluğudur. Bunun nedeni, her
cur_path + char
birinin bir \$O(l)\$operasyon ve sen yap \$l\$ zamanlar.Mevcut algoritma ile bir 'eh, vidalayın' yaklaşımını izlemeyi öneririm ve yeterince hızlı olduğu için mutlu olurum. Yığınla manuel olarak uğraşmak hiç eğlenceli değil .
Şahsen ben hayran değilim
acc.append
, onun yerineyield
ve kullanırdımyield 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 arama işlevi özyinelemeden yararlanır, çünkü bu yinelemeli olarak çözülmesi zor bir sorun gibi görünüyordu. Bariz bir alternatif yolu kaçırıyorsam, oradaki tüm ipuçlarını takdir ederim.
Yığını manuel olarak oluşturmak mümkün olsa da, bu çok basit değil. Trie'nin Python'un 1000 yığın sınırını aşma ihtimalinin düşük olduğu göz önüne alındığında, muhtemelen bunu göz ardı edebilirsiniz.
Daha önce yığını oluştururken değindiğimiz gibi, sonucu aynı anda kolayca oluşturabilir ve \$O(l^2)\$performans sadece \$O(l)\$.Ancak görebilmeniz gerektiği gibi bu bir iğrençliktir. Kimsenin bunu sürdürmek istediğini sanmıyorum.
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)
Boş repliklerinizin pek hayranı değilim. Rastgele görünüyorlar ve gerekli değiller.
Trie, bir sınıfta daha iyi tanımlanabilir. Şekersiz bir sınıf bile kodunuzun anlaşılmasını kolaylaştırır, çünkü o zaman "nedir
_add_string
" ve "nasıl idare ederim " diye düşünmek zorunda kalmazsınıztable
.
Yıllar boyunca birkaç deneme yazdım , bunu bir sınıf yapmaya karar verirseniz yardımcı olabilirler.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)
-
Şimdiye kadarki plan
make_lookup_table_from_path
, kabuk yüklendiğinde bir kez çağrı yapmak , tabloyu ana döngünün dışındaki bir değişkene kaydetmek, ardından kaydedilen tablo üzerinde aramalar yapmak olacak ("tablo" ne kadar çok yazarsam, o kadar çok I ' Bunun muhtemelen doğru kelime olmadığını anlıyorum).Burada bir Trie kullanmak iyi bir çözümdür.
Her aradığınızda masayı yeniden inşa ediyor olsaydınız, muhtemelenfind_matching
bir basitstr.startswith
bunu kilometrelerce gerçekleştirirdi.
Genel
Kodunuzun tarzı biraz tuhaf görünüyor. Ama aksi halde iyidir. En çok bir sınıf kullanmanızı öneririm.