Похоже, что какой-то мой проект потребует использования четырехъярусных деревьев, с которыми я никогда раньше не работал. Из того, что я прочитал, они должны позволить существенные улучшения производительности, чем попытка грубой силы в проблеме. Являются ли какие-либо из этих модулей python полезными?
РЕДАКТИРОВАТЬ 1: Кто-нибудь знает о лучшей реализации, чем тот, который представлен в вики файле pygame?
EDIT 2: Вот несколько ресурсов, которые другие могут найти полезными для методов поиска путей в Python.
В этот комментарий, joferkington относится к текущему вопросу и говорит:
Только для того, что стоит,
scipy.spatial.KDTree(и/или scipy.spatial.cKDTree, который написан на C по соображениям производительности ) является гораздо более надежным выбором, чем перечисленные опции.
Другая библиотека для проверки - PyQuadTree, чистый индекс квадранта python, который также работает на Python 3x. Все, что вам нужно добавить, это его ограничивающая рамка в виде последовательности длиной 4 длины, поэтому ее можно использовать для различных целей и даже для отрицательных систем координат.
Хотя я и являюсь автором, я действительно просто взял чью-либо структуру/код quadtree и сделал ее более удобной для пользователя, добавила поддержку прямоугольников-квадрациклов и добавила документацию. Простой пример использования:
#SETUP
import pyqtree
spindex = pyqtree.Index(bbox=[0,0,1000,500])
#ADD SOME ITEMS
for item in items:
spindex.insert(item=item, bbox=item.bbox)
#RETRIEVE ITEMS FROM A REGION
result = spindex.intersect(bbox=[233,121,356,242])
Иногда неясно, как реализовать структуры данных, такие как деревья в Python.
Например,
D
/ \
B F
/ \ / \
A C E G
- простая двоичная древовидная структура. В Python вы будете представлять его так:
[D,B,F] является node с левым и правым поддеревом. Чтобы представить полное дерево, вы должны:
[D,[[B,A,C],[F,E,G]]]
Это простой список вложенных списков, где любой node может быть значением типа D или C, а любой node может быть поддеревом, которое является рекурсивно списком вложенных списков. Вы можете сделать что-то подобное со словарем словарей. Эти типы реализаций являются немного быстрыми и грязными и могут быть неприемлемыми в задании, где преподаватель ожидает класс node с указателями на другие узлы, но в реальном мире, как правило, лучше использовать оптимизированные реализации списков Python/словари. Только если результат каким-то образом неадекватен, перепишите его так, чтобы он был написан на C или Java.
Помимо этого, конечно, вам нужно реализовать различные алгоритмы для управления вашими деревьями, потому что quadtree - это больше, чем просто некоторые данные; это набор правил о том, как вставлять и удалять узлы. Если это не вопрос, связанный с курсом, то Quadtree 0.1.2, вероятно, будет хорошей идеей.
Индекс пакета python создает две другие библиотеки при поиске quadtree: http://pypi.python.org/pypi?%3Aaction=search&term=quadtree&submit=search
отказ от ответственности: никогда не использовались квадранты или любая из этих библиотек.