如何知道值所在的段

Question

L = [('key1', 14), ('key2', 20), ('key3', 13), ('key4', 10), ('key5', 11)]

假设我得到了list如上所述.每个元组的第二个元素在概念上表示块存储器的大小.这些块存储器是相邻的和顺序的.他们的关系可以表示为:

0 ____ 14 ____ 14 + 20 14 ____ + 20 + 13 14 ____ + 20 + 13 + 10 14 ____ + 20 + 13 + 10 + 11

现在用户将给我'绝对地址',我应该给他一个密钥来解密整个内存块.例如,如果他想访问地址'10',那么我应该为他返回key1.如果他想访问'15',那么我应该返回key2.

我的实现现在必须每次都从头开始搜索.实际上,有许多内存块,用户希望一直访问.表现不好.

L = [('key1', 14), ('key2', 20), ('key3', 13), ('key4', 10), ('key5', 11)]
def get_key(address):
    c = 0
    offset = 0
    for i in L:
        if address < i[1] + offset:
            break
        c += 1
        offset += i[1]
    return c

print(get_key(15))

我怎样才能提高性能？

数据结构不必是list(L).但已知的事情应该是(1)块大小,(2)密钥,(3)用户将访问'绝对地址'.

根据Burhan Khalid的说明,最终代码如下(另请参阅如何在列表中查找累积的数字总和？):

from bisect import bisect
from itertools import accumulate

L = [('key1', 14), ('key2', 20), ('key3', 13), ('key4', 10), ('key5', 11)]
markers = [i[0] for i in L]
boundaries = list(accumulate([i[1] for i in L]))

##offsets = []
##offsets.append(boundaries[0])
##for offset in boundaries[1:]:
##   offsets.append(sum(offsets)+offset)

def buckets(value, boundaries, markers):
   i = bisect(boundaries, value)
   return markers[i]

print(buckets(67, boundaries, markers))

Answer 1

1. 构建每个项目的终点的绝对地址列表.该列表的第二项显然保证升序.

L2 = [('key1', 14), ('key2', 34), ('key3', 47), ('key4', 57), ('key5', 68)]

2. 在上面的列表中对请求的绝对地址执行二进制搜索.

总体时间复杂度应该是O(n)空间复杂度O(n),每个查询都需要O(logn)时间.