Есть ли какая-нибудь из этих четырехъядерных библиотек?

Похоже, что какой-то мой проект потребует использования четырехъярусных деревьев, с которыми я никогда раньше не работал. Из того, что я прочитал, они должны позволить существенные улучшения производительности, чем попытка грубой силы в проблеме. Являются ли какие-либо из этих модулей python полезными?

Quadtree 0.1.2 <= Нет: невозможно выполнить в Python 3.1
QuadTree <= Да: просто при работе с прямоугольниками
quadtree.py <= Нет: нет поддержки необходимых операций

РЕДАКТИРОВАТЬ 1: Кто-нибудь знает о лучшей реализации, чем тот, который представлен в вики файле pygame?

EDIT 2: Вот несколько ресурсов, которые другие могут найти полезными для методов поиска путей в Python.

Ответ 1

В этот комментарий, joferkington относится к текущему вопросу и говорит:

Только для того, что стоит, scipy.spatial.KDTree (и/или scipy.spatial.cKDTree, который написан на C по соображениям производительности ) является гораздо более надежным выбором, чем перечисленные опции.

Ответ 2

Другая библиотека для проверки - 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])

Ответ 3

Иногда неясно, как реализовать структуры данных, такие как деревья в 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, вероятно, будет хорошей идеей.

Ответ 4

Индекс пакета python создает две другие библиотеки при поиске quadtree: http://pypi.python.org/pypi?%3Aaction=search&term=quadtree&submit=search

отказ от ответственности: никогда не использовались квадранты или любая из этих библиотек.