Klingt alles sehr brauchbar. Wieso bin ich nicht mal auf
if v in myDict.values() gekommen?
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.