Как лучше сортировать данные в которых не отсортирован только 1 объект?

Question

[Pragma Games]

Всем привет. Есть массив позиций объектов (Xpos, Ypos,Zpos), данный массив должен быть всегда отсортирован по возрастанию Ypos. В любой момент времени любой из объектов может поменять свою позицию, мы знаем что это за объект. После каждого изменения массив нужно сортировать, каким способом лучше это сделать ? Либо возможно вообще стоит использовать двусвязный список и если объект меняется удаляем его из списка и вставляем в нужную позицию ?

Comments

[Akina]

Ответ зависит от того, для чего нужен массив и как он используется. Может, и односвязного списка хватит...

[Pragma Games]

Akina, Там хранятся позиции платформ, когда персонаж теряет из виду нижние платформы они перемещаются вверх через определенное время. Но мне точно нужно знать какие платформы находятся ниже персонажа, а какие выше, что бы спавнить врагов выше персонажа и вне поля его видимости, для этого я сортирую список и бинарным поиском узнаю какие платформы выше персонажа. В данный момент позиции хранятся в List, все работает так как я хочу, но мне интересен момент скорости работы разных решений этого вопроса. Большое спасибо за такой быстрый ответ )

[Akina]

Ну раз надо и туда, и сюда, то да, двусвязный список, возможно, и подойдёт.

Вот только для применения именно бинарного поиска надо хранить либо сам список, либо индексный массив к нему в физически сортированном порядке. Так что тут скорее более оптимальным будет физически упорядоченный индексный массив (ну не гонять же сами объекты - они пухлые, поди). А при перемещении элемента придётся физически перемещать все записи между новой и старой позициями.

Кстати, а каков вообще порядок размера массива? десятки записей? сотни? тысячи? И каково при этом среднее смещение элемента?

PS. По сути Ordered List именно это и делает. Другой вопрос - насколько велики у него накладные расходы на поддержание списка в сортированном порядке, и будет ли вменяемый профит, если создавать свой ordered list вручную...

[Pragma Games]

Спасибо за ответ, он очень помог. Еще раз спасибо за такую оперативность )

Answer 1

[Wataru]

Нужно делать вставку, как в insert sort. Вы написали, что используете бинпоиск в этом массиве, поэтому реализовывать его на связных списках нельзя. Поэтому у вас будет массив и вы за один проход сможете переместить элемент куда надо.

Самое быстрое - это обработать 2 случая, элемент изменил свое значение вниз или вверх. Потом циклом или влево или вправо надо swap-ать его со следующим, пока они стоят не в том порядке. Можно чуть соптимизировать и выкинуть лишние операции из каждого свап-а:

// a[moved] увеличился.
tmp = a[moved];
for (i = moved+1; i < a.size() && a[i] < tmp; ++i) {
  a[i-1] = a[i];
}
a[i-1] = tmp;

Comments

[Pragma Games]

Спасибо за ваш ответ, он очень помог. А если не привязываться к тому решению которое есть у меня, как бы вы решали подобную задачу ?

[Wataru]

MARK KURDA, Я так понял, у вас каждый раз нижняя платформа перемещается в самый верх? Тогда их даже сортировать не надо. Используйте циклический массив. Сами платформы вообще не перемещаются в массиве - у вас будет 2 индекса: начало массива и конец. Они могут быть в массиве как угодно: например, начало - индекс 5, конец - индекс 4. И получается, что платформы в массиве по порядку идут так: {5, 6, 7, ..., n-1, 0, 1, 2, 3, 4}

В таком массиве можно точно также устраивать бинарный поиск. Просто забудьте что ваш массив циклический. Когда вам нужно обратиться к i-тому по порядку элементу вы обращаетесь к (be+i)% n индексу в массиве.

Потом, вам не нужен бинарный поиск, если игрок не может телепортироватся. Можно поддерживать индекс платформы, на которой игрок находится. И менять его при движении персонажа.

[Pragma Games]

Идею понял, она классная. А если мне потом придется уменьшить общее количество платформ ?

[Wataru]

MARK KURDA, Можно и уменьшать и увеличивать количество, если вы с конца удаляете/добавляете. Для этого и есть 2 указателя на начало и на конец массива. При добавлении платформы в конец надо сдвинуть конечный указатель. Пока всего в циклическом массиве элементов не больше, чем размер выделенного массива - все работает.

Вот если вы новую платформу в середину добавляете или удаляете, то тут уже надо смотреть на то, как часто у вас какие операции происходят. Может быстрее будет как в моем ответе вставкой делать. Или будет лучше вместо массива вообще использовать бинарное балансированное дерево (какой-нибудь std::set в C++). В этой структуре можно добавлять, удалять что угодно и искать ближайшую к игроку платформу за логарифм и итерироваться по всем платформам почти также быстро, как в массиве. Вам даже ничего своего писать, скорее всего не придется - просто использовать стандартную структуру языка.

[Pragma Games]

Wataru, Да, я все понял, еще раз огромное спасибо за ваш ответ и за оперативность.

[Руслан .]

MARK KURDA, Wataru, Тут есть нюанс. Если используем массив, то при вставке нового элемента есть еще накладные расходы на увеличение длинны массива и это может быть по затрата больше чем все остальное.

Тут наверное (если нужна сортировка только по Ypos, а другие атрибуты могут идти вразнобой) можно использовать что-то вроде hashmap, где key это Ypos, а value сам объект со всеми атрибутами.
По идее, если есть много объектов с повторяющимися Ypos, то сортировать список Ypos будет выгоднее (он будет сильно короче чем список всех объектов) чем гонять строки в большом массиве всех объектов. И так как hasmmap внутри содержит связанный список (в Java), то при добавлении объекта с уже имеющимся Ypos не нужно будет двигать элементы по массиву.

[Wataru]

Руслан .,

Если используем массив, то при вставке нового элемента есть еще накладные расходы на увеличение длинны массива и это может быть по затрата больше чем все остальное.

Но массив можно изначально завести на максимальное количество элементов. Или использовать какой-нибудь нормальный массив, вроде std::vector в C++, который за счет немного большего потребления памяти позволяет добавлять новые элементы за константное время, даже с учетом переаллокации.

[Руслан .]

Wataru, Все так, но часто максимальный размер массива не известен, ну и сразу резервировать большой объем на будущее, это не сосем эффективно, т.к. в точке память может понадобиться кому-то другому.

[Pragma Games]

Руслан ., Код пишу на С#, на каком решении оптимальнее остановиться ? Изначально 200 объектов, нижний предел до которого они могут опуститься 150, высший предел 250. На счет затрачиваемой памяти на один объект ничего не могу сказать. И да, Ypos в каждой группе состоящих из 8-16 объектов будет одинаковым.

[Wataru]

MARK KURDA, Я бы завел массив на 250 платформ и двумя указателями в нем реализовал циклический массив.

[Pragma Games]

Wataru, Понял

[Руслан .]

MARK KURDA, учитывая что у вас количество элементов небольшое фиксированный массив вполне подходит, чтобы не усложнять решение.
Только тут два нюанса:
1. Фиксированный массив - если потребуется расширить массив вам придется изменять код.
2. Так как у вас стоит условие, что элементы д.б. отсортированы по Ypos, то циклический массив может не подойти, т.е. элементы достигшие конца массива с наибольшими Ypos будут писаться в начальные элементы массива, там где обычно минимальные Ypos, что-то вроде 4-5-1-2-3., а это уже приводит к нарушению сортировки.

Более сложное решение с коллекциями более универсально, т.к. размер коллекции меняется динамически по мере использования. Ну и так как ключей минимум в 8 раз меньше чем всех элементов, то сортировать такой массив быстрее и искать нужно по нему тоже быстрее. Хотя на ваших текущих объемах возможно это оверинжениринг.

[Pragma Games]

Руслан ., Я понял , спасибо за ответ