Вообще сегодня День Программиста!

[febb]

Поэтому будет исключительно программистский пост!

avva пишет:
Владимир Ярославский из Сана придумал новый вариант Квиксорта, работающий быстрее обычного. Основная идея проста до безобразия: вместо одного опорного элемента (pivot) выбираем два, распихиваем элементы в три подмассива: меньше первого опорного, между первым и вторым, и больше второго, и спускаемся рекурсивно три раза вместо обычных двух.

А я вот как-то выдумал алгоритм в несколько раз быстрее квиксорта для массивов строк.
Наверное он похож на алгоритм Седжвика, но мне кажется должен быть быстрее.
Идея такая:
Рекурсивно, начиная со старшего байта:
1) вычисляем гистограмму встречающихся байт и сортируем на 256 кусков в один проход
2) для каждого из 256 кусков повторяем 1) для следующего байта и т.д.

Конечно для ограничения вырождения алгоритм нужно усложнить и т. п.
Но вот на самом примитивном уровне как он выглядит на С++:



void ByteSort(char ** Array, size_t Num, size_t size, size_t offset=0)
{
size_t S[256], // starting index per group
H[256]; // (histogram) number of elements in group
// init historgram:
memset(H, 0, sizeof(H));
// 1st path: make historgram of byte values:
register unsigned char ** data = (unsigned char **)Array;
register size_t i;
for(i=0; i < Num; i++)
++H[ data[i][offset] ];
// calculate staring index positions:
size_t s = 0;
for(i=0; i < 256; i++)
{ S[i] = s; s += H[i]; }
// sorting by regrouping data:
unsigned char ** ds = new unsigned char * [ Num ]; // allocate temp array for sorted elements
for(i=0; i < Num; i++)
{
unsigned char * d = data[i];
ds[ S[ d[offset] ]++ ] = d; // increment current position and copy element
}
memcpy(data, ds, sizeof(*data)*Num); // copy sorted array back
delete [] ds; // free mem
// sort recurecively all the groups:
if(--size)
{
++offset;
s = 0;
for(i=0; i < 256; i++)
{
size_t h = H[i];
if(h > 1)
ByteSort(Array + s, h, size, offset);
s += h; //calculate starting index
}
}
}

Мне интересно, кто-нибудь теоретически может оценить, насколько он быстрее?
По тестам со случайными массивами работает раз в 10 быстрее квиксорта.
Плохие случаи я не исследовал.

Всех программистов с Праздником!

Comments

[bird-123.livejournal.com]

лучше бы ты что-то матерное написал - я бы и то больше поняла ))

[febb.livejournal.com]

Дык это самый настоящий программистский мат! :)
Только на С++ :)

[bespechnoepero.livejournal.com]

Давно уже пора хардвэр делать для сорта, скажем матрица 256 на 256 логических элементов, и сравнивать страницами, так сказать, чтобы сузить зону поиска. Вообще нерационально все время на софт полагаться. Он, конечно, гибкий, но в мире существует куча апликаций со статической структурой, та же база данных магазина Амазон, например, или банковские базы данных. Они досаточно большие, чтобы форматировать диск не под некий абстрактный файл операционной системы, а под саму базу данных, ведь структура формата диска аналогична таблице, только что не квадратная, а круглая, но все же это обыкновенная двухмерная таблица, только что на магнитном носителе. Так ведь и таблица базы данных она тоже не на мониторе в самом деле находится. Тогда можно редактировать записи в базе данных без переписывания всего файла. Я уже не говорю, что с такой структурой форматирования хард диска поиск тоже можно оптимизировать.

[vazhskiy.livejournal.com]

С новым праздником! Хотя меня он как-то особо не касается.

[febb.livejournal.com]

Спасибо!

[skwo-82.livejournal.com]

С профессиональны праздником!!! Пусть он будет солнечным и радостным!

[febb.livejournal.com]

Спасибо!

[artcan.livejournal.com]

А тут вот товарищи подсказывают, что нынче еще и День Танкиста!)))
Предлагаю накатить за тех, кто танковыми клиньями взрывает унылый листинг))))

[febb.livejournal.com]

Все мы немного лошади танкисты! ^)

[kaimira.livejournal.com]

Поздравляю с профессиональным праздником!

[febb.livejournal.com]

Спасибо!

[febb.livejournal.com]

спасибо)