mit Halbierung auf Liste der Tupel aber Vergleich nur mit ersten Wert

Question

Ich lese that question über wie bisect auf einer Liste von Tupeln zu verwenden, und ich verwendete diese Informationen zu beantworten that question. Es funktioniert, aber ich hätte gerne eine allgemeinere Lösung.

Da bisect erlaubt keine key Funktion angeben, wenn ich diese:

import bisect 
test_array = [(1,2),(3,4),(5,6),(5,7000),(7,8),(9,10)] 

und ich möchte das erste Element zu finden, wo x > 5 für jene (x,y) Tupel (nicht y überhaupt bedenkt, ich sind zur Zeit dies zu tun:

bisect.bisect_left(test_array,(5,10000)) 

und ich das richtige Ergebnis zu bekommen, weil ich wissen , dass keine y ist größer als 10000, also bisect verweist mich auf den Index (7,8). Hätte ich stattdessen 1000 gesetzt, wäre es falsch gewesen.

für ganze Zahlen, kann ich

bisect.bisect_left(test_array,(5+1,)) 

aber im allgemeinen Fall tun, wenn es schwimmt sein kann, wie ohne zu wissen, die Maximalwert des zweiten Elements zu, dass?

test_array = [(1,2),(3,4),(5.2,6),(5.2,7000),(5.3,8),(9,10)] 

Ich habe dies versucht:

bisect.bisect_left(test_array,(min_value+sys.float_info.epsilon,)) 

und es nicht funktioniert hat, aber ich habe versucht, dies:

bisect.bisect_left(test_array,(min_value+sys.float_info.epsilon*3,)) 

und es funktionierte. Aber es fühlt sich an wie ein schlechter Hack. Irgendwelche sauberen Lösungen?

Answer 1

bisect unterstützt beliebige Sequenzen. Wenn Sie bisect mit einem Schlüssel verwenden müssen, anstatt den Schlüssel zu bisect zugeben, können Sie es in der Folge bauen:

class KeyList(object): 
    # bisect doesn't accept a key function, so we build the key into our sequence. 
    def __init__(self, l, key): 
     self.l = l 
     self.key = key 
    def __len__(self): 
     return len(self.l) 
    def __getitem__(self, index): 
     return self.key(self.l[index]) 

Dann können Sie bisect mit einem KeyList, mit O verwenden (log n) Leistung und keine Notwendigkeit, die bisect Quelle zu kopieren oder Ihre eigene binäre Suche schreiben:

bisect.bisect_right(KeyList(test_array, key=lambda x: x[0]), 5) 

Answer 2

Dazu:

... wollen Sie die erste Position zu finden, wo x> 5 für die (x, y) Tupel (nicht y unter Berücksichtigung überhaupt)

So etwas wie:

import bisect 
test_array = [(1,2),(3,4),(5,6),(5,7000),(7,8),(9,10)] 

first_elem = [elem[0] for elem in test_array] 
print(bisect.bisect_right(first_elem, 5)) 

die bisect_right Funktion wird der erste Index Vergangenheit nehmen, und da Sie mit dem ersten Element des Tupels nur besorgt sind, ist dieser Teil scheint gerade nach vorne. ... verallgemeinere ich immer noch nicht auf eine bestimmte Schlüsselfunktion.

Wie Jean-FrancoisFabre darauf hingewiesen hat, verarbeiten wir bereits das gesamte Array, daher ist die Verwendung von bisect möglicherweise nicht einmal sehr hilfreich.

nicht sicher, ob es ein schneller ist, aber wir könnten alternativ so etwas wie itertools verwenden (ja, das ist ein bisschen hässlich):

import itertools 
test_array = [(1,2),(3,4),(5,6),(5,7000),(7,8),(9,10)] 

print(itertools.ifilter(
    lambda tp: tp[1][0]>5, 
    ((ix, num) for ix, num in enumerate(test_array))).next()[0] 
) 

Answer 3

Dies ist ein (quick'n'dirty) bisect_left Implementierung, die erlaubt eine beliebige Tastenfunktion:

def bisect(lst, value, key=None): 
    if key is None: 
     key = lambda x: x 
    def bis(lo, hi=len(lst)): 
     while lo < hi: 
      mid = (lo + hi) // 2 
      if key(lst[mid]) < value: 
       lo = mid + 1 
      else: 
       hi = mid 
     return lo 
    return bis(0) 

> from _operator import itemgetter 
> test_array = [(1, 2), (3, 4), (4, 3), (5.2, 6), (5.2, 7000), (5.3, 8), (9, 10)] 
> print(bisect(test_array, 5, key=itemgetter(0))) 
3 

Dies hält die O(log_N) up-Leistung, da es tut kein neues list der Schlüssel montieren. Die Implementierung der binären Suche ist weit verbreitet, aber dies wurde direkt aus der bisect_leftsource übernommen. Es sollte auch beachtet werden, dass die Liste in Bezug auf die gleiche Schlüsselfunktion sortiert werden muss.

Answer 4

Als Ergänzung zu den netten Anregungen, würde Ich mag meine eigene Antwort hinzuzufügen, die mit Schwimmern arbeiten (wie ich es gerade herausgefunden)

bisect.bisect_left(test_array,(min_value+abs(min_value)*sys.float_info.epsilon),)) 

funktionieren würde (ob min_value positiv ist oder nicht) . epsilon multipliziert mit min_value ist garantiert sinnvoll, wenn zu min_value hinzugefügt (es ist nicht absorbiert/abgebrochen). Es ist also der nächst höhere Wert, min_value und bisect wird damit arbeiten.

Wenn Sie nur ganze Zahlen haben, die noch schneller sein & deutlicher:

bisect.bisect_left(test_array,(min_value+1,))