Seite 1 von 1
Listenlücken
Verfasst: Donnerstag 14. Dezember 2006, 17:26
von uphill
Hi,
ich hab hier eine liste, und wollte wissen wie ich am schnellsten eine Lücke finde. zB:
in diesem Fall die 4
und in diesem die 6...
danke
uphill
Verfasst: Donnerstag 14. Dezember 2006, 17:42
von Leonidas
Wenn du nur die erste Lücke haben willst, kannst du diese hübsch obskure LC nehmen:
Code: Alles auswählen
[first for first, second in enumerate(li) if first+1 != second][0] + 1
Eine anständige, mehrzeilige Lösung zu finden ist mir im Moment zu anstrengend
Verfasst: Donnerstag 14. Dezember 2006, 18:07
von BlackJack
Etwas speicherschonender:
Code: Alles auswählen
(first for first, second in enumerate(li) if first+1 != second).next() + 1
Beide Varianten fallen leider auf die Nase wenn keine Lücke vorhanden ist.
Verfasst: Donnerstag 14. Dezember 2006, 19:32
von mitsuhiko
Code: Alles auswählen
def find_spaces(iterable):
last = None
for item in iterable:
if last is not None and last + 1 != item:
yield last
last = item
Verfasst: Donnerstag 14. Dezember 2006, 21:38
von Joghurt
Wie ineffizient
. Das läuft ja in O(N), man kann es aber auch in O(log N) machen:
Code: Alles auswählen
def find_gap(list):
first = list[0]
step = len(list)
pos = step/2
while True:
step /= 2
if pos >= len(list):
pos = len(list)-1
if list[pos] != first + pos:
if step == 0:
return pos
pos -= step
else:
pos += step
if step == 0:
return False
(Nicht zu ernst nehmen)
Verfasst: Donnerstag 14. Dezember 2006, 22:41
von uphill
@linduas das geht nicht mit 0
Code: Alles auswählen
[first for first, second in enumerate(li) if first+1 != second][0] + 1
Code: Alles auswählen
In [12]: li = [0,1,2,12,23,43,255]
In [13]: [first for first, second in enumerate(li) if first+1 != second][0] + 1
Out[13]: 1
[/quote]
Verfasst: Donnerstag 14. Dezember 2006, 22:51
von Leonidas
uphill hat geschrieben:@linduas das geht nicht mit 0
Bitte Augen etwas nach links drehen, und dort meinen Nick korrekt ablesen. Dankeschön.
Ansonsten: hast recht. Das liegt daran, dass enumerate mit 0 zu zählen anfängt und nicht mit dem ersten Element der übergebenen Liste. Dazu müsste man eine alternative Emumerate-Funktion implementieren. Dummerweise geht bei mir die Shell grad nicht, sonst könnte ich dir schnell einen Quelltext posten. Andererseits ist es auch egal, weil blackbird schon eine universellere Möglichkeit gepostet hat.
Verfasst: Donnerstag 14. Dezember 2006, 23:10
von sape
>> Dazu müsste man eine alternative Emumerate-Funktion implementieren
Wie wäre es mit `whiletake` @ `count(1)` @ `Liste` in einer LC?
EDIT: Ich meinte natürlich `takewhile` ^^ Naja, bin aber ehe nicht der Fan von `takewhile`
Brauchte ich bis her nicht.
Verfasst: Donnerstag 14. Dezember 2006, 23:20
von sape
Blödsinn -> über `izip(count(1), Liste)` iterieren
@Sape!!
Verfasst: Donnerstag 14. Dezember 2006, 23:42
von BlackJack
Jau, um diesen Gedanken mal zuende zu führen:
Code: Alles auswählen
from itertools import count, groupby, imap, izip
from operator import itemgetter
def search_first_gap(iterable):
dummy, before_gap = groupby(izip(iterable, count()),
key=lambda (a, b): a - b).next()
return max(imap(itemgetter(0), before_gap)) + 1
def main():
data = [0, 1, 2, 3, 4, 5, 12]
print search_first_gap(data)
Verfasst: Freitag 15. Dezember 2006, 01:20
von sape
Wow, sieht wie immer wider sehr nach FP aus
Puh, das werde ich mal morgen genauer studieren. Sieht auf jeden fall sehr interessant und (für mich) Kompliziert aus.
lg
Verfasst: Freitag 15. Dezember 2006, 17:12
von uphill
@BlackJakck:
cooler ansatz nur leider nich python 2.3 kompatibel
greez
Verfasst: Freitag 15. Dezember 2006, 17:27
von uphill
danke auf jeden fall für die vielen Antworten aber leider funzt der yield ansatz von BlackJack komischer weise auch nicht. Versteh allerdings nicht so genau warum.
greez.
Verfasst: Freitag 15. Dezember 2006, 17:38
von uphill
Code: Alles auswählen
def find_spaces(iterable):
last = None
for item in iterable:
if last is not None and last + 1 != item:
yield last+1
last = item
das geht, und das werd ich verwenden und nochmal thx@all
Verfasst: Freitag 15. Dezember 2006, 21:06
von sape
Jao, nun hab ich BlackJacks Beispiel verstanden. Wieder was dazugelernt!
lg