сортировка ОООЧЕНЬ большого массива типа double на с

[Таня Тайс]

как подступиться к такой задаче лучше всего, если учесть, что я не хочу ждать 4 часа?

[finanzmaster]

Таня Тайс писал(а):

как подступиться к такой задаче лучше всего, если учесть, что я не хочу ждать 4 часа?

1. Компьютер помощнее
2. Запустить рутину сортировки на ночь

Ну а если что-то более экстравагантное требуется, то ищите про распараллеливание алгоритмов сортировки

[Таня Тайс]

а какой алгоритм лучше всех? на Ваш взгляд?

Добавлено спустя 9 минут 31 секунду:

все числа массива лежат в интервале от нуля до 10.
много алгоритмов, трудно быстро сориентироваться...

[barga44]

Стандартный подход предусматривает Quicksort
алгоритм.Рекурсивную сортировку.
Обычно она самая быстрая.
Смотрите 193 страницу книги Deitel, С++,How to program.2001 год
ISBN 0-13-089571-7
У меня когда-то была такая задача лет 15 назад.Придумал такой алгоритм.

1.Сначала провел грубую сортировку.
То есть.
Разбил масив на 2 массива.
В первый входит числа от 0 до 5.
Во второй от 5 до 10.
Образовал из заданных массивов десять массивов.
В первый масив входят числа от 0 до 1.Во второй от 1 до 2,и т.д.
2.
Отсортировал все числа от 0 до 1.От 1 до 2.
3.Можно ввести десять массивов целых чисел.
Им присвоить значения округленные от заданных чисел массива,умноженные на целое число 100.
То есть.Если задано число
3.14
То присваиваю 314.
Который у вас задано с двойной точностью.
Получил 10 массивов неотсортированных из цедыз чисел.
Просортировал каждый массив.
Получил 10 массивов отсортированных.
4.Затем провел более качественную сортировку.
5.Присвоил этим целым значениям те числа которые были с двойной точностью.
И отсортировал снова.
5.
Опять образовал один массив из 10 массивов.
6.Опять провел сортировку проверочную или контрольную,что все правильно сделано.
7.Подразумевается, что вы используете динамическое выделение памяти.
8.Если вы владеете технологией, описанной в книге Intel,threading Building Blocks,
James Reinders.2007 год,
ISBN-0-596-51480-8

То вы можете использовать 2 ядра вашего процессора.То есть задачу решите в 1.5-1.9 раза быстрее, чем обычно.
если у вас 4 ядра, то в 2.2-3.5 раза быстрее.
То есть появляется возможность распараллелоить задачу по ядрам.На
одном компьютере.
Если вам не трудно, скажите какой размерности у вас массив.

[finanzmaster]

Таня Тайс писал(а):

а какой алгоритм лучше всех? на Ваш взгляд?

Добавлено спустя 9 минут 31 секунду:

все числа массива лежат в интервале от нуля до 10.
много алгоритмов, трудно быстро сориентироваться...

Я люблю HeapSort.
У QuickSort в случае больших массивов есть вероятность вылететь со Stack Overflow, впрочем, оптимизированных реализациях этого избегают.
Алгоритма с complexity лучше O(n*log(n)) не существует.
У Вас, правда, доп. ограничение, но я сомневаюсь, что оно может помочь.
Так что если сильно быстро надо - то только распаралеливание остается.


P.S.
Завтра посмотрю - по-моему, у меня на работе есть закладка на страницу, где HeapSort хорошо объяснен (чтобы его понять, надо рисовать процесс - как heap создается и поэтапно сортируется).

Вот: http://www.hipphampel.de/index.php5?ite ... _embedding

[Фома]

Таня Тайс писал(а):

а какой алгоритм лучше всех? на Ваш взгляд?

Ваша проблема отнюдь не в каком-то специальном алгоритме сортировки, а в элементарной нехватке оперативной памяти (компьютер начинает заниматься свопингом). Вот такой тестовый примерчик на моем компьютере выполнялся 51 секунду (извинте, правда на C#).

using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 250000000;
            double[] m = new double[n]; // Размер массива 2 000 000 000 байт
            Random ran = new Random(1);

            DateTime st = DateTime.Now;
            for(int i = 0; i < n; i++)
            {
                m[i] = ran.NextDouble() * 10.0;
            }
            Console.WriteLine((DateTime.Now - st).ToString());  // Примерно 7 сек

            st = DateTime.Now;

            Array.Sort<double>(m);

            Console.WriteLine((DateTime.Now - st).ToString());  // Примерно 51 сек
        }
    }
}        

Если Ваш массив гораздо больше, то либо увеличивайте разрядность процессора и размер памяти, либо используйте любую СУБД, коих сейчас много бесплатных (Firebird, Postgress, DB2-C, MySql ....).

[Yuri Gendelman]

Таня Тайс писал(а):

как подступиться к такой задаче лучше всего, если учесть, что я не хочу ждать 4 часа?

ОООЧЕНЬ большой массив не поместится в RAM (иначе он не ОООЧЕНЬ большой). В таких случаях используются методы внешней сортировки со слиянием. Посмотрите для начала 3-й том Кнута ("Сортировка и поиск"). На ленточную терминологию вимание не обрашайте. При этом порции, помещающиеся в RAM-буфере, сортируются quicksort, heapsort, quickersort или другим имеющимся в Вашем распоряжении методом.

[Таня Тайс]

Спасибо большое за помощь! Мне тоже нужно время для обработки полученной информации...
(как и компьютеру)
Добавлено спустя 4 минуты 3 секунды:

barga44 в сообщении #159931 писал(а):

Если вам не трудно, скажите какой размерности у вас массив.

порядка ~$10^9$ , предполагается это число увеличить (чем больше, тем точнее), а массив одномерный.

[Zai]

Таня Тайс писал(а):

порядка ~$10^9$ , предполагается это число увеличить (чем больше, тем точнее), а массив одномерный.

Если у Вас очень большие объемы, то нужно писать параллельную версию для кластера с большим числом узлов (64 и выше). Алгоритм получится или итерационный, когда пересылка будет проводится после локальной пересортировки, или распределенный, когда малое число, встреченное в массиве сразу пересылается на необходимый узел. Могут возникнуть проблемы неэффективности сетевых протоколов. По субъективному опыту работ с обращением матриц - запись числа на диск компьютера в несколько раз дольше его сохранения в оперативной памяти рядом находящегося в локальной сети компьютера.

[Yuri Gendelman]

Zai писал(а):

Если у Вас очень большие объемы, то нужно писать параллельную версию для кластера с большим числом узлов (64 и выше).

Это - теоретически совершено правильный совет.
Но практики пишут программы для доступного в данный момент компьютера.

Кстати, не понятно, зачем нужно сортировать такую кучу данных.
Если речь идет о построении гистограмм, поиске медианы и прочих квантилей, и т.п., то для маленьких массивов действительно можно начать с сортировки. Но для ОООЧЕНЬ больших массивов лучше поискать специальные методы.

[worm2]

Если специфика задачи такова, что множество различных значений существенно меньше, чем множество всех значений (т.е., в среднем, каждое значение выпадает много раз; такое возможно, например, если данные идут с какого-то измерительного прибора с малой разрядностью АЦП), то сортировку можно ускорить. Грубо говоря, просто заводим список всех значений, учитывая в нём кратность каждого появившегося значения. Дальнейшее тривиально.

[Таня Тайс]

Yuri Gendelman в сообщении #160257 писал(а):

не понятно, зачем нужно сортировать такую кучу данных

Computer Simulation

worm2 в сообщении #160285 писал(а):

Если специфика задачи такова, что множество различных значений существенно меньше, чем множество всех значений

нет, все значения с высокой вероятностью различны.

Добавлено спустя 1 минуту 37 секунд:

это z- позиции частиц в жидкости, термодинамика

Добавлено спустя 7 минут 25 секунд:

finanzmaster
Спасибо за ссылку! Я как раз хотела спросить почему такой хороший алгоритм - мне известный как "Baum"= "дерево" и применяющийся для сортировки слов, нельзя применить для сортировки чисел. Он из книги Rernighan, Ritchie.

[Zai]

Yuri Gendelman писал(а):

Но практики пишут программы для доступного в данный момент компьютера.

Вы преувеличиваете недоступность компьютеров с большим числом узлов. Они, как правило, сильно недогружены большую часть времени года, однако программировать для них более сложно.

[Андрей АK]

Если вам надо отсортировать только числа ... забудьте про алгоритмы сортировки.
Достаточно подсчитать общее количество чисел для каждого значения - делается за один проход и дальше хранить только эти данные (вместо массива).
А вот если к каждому числу привязана ещё дополнительная информация - то всё равно - есть такой метод , с подсчётом количества чисел каждого значения - после подсчёта каждое число ,одним действием!, перемещается на отведённое ему место, вот и всё.
Время сортировки ~n (а вовсе не n*log(n)).

[xaxa3217]

Цитата:

Если вам надо отсортировать только числа ... забудьте про алгоритмы сортировки.

а если человеку приспичит написать программу, пусть и про программирование вовсе забудет?

Цитата:

Достаточно подсчитать общее количество чисел для каждого значения - делается за один проход и дальше хранить только эти данные (вместо массива).

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

Цитата:

Время сортировки ~n (а вовсе не n*log(n)).

еще немного и ваша Сортировка будет сортировать быстрее чем считывать необходимые данные.
--

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