могу, но это не оверхед будет? мне кажется мне нужен тупл туплов или типа того

могу, но это не оверхед будет? мне кажется мне нужен тупл туплов или типа того

Да, это оверзед. Можешь в данном случае написать свой велосипед - btree.

Хотz думаю, что либа на питоне есть для этого.

блин, что ты хочешь делать с этими объектами?

операции вроде поиска соседей я могу считать самостоятельно, и тянуть по результирующим ключам

операции вроде поиска соседей я могу считать самостоятельно, и тянуть по результирующим ключам

Тогда используй btree.

хорошо, спасибо

лол

зачем ему btree

зачем ему btree

Твои предложения?

btree во первых тяжело реализовывать, во вторых оно хорошо работает с жеским диском

btree во первых тяжело реализовывать, во вторых оно хорошо работает с жеским диском

Чего? Бинарное дерево тяжело реализовывать?

и по какому ключу ты собрался строить дерево?

и зачем?

ну вот пример операции - есть несколько экземпляров с разными координатами и один, к которому нужно найти ближайший. Считаю, достаю. Всё.

и по какому ключу ты собрался строить дерево?

[x,y]

ну вот пример операции - есть несколько экземпляров с разными координатами и один, к которому нужно найти ближайший. Считаю, достаю. Всё.

Ну, здесь бинарка не всегда заходит нормально.

и зачем?

Предложения какие?

то есть ключ это тупл?

то есть ключ это тупл?

Да.

и что оно будет искать там?

и что оно будет искать там?

Ты понял свой вопрос? Я - нет.

что угодно, но не ближайшего соседа

что угодно, но не ближайшего соседа

Ок, структура, в которой можно быстро найти соседа в n-мерном пространстве? Давай.

quadtree

objects[15][154] - O(1) же достанет?

за логарифм ищет

только если ключи целые

btree тут вообще ни к селу ни к городу

аа гады кто забанил в С конфе

И правильно сделали.

я ж пошутить хотел

я ж пошутить хотел

Поверь. Хаскель заебал уже всех.

Ок, структура, в которой можно быстро найти соседа в n-мерном пространстве? Давай.

R*-tree

это уже обобщение

Ну вот, насоветовали. Выбирай то, что нравтся.

основная идея - рекурсивное разбиение пространства

основная идея - рекурсивное разбиение пространства

Только вопрос - для представления точек оверхеда по памяти не будет?

Т.е. он будет. Не много ли это на мильён точек?

у любого дерева оверхед по памяти

тем более что можно задать определённую глубину

тем более что можно задать определённую глубину

Т.е. ты предлагаешь терять точность?

зависит от того чего хотят добиться.

r*-tree оченьхорошо подходит

из всех спэтиал три его чаще всего используют для геоданных.

и неслучайно.

для статических данных идеальный вариант

https://pypi.python.org/pypi/Rtree/

очень хорошо балансируется

для многомерных данных да

Нe вот, если лень разбираться, а хочется использовать.

для двумерных вполне норм quadtree

Нет, как раз таки для двухмерных.

И для максимального перфоманса именно r*

оно дороже строится, но работает на запросы быстрее.

для двумерных вполне норм quadtree

Вот смотри, у нас есть квадрат 1x1. Если добавить в quadtree точку 0.54 0.54, то какую структуру дерево будет иметь? А то я не сумел понять структуру quadtree.

quadtree примитивное вообще

Я правильно понимаю, что там вся информация хранится в листах дерева?

берет квадрат и делит на 4 квадрата

квадтри просто четверит пространство.

и так рекурсивно

если в вершине слишком много точек она бьется на 4

можно задать глубину рекурсии, и тем самым точность поиска

можно задать глубину рекурсии, и тем самым точность поиска

Блин, здесь что-то мне кажется уж очень большой оверхед по памяти.

нопе

ERROR: S client not available

На самом деле обычный деревянный

в худшем случае nlogn

Как раз таки перформанс похуже.

проще взять готовую имплементацию какой либо структуры данных и заюзать

самому довольно сложно писать

деревья

проще взять готовую имплементацию какой либо структуры данных и заюзать

А почему на btree ты написал, что там очень сильно используется диск?

потому что btree читает блоками, обычно этот блок подгоняют по размер блока жесткого диска в базах данных

а в памяти юзают что нибудь попроще, типа red-black tree

потому что btree читает блоками, обычно этот блок подгоняют по размер блока жесткого диска в базах данных

Понял, мой косяк. Буду теперь называть binTree

btree вообще для базданных юзают

не, твой косяк в том, что бинарное дерево с ключём из тупла (x,y) никак не помогает искать ближайшего соседа

по первых нужно определить операцию < для тупла

помогает на самом деле, но по хитрому.

не, твой косяк в том, что бинарное дерево с ключём из тупла (x,y) никак не помогает искать ближайшего соседа

Это требование появилось после моего предложения.

помогает на самом деле, но по хитрому.

Как?

ключ должен иметь операцию <

kd-tree

как определить операцию < для тупла (x,y)?

пространство делится бинарно, по очереди по каждому измерению.

Эм, как угодно.

сначала иксы, потом игреки

Другое дело, что он не отражает сути расстояния.

как определить операцию < для тупла (x,y)?

Так как это в плючах делается, к примеру.

в том то и дело

что ближайшего соседа так не найдешь

если ключ - обе координаты, тогда храни в редисе)

Ок

Подумаем

А на макоси есть пиратство?

да)

А на макоси есть пиратство?

ДА