如何对文本文件执行二进制搜索以在 python 中搜索关键字? [英] How do I perform binary search on a text file to search a keyword in python?

问题描述

文本文件包含两列 - 索引号(5 个空格)和字符(30 个空格).它按字典顺序排列.我想执行二分搜索来搜索关键字.

The text file contains two columns- index number(5 spaces) and characters(30 spaces). It is arranged in lexicographic order. I want to perform binary search to search for the keyword.

推荐答案

这是使用 Python 内置的 bisect 模块的有趣方法.

Here's an interesting way to do it with Python's built-in bisect module.

import bisect
import os


class Query(object):

    def __init__(self, query, index=5):
        self.query = query
        self.index = index

    def __lt__(self, comparable):
        return self.query < comparable[self.index:]


class FileSearcher(object):

    def __init__(self, file_pointer, record_size=35):
        self.file_pointer = file_pointer
        self.file_pointer.seek(0, os.SEEK_END)
        self.record_size = record_size + len(os.linesep)
        self.num_bytes = self.file_pointer.tell()
        self.file_size = (self.num_bytes // self.record_size)

    def __len__(self):
        return self.file_size

    def __getitem__(self, item):
        self.file_pointer.seek(item * self.record_size)
        return self.file_pointer.read(self.record_size)


if __name__ == '__main__':
    with open('data.dat') as file_to_search:
        query = raw_input('Query: ')
        wrapped_query = Query(query)

        searchable_file = FileSearcher(file_to_search)
        print "Located @ line: ", bisect.bisect(searchable_file, wrapped_query)

这篇关于如何对文本文件执行二进制搜索以在 python 中搜索关键字?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！