kdvNickDeeЯ просто представляю себе - мне нужно взять из файла строки и посортировать..
мнэ....
ну взял ты строки. произвольной длины. Как ты их будешь переставлять местами (сортировать)? Известно же, что или ты будешь сортировать указатели на них, или сами строки. Индекс - это и есть отсортированные указатели на строки переменной длины. А по PLAN SORT один вариант - сортировать строки фиксированной (максимально возможной длины).

я фигею, что объясняю как бы прописные алгоритмические истины :-)
Я тоже фигею, т.к. сортировать я буду не строки, а создам указатели на строки, длина которых 4 байта или 8 байт, в зависимости от архитектуры, и буду оперировать ими. Переставлять местами записи я бы не додумался.
Так что думаю в коде всё-таки поинтеры местами меняются, как в прописных алгоритмических истинах :)

Dimitry SibiryakovNickDeeпри N = 1 он равен 58mb.
при N = 32000 он равен 583mb.
Т.е. одни и те же данные хранятся в БД с разной степенью эффективности. Разница в 10
раз.
И тебя не восхищает, что разница в 10 раз, а не в 32000 раз?.. Ты вообще программист?..

Меня восхищает что разница вообще есть. А тебя не восхищает что есть разница в 10 раз? Ты вообще программист?.. :)

Dimitry SibiryakovNickDeeЯ просто представляю себе - мне нужно взять из файла строки и
посортировать... зачем мне делать их паддинг?
А ты возьми да напиши программу для их сортировки. Без паддинга. И посмотри насколько она
будет медленнее работать.

За счёт чего медленней? Что, скорость сравнения S1 > S2 зависит от паддинга? Не зависит.
Так для чего делать им паддинг?

Симонов ДенисNickDee,

сортировка в кортежей в памяти это одно. Совсем другое дело когда эти данные в память не умещаются. Например не умещаются из-за паддинга :)
Я вот думаю что если у меня есть набор данных из миллиона записей для сортировки, и часть из них не входит в память и сливается во временные файлы, то я уж точно буду сортировать поинтеры, а не менять местами записи этого набора данных в оперативке или на диске. И для этого мне паддинг точно не нужен.

Dimitry SibiryakovNickDeeЗа счёт чего медленней? Что, скорость сравнения S1 > S2 зависит от паддинга?
Не зависит. Так для чего делать им паддинг?
Отсортируй десяток гигабайт - узнаешь.

Хм.
При
получается вообще сортируются числа, но данные всё-равно паддятся и используются временные файлы. Засада прям :)

Так и не понял зачем паддить. Зафетчили первый блок записей (сколько их там в половину сортировочного кэша входит), создали к записям массив поинтеров, посортировали этот массив. Зафетчили второй блок записей, создали к записям массив поинтеров, посортировали этот массив. Далее создаём на диске файл и, используя информацию из двух массивов поинтеров, сливаем записи из двух блоков в один, как при сортировке слиянием. Получаем на диске файл с отсортированными записями из двух первых отффетченных блоков.
Далее фетчим ещё два блока и проделываем с ними то же самое, т.е. создаём по ним файл с отсортированными записями.
В конце концов получится N файлов, каждый из которых будет содержать отсортированные внутри записи.
И без всякого паддинга.
Дальше попарно сливаем эти файлы, создавая новые (и удаляя при этом те, из которых данные уже были слиты).
В конце останется один большой файл.
Если сортировочный кэш равен 50 мегабайт, а записей на 200 мегабайт, то на первом этапе будет создано 4 файла по 50 мегабайт. Потом 2 по сто (с удалением предудущих четырёх). Потом эти два сольются в один. Хотя тут я не уверен, т.к. зачем нам сливать последние два, когда можно вместо создания последнего файла сразу отдавать записи движку. И даже скажу больше - не факт что будт эффективно даже из четырёх файлов делать два. Возможно проще отдавать записи движку выбирая нужную из 4-х источников, чтобы сэкономить на записи двух файлов по 100 МБ. Хотя возможно это зависит от скорости дисковой системы.
Места паддингу я так и не нашёл :)

kdvdimitrэто в куда тебя занесло? :-)
еще не занесло. Завтра в Брюссель, в логово демократии :-)

NickDeeДалее фетчим ещё два блока и проделываем с ними то же самое, т.е. создаём по ним файл с отсортированными записями.
ну ты хоть бы исходники ФБ почитал...
Мне проще достать подходящий алгоритм из коллективного бессознательного :)