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
Рукотворные деревья штука симпатичная, но бес всякой полезной обвязки, которая есть у контейнеров стандартной библиотеки узко применимая. А писать полноценный класс как то долго.

Новые блоги и статьи Все статьи Все блоги /
Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .	Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .
интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .

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

	std::map для k-d дерева 28.04.2021, 20:06. Показов 2071. Ответов 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 фрилансер 6495 / 5724 / 1133 Регистрация: 11.10.2019 Сообщений: 15,286
	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 фрилансер 6495 / 5724 / 1133 Регистрация: 11.10.2019 Сообщений: 15,286
	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