Я пытаюсь создать общее дерево. Там кто-либо создается в структурах данных в Python для реализации дерева?
Я реализовал деревья, используя вложенные словари. Это довольно просто сделать, и у меня это сработало с довольно большими наборами данных. Я разместил образец ниже, и вы можете увидеть больше на Google code
def addBallotToTree(self, tree, ballotIndex, ballot=""):
"""Add one ballot to the tree.
The root of the tree is a dictionary that has as keys the indicies of all
continuing and winning candidates. For each candidate, the value is also
a dictionary, and the keys of that dictionary include "n" and "bi".
tree[c]["n"] is the number of ballots that rank candidate c first.
tree[c]["bi"] is a list of ballot indices where the ballots rank c first.
If candidate c is a winning candidate, then that portion of the tree is
expanded to indicate the breakdown of the subsequently ranked candidates.
In this situation, additional keys are added to the tree[c] dictionary
corresponding to subsequently ranked candidates.
tree[c]["n"] is the number of ballots that rank candidate c first.
tree[c]["bi"] is a list of ballot indices where the ballots rank c first.
tree[c][d]["n"] is the number of ballots that rank c first and d second.
tree[c][d]["bi"] is a list of the corresponding ballot indices.
Where the second ranked candidates is also a winner, then the tree is
expanded to the next level.
Losing candidates are ignored and treated as if they do not appear on the
ballots. For example, tree[c][d]["n"] is the total number of ballots
where candidate c is the first non-losing candidate, c is a winner, and
d is the next non-losing candidate. This will include the following
ballots, where x represents a losing candidate:
[c d]
[x c d]
[c x d]
[x c x x d]
During the count, the tree is dynamically updated as candidates change
their status. The parameter "tree" to this method may be the root of the
tree or may be a sub-tree.
"""
if ballot == "":
# Add the complete ballot to the tree
weight, ballot = self.b.getWeightedBallot(ballotIndex)
else:
# When ballot is not "", we are adding a truncated ballot to the tree,
# because a higher-ranked candidate is a winner.
weight = self.b.getWeight(ballotIndex)
# Get the top choice among candidates still in the running
# Note that we can't use Ballots.getTopChoiceFromWeightedBallot since
# we are looking for the top choice over a truncated ballot.
for c in ballot:
if c in self.continuing | self.winners:
break # c is the top choice so stop
else:
c = None # no candidates left on this ballot
if c is None:
# This will happen if the ballot contains only winning and losing
# candidates. The ballot index will not need to be transferred
# again so it can be thrown away.
return
# Create space if necessary.
if not tree.has_key(c):
tree[c] = {}
tree[c]["n"] = 0
tree[c]["bi"] = []
tree[c]["n"] += weight
if c in self.winners:
# Because candidate is a winner, a portion of the ballot goes to
# the next candidate. Pass on a truncated ballot so that the same
# candidate doesn't get counted twice.
i = ballot.index(c)
ballot2 = ballot[i+1:]
self.addBallotToTree(tree[c], ballotIndex, ballot2)
else:
# Candidate is in continuing so we stop here.
tree[c]["bi"].append(ballotIndex)
Какие операции вам нужны? В Python часто можно найти хорошее решение, используя dict или список с модулем bisect.
На PyPI есть много, много реализаций деревьев, и многие типы деревьев почти тривиально реализовать самостоятельно на чистом Python. Однако это редко бывает необходимо.
Python не имеет такого обширного набора «встроенных» структур данных, как Java. Однако, поскольку Python является динамическим, легко создать общее дерево. Например, двоичное дерево может быть:
class Tree:
def __init__(self):
self.left = None
self.right = None
self.data = None
Вы можете использовать его так:
root = Tree()
root.data = "root"
root.left = Tree()
root.left.data = "left"
root.right = Tree()
root.right.data = "right"
Нет встроенных деревьев, но вы можете легко построить их, создав подкласс типа узла из списка и написав методы обхода. Если вы сделаете это, я счел полезным bisect .
Есть также много реализаций PyPi , которые вы можете просмотреть.
Если я правильно помню, стандартная библиотека Python не включает древовидные структуры данных по той же причине, что и библиотека базовых классов .NET: уменьшается локальность памяти, что приводит к большему количеству промахов в кэше. На современных процессорах обычно быстрее просто поместить в кэш большой кусок памяти, а структуры данных с «богатым указателем» сводят на нет это преимущество.