Was ist ein effizienter Weg, um vorherige und nächste Werte einer Schleifenliste von Objekten in Python zurückzugeben?

Question

Ich habe eine Liste von Python-Objekte:

fruits = [ 'apple', 'orange', 'banana', 'grape', 'cherry' ] 

Ich habe derzeit eine for Schleife in einer Klassenmethode, die „prev_fruit“ und „next_fruit“ Objekte für ein bestimmtes Objekt zurückgibt:

def get_prev_next(self, fruit_list): 
    prev_fruit = next_fruit = None 
    fruit_list_length = len(fruit_list) 
    for idx, fruit in enumerate(fruit_list): 
     if fruit == self: 
      if idx > 0: 
       prev_fruit = fruit_list[idx-1] 
      if idx < (fruit_list_length-1): 
       next_fruit = fruit_list[idx+1] 
    return prev_fruit, next_fruit 

Diese funktioniert, obwohl es wahrscheinlich effizientere Möglichkeiten gibt, dies zu tun (worüber ich glücklich bin).

Ich möchte jetzt die Liste optional "Schleifen" (vorher für den ersten Index ist der letzte und der nächste Index für die letzte ist zuerst).

def get_prev_next(self, fruit_list, looping=False): 
    ... 

Was ist eine effiziente Möglichkeit, dies auf Listen von Objekten mit 1-10000 Werten zu tun?

„effizient“ ist nicht unbedingt „effizienteste“ als Code Lesbarkeit und Portabilität ist ein Faktor - ich will nicht den Ansatz von sechs Monaten ab jetzt

Answer 1

umlernen Wenn die Eingabe eine Liste ist , dann bist du Art stecken die Liste für den Index der Frucht zu suchen, die Sie haben und dann die vorherigen und nächsten diejenigen aus, dass immer ...

def forgiving_getitem(lst, ix, default=None): 
    if 0 <= ix < len(lst): 
     return lst[ix] 
    else: 
     return default 

ix = fruit_list.index(self) 
previous = forgiving_getitem(fruit_list, ix - 1) 
next = forgiving_getitem(fruit_list, ix + 1) 

Leider ist dies O (N) Laufzeitkomplexität hat . Wenn Sie dies häufig mit der gleichen fruit_list tun, ist es möglicherweise besser, eine andere Datenstruktur (z. B. eine doppelt verknüpfte Liste) zu erstellen, bei der jeder Knoten die Frucht und die vorherigen und nächsten Früchte trägt. In diesem Fall ist O (1) das vorherige und das nächste zu erhalten, und Sie müssen nur O (N) Zeit damit verbringen, die Knoten an erster Stelle zu konstruieren, jedoch könnte ein anderes Code-Refactoring involviert sein, um mit Knoten anstelle von Früchten zu arbeiten direkt ...