std::map для k-d дерева

@squareroot · Регистрация: 19.10.2019

Студворк — интернет-сервис помощи студентам

Добрый день.
Хочу найти SOTA для реализации K-D деревьев.
Базовые варианты как я понимаю - либо самому делать структуру, либо использовать что то из стандартной библиотеки.
Самый логичный вариант попробовать сочинить что то с использованием std::map, но компаратор у std::map всего один и этот компаратор как должен знать по какой оси ему проводить сравнение. В общем, если не лезть в недра либы, а обойтись стандартным апи пока непонятно как это делать.
Сделать свою структурку не проблема, но в стандартной библиотеки уже все оптимизировано и навешено всяких пряников, а тут надо или обойтись скромными возможностями или писать самому.
Есть конечно вариант со сторонними библиотека, например CGAL, но хочется обойтись стандартной библиотекой.

Добавлено через 5 минут
Вот если было понимание как находить корневой узел, то это облегчило бы дело.
Никто ведь не запрещает использовать компаратор как статический оператор.

Добавлено через 13 минут
Пока склоняюсь к мысли создать класс наследник от std::map и переопределить все методы, которые приводят к поиску т.е. это оператор [], find, at
В переопределенных методах сбрасывать циклический счетчик осей и вызывать основной метод.
Но насколько это решение корректное ?

@squareroot · 28.04.2021, 22:42 **[ТС]**

Я правда вынес за скобки вопрос инициализации мапы.

Добавлено через 2 минуты
Алексей1153, Можно поподробнее.
Взяли получили хеш от чего то там и как они помогу в поиске ближайшей точки ?
Есть геохеши, но это не имеет никакого отношения к обычным хешам.

Алексей1153 · 28.04.2021, 22:54

Сообщение от squareroot

получили хеш от чего то там

да просто уникальный uint64_t id точки. Основная мапа - это просто свалка точек. Всё интересное - в индексах. А каждый индекс представляет собой связь id-> координата

Понятно, что нет возможности узнать, в каком первом из трёх индексов (x,y,z) нужно будет начинать искать.

Берётся любой, там ищем ближайшие точки.
Берём второй, там ищем ближайшие точки.
Потом третий

пересечение трёх поисков - результат

основная затрата времени тут будет на поиск пересечения результатов

@squareroot · 28.04.2021, 22:59 **[ТС]**

Алексей1153, Есть k-d дерево.
Вы придумали что-то лучшее ? Тогда Вам надо срочно начинать диссер писать.
Но тут тема про k-d.

Алексей1153 · 28.04.2021, 23:21

Сообщение от squareroot

диссер писать

лень

Добавлено через 1 минуту
squareroot, мой вариант не будет, конечно, самый супер-пупер быстрым и оптимальным, но он рабочий на 100%. И его даже можно использовать при проверке супер-пуперского быстрого алгоритма

@squareroot · 28.04.2021, 23:24 **[ТС]**

Алексей1153, Спасибо за желание помочь, но я в ~~название темы~~ заглавном посте не просто так указал слово SOTA

Алексей1153 · 28.04.2021, 23:34

squareroot, кстати, интернет не подсказал мне, что сие обозначает.

Не по теме:

Там есть варианты:

1)S.O.T.A – Stalker Online Time Anomaly
2)компания по втюхиванию женщинам краски
3)магазин электроники в Киеве
4)некое СМИ

описание дерева в вики нашлось, но как я там увидел структуру описания узла, я сильно засомневался в его эффективности при реализации на C++

@squareroot · 28.04.2021, 23:39 **[ТС]**

Алексей1153, https://en.wikipedia.org/wiki/State_of_the_art

Добавлено через 3 минуты
Наверно куча даёт больше гибкости чем мапа. Наверно стоит подумать в эту сторону.

Алексей1153 · 28.04.2021, 23:46

выражение State-of-the-art - означает нечто новейшее, современнейшее, насколько я понял

ну, ок, что на эту тему нам говорит интернет

даже статья на всеми любимом хабре имеется

@squareroot · 28.04.2021, 23:59 **[ТС]**

Алексей1153, Я ее видел, но хотелось проверить можно ли брать за основу std::map
Рукотворные деревья штука симпатичная, но бес всякой полезной обвязки, которая есть у контейнеров стандартной библиотеки узко применимая. А писать полноценный класс как то долго.

Новые блоги и статьи Все статьи Все блоги /
Транскрипция 55-минутного видео через Whisper: WhisperDesktop облажался, спас Google Colab[ anaschu 01.06.2026 Понадобилось получить текст из свежезагруженного видео на YouTube. Казалось бы, задача на пять минут. Заняла полтора часа. Делюсь опытом — может кому пригодится последовательность решений. . . .	21 мат мед. Планы на развитие модели здравоСохранения anaschu 01.06.2026 AnyLogic: план развития симуляционной модели рабочего коллектива — динамический абсентеизм, реальные данные, три сценария сравнения Продолжаю серию постов о дискретно-событийной модели рабочего. . .	20. Мат мед. Абсентеизм как отдельный тип простоя anaschu 29.05.2026 Апдейт модели: исправленные баги, абсентеизм и новые механизмы Продолжаю развивать ранее описанную модель рабочего коллектива на AnyLogic. За последние несколько дней был проведён серьёзный. . .	19. здоровье, усталость и психотип работника влияют на производительность предприятия, и наоборот, производительность на здоровье, усталось и психотип anaschu 28.05.2026 Дискретно-событийная модель рабочего коллектива на AnyLogic: здоровье, выгорание, психотипы и микростимуляция Привет, коллеги. Хочу поделиться итогами нескольких недель работы над симуляционной. . .
"Прокси" для последовательного порта Eddy_Em 28.05.2026 Эту штуку написал я достаточно давно. Но сейчас вот понадобилось настроить датчик грозы, но при этом не отключать его от "метеодемона". Соответственно, надо запустить этот "прокси": метеодемон будет. . .	Рефакторинг программы уравнивания. Massaraksh7 26.05.2026 Пример по предыдущей записи в блоге. Но, надо заметить, что, во-первых, там оптимизация не только математики, но и работы с базой данных, и с графами, а во-вторых, это ещё не всё.	Использование TThread в Lazarus для математических вычислений. Massaraksh7 25.05.2026 Производя рефакторинг своих программ на предмет ускорения их работы, обратил внимание на такой аспект, как сокращение времени матвычислений. Дело в том, что приходится работать с большими матрицами. . .	Модель здравосохранения 18. Чем здоровее работник, тем быстрее выгорает anaschu 24.05.2026 Имитационная модель корпоративного здравоохранения: что показывает математика Сегодня в модели рабочего коллектива на AnyLogic появились три новые механики — выгорание через накопленную усталость,. . .

@squareroot 13 / 13 / 1 Регистрация: 19.10.2019 Сообщений: 607

	std::map для k-d дерева 28.04.2021, 20:06. Показов 2060. Ответов 28 Метки нет (Все метки) Добрый день. Хочу найти SOTA для реализации K-D деревьев. Базовые варианты как я понимаю - либо самому делать структуру, либо использовать что то из стандартной библиотеки. Самый логичный вариант попробовать сочинить что то с использованием std::map, но компаратор у std::map всего один и этот компаратор как должен знать по какой оси ему проводить сравнение. В общем, если не лезть в недра либы, а обойтись стандартным апи пока непонятно как это делать. Сделать свою структурку не проблема, но в стандартной библиотеки уже все оптимизировано и навешено всяких пряников, а тут надо или обойтись скромными возможностями или писать самому. Есть конечно вариант со сторонними библиотека, например CGAL, но хочется обойтись стандартной библиотекой. Добавлено через 5 минут Вот если было понимание как находить корневой узел, то это облегчило бы дело. Никто ведь не запрещает использовать компаратор как статический оператор. Добавлено через 13 минут Пока склоняюсь к мысли создать класс наследник от std::map и переопределить все методы, которые приводят к поиску т.е. это оператор [], find, at В переопределенных методах сбрасывать циклический счетчик осей и вызывать основной метод. Но насколько это решение корректное ? 0

@squareroot 13 / 13 / 1 Регистрация: 19.10.2019 Сообщений: 607
	28.04.2021, 22:42 [ТС]
	Я правда вынес за скобки вопрос инициализации мапы. Добавлено через 2 минуты Алексей1153, Можно поподробнее. Взяли получили хеш от чего то там и как они помогу в поиске ближайшей точки ? Есть геохеши, но это не имеет никакого отношения к обычным хешам. 0

@squareroot 13 / 13 / 1 Регистрация: 19.10.2019 Сообщений: 607
	28.04.2021, 22:59 [ТС]
	Алексей1153, Есть k-d дерево. Вы придумали что-то лучшее ? Тогда Вам надо срочно начинать диссер писать. Но тут тема про k-d. 0

@squareroot 13 / 13 / 1 Регистрация: 19.10.2019 Сообщений: 607
	28.04.2021, 23:24 [ТС]
	Алексей1153, Спасибо за желание помочь, но я в ~~название темы~~ заглавном посте не просто так указал слово SOTA 0

Алексей1153 фрилансер 6486 / 5714 / 1133 Регистрация: 11.10.2019 Сообщений: 15,234
	28.04.2021, 23:34
	squareroot, кстати, интернет не подсказал мне, что сие обозначает. Не по теме: Там есть варианты: 1)S.O.T.A – Stalker Online Time Anomaly 2)компания по втюхиванию женщинам краски 3)магазин электроники в Киеве 4)некое СМИ описание дерева в вики нашлось, но как я там увидел структуру описания узла, я сильно засомневался в его эффективности при реализации на C++ 0

@squareroot 13 / 13 / 1 Регистрация: 19.10.2019 Сообщений: 607
	28.04.2021, 23:39 [ТС]
	Алексей1153, https://en.wikipedia.org/wiki/State_of_the_art Добавлено через 3 минуты Наверно куча даёт больше гибкости чем мапа. Наверно стоит подумать в эту сторону. 0

Алексей1153 фрилансер 6486 / 5714 / 1133 Регистрация: 11.10.2019 Сообщений: 15,234
	28.04.2021, 23:46
	выражение `State-of-the-art` - означает нечто новейшее, современнейшее, насколько я понял ну, ок, что на эту тему нам говорит интернет даже статья на всеми любимом хабре имеется 0

@squareroot 13 / 13 / 1 Регистрация: 19.10.2019 Сообщений: 607
	28.04.2021, 23:59 [ТС]
	Алексей1153, Я ее видел, но хотелось проверить можно ли брать за основу std::map Рукотворные деревья штука симпатичная, но бес всякой полезной обвязки, которая есть у контейнеров стандартной библиотеки узко применимая. А писать полноценный класс как то долго. 0