쉘에서 사용하기위한 간단한 단어 자동 완성기
문제
저는 간단한 셸을 작성 중이며 부분적으로 단어를 입력 한 다음을 누를 때 bash가 제공하는 멋진 자동 완성 기능을 갖고 싶습니다 tab.
지금은 쉘과 독립적으로 작동 할 수 있지만 시스템에서 명령을 찾을 수있는 기능이 있습니다. 예 :
>>> 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 번 키를 찾는 것이 아니라 한 번만 키를 찾는 이점이 있습니다.나는 당신의 용어를 좋아하지 않습니다.
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에서 전체 단어를 재구성합니다. 이것은 발견 된 모든 문자열에 대해 string +를 필요로하지만 좋지 않습니다.
하나의 값을 얻으면 코드가 \$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은 셸이로드 될 때 한 번 호출 하고 메인 루프 외부의 변수에 테이블을 저장 한 다음 저장된 테이블을 조회하는 것입니다 ( "테이블"을 더 많이 쓸수록 더 많이 m 그게 아마도 올바른 단어가 아니라는 것을 깨달았습니다.)여기에서 Trie를 사용하는 것이 좋은 해결책입니다.
호출 할 때마다 테이블을 재 구축했다면find_matching간단한 사람str.startswith이이 작업을 마일만큼 수행 할 것입니다.
사무용 겉옷
코드 스타일이 약간 이상해 보입니다. 하지만 그렇지 않으면 좋습니다. 나는 무엇보다도 클래스를 사용하는 것이 좋습니다.