Эффективный алгоритм сортировки 2d точек в набор границ Парето
У меня есть набор точек, которые мне нужно отсортировать по набору границ Парето, пример ниже:
У меня есть способ сделать это, но для большого количества точек, более 60 тысяч точек, он становится очень медленным.
Метод, который я использую, включает итеративный вызов библиотечной функции, которая может найти один фронт Парето:
- Начните со всех пунктов
remaining_points: Vec<Point> - Создайте пустой
all_frontiers: Vec<Vec<Point>> - Отфильтруйте точки на фронте Парето
frontier: Vec<Point>и добавьте их вall_frontiers. - Удалить
frontierбаллов изremaining_points - Повторяйте 3-4, пока
remaining_points.is_empty()
Я не знаю (и не смог найти) лучшего подхода к этой проблеме. Может ли кто-нибудь дать предложения?
Перекрестная публикация: stackoverflow.com/q/78881630/781723 , cs.stackexchange.com/q/169391/755 . Пожалуйста не размещайте один и тот же вопрос на нескольких сайтах.
—
18.08.2024 08:11
Стоит ли изучать PHP в 2026-2027 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
2
63
1
Перейти к ответу
Данный вопрос помечен как решенный
Ответы 1
Ответ принят как подходящий
Я пришел к более быстрому в 10 раз алгоритму, специфичному для моего варианта использования (целочисленные точки, 2d, точки часто имеют одно и то же значение x или y).
- Найдите размерность с наименьшим диапазоном (x или y)
- Группируйте точки по этому измерению в сегменты.
- Сортировка каждой группы по другому измерению
- Просмотрите первую точку каждой группы и вычислите границу Парето.
- Для каждой точки границы удалите ее из группы в сегменте. Если ведро пусто, также удалите его.
- Цикл 4-5, пока ведра не опустеют.
Другие вопросы по теме
Можно ли упростить сравнение координатных расстояний (евклидова расстояния)?
Оптимизируйте идентификацию квантилей по столбцам массива
Есть ли эффективный способ извлечь фрагмент трехмерного массива?
Есть ли более быстрый способ написать код для получения множества случайных выборок из 1:N?
Как оптимизировать следующую структуру как векторизованную операцию
Оценка производительности элементов в функции R
Как рассчитать максимальный параллелизм узлов в DAG?
Синтаксический сахар для синхронизации блока кода в C++
C++ Существует ли быстрый многомерный массив, который позволяет использовать подмассивы разного размера?
Обеспечивают ли левый и правый сдвиг лучшую производительность по сравнению с операциями умножения и деления?
Похожие вопросы
Крупнейший продукт в сетке «Не в том же направлении»
Как рассчитать максимальный параллелизм узлов в DAG?
Корректность алгоритма решения задачи трехсторонней непересекаемости
Реализация приоритетной очереди с помощью Dijkstra
Возвращает ли low_bound() один и тот же результат с обратными итераторами вектора в порядке возрастания и прямыми итераторами вектора в порядке убывания?
Почему тип итератора `std::views::transform` не кажется детерминированным типом?
Сжатие массива элементов при уменьшении размера каждого элемента с 8 бит до 3 бит
Числа, встречающиеся дважды в одном и том же столбце и строке в программе доски судоку
Итерация вперед или назад в зависимости от порядка итераторов
Как я могу обнаружить повторяющиеся фрагменты целых чисел в Go?
Отсортируйте точки по max(x,y)+3*min(x,y)/8 (или просто /2) в качестве прокси для hyp(x,y), и вам следует выполнить поиск точек на внешних границах график намного более локальный.