Seite 1 von 2

Re: brauche es für eine große Liste

Verfasst: Montag 1. Januar 2007, 19:45
von Luzandro
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?

Re: brauche es für eine große Liste

Verfasst: Montag 1. Januar 2007, 20:42
von 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.

Re: brauche es für eine große Liste

Verfasst: Dienstag 2. Januar 2007, 12:54
von droptix
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.

Verfasst: Dienstag 2. Januar 2007, 15:48
von 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.

flat braucht ID

Verfasst: Dienstag 2. Januar 2007, 16:07
von droptix
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?

Re: flat braucht ID

Verfasst: Dienstag 2. Januar 2007, 17:01
von BlackJack
droptix hat geschrieben:Leider stehen diese versteckten Methoden wie `__cmp__` oder `__hash__` nicht in meinem Büchlein.
Dann benutzt Du das falsche Büchlein. :-)
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.
Eigentlich reicht es wenn man den Baum nur durch einzelne Elemente darstellt, ohne `set()`. Man muss sich nur den Wurzelknoten merken, der Rest hängt da ja dran und ist über die Kinder zu erreichen. Ich hatte hier ja schonmal eine Lösung als Objektbaum gebastelt:

http://paste.pocoo.org/show/485/

Da gibt's beim Aufbau des Baums mit `directory_map` noch ein Dictionary, das komplette Verzeichnispfade als Zeichenkette auf das entsprechende `Directory`-Objekt abbildet, aber das ist nur um die Zeit zu sparen sich durch den Baum zu arbeiten. Man könnte stattdessen auch den Pfad zerlegen und von der Wurzel bis zum gewünschten Verzeichnis laufen. Dann wäre es geschickter `Directory.children` als Dictionary zu implementieren und dort die Namen der Unterverzeichnisse einzutragen. Das wäre vielleicht sowieso geschickter.
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?
Bei einfachen Zuweisungen werden *nie* Kopien angelegt.