在Python中对字符串前缀执行二进制搜索
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了在Python中对字符串前缀执行二进制搜索,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2388字,纯文字阅读大概需要4分钟。
内容图文
![在Python中对字符串前缀执行二进制搜索](/upload/InfoBanner/zyjiaocheng/761/1cbf7d043566469e818a4c846cef47d5.jpg)
我想搜索以给定子字符串开头的所有元素的排序字符串列表.
这是一个查找所有完全匹配的示例:
import bisect
names = ['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert', 'chris']
names.sort()
leftIndex = bisect.bisect_left(names, 'bob')
rightIndex = bisect.bisect_right(names, 'bob')
print(names[leftIndex:rightIndex])
打印[‘bob’,’bob’,’bob’].
相反,我想搜索所有以’bob’开头的名字.我想要的输出是[‘bob’,’bob’,’bob’,’bobby’,’bobert’].如果我可以修改bisect搜索的比较方法,那么我可以使用name.startswith(‘bob’)来执行此操作.
举个例子,在Java中它很容易.我会用:
Arrays.binarySearch(names, "bob", myCustomComparator);
其中’myCustomComparator’是一个利用startswith方法(和一些额外的逻辑)的比较器.
我如何在Python中执行此操作?
解决方法:
通过使用使用选择的自定义比较器的实例,可以使用自定义比较来欺骗bisect:
>>> class PrefixCompares(object):
... def __init__(self, value):
... self.value = value
... def __lt__(self, other):
... return self.value < other[0:len(self.value)]
...
>>> import bisect
>>> names = ['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert', 'chris']
>>> names.sort()
>>> key = PrefixCompares('bob')
>>> leftIndex = bisect.bisect_left(names, key)
>>> rightIndex = bisect.bisect_right(names, key)
>>> print(names[leftIndex:rightIndex])
['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert']
>>>
DOH.正确的平分工作,但左边显然没有. “adam”没有以“bob”为前缀!要修复它,你也必须调整顺序.
>>> class HasPrefix(object):
... def __init__(self, value):
... self.value = value
... def __lt__(self, other):
... return self.value[0:len(other.value)] < other.value
...
>>> class Prefix(object):
... def __init__(self, value):
... self.value = value
... def __lt__(self, other):
... return self.value < other.value[0:len(self.value)]
...
>>> class AdaptPrefix(object):
... def __init__(self, seq):
... self.seq = seq
... def __getitem__(self, key):
... return HasPrefix(self.seq[key])
... def __len__(self):
... return len(self.seq)
...
>>> import bisect
>>> names = ['adam', 'bob', 'bob', 'bob', 'bobby', 'bobert', 'chris']
>>> names.sort()
>>> needle = Prefix('bob')
>>> haystack = AdaptPrefix(names)
>>> leftIndex = bisect.bisect_left(haystack, needle)
>>> rightIndex = bisect.bisect_right(haystack, needle)
>>> print(names[leftIndex:rightIndex])
['bob', 'bob', 'bob', 'bobby', 'bobert']
>>>
内容总结
以上是互联网集市为您收集整理的在Python中对字符串前缀执行二进制搜索全部内容,希望文章能够帮你解决在Python中对字符串前缀执行二进制搜索所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。