Группировка быстрее сортировки
От: PlushBeaver  
Дата: 13.08.21 20:04
Оценка:
Задача: дан массив длиной N из объектов, у которых есть признак-целое число; нужно получить группы объектов, у которых значения признака равны.

Очевидно, задача решаема сортировкой. Но задумался, может ли в принципе быть более быстрое решение за счет того, что порядок групп и объектов в группе не задан наперед. Последнее, например, позволяет использовать нестабильные сортировки. Эквивалентна ли эта задача сортировке? Я вижу отличие в том, что ключ сортировки не задан наперед, а выбирается алгоритмом. Например, пусть есть массив [a, a, b, b]. Если использовать сортировку и присвоить ключи a=10, b=20, то перестановок не нужно, а если a=20, b=10, то нужны. С другой стороны, у выбора ключей есть какая-то сложность, и можно сказать, что ключи зависят от всего массива.
Re: Группировка быстрее сортировки
От: koenjihyakkei Россия  
Дата: 13.08.21 20:52
Оценка: 2 (1) +1 :)
Здравствуйте, PlushBeaver, Вы писали:

PB>Задача: дан массив длиной N из объектов, у которых есть признак-целое число; нужно получить группы объектов, у которых значения признака равны.


Не знаю, может я не до конца вкурил задачу, но зачем вообще сортировать. Может просто создать мапу из битсетов, где ключ — признак, значение — индексы в массиве, потом просто пройтись по массиву, добавляя в соответствующий элемент мапы бит индекса.
Отредактировано 13.08.2021 20:53 koenjihyakkei . Предыдущая версия .
Re: Группировка быстрее сортировки
От: vsb Казахстан  
Дата: 13.08.21 21:27
Оценка:
Как вариант — сделать map<key, int> и перед сортировкой пройти по списку и заполнить этот map возрастающими значениями. И потом сортировать по ним. Такое решение в среднем будет аналогично сортировке, но в вырожденных случаях, например когда исходный массив отсортирован по убыванию и обычная сортировка его переставит задом наперёд, это позволит избавиться от такой проблемы.
Re: Группировка быстрее сортировки
От: Sharowarsheg  
Дата: 13.08.21 23:36
Оценка:
Здравствуйте, PlushBeaver, Вы писали:

PB>Задача: дан массив длиной N из объектов, у которых есть признак-целое число; нужно получить группы объектов, у которых значения признака равны.


Если, скажем, сделать хеш-таблицу, и раскладывать на группы за один проход — будет O(N) по времени ценой N^2 памяти, если я ничего не путаю.
Re[2]: Группировка быстрее сортировки
От: Буравчик Россия  
Дата: 14.08.21 09:15
Оценка: +2
Здравствуйте, Sharowarsheg, Вы писали:

S>Если, скажем, сделать хеш-таблицу, и раскладывать на группы за один проход — будет O(N) по времени ценой N^2 памяти, если я ничего не путаю.


Откуда O(N^2)?

Будет O(N) и по времени, и по памяти
Хэш-таблица: признак => список_индексов_элементов
Best regards, Буравчик
Re[3]: Группировка быстрее сортировки
От: Sharowarsheg  
Дата: 14.08.21 09:32
Оценка:
Здравствуйте, Буравчик, Вы писали:

S>>Если, скажем, сделать хеш-таблицу, и раскладывать на группы за один проход — будет O(N) по времени ценой N^2 памяти, если я ничего не путаю.


Б>Откуда O(N^2)?


Б>Будет O(N) и по времени, и по памяти

Б>Хэш-таблица: признак => список_индексов_элементов

Да, и правда, можно связный список взять, у него добавление O(1).
Re[2]: Группировка быстрее сортировки
От: PlushBeaver  
Дата: 17.08.21 21:44
Оценка:
Здравствуйте, koenjihyakkei, Вы писали:
K>Не знаю, может я не до конца вкурил задачу, но зачем вообще сортировать. Может просто создать мапу из битсетов, где ключ — признак, значение — индексы в массиве, потом просто пройтись по массиву, добавляя в соответствующий элемент мапы бит индекса.

Когда-то сходу отмел такое решение, заподозрив, что случайный доступ к ячейкам будет медленным. Проверил, и бенчмарк показал, что это лучше сортировок.

Но еще быстрее при N <= 128 оказалось такое решение:
1. Рассмотриваем часть массива [left; right), изначально [0; N), пока она не пустая.
2. Проходимся по этой части и перекладываем в массив-группу элементы, равные X[left], помечая их в исходном массиве.
3. Очередная группа составлена.
4. Увеличиваем left до индекса первого непомеченного и отличного от X[left].
5. Уменьшаем right до индекса последнего непомеченного и отличного от X[left] плюс 1.
6. goto 1.
Формально O(N^2). Возможно, выигрывает за счет векторизуемости?
Re[3]: Группировка быстрее сортировки
От: Mr.Delphist  
Дата: 26.08.21 11:24
Оценка:
Здравствуйте, PlushBeaver, Вы писали:

PB>Но еще быстрее при N <= 128 оказалось такое решение:


Подозреваю, всё в кэш поместилось?
Re: Группировка быстрее сортировки
От: Умака Кумакаки Ниоткуда  
Дата: 20.09.21 15:29
Оценка:
Здравствуйте, PlushBeaver, Вы писали:

PB>Задача: дан массив длиной N из объектов, у которых есть признак-целое число; нужно получить группы объектов, у которых значения признака равны.

максимальное количество групп? максимальное количество признаков? максимальное количество объектов? насколько массивны объекты? от этих значений слишком много зависит во времена кешей.
нормально делай — нормально будет
Отредактировано 20.09.2021 15:34 Умака Кумакаки . Предыдущая версия . Еще …
Отредактировано 20.09.2021 15:31 Умака Кумакаки . Предыдущая версия .
Re[4]: Группировка быстрее сортировки
От: PlushBeaver  
Дата: 27.09.21 17:25
Оценка:
Здравствуйте, Mr.Delphist, Вы писали:

MD>Подозреваю, всё в кэш поместилось?


Да, но любое упомянутое в теме решение умещается в кэш на таких объемах. В моем случае еще хэш таблица статически выделенная, то есть локальность хорошая. Следовательно, дело все-таки в алгоритме.
Re[2]: Группировка быстрее сортировки
От: PlushBeaver  
Дата: 27.09.21 17:31
Оценка:
Здравствуйте, Умака Кумакаки, Вы писали:

УК> максимальное количество групп? максимальное количество признаков?


У каждого объекта один признак --- целое число. Может быть у всех объектов в одно и то же, может быть, у каждого свое. Возможных значений признака больше, чем объектов.

УК> максимальное количество объектов?


До 256, обычно 128.

УК> насколько массивны объекты?


Указатели.
Re[3]: Группировка быстрее сортировки
От: Умака Кумакаки Ниоткуда  
Дата: 28.09.21 18:32
Оценка:
Здравствуйте, PlushBeaver, Вы писали:

PB>Здравствуйте, Умака Кумакаки, Вы писали:



PB>До 256, обычно 128.


PB>Указатели.



пусть признак и указатель по 64 бита, это до 4к памяти, оно же целиком в L1 кеше будет, что тут может быть быстрее стандартного std::sort? и, тем более, как может быть вариант с хеш таблицей быстрее? любая аллокация на порядок медленне будет чем эта сортировка, покажите код
нормально делай — нормально будет
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.