Страницы:Кликните, чтобы указать произвольную страницу123далее
rGlory: (C++) Быстрая сортировка небольшого количества элементов
rGlory
Expert
Автор темы
4086/4170 ответов
23 года на iXBT, с марта 2001
50 фото на iXBT.photo
Чаще пишет РІ "Программирование" (97%)
США, Philadelphia, PA
Инфо Ответить
rGlory ExpertАвтор темы
  11 лет назад / 28 августа 2013 17:22
Возникла задача оптимизации. Есть небольшая последовательность структур (порядка десятка) , которую нужно отсортировать два раза (по двум ключам). Прикол в том, что пересортировывать нужно после изменения только одного элемента (в котором могут измениться два ключевых поля или одно или ни одного), но элемент всегда модифицируется только один. Сейчас использую std::sort, но насколько я помню, он не очень хорошо работает с почти отсортированными последовательностями. Есть идеи у всезнающего all?
loyolla
Member
510/537 ответов
19 лет на iXBT, с декабря 2005
Чаще пишет РІ "Программирование" (95%)
Инфо Ответить
l
loyolla Member
11 лет назад / 28 августа 2013 17:39
Insertion sort ?
Akina
Expert
2861/24216 ответов
25 лет на iXBT, с октября 1999
Чаще пишет РІ "OС и сист. ПО" (16%)
Россия, Зеленоград (Москва)
Инфо Ответить
A
Akina Expert
11 лет назад / 28 августа 2013 17:53
А индекс изменившегося элемента в изначально-сортированном массиве - известен? тогда изъятие этого элемента и простая бинарная вставка. Иначе - один проход пузырька, чтобы найти изменившийся элемент и определить направление его перемещения, а потом опять-таки бинарная вставка.
rGlory
Expert
Автор темы
4087/4171 ответов
23 года на iXBT, с марта 2001
50 фото на iXBT.photo
Чаще пишет РІ "Программирование" (97%)
США, Philadelphia, PA
Инфо Ответить
rGlory ExpertАвтор темы
11 лет назад / 28 августа 2013 18:06
Akina
А индекс изменившегося элемента в изначально-сортированном массиве - известен?
Коненчо нет, исходя из того, что оба ключа, по которым происходит сортировка могут измениться. Кроме того эти ключи не уникальны.
Иначе - один проход пузырька, чтобы найти изменившийся элемент и определить направление его перемещения, а потом опять-таки бинарная вставка.
Причем два раза? Я вот думаю, а не будет быстрее просто пройти по последовательности один раз (походу заменить элемент) и построить обе сортированные последовательности через insertion sort? (спасибо loyolla )
vic_one
Member
294/1037 ответов
19 лет на iXBT, с ноября 2005
Чаще пишет РІ "Программирование" (70%)
Инфо Ответить
v
vic_one Member
11 лет назад / 28 августа 2013 18:10
rGlory
Природа ключей какова (число или объект)?
Если число, то все просто, но для большинства не очевидно.
rGlory
Expert
Автор темы
4088/4172 ответов
23 года на iXBT, с марта 2001
50 фото на iXBT.photo
Чаще пишет РІ "Программирование" (97%)
США, Philadelphia, PA
Инфо Ответить
rGlory ExpertАвтор темы
11 лет назад / 28 августа 2013 18:12
vic_one
Число, цена, если конкретно.
Akina
Expert
2862/24217 ответов
25 лет на iXBT, с октября 1999
Чаще пишет РІ "OС и сист. ПО" (16%)
Россия, Зеленоград (Москва)
Инфо Ответить
A
Akina Expert
11 лет назад / 28 августа 2013 18:24
rGlory
Коненчо нет, исходя из того, что оба ключа, по которым происходит сортировка могут измениться.

Не, годи... После того, как ты ПЕРВЫЙ раз их отсортирил, они расположены в некотором порядке. И каждый соответственно при этой сортировке имеет какой-то номер (который уникален даже для случая, если ключи сортировки совпадают). Изменение ключа до начала второй сортировки не изменяет этого порядкового номера. Так вот именно этот номер - известен?

Кстати... у нас это массив, коллекция, связный список или вообще что?

а не будет быстрее просто пройти по последовательности один раз (походу заменить элемент) и построить обе сортированные последовательности через insertion sort?

Ты себя понял? я - извини, нет...

Для того, чтобы найти местоположение изменившегося элемента (если его индекс неизвестен) - нужно всё равно выполнить один проход. В худшем случае (это самый последний элемент, или наоборот, самый первый, но и после второй сортировки он останется самым первым) - по всей последовательности. Найдя этот элемент, нужно определить, куда его следует переставить, и собственно переставить, это однократная простая вставка, т.е. в худшем случае log2 (это самый последний элемент, и его надо переставлять).

Добавление от 28.08.2013 18:28:

Akina
это самый последний элемент

Дополнение - также и предпоследний. Ибо для определения изменившегося надо просмотреть на 1 элемент вперёд.
Дрон
Member
273/3389 ответов
23 года на iXBT, с мая 2001
Чаще пишет РІ "Общий" (49%)
Великобритания, Лондон
Инфо Ответить
Д
Дрон Member
11 лет назад / 28 августа 2013 18:32
Я не понял use case: когда надо сортировать, когда изменяются элементы, сколько раз это происходит?
Пока это всё похоже на два std::set<Element*> с разными функторами сравнения.
vic_one
Member
295/1038 ответов
19 лет на iXBT, с ноября 2005
Чаще пишет РІ "Программирование" (70%)
Инфо Ответить
v
vic_one Member
11 лет назад / 28 августа 2013 18:39
rGlory
Коненчо нет, исходя из того, что оба ключа, по которым происходит сортировка могут измениться. Кроме того эти ключи не уникальны.
Можно позицию определить по дополнительному индексу, который будет формироваться при сортировке.

Если позиция известна, то можно определить в какую сторону сместится элемент в новом индексе.
rGlory
Expert
Автор темы
4089/4173 ответов
23 года на iXBT, с марта 2001
50 фото на iXBT.photo
Чаще пишет РІ "Программирование" (97%)
США, Philadelphia, PA
Инфо Ответить
rGlory ExpertАвтор темы
11 лет назад / 28 августа 2013 18:59
Akina
И каждый соответственно при этой сортировке имеет какой-то номер (который уникален даже для случая, если ключи сортировки совпадают). Изменение ключа до начала второй сортировки не изменяет этого порядкового номера. Так вот именно этот номер - известен?
Не знаю, зависит от того, как я буду хранить отсортированные элементы. Можно хранить так, что буду знать, но это накладные расходы. В этом в общем-то и вопрос, вернее часть его.
Кстати... у нас это массив, коллекция, связный список или вообще что?
Могу хранить как хочу. До этого хранил в boost::multi_index_container с тремя соотвествующими индексами. Но профайлер показал, что в этом месте затык. Поэтому и оптимизирую. Замена на три std::vector, в первом хранятся элементы, а в двух других отсортированные индексы на первый (через std::sort), показала прирост. Сейчас думаю как бы еще заоптимизировать...
Ты себя понял? я - извини, нет...
Прохожу один раз, походу сразу строю два отсортированных вектора и меняю мой элемент, когда встретился. Итого один проход по моему вектору (но полная сортировка двух векторов). Не будет ли так быстрее для десятка элементов.
Дрон
Я не понял use case: когда надо сортировать, когда изменяются элементы, сколько раз это происходит?
Каждый раз приходит изменение одного элемента из десятка, мне нужно найти новую лучшую цену из десяти с учетом изменения. (вернее не только лучшую но это уже детали).
Пока это всё похоже на два std::set<Element*> с разными функторами сравнения.
Я уже хранил имеенно так в multi_index_container, накладные расходы большие. Я подозреваю, что кэш много мажет, так как по указателю объекты разбросаны.

vic_one
Можно позицию определить по дополнительному индексу, который будет формироваться при сортировке.
Это накладные расходы, стоит ли?
Konstantin Mironovich
Expert
3792/20942 ответов
25 лет на iXBT, с ноября 1999
Чаще пишет РІ "Политика" (35%)
Инфо Ответить
K
Konstantin Mironovich Expert
11 лет назад / 28 августа 2013 19:01
Akina
тогда изъятие этого элемента и простая бинарная вставка
верно. потому что поиск (вставка) по отсортированному быстрее сортировки.
сортировка по второму ключу (при условии первого) - вообще копейки. начинается с той пары, куда произошла вставка и заканчивается как только изменится значение первого ключа.
rGlory
Expert
Автор темы
4090/4174 ответов
23 года на iXBT, с марта 2001
50 фото на iXBT.photo
Чаще пишет РІ "Программирование" (97%)
США, Philadelphia, PA
Инфо Ответить
rGlory ExpertАвтор темы
11 лет назад / 28 августа 2013 19:06
Konstantin Mironovich
сортировка по второму ключу (при условии первого) - вообще копейки.
Я, наверное, неясно выразился. Там две независимых сортировки по разным ключам.
vic_one
Member
296/1039 ответов
19 лет на iXBT, с ноября 2005
Чаще пишет РІ "Программирование" (70%)
Инфо Ответить
v
vic_one Member
11 лет назад / 28 августа 2013 19:14
rGlory
Это накладные расходы, стоит ли?
Вы хотите достичь дзена?
rGlory
Expert
Автор темы
4091/4175 ответов
23 года на iXBT, с марта 2001
50 фото на iXBT.photo
Чаще пишет РІ "Программирование" (97%)
США, Philadelphia, PA
Инфо Ответить
rGlory ExpertАвтор темы
11 лет назад / 28 августа 2013 19:34
vic_one
Вы хотите достичь дзена?
Нет, я хочу заоптимизировать эту функцию. Накладные расходы == замедление. Будут ли эти накладные расходы выше, чем сортировка вставкой двух массивов, мне не понятно. Поэтому и спрашиваю.
vic_one
Member
297/1040 ответов
19 лет на iXBT, с ноября 2005
Чаще пишет РІ "Программирование" (70%)
Инфо Ответить
v
vic_one Member
11 лет назад / 28 августа 2013 19:39
rGlory
Я бы уже проверил.
KPAH
Expert
2772/12099 ответов
23 года на iXBT, с декабря 2001
232 фото на iXBT.photo
Чаще пишет РІ "Общий" (37%)
Россия, Москва
Инфо Ответить
KPAH Expert
11 лет назад / 28 августа 2013 20:05
rGlory
Поэтому и оптимизирую. Замена на три std::vector, в первом хранятся элементы, а в двух других отсортированные индексы на первый (через std::sort), показала прирост. Сейчас думаю как бы еще заоптимизировать...
Зависит от:
1) наиболее вероятного смещения элемента при изменении ключа
2) от стоимости копирования объекта
3) от стоимости функции сравнения

Получается что:
1) если копировать дорого и смещения небольшие - то можно пользоваться двумя списками указателей
2) если копировать дорого, смещения большие и сравнивать ключи дорого - массивы указателей
3) если копирование дешёвое и смещения небольшие, то можно и массив объектов
4) если пересортировка выполняется очень часто, но при этом очень часто ничто никуда не двигается то тоже может быть выгоднее делать через массив*, забив на стоимость сравнения и копирования - высокая когерентность сравниваемых объектов по кэшу может побороть все остальные негативные аспекты такой организации данных.

Все эти структуры данных нужно будет один раз отсортировать и потом поддерживать в сортированном состоянии.

* - возможно будет эффективнее даже сделать два отсортированных массива в которых хранить по копии каждого сортируемого объекта
rGlory
Expert
Автор темы
4092/4176 ответов
23 года на iXBT, с марта 2001
50 фото на iXBT.photo
Чаще пишет РІ "Программирование" (97%)
США, Philadelphia, PA
Инфо Ответить
rGlory ExpertАвтор темы
11 лет назад / 28 августа 2013 20:16
KPAH
Объекты небольшие, две цены (uint64_t) два размера (uint32_t) и enum. Сравнение соотвественно идет по uint64_t, стало быть дешевое.
Я тоже склоняюсь к 4, сейчас пробую.
Спасибо.
Дрон
Member
274/3390 ответов
23 года на iXBT, с мая 2001
Чаще пишет РІ "Общий" (49%)
Великобритания, Лондон
Инфо Ответить
Д
Дрон Member
11 лет назад / 28 августа 2013 23:51
Я бы тогда попробовал осуществить вставку из insertion sort, надеясь на STL. Найти позицию - std::find_if или std::lower_bound - смотря кто быстрее будет для 10 элементов; вставить элемент через insert у вектора, он для POD'ов (а объекты ведь такие?) сведётся к memmove, должно быть быстро. Если тип не POD, можно помочь компилятору, определив нужные трейты.
Warper
Member
398/839 ответов
16 лет на iXBT, с апреля 2008
Чаще пишет РІ "Программирование" (53%)
Инфо Ответить
W
Warper Member
11 лет назад / 29 августа 2013 01:48
Обычный sort, если он основан на стабильном алгоритме, должен работать быстрее для отсортированных данных, но плюс-минус пообменять половину массива - это норма. Быстро - это O(n).

rGlory
Часто ли идут обращения к этому безобразно маленькому набору?
Обращения с поиском по отсортированному списку бинарным поиском тянут на 3-4 сравнения в худшем случае (по прикидкам в среднем 2.6-2.9 сравнений в зависимости от уверенности в наличии искомого значения), а поиск по неотсортированному массиву тянет на 9-10 сравнений в худшем случае (по прикидкам в среднем 5-6 сравнений). Для меньших количеств элементов разница между бинарным и линейным поиском и того меньше.
Любая сортировка требует минимум O(n), то есть она минимум хуже поиска. Перевставка элемента тянет на 9 сравнений и 9 парных перестановок или memmove на 9 элементов и вставку 1 в новое место в худшем случае. И ради оптимизации это будет делаться 2 раза, в дополнение к обновлению обычного вектора (как я понял, в ходе оптимизации появилось уже 3 копии данных).

Стоит ли ради потенциально двукратного ускорения в поиске элемента (в самом наполненном случае) делать обновление в 10+ раз медленней?

Если стоит, лучше не полагаться на insertion_sort, он делает обмены от текущей позиции до новой позиции, в лучшем случае по одному элементу за шаг сравнение, плюс сравнивает со всеми предыдущими элементами. Для перевставки элемента из середины придётся "схлопывать" массив и обменивать примерно половину элементов.
Я бы вообще забыл про векторы в данном случае, коли уж такие оптимизациии попёрли
1) Ищем позицию элемента i.
2) Сравниваем старое и новое значение ключа. Равно - конец, вставляем новое значение на месте.
3) Больше/меньше - ищем новую позицию по остаткам массива до/после, бинарным поиском.
4) memmove от i+-1 до новой позиции (включительно) на размер одного объекта (предполагаем, что они movable)
5) Вставляем обновлённый элемент в новую позицию
vertur
Member
2575/3001 ответов, #5 в рейтинге
16 лет на iXBT, с марта 2008
Чаще пишет РІ "Программирование" (52%)
Гондурас, default city
Инфо Ответить
v
vertur Member
11 лет назад / 29 августа 2013 03:13
А что мешает использовать два красно-черных дерева по двум индексам ? Тогда и сортировка ненужна будет вовсе.


А так да, сначала воткнуть куда ни попадя буст, а потом вот и появляются такие темы.
rGlory
Expert
Автор темы
4093/4177 ответов
23 года на iXBT, с марта 2001
50 фото на iXBT.photo
Чаще пишет РІ "Программирование" (97%)
США, Philadelphia, PA
Инфо Ответить
rGlory ExpertАвтор темы
11 лет назад / 29 августа 2013 04:55
Warper
Часто ли идут обращения к этому безобразно маленькому набору?
Часто. И таких наборов много.
Стоит ли ради потенциально двукратного ускорения в поиске элемента (в самом наполненном случае) делать обновление в 10+ раз медленней?
Сортировка делается не для поиска элемента, а для вычисления лучшей цены. Как сделать такое вычисление без сортировки, я не знаю. Во всяком случае пока. Поэтому и сортирую.
MBo
Member
237/281 ответов
23 года на iXBT, с ноября 2001
Чаще пишет РІ "Программирование" (79%)
Инфо Ответить
M
MBo Member
11 лет назад / 29 августа 2013 06:44
rGlory
Сортировка делается не для поиска элемента, а для вычисления лучшей цены.

Если нужна одна лучшая цена, то напрашивается очередь по приоритетам.
rGlory
Expert
Автор темы
4094/4178 ответов
23 года на iXBT, с марта 2001
50 фото на iXBT.photo
Чаще пишет РІ "Программирование" (97%)
США, Philadelphia, PA
Инфо Ответить
rGlory ExpertАвтор темы
11 лет назад / 29 августа 2013 06:51
MBo
Если нужна одна лучшая цена, то напрашивается очередь по приоритетам.
Если бы одна, я бы за один проход нашел/посчитал цену/количество по обоим направлениям. К сожалению там немного сложнее, нужно найти две лучшую и уровня N и количество для них.
Konstantin Mironovich
Expert
3793/20944 ответов
25 лет на iXBT, с ноября 1999
Чаще пишет РІ "Политика" (35%)
Инфо Ответить
K
Konstantin Mironovich Expert
11 лет назад / 29 августа 2013 09:38
где-то напоминает реальную задачку Гугля - кэширование запросов. кроме всего трудность еще в том, что статистика запросов меняется с течением дня, недели.
если модификации частые и "разнообразные", то я бы не двигал данные, а работал с указателями. ну или цену-размер засунул в одно int64 число (сложно понять почему на цену нужно 64 разряда.)
bislomet
Member
214/449 ответов
17 лет на iXBT, с ноября 2007
4 фото на iXBT.photo
Чаще пишет РІ "Программирование" (66%)
Германия, мой адрес - не дом и не улица...
Инфо Ответить
b
bislomet Member
11 лет назад / 29 августа 2013 09:47

Konstantin Mironovich
сложно понять почему на цену нужно 64 разряда
где-то в статье про первые версии .net по поводу 64-битной арифметики было написано:
(примерно, это не цитата)"наконец-то возможно представить стандартными средствами нац. долг США"
Даже страшно представить, что именно сортирует rGlory
rGlory
Expert
Автор темы
4095/4179 ответов
23 года на iXBT, с марта 2001
50 фото на iXBT.photo
Чаще пишет РІ "Программирование" (97%)
США, Philadelphia, PA
Инфо Ответить
rGlory ExpertАвтор темы
11 лет назад / 29 августа 2013 17:27
Konstantin Mironovich
то я бы не двигал данные, а работал с указателями
В том то и дело, что передвигать и работать с данными небольшого размера, но находящимися в участке непрерывной памяти, это может быть быстрее, из-за кэша.
ну или цену-размер засунул в одно int64 число
Что это даст?
bislomet
Даже страшно представить, что именно сортирует rGlory
Ничего страшного. Просто у нас класс, который имплементирует цену в виде fixed point десятичного числа, с 4 разрядами после запятой. int32_t / 10000 в принципе может переполниться.
Konstantin Mironovich
Expert
3795/20947 ответов
25 лет на iXBT, с ноября 1999
Чаще пишет РІ "Политика" (35%)
Инфо Ответить
K
Konstantin Mironovich Expert
11 лет назад / 29 августа 2013 18:12
rGlory
в случае равновероятного ввода у вас там n/2 сдвигов в среднем при каждой модификации. с кэшем не так все просто в многоядерной конфигурации.
vic_one
Member
306/1049 ответов
19 лет на iXBT, с ноября 2005
Чаще пишет РІ "Программирование" (70%)
Инфо Ответить
v
vic_one Member
11 лет назад / 29 августа 2013 20:09
rGlory
Просто у нас класс, который имплементирует цену в виде fixed point десятичного числа, с 4 разрядами после запятой. int32_t / 10000 в принципе может переполниться.
"траекторный шаблон" определен?

Подсказываю 32 бита это 14 разрядов под 4 цифры после запятой и 18 до. Максимальное число 262143.9999
rGlory
Expert
Автор темы
4099/4183 ответов
23 года на iXBT, с марта 2001
50 фото на iXBT.photo
Чаще пишет РІ "Программирование" (97%)
США, Philadelphia, PA
Инфо Ответить
rGlory ExpertАвтор темы
11 лет назад / 29 августа 2013 20:27
vic_one
"траекторный шаблон" определен?
Осильте сначала ту тему, потому будете бросаться термином невиданной мощи где не попадя.
Подсказываю 32 бита это 14 разрядов под 4 цифры после запятой и 18 до. Максимальное число 262143.9999
Я как бы в курсе (на самом деле 214748.3647). Но инструменты бывают разные, цена некоторых может и перевалить. Кроме того этот тип может участвовать в вычислениях.
jooher
Member
1253/1936 ответов
20 лет на iXBT, с ноября 2004
Чаще пишет РІ "Программирование" (64%)
Россия
Web-страница
Инфо Ответить
j
jooher Member
11 лет назад / 29 августа 2013 20:49
rGlory
инструменты бывают разные, цена некоторых может и перевалить
Помница, у какого-то российского банка были акции и по 10-6 копеек. Такшта и за 4 разряда может перевалить
Как раз цены-то имеет смысл держать в плавающих точках, тем более что на больше-меньше их можно сравнивать целочисленными инструкциями.
Konstantin Mironovich
Expert
3797/20950 ответов
25 лет на iXBT, с ноября 1999
Чаще пишет РІ "Политика" (35%)
Инфо Ответить
K
Konstantin Mironovich Expert
11 лет назад / 29 августа 2013 20:55
jooher
Помница, у какого-то российского банка были акции и по 10-6 копеек. Такшта и за 4 разряда может перевалить
мы эту тему как-то обсуждали. я тогда говорил, что в той конторе где я работал, система внутри работала с 6ю разрядами, а наружу выдавала 4.
Ваш ответ:

Нет значка Нет значка Р’РѕС‚ тут! Лампочка Восклицание Р’РѕРїСЂРѕСЃ Класс! Улыбка Злость Огорчение РџРѕРіРѕРІРѕСЂРёРј? Краснею Подмигивание Ругаю РћРґРѕР±СЂСЏСЋBIUdelSxsupxsuboffsp spoilerqurlimgvideo• list1. list1 codeprecenter-hr-rusQWE→ЙЦУ
файлыочистить
Ваше имя: Авторизуйтесь Предпросмотр В полную форму
вставить выделенную цитату в окно ответа
Если Вы считаете это сообщение ценным для дискуссии (не обязательно с ним соглашаться), Вы можете поблагодарить его автора, а также перечислить ему на счет некоторую сумму со своего баланса (при отзыве благодарности перечисленная сумма не будет вам возвращена).
Также вы можете оценить сообщение как неудачное.
В течение суток можно 20 раз оценить сообщения разных участников (купите Premium-аккаунт, либо оплачивайте оценки сверх лимита).
Если Вы считаете это сообщение ценным для дискуссии (не обязательно с ним соглашаться), Вы можете поблагодарить его автора, а также перечислить ему на счет некоторую сумму со своего баланса (при отзыве благодарности перечисленная сумма не будет вам возвращена).
Также вы можете оценить сообщение как неудачное.
В течение суток можно 20 раз оценить сообщения разных участников (купите Premium-аккаунт, либо оплачивайте оценки сверх лимита).
Страницы:Кликните, чтобы указать произвольную страницу123далее