Was ist schneller: Schleife gegen Einzeiler

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.
droptix
User
Beiträge: 521
Registriert: Donnerstag 13. Oktober 2005, 21:27

Beispiel:

Code: Alles auswählen

myList = [
    ("foo", "bar"),
    ("blah", "blubb")
]
Welche Version von den folgenden arbeitet eigentlich schneller?

Code: Alles auswählen

def inList(x, l):
    r = []
    for i in l:
        if i == x:
            r.append(i)
    return r

print inList(("foo", "bar"), myList)
oder

Code: Alles auswählen

def inList(x, l):
    return [i for i in l if i == x]

print inList(("foo", "bar"), myList)
Worin liegen die Unterschiede?
Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Als weitere Alternative werfe ich mal filter() ins Rennen.

Geschwindigkeits-(aber keine Speicherverbrauchs-)vergleiche kannst du über das timeit-Modul durchführen.
droptix
User
Beiträge: 521
Registriert: Donnerstag 13. Oktober 2005, 21:27

Y0Gi hat geschrieben:Als weitere Alternative werfe ich mal filter() ins Rennen.
Hättest du dafür mal ein äquivalentes Beispiel zu meinem oben?
BlackJack

Code: Alles auswählen

def in_list(x, l):
    return filter(lambda i: x == i, l)
Flano
User
Beiträge: 43
Registriert: Sonntag 5. September 2004, 14:13

Ich denke der Einzeiler ist schneller, da die Ergebnisse aus der
"for Schleife" nicht erst in eine Liste geschrieben werden.
Besser lesbar(für mich) ist allerdings die "Schleife" und das
ist für mich immer das wichtigere Kriterium. Sehr wahrscheinlich
wirst du beim ausführen von:

Code: Alles auswählen

print inList(('foo', 'bar'), myList) *10000000
bei den drei Versionen, mit der Stoppuhr, keinen Unterschied
feststellen.

Gruß Flano
BlackJack

Ich finde die List-Comprehension am einfachsten zu erfassen. In der Schleife muss man sich komplexeren Code anschauen und hat einen Namen mehr.
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Die List Comprehension ist intern genau gleich implementiert. Sie spuckt sogar den Bezeichner in den Namensraum aus, wie das auch die for-Schleife tut :D
TUFKAB – the user formerly known as blackbird
Flano
User
Beiträge: 43
Registriert: Sonntag 5. September 2004, 14:13

Sorry,

Code: Alles auswählen

print in_list(('foo', 'bar'), myList) *1000000
ist natürlich Blödsinn als Geschwindigkeitsnachweis, da das Ergebnis
der Funktion multipliziert wird und nicht zig mal die Funktion
ausgeführt wird.
Stattdessen:

Code: Alles auswählen

for a in range(1000000):
    print in_list(('foo', 'bar'), myList)
Ich hoffe jetzt macht es Sinn.

Gruß Flano
BlackJack

Die Liste ist ein wenig zu kurz. Der Code drumherum dürfte mehr Zeit brauchen als das was Du messen möchtest.

Die List-Comprehension dürfte etwas schneller sein als die Schleife, weil dort die `append()`-Methode jedesmal neu vom Objekt abgefragt werden muss, wo bei der List-Comprehension klar ist, welche Methode bzw. welcher Bytecode ausgeführt werden muss.

Ganz gut am Bytecode zu sehen:

Code: Alles auswählen

In [20]: import dis

In [21]: def a(x, l):
   ....:     r = []
   ....:     for i in l:
   ....:         if i == x:
   ....:             r.append(i)
   ....:     return r
   ....:

In [22]: def b(x, l):
   ....:     return [i for i in l if i == x]
   ....:

In [23]: dis.dis(a)
  2           0 BUILD_LIST               0
              3 STORE_FAST               3 (r)

  3           6 SETUP_LOOP              44 (to 53)
              9 LOAD_FAST                1 (l)
             12 GET_ITER
        >>   13 FOR_ITER                36 (to 52)
             16 STORE_FAST               2 (i)

  4          19 LOAD_FAST                2 (i)
             22 LOAD_FAST                0 (x)
             25 COMPARE_OP               2 (==)
             28 JUMP_IF_FALSE           17 (to 48)
             31 POP_TOP

  5          32 LOAD_FAST                3 (r)
             35 LOAD_ATTR                4 (append)
             38 LOAD_FAST                2 (i)
             41 CALL_FUNCTION            1
             44 POP_TOP
             45 JUMP_ABSOLUTE           13
        >>   48 POP_TOP
             49 JUMP_ABSOLUTE           13
        >>   52 POP_BLOCK

  6     >>   53 LOAD_FAST                3 (r)
             56 RETURN_VALUE

In [24]: dis.dis(b)
  2           0 BUILD_LIST               0
              3 DUP_TOP
              4 STORE_FAST               2 (_[1])
              7 LOAD_FAST                1 (l)
             10 GET_ITER
        >>   11 FOR_ITER                30 (to 44)
             14 STORE_FAST               3 (i)
             17 LOAD_FAST                3 (i)
             20 LOAD_FAST                0 (x)
             23 COMPARE_OP               2 (==)
             26 JUMP_IF_FALSE           11 (to 40)
             29 POP_TOP
             30 LOAD_FAST                2 (_[1])
             33 LOAD_FAST                3 (i)
             36 LIST_APPEND
             37 JUMP_ABSOLUTE           11
        >>   40 POP_TOP
             41 JUMP_ABSOLUTE           11
        >>   44 DELETE_FAST              2 (_[1])
             47 RETURN_VALUE
droptix
User
Beiträge: 521
Registriert: Donnerstag 13. Oktober 2005, 21:27

Also mir geht es darum, einen Wert in einer sehr großen Liste zu ermitteln, die während des Programms sogar noch anwächst. Also eignet sich hier die List-Comprehension am besten. Damit ermittelt man zwar nicht direkt den gesuchten Wert, aber anhand der Länge der Liste (Null = leer = Wert nicht enthalten bzw. größer Null heißt "gefunden") dürfte sich die Frage klären lassen:

Code: Alles auswählen

myList = [
    ("foo", "bar"),
    ("blah", "blubb")
]

def inList(x, l):
    if len([i for i in l if i == x]) == 0:
        return False
    else:
        return True

print inList(("foo", "bar"), myList)
Danke!
Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Müsste nicht anstelle der List Comprehension eine Generator Expression (außen runde statt eckige Klammern, verwendet Iterator) noch schneller oder zumindest bei großen Datenmengen speicherfreundlicher sein?
BlackJack

droptix hat geschrieben:Also mir geht es darum, einen Wert in einer sehr großen Liste zu ermitteln, die während des Programms sogar noch anwächst. Also eignet sich hier die List-Comprehension am besten. Damit ermittelt man zwar nicht direkt den gesuchten Wert, aber anhand der Länge der Liste (Null = leer = Wert nicht enthalten bzw. größer Null heißt "gefunden") dürfte sich die Frage klären lassen:
Das ist aber umständlich und unnötig langsam. Wenn Du nur wissen willst, ob ein Element mindestens einmal enthalten ist kannst Du den ``in``-Operator benutzen: ``if x in liste:``. Da wird a) keine zusätzliche Liste angelegt und b) bricht die Suche beim ersten Treffer ab, es muss also nicht unnötigerweise der Rest der Liste durchlaufen werden.

Wenn diese Operation oft durchgeführt werden muss, wäre ein `set()` geeigneter. Da ist die Laufzeit vom ``in``-Operator unabhängig von der Anzahl der Elemente weil dort, genau wie bei Dictionaries, intern eine Hashtabelle verwendet wird. Im `set()` kann jedes Element aber nur einmal enthalten sein und die Reihenfolge bleibt nicht erhalten. Wenn das ein Problem ist, müsstest Du parallel eine Liste verwalten.
droptix
User
Beiträge: 521
Registriert: Donnerstag 13. Oktober 2005, 21:27

BlackJack hat geschrieben:Das ist aber umständlich und unnötig langsam. Wenn Du nur wissen willst, ob ein Element mindestens einmal enthalten ist kannst Du den ``in``-Operator benutzen: ``if x in liste:``. Da wird a) keine zusätzliche Liste angelegt und b) bricht die Suche beim ersten Treffer ab, es muss also nicht unnötigerweise der Rest der Liste durchlaufen werden.
Mein Ziel ist es eigentlich, in einem Dictionary nach einem bestimmten Werte-Paar zu suchen. Leider kann ich dafür if a in b nicht verwenden. Das Dictionary bildet dabei eine Tabelle ab. Die erste Spalte enthält eine eindeutige ID (enstpricht dem Key im Dictionary):

Code: Alles auswählen

myDict = {
    1: ("foo", "bar"),
    2: ("blah", "blubb")
}

def inDict(v, d):
    for i in d:
        if d[i] == v:
            return True
    return False

print inDict(("foo", "bar"), myDict)
BlackJack hat geschrieben:Wenn das ein Problem ist, müsstest Du parallel eine Liste verwalten.
Ich behelfe mir momentan wie folgt: Beim dynamischen Erstellen des Dictionaries wid zusätzlich eine Liste angefertigt, die so aussieht:

Code: Alles auswählen

cache = []
cache.append(("foo", "bar"))
cache.append(("blah", "blubb"))
Dadurch kann ich natürlich jetzt mittels if v in cache schnell nach dem Werte-Paar suchen und kriege recht schnell ein True/False. ABER: Dadurch belege ich unnötig viel Speicherplatz, weil das Werte-Paar quasi doppelt im Programm abgelegt wird. Das erhöht auch die Daten-Redundanz und bringt eigentlich nur Nachteile. Daher wäre es mir lieber, diret in myDict nach dem Werte-Paar zu suchen. Allerdings sehe ich keine Möglichkeit, außer es von Anfang bis Ende zu durchwandern.

Jedes Werte-Paar ist allerdings einmalig, daher könnte ich anstelle der Liste parallel ein Set verwalten. Trotzdem bleiben dadurch Daten-Redundanz und die anderen Nachteile.
Benutzeravatar
Luzandro
User
Beiträge: 87
Registriert: Freitag 21. April 2006, 17:03

Code: Alles auswählen

("foo", "bar") in myDict.values()
?
[url=http://www.leckse.net/artikel/meta/profilieren]Profilieren im Netz leicht gemacht[/url]
BlackJack

droptix hat geschrieben:Mein Ziel ist es eigentlich, in einem Dictionary nach einem bestimmten Werte-Paar zu suchen. Leider kann ich dafür if a in b nicht verwenden. Das Dictionary bildet dabei eine Tabelle ab. Die erste Spalte enthält eine eindeutige ID (enstpricht dem Key im Dictionary):

Code: Alles auswählen

myDict = {
    1: ("foo", "bar"),
    2: ("blah", "blubb")
}

def inDict(v, d):
    for i in d:
        if d[i] == v:
            return True
    return False

print inDict(("foo", "bar"), myDict)
Die Funktion kannst Du durch das hier ersetzen:

Code: Alles auswählen

print ('foo', 'bar') in my_dict.itervalues()
Greifst Du auf die Elemente eigentlich auch über die ID zu? Falls ja, auch in der Programmphase wo du diesen Werte-Test benötigst?
BlackJack hat geschrieben:Wenn das ein Problem ist, müsstest Du parallel eine Liste verwalten.
Ich behelfe mir momentan wie folgt: Beim dynamischen Erstellen des Dictionaries wid zusätzlich eine Liste angefertigt, die so aussieht:

Code: Alles auswählen

cache = []
cache.append(("foo", "bar"))
cache.append(("blah", "blubb"))
Dadurch kann ich natürlich jetzt mittels if v in cache schnell nach dem Werte-Paar suchen und kriege recht schnell ein True/False.
Nicht wirklich schnell, bzw. nicht viel schneller als das durchgehen des Dictionaries und bei weitem nicht so schnell wie es mit `set()`s geht, vor allem wenn es sich um viele Elemente handelt.
ABER: Dadurch belege ich unnötig viel Speicherplatz, weil das Werte-Paar quasi doppelt im Programm abgelegt wird. Das erhöht auch die Daten-Redundanz und bringt eigentlich nur Nachteile.
Das Wertepaar selbst wird nur einmal abgelegt. Liste, `set()` oder Dictionary enthalten nur eine Referenz.
Benutzeravatar
Luzandro
User
Beiträge: 87
Registriert: Freitag 21. April 2006, 17:03

BlackJack hat geschrieben:

Code: Alles auswählen

print ('foo', 'bar') in my_dict.itervalues()
ah, es gibt sogar sowas - dachte schon der Nachteil bei meinem Vorschlag ist eben, dass es die komplette Liste liefert
Nicht wirklich schnell, bzw. nicht viel schneller als das durchgehen des Dictionaries und bei weitem nicht so schnell wie es mit `set()`s geht, vor allem wenn es sich um viele Elemente handelt.
Nur zum Verständnis: mit Dictionary durchgehen meinst du über itervalues wie oben? Weil bei einem "inversen" Dictionary, sprich wenn er den Schlüssel abfragen will, müsste der Zugriff bei Dictionary oder Set doch genau gleich sein, oder?
[url=http://www.leckse.net/artikel/meta/profilieren]Profilieren im Netz leicht gemacht[/url]
BlackJack

Luzandro hat geschrieben:
Nicht wirklich schnell, bzw. nicht viel schneller als das durchgehen des Dictionaries und bei weitem nicht so schnell wie es mit `set()`s geht, vor allem wenn es sich um viele Elemente handelt.
Nur zum Verständnis: mit Dictionary durchgehen meinst du über itervalues wie oben? Weil bei einem "inversen" Dictionary, sprich wenn er den Schlüssel abfragen will, müsste der Zugriff bei Dictionary oder Set doch genau gleich sein, oder?
Ja ich meinte das lineare Suchen in den Werten und ja Zugriff auf Schlüssel bei Dictionaries und Elementen bei `set()`s sollten etwa gleichschnell sein.

@droptix: Zu dem Dictionary fällt mir noch ein: Werden die IDs in aufsteigender Reihenfolge und zusammenhängend vergeben und später keine gelöscht, so dass keine Lücken entstehen? Dann könnte man das Dictionary durch eine Liste ersetzen. Wenn die IDs mit 0 statt 1 anfangen dürften, braucht man noch nicht einmal den Index anpassen.
droptix
User
Beiträge: 521
Registriert: Donnerstag 13. Oktober 2005, 21:27

Klingt alles sehr brauchbar. Wieso bin ich nicht mal auf if v in myDict.values() gekommen? :oops:
BlackJack hat geschrieben:Zu dem Dictionary fällt mir noch ein: Werden die IDs in aufsteigender Reihenfolge und zusammenhängend vergeben und später keine gelöscht, so dass keine Lücken entstehen? Dann könnte man das Dictionary durch eine Liste ersetzen. Wenn die IDs mit 0 statt 1 anfangen dürften, braucht man noch nicht einmal den Index anpassen.
Ja, die IDs sind unique und in aufsteigender Reihenfolge. Einfach nur Zahlen beginnend bei 1. Könnten aber auch bei Null anfangen.

Aber das trifft ja nun leider nicht mehr das zuletzt von mir genannte Beispiel. Also machen wir's ganz konkret. Ich bin immernoch dabei, mein Dateisystem als flachen Baum abzubilden. Um diesen `FlatTree` weitestgehend zu abstrahieren, habe ich folgende Klasse geschrieben:

Code: Alles auswählen

#!/usr/bin/python

class FlatTree:
	""" Is a flatened model of a tree like a SQL table. Consists of a list of
	values (e.g. directory or file names) with a unique ID and their parent ID.
	
	Example: /foo/bar
	
	id | value | parentID
	---+-------+---------
	 1 |       | None
	 2 | foo   | 1
	 3 | bar   | 2 """
	def __init__(self):
		self.ID = 0
		self.tree = {}
		# caching needs more memory but makes `GetTreeID` working faster
		self.caching = True
		self.cache = {}
	
	def CreateID(self):
		""" Raises unique ID and returns it. """
		self.ID += 1
		return self.ID
	
	def AddBranch(self, value, parentID=None, attributes=None):
		""" Adds a child node to a parent node and returns the new unique
		ID. """
		ID = self.CreateID()
		self.tree[ID] = {}
		self.tree[ID]['value'] = value
		self.tree[ID]['attributes'] = attributes
		self.tree[ID]['parentID'] = parentID
		if self.caching == True:
			# cache value and parent ID as unique identifiers
			self.cache[(value, parentID)] = ID
		return ID
	
	def AddRoot(self, value, attributes=None):
		""" Adds a root node having no parent node and returns the new unique
		ID. """
		return self.AddBranch(value, None, attributes)
	
	def RebuildPath(self, ID):
		""" Rebuilds the full path from a unique ID in the tree by going
		through it recursively. Returns False if ID is not in the tree.
		Otherwise returns a list of values that can be concatenated. """
		path = []
		parentID = ID
		while parentID is not None:
			parent = self.tree[parentID]
			parentID = parent['parentID']
			path.append(parent['value'])
		path.reverse()
		return path
	
	def GetTreeID(self, value, parentID):
		""" Checks if value and parentID are present in the tree. If yes, it
		returns the unique ID of the tree item containing both. If no, it
		returns False. """
		if self.caching == True:
			# with caching the ID can be found much faster
			if (value, parentID) in self.cache:
				return self.cache[(value, parentID)]
			else:
				return False
		else:
			# without caching the ID will be searched
			for ID in self.tree:
				if self.tree[ID]['value'] == value and self.tree[ID]['parentID'] == parentID:
					return  ID
			return False

if __name__ == "__main__":
	t = FlatTree()
	root = t.AddRoot("")
	foo = t.AddBranch("foo", root)
	bar = t.AddBranch("bar", foo)
	print "/".join(t.RebuildPath(bar))
Die Frage ist, wie kriege ich heraus, ob sich dasselbe Element bereits im Baum befindet, damit man es nicht zweimal einträgt? Eindeutiger Hinweis sind `value` und `parentID`. Gibt es bereits ein Element, dass für beide Parameter gleiche Werte aufweist, dann darf es nicht noch einmal in den `FlatTree` eingetragen werden.

Wie gesagt, um nicht das gesamte Dictionary sequentiell durchzugehen, habe ich den Schalter `caching` eingebaut, der standardmäßig auf `True` steht. Das prüft die Methode `GetTreeID`. Liefert sie `False`, gibt's das Element noch nicht, andernfalls liefert sie die ID desjenigen gleichen Elements, das sich bereits im Baum befindet.

Die Liste `cache` beinhaltet jeweils `name` und `parentID` als Tupel. Diese werden beim Hinzufügen eines Baum-Astes durch `AddBranch` automatisch in `cache` eingetragen. Dieses künstliche Caching würde ich gern umgehen, aber nicht auf Kosten der Zeit.
BlackJack

Das künstliche caching lässt sich nicht umgehen. Jedenfalls nicht wenn es effizient sein soll. Wenn es eine SQL-Tabelle wäre, müsstest Du über die Spalten `value` und `parentID` auch einen Index anlegen und damit Speicher darauf verwenden wenn der Zugriff effizient sein soll.

Ich bin auch nach wie vor nicht davon überzeugt, dass es geschickt ist eine Datenbank-Tabelle nachzubauen und damit letztendlich viel zu kompliziert Mechanismen zu implementieren, die es in der Sprache schon gibt. Pack die Pfad-Stückchen in Objekte. Jedes Objekt hat implizit eine eindeutige Identität und die lässt sich direkt referenzieren, anstatt selber eine Tabelle/Dictionary mit Zahlen als Identitäten/Referenzen zu basteln.

Das Du ein Dictionary mit Namen, Attributen und einer ID anlegst, ist ein Hinweis, dass dort mehrere Daten zusammengehören. Und das kann man mit Klassen besser lösen. Da kannst Du dann auch gleich definieren was es heisst, das zwei Pfad-Fragmente gleich sind, also Name und Referenz auf das selbe Elternteil und eine Hash-Funktion über die Attribute die beim Vergleich herangezogen werden, und schon kann man die Objekte in ein `set()` stecken oder als Schlüssel in Dictionaries verwenden. Beispiel:

Code: Alles auswählen

class PathElement(object):
    def __init__(self, name, parent, attributes):
        self.name = name
        self.parent = parent
        self.attributes = attributes
    
    def __cmp__(self, other):
        return (cmp(self.name, other.name)
                or cmp(id(self.parent), id(other.parent)))
    
    def __hash__(self):
        return hash((self.name, id(self.parent)))
    
    def path_to_element(self):
        result = [self.name]    # Oder nur [].
        parent = self.parent
        while parent is not None:
            result.append(parent.name)
            parent = parent.parent
        result.reverse()
        return result
Die Datenstruktur ist übrigens denkbar ungeeignet um alle Pfade aufzulisten, weil man nur einfach von einem Eintrag zur Wurzel kommt, aber nicht umgekehrt.
droptix
User
Beiträge: 521
Registriert: Donnerstag 13. Oktober 2005, 21:27

Ich versteh schon was du meinst. Es ist auch sehr logisch, einen Baum aus einzelnen Ästen aufzubauen. So geschieht das ja auch bei XML/DOM.

Hmmm... ich hab `FlatTree` ja extra ausgelagert, um das jederzeit vollständig anpassen bzw. austauschen zu können. Leider stehen diese versteckten Methoden wie `__cmp__` oder `__hash__` nicht in meinem Büchlein. So wie du's dargestellt hast wird es einleuchtend, aber das muss man ja erstmal wissen :lol:

Du meinst, dass der gesamte Baum dann durch ein set() abgebildet wird? Um auch umgekehrt die Pfade auflösen zu können, könnte man ja für jedes Element noch das Attribut `children` als set() einführen. Und für eine eindeutige ID eben noch ein Attribut `id`. Irgendwann muss ich das ja mal flach machen und dann bleibt mir nur der Weg über eine ID.

Ich weiß auch immer nicht, ab wann eine Kopie angefertigt und an welchen Stellen nur referenziert wird. Gibt's dazu mal ne verständliche Erklärung im Netz?
Antworten