Является какая-либо из этих библиотек дерева квадрантов пользой?
Кажется, что определенный мой проект потребует использования деревьев квадрантов, что-то, с чем я никогда не работал прежде. Из того, что я читал, они должны позволить существенные улучшения производительности, чем попытка "в лоб" проблемы уступила бы. Является какой-либо из этих модулей Python пользой?
- Дерево квадрантов 0.1.2 <= номер: не мог выполниться в Python 3.1
- QuadTree <= Да: простой при работе с прямоугольниками
- quadtree.py <= номер: никакая поддержка необходимых операций
РЕДАКТИРОВАНИЕ 1: кто-либо знает о лучшей реализации, чем та, представленная в pygame Wiki?
РЕДАКТИРОВАНИЕ 2: Вот несколько ресурсов, которые другие могут найти полезным для новаторских методов в Python.
2 ответа
Иногда неочевидно, как реализовать в Python структуры данных, такие как деревья.
Например,
D
/ \
B F
/ \ / \
A C E G
представляет собой простую двоичную древовидную структуру. В Python это можно представить так:
[D, B, F] - это узел с левым и правым поддеревом. Чтобы представить полное дерево, вы должны иметь:
[D,[[B,A,C],[F,E,G]]]
Это простой список вложенных списков, где любой узел может быть значением, таким как D или C, а любой узел может быть поддеревом, которое рекурсивно представляет собой список вложенных списков. Вы можете сделать что-то подобное со словарем словарей. Эти типы реализаций немного быстры и грязны и могут быть неприемлемы в задании, где инструктор ожидает класс Node с указателями на другие узлы, но в реальном мире обычно лучше использовать оптимизированные реализации списков / словарей Python. первый. Только если результат в чем-то неадекватен, перепишите его так, чтобы он выглядел так, как если бы вы написали его на C или Java.
Помимо этого, конечно, вам необходимо реализовать различные алгоритмы для управления вашими деревьями, потому что квадродерево - это больше, чем просто некоторые данные; это набор правил о том, как вставлять и удалять узлы. Если это не вопрос курсовой, то Quadtree 0.1.2 , вероятно, будет хорошей идеей.
При поиске quadtree индекс пакета python выдает 2 другие библиотеки: http://pypi.python.org/pypi?%3Aaction=search&term=quadtree&submit=search
disclaimer: никогда не использовал quadtrees или любую из этих библиотек.