ตัวเติมคำอัตโนมัติแบบง่ายๆสำหรับใช้ในเชลล์

Aug 19 2020

ปัญหา

ฉันกำลังเขียนเชลล์ธรรมดาและฉันต้องการมีคุณสมบัติเติมข้อความอัตโนมัติที่ดีที่ 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)]

คำตอบ

3 Peilonrayz Aug 19 2020 at 03:46
  1. คุณสามารถใช้dict.setdefaultแทนการปรับเปลี่ยน Trie ตามเงื่อนไข สิ่งนี้มีประโยชน์ในการค้นหาคีย์เพียงครั้งเดียวเมื่อเทียบกับสูงสุด 3 ครั้งด้วยรหัสปัจจุบันของคุณ

  2. ฉันไม่ใช่แฟนของคำศัพท์ของคุณ:

    • table ทำให้ฉันคิดว่าอาร์เรย์ 2d มากกว่าต้นไม้
    • ฉันไม่ต้องการที่จะnodecur_level
    • อะไรcหมายถึง?
    • ทำไมไม่เรียกมัน_add_value?
def _add_value(root: Table, string: str) -> None:
    node = root
    for char in string + _TERMINATOR:
        node = node.setdefault(char, {})
  1. ใน_extract_stringsฉันจะย้ายacc = []ตามนิยามฟังก์ชันดังนั้นรหัสจึงไม่อยู่ในตำแหน่งทั้งหมด

  2. ในฟังก์ชันเรียกซ้ำฉันใช้สตริงเพื่อติดตามคำว่า "จนถึงตอนนี้" และส่งสำเนาที่ต่อกันไปให้เด็ก ๆ เพื่อให้พวกเขาใช้ เดิมทีฉันใช้รายการดังนั้นฉันจึงสามารถต่อท้ายได้โดยไม่ต้องสร้างวัตถุใหม่ทุกครั้ง แต่การแบ่งปันรายการที่ไม่แน่นอนระหว่างการเรียกซ้ำได้รับการพิสูจน์แล้วว่าเป็นปัญหา ฉันยังส่งคืนเฉพาะตอนจบจากฟังก์ชันการค้นหาจากนั้นสร้างคำเต็มใหม่ใน find_matching สิ่งนี้จำเป็นต้องใช้สตริง + สำหรับทุกสตริงที่พบซึ่งไม่ดีนัก

    เมื่อได้ค่าหนึ่งรหัสของคุณจะทำงานใน\$O(l^2)\$ที่ไหน\$l\$คือความยาวสูงสุดของสตริง เนื่องจากแต่ละรายการcur_path + charเป็น\$O(l)\$การดำเนินการและคุณทำมัน\$l\$ ครั้ง.

    ด้วยอัลกอริทึมปัจจุบันฉันขอแนะนำให้ทำตามวิธีการ 'eh, screw it' และขอให้มีความสุขที่เร็วพอ ในฐานะที่ตนเองจัดการกับสแต็คเป็นไม่สนุก

    ส่วนตัวผมไม่ได้เป็นแฟนของacc.appendผมใช้แทนและyieldyield 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. ฟังก์ชันการค้นหา _extract_strings ใช้ประโยชน์จากการเรียกซ้ำเพราะดูเหมือนว่าจะเป็นปัญหาที่เจ็บปวดในการแก้ไขซ้ำ ๆ หากฉันพลาดวิธีอื่นที่ชัดเจนฉันจะขอบคุณเคล็ดลับที่นั่น

    ในขณะที่การสร้างสแตกด้วยตนเองนั้นเป็นไปได้ แต่ก็ไม่ง่ายเลย เนื่องจาก trie ไม่น่าจะเกินขีด จำกัด 1,000 stack ของ Python คุณอาจเพิกเฉยต่อสิ่งนี้ได้
    อย่างที่เคยสัมผัสมาก่อนเมื่อสร้างสแต็กเราสามารถสร้างผลลัพธ์ในเวลาเดียวกันได้อย่างง่ายดายโดยเปลี่ยน\$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)
    
  4. ฉันไม่ได้คลั่งไคล้สายว่างของคุณมากมาย ดูเหมือนสุ่มและไม่จำเป็น

  5. ทั้งสามคนจะอธิบายได้ดีกว่าในชั้นเรียน ชั้นเรียนแม้จะไม่มีน้ำตาล แต่ก็ทำให้เข้าใจรหัสของคุณได้ง่ายขึ้นเพราะคุณไม่ต้องคิดว่า "คืออะไร_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)
    
  6. แผนจนถึงตอนนี้จะมีการเรียกmake_lookup_table_from_pathหนึ่งครั้งเมื่อโหลดเชลล์บันทึกตารางในตัวแปรนอกลูปหลักจากนั้นทำการค้นหาบนตารางที่บันทึกไว้ (ยิ่งฉันเขียน "ตาราง" มากเท่าไหร่ฉันก็ยิ่งมากขึ้นเท่านั้น m ตระหนักดีว่านั่นอาจไม่ใช่คำที่ถูกต้อง)

    การใช้ Trie นี่เป็นทางออกที่ดี
    หากคุณกำลังสร้างตารางใหม่ทุกครั้งที่คุณโทรหาfind_matchingวิธีง่ายๆstr.startswithก็น่าจะทำได้ตามระยะทางหลายไมล์

โดยรวม

รูปแบบรหัสของคุณดูแปลก ๆ เล็กน้อย แต่อย่างอื่นก็ดีนะ ฉันขอแนะนำให้ใช้ชั้นเรียนเป็นส่วนใหญ่