シェルで使用するための簡単な単語のオートコンプリート
問題
私は単純なシェルを書いています。単語を部分的に入力してからtab：を押したときにbashが持つ優れたオートコンプリート機能が必要です。
現在、シェルとは独立して動作できますが、システム上のコマンドを検索できる機能があります。例：
>>> 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)]
回答
dict.setdefault条件付きでトライを変更するのではなく、使用できます。これには、現在のコードで最大3回ではなく、キーを1回だけ検索するという利点があります。私はあなたの用語のファンではありません：
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, {})
では、関数定義の後に
_extract_strings移動acc = []して、コードがいたるところにないようにします。-
再帰関数では、文字列を使用して「これまで」という単語を追跡し、連結されたコピーを子に渡して使用できるようにしています。私はもともとリストを使用していたので、毎回新しいオブジェクトを作成せずに追加することができましたが、再帰間で可変リストを共有することには問題があることがわかりました。また、ルックアップ関数からエンディングのみを返し、find_matchingで単語全体を再構築します。ただし、これには、見つかったすべての文字列に対して文字列+が必要ですが、これは素晴らしいことではありません。
1つの値を取得すると、コードは\で実行されます$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) -
ルックアップ関数_extract_stringsは再帰を利用します。これは、これを繰り返し解決するのは面倒な問題のように思われたためです。明らかな代替方法がない場合は、そこにヒントをいただければ幸いです。
スタックを手動で構築することは可能ですが、それは非常に簡単ではありません。トライが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) 私はあなたの空の行の多くのファンではありません。それらはランダムに見え、必要ありません。
トライはクラスでよりよく説明されます。クラスは、砂糖がなくても、コードを理解しやすくします。そうすれば、「何であるか
_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)-
これまでの計画で
make_lookup_table_from_pathは、シェルがロードされたときに1回呼び出し、テーブルをメインループの外側の変数に保存してから、保存されたテーブルをルックアップします（「テーブル」と書くほど、「 mそれはおそらく正しい言葉ではないことに気づきます）。ここでTrieを使用するのは良い解決策です。
呼び出すたびにテーブルを再構築する場合find_matching、単純なものstr.startswithはおそらくこれを何マイルも実行します。
全体
あなたのコードのスタイルは少し奇妙に思えます。しかし、そうでなければそれは良いことです。何よりもクラスを使用することをお勧めします。