Wie weiß man, in welchem ​​Segment sich ein Wert befindet?

Question

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

Angenommen, ich habe eine list wie oben. Das zweite Element jedes Tupels repräsentiert konzeptionell die Größe eines Blockspeichers. Diese Blockspeicher sind benachbart und sequentiell. Ihre Beziehung könnte wie folgt dargestellt:

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

Nun wird der Benutzer geben Sie mir die ‚absolute Adresse 'und ich sollte ihm einen Schlüssel zurückgeben, um den ganzen Speicherblock zu entschlüsseln. Zum Beispiel, wenn er auf die Adresse '10' zugreifen möchte, sollte ich key1 für ihn zurückgeben. Wenn er auf '15' zugreifen möchte, dann sollte ich key2 zurückgeben.

Meine Implementierung muss jetzt jedes Mal von Anfang an suchen. In Wirklichkeit gibt es viele Speicherblöcke, auf die Benutzer ständig zugreifen möchten. Die Leistung ist schlecht.

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)) 

Wie könnte ich die Leistung verbessern?

Die Datenstruktur nicht hat ein list (L) zu sein. Aber die bekannten Dinge sollten (1) die Blockgröße sein, (2) der Schlüssel, (3) Benutzer wird die 'absolute Adresse' zugreifen.

Wie pro Burhan Khalid Anweisung ist der endgültige Code wie folgt (siehe auch How to find the cumulative sum of numbers in a list?):

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

Sie können einen Array-Bisektionsalgorithmus verwenden, um den angeforderten Betrag in den richtigen Offset zu setzen.

Die documentation for the bisect module liefert das folgende Beispiel, das leicht für diese geändert werden können:

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'): 
     i = bisect(breakpoints, score) 
     return grades[i] 

>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]] 
['F', 'A', 'C', 'C', 'B', 'A', 'A'] 

Hier ist, wie Sie es verwenden würde (nicht getestet):

markers = [i[0] for i in initial_list_of_tuples] 
boundaries = [i[1] for i in initial_list_of_tuples] 
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] 

Answer 2

1. Erstellen Sie eine Liste der absoluten Adresse des Endpunkts der einzelnen Elemente. Der zweite Punkt dieser Liste ist garantiert aufsteigend.

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

2. Führen binäre Suche nach der gewünschten absoluten Adresse auf dem oberen Liste.

Gesamtzeitkomplexität O(n) mit Platz Komplexität O(n) sein sollte, jede Abfrage dauert O(logn) Zeit.