Сортировка очень болших бинарных файлов

Да, естественно искал на:
- www.sourceforge.net
- www.google.com/linux
- www.linux.org.ru

Пока единственное, что нашел - это bsdsort, используемый в NetBSD. Он на ПОРЯДОК быстрее GNU sort (т.к. использует radix алгоритм), хотя и тестировал пока на небольшом файле ~100Мб.

Что беспокоит в bsdsort:
- дружит ли с локалью (возможно будет сортировка по именам на русском языке);
- можно ли его с исходниками засунуть в GNU проект и выложить под GPL, вроде BSD->GPL допустимо;
- как себя поведет на очень больших файлах.

bsdsort с локалью не дружит, системный GNU sort не буду пока заменять им :-( хотя внутри себя он использует setlocale и видимо какие то вызовы libc, зависимые от локали также использует ...

напиши сам..

всё-же просто до безобразия - бьешь очень-большой файл на 2^n кусков, каждый кусок сортируешь qsort`ом, далее применяешь сортировку слиянием.

qsort - в стандартной библиотеке, merge sort - http://en.wikipedia.org/wiki/Merge_sort

успехов !

>хотя внутри себя он использует setlocale и видимо какие то вызовы libc, зависимые от локали также использует ...

-g, --general-numeric-sort

Если диапазон значений, кот может принимать сортируемая величина, невелик, можно выделить массив из N бит, где N - максимальное значение, кот может принимать сортируемая величина. За первый проход установить биты, соответствующие значениям в файле, за второй проход - напечатать отсортированную последовательность.

> Если диапазон значений, кот может принимать сортируемая величина, невелик, можно выделить массив из N бит, где N - максимальное значение, кот может принимать сортируемая величина. За первый проход установить биты, соответствующие значениям в файле, за второй проход - напечатать отсортированную последовательность.

А где хранить количество вхождений каждого элемента?

Да, уникальность данных забыл указать (

>Если диапазон значений, кот может принимать сортируемая величина, невелик, можно выделить массив из N бит, где N - максимальное значение, кот может принимать сортируемая величина. За первый проход установить биты, соответствующие значениям в файле, за второй проход - напечатать отсортированную последовательность.

В вопросе же указаны типы сортируемых данных - unsigned int и float. Для float этот алгоритм в принципе крив. А для unsigned int потребует структуры в 2^32/(8*1024*1024)=512 метров если не учитывать количество повторов и использовать битовые счетчики (есть/нет). Если нормально вести счетчики, то умножай 512 на размер счетчика - при 8 битном счетчике надо 4 гига, зато действительнео быстро.

Там указаны типы данных, а не диапазон значений - это разные вещи.

> Если диапазон значений, кот может принимать сортируемая величина, невелик, можно выделить массив из N бит, где N - максимальное значение, кот может принимать сортируемая величина. За первый проход установить биты, соответствующие значениям в файле, за второй проход - напечатать отсортированную последовательность.

Вот родилось глядя на все эти безобразия - надо провести предобработку данных. Первым проходом собираем статистику появления величин в целевом файлае - их минимальное и максимальное значение, максимальное количество вхождений элемента + вырабатываем функцию отображения целевых значений в значения натурального ряда 0,1,2,....число различных злементов в целевых данных Создаем массив соответствующей размерности (число различных злементов в целевых данных) из элементов соответствующей размерности (достаточной для хранения максимального числа вхождений) Потом применяем вышепредложенный алгоритм

>Там указаны типы данных, а не диапазон значений - это разные вещи.

Разные но важные. Тип данных unsigned int предполагает некоторый максимум (2^32 например) который может проявиться, и если нужна программа для работы с данными этого типа она должна ожидать что ей может понадобиться обрабатывать значение 2^32-1. И вообще, как ты видишь свой алгоритм применительно к флоатам?

KIV : ахрененно нужная операция :)

чтобы узнать размерности массива - собирать поэлементную статистику, а для сбора статистики использовать ну например деревья..(массив низзя - потому что размерность неизвеста) вообщем масло-маслянное. с доп. расходом памяти.

насколбко понимаю, условие задачи подразумевает, что сортируемые данные не помещаются в память и их природа неизвестна (/dev/random).

Просто получится что после установления функции отображения память то освобождается... создается массив. Только вот построение функции дело хитрое :)

>насколбко понимаю, условие задачи подразумевает, что сортируемые данные не помещаются в память и их природа неизвестна (/dev/random).

Ну, во первых, у дев/рандома природа известна :) А я вообще стараюсь на счет условий задачи не понимать больше чем записано в условии - еще я сам себе проблемы не городил :)

Если файл содержит кучу _неповторяющихся_ unsigned int, то сортировку можно очень сильно оптимизировать при помощи обнулённой битовой матрицы. Всего таких чисел может быть не более 1 << (sizeof(unsigned int) * CHAR_BITS) тоесть для 32 битного unsigned int не более 4294967296 бит или 512Mb. Последовательно читаешь файл и используя очередной unsigned int как индекс устанавливаешь соответствующий бит в матрице в единицу. Затем последовательно, бит за битом, перечитываешь матрицу и для каждого выставленного в единицу бита выводишь его номер.

Чтобы уточнить, допишу:
- некоторые системы, которые обрабатывают эти файлы имеют у себя всего от 32Мб ОЗУ;
- количество сортируемых строк в типовом 900Мб файле - 7 миллионов.

Можно сортировать методом вставки, как это делают при получении карт.
Тоесть, создаём ещё один файл с массивом или связанным списком
сортируемых чисел и начинаем заполнять его как при получении карт,
вставляя очередное прочитнанное число между двумя подходящими. Если
используется связанный список, вставка будет более быстрой.

Например:

int data[5] = {12, 8, -5, 0, 7};

struct data_item {
        int num;
        int next;
} data_list[6];

data_list[0] = {0,0};  /* используется для указания на первый */
                       /* если next == 0, элемент списка последний */

после этого заполняем data_list из data. После очередного шага
data_list будет таким:

1. data_list == {{0,1}, {12,0}, {0,0}, {0,0}, {0,0}, {0,0}}
2. data_list == {{0,2}, {12,0}, {8,1}, {0,0}, {0,0}, {0,0}}
3. data_list == {{0,3}, {12,0}, {8,1}, {-5,2}, {0,0}, {0,0}}
4. data_list == {{0,3}, {12,0}, {8,1}, {-5,4}, {0,2}, {0,0}}
5. data_list == {{0,3}, {12,0}, {8,1}, {-5,4}, {0,5}, {7,2}}

Теперь, если необходимо, числа из списка можно переписать в массив.