Listenlücken

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
uphill
User
Beiträge: 22
Registriert: Sonntag 10. Dezember 2006, 20:17

Donnerstag 14. Dezember 2006, 17:26

Hi,
ich hab hier eine liste, und wollte wissen wie ich am schnellsten eine Lücke finde. zB:

Code: Alles auswählen

li = [1,2,3,5,12]
in diesem Fall die 4

Code: Alles auswählen

li = [1,2,3,4,5,12]
und in diesem die 6...

danke

uphill
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Donnerstag 14. Dezember 2006, 17:42

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 8)
My god, it's full of CARs! | Leonidasvoice vs Modvoice
BlackJack

Donnerstag 14. Dezember 2006, 18:07

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. :-(
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Donnerstag 14. Dezember 2006, 19:32

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
TUFKAB – the user formerly known as blackbird
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Donnerstag 14. Dezember 2006, 21:38

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)
uphill
User
Beiträge: 22
Registriert: Sonntag 10. Dezember 2006, 20:17

Donnerstag 14. Dezember 2006, 22:41

@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]
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Donnerstag 14. Dezember 2006, 22:51

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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Donnerstag 14. Dezember 2006, 23:10

>> 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.
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Donnerstag 14. Dezember 2006, 23:20

Blödsinn -> über `izip(count(1), Liste)` iterieren

:roll: @Sape!!
BlackJack

Donnerstag 14. Dezember 2006, 23:42

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)
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Freitag 15. Dezember 2006, 01:20

Wow, sieht wie immer wider sehr nach FP aus :D Puh, das werde ich mal morgen genauer studieren. Sieht auf jeden fall sehr interessant und (für mich) Kompliziert aus.

lg
uphill
User
Beiträge: 22
Registriert: Sonntag 10. Dezember 2006, 20:17

Freitag 15. Dezember 2006, 17:12

@BlackJakck:
cooler ansatz nur leider nich python 2.3 kompatibel

greez
uphill
User
Beiträge: 22
Registriert: Sonntag 10. Dezember 2006, 20:17

Freitag 15. Dezember 2006, 17:27

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.
uphill
User
Beiträge: 22
Registriert: Sonntag 10. Dezember 2006, 20:17

Freitag 15. Dezember 2006, 17:38

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
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Freitag 15. Dezember 2006, 21:06

Jao, nun hab ich BlackJacks Beispiel verstanden. Wieder was dazugelernt! :D

lg
Antworten