Войти
ПрограммированиеФорумОбщее

Быстьрый доступ к члену массива после std::sort()

Страницы: 1 2 Следующая »
#0
10:19, 15 сен. 2020

Допустим, есть у меня массив объектов. Я знаю индекс нужного объекта в массиве, и через этот индекс могу ссылаться на объект.
Сортирую массив посредством std::sort и все, что дальше? Теперь я не знаю где нужный мне объект, так как теперь по его индексу может находится любой другой.

Можно, конечно, хранить в объекте уникальный ключ и после сортировки искать в массиве этот ключ и так определять местоположение объекта, но нельзя ли как-нибудь быстрее?
Как в геймдеве поступают?


#1
(Правка: 10:36) 10:34, 15 сен. 2020

во-первых, нормальное решение — ясное дело, не ссылаться по индексу на элементы массива, который ты сортируешь.

во-вторых, индексация объектов, порядок и время жизни которых непостоянны, нормально(за O(1)) реализуются через sparse set.

#2
(Правка: 10:39) 10:35, 15 сен. 2020

std::find()

#3
(Правка: 10:38) 10:38, 15 сен. 2020

ещё один вариант — вместо сортировки массива объектов, сортируй сразу массив своих индексов, а функцию компаратора передавай сравнение объектов по этим индексам. это, кстати, гораздо эффективнее, чем сами объекты ворочать и индексы после сортировки как раз будут корректные.

#4
(Правка: 11:01) 11:00, 15 сен. 2020

Suslik
Я так понял эффективность Sparse Set обусловлена повышенным расходом памяти?

> ещё один вариант — вместо сортировки массива объектов, сортируй сразу массив
> своих индексов, а функцию компаратора передавай сравнение объектов по этим
> индексам. это, кстати, гораздо эффективнее, чем сами объекты ворочать и индексы
> после сортировки как раз будут корректные.
std::sort ворочает сами объекты? Я-то думал он как-то хитро работает с адресами объектов, учитывая как хвалят его скорость.
Тогда, конечно, попробую сортировать массив индексов.

#5
(Правка: 11:26) 11:23, 15 сен. 2020

Suslik
> ещё один вариант — вместо сортировки массива объектов, сортируй сразу массив
> своих индексов, а функцию компаратора передавай сравнение объектов по этим
> индексам. это, кстати, гораздо эффективнее, чем сами объекты ворочать и индексы
> после сортировки как раз будут корректные.
Попробовал - работает.
И хотя теперь вместо objects[n] местами надо будет использовать objects[indexesObjects[n]], полагаю, оно того стоит.
Ну и не забывать теперь, что при вставке, удалении, добавлении - надо обрабатывать два массива вместо одного.

Все во славу Святой Оптимизации. :)

#6
11:25, 15 сен. 2020

https://skypjack.github.io/2019-09-25-ecs-baf-part-5/

#7
11:38, 15 сен. 2020

lookid
> https://skypjack.github.io/2019-09-25-ecs-baf-part-5/
Ознакомился.
Я правильно понимаю что такую достаточно сложную вещь как sparse set имеет смысл использовать когда количество элементов массива сотни или тысячи?

#8
12:06, 15 сен. 2020

MikeNew
> std::sort ворочает сами объекты?
что в контейнере лежит то и ворочает, если у тебя там указатели то и перемещаться будут только указатели. Главное компаратор указать, а то отсортируешь адреса указателей.

#9
1:51, 16 сен. 2020

Suslik
Если в объекте легко выделить ключ, по которому сортируем,- может быть быстрее сортировать массив структур {key;payload} (где payload - индекс в массиве), чем массив индексов, из-за лучшей локальности (отсутствует лишняя индирекция).

Мне в radix sort помогало. Для std::sort - возможно должно ещё сильнее помогать, т. к. O(n*log n) индирекций.

#10
4:53, 16 сен. 2020

MikeNew
> при вставке, удалении, добавлении - надо обрабатывать два массива вместо одного.
Интересно, а как ты реализовал удаление?

#11
6:21, 16 сен. 2020

Можно еще такой трюк провести - std::sort обменивает элементы с помощью std::swap, поэтому если std::swap перегрузить для своих типов объектов, то можно полностью контролировать то что с ними происходит во время перестановок.
Например реально обновить какую то информацию в самом объекте о том какой он индекс имеет.
Но это как бы трюк в обратную сторону, т.е. для сабжа конкретно не подходит, но в целом полезно иметь ввиду в подобного рода задачах.

#12
7:02, 16 сен. 2020

san
> Интересно, а как ты реализовал удаление?
Пока никак, руки не дошли.
Должно же получится, если в самих объектах дополнительно хранить индексы этих объектов в массиве. Через день-два попытаюсь проверить.

#13
(Правка: 9:09) 9:09, 16 сен. 2020

Suslik
> вместо сортировки массива объектов, сортируй сразу массив своих индексов, а
> функцию компаратора передавай сравнение объектов по этим индексам.
Суслик дело говорит.

Сортировать сам пул объектов вам надо, только если у вас есть какая-то доказанная гипотеза о частоте доступа. Сортировать надо срез данных для вывода, вроде {индекс, текстура, геометрия, удалённость от камеры} для рендеринга. Или {индекс, имя, здоровье} для списка самых раненых.

#14
16:29, 18 сен. 2020

MikeNew
> Как в геймдеве поступают?


хранят std::vector<Entity*> - при вставке удалении сортируют - поиск по binar _search

Страницы: 1 2 Следующая »
ПрограммированиеФорумОбщее