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

[Андрей АK]

xaxa3217 писал(а):

Цитата:

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

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

Не надо никуда обращаться.
Если числа принимают только 10 значений, то достаточно знать их количество в каждом из значений, всё остальное вычисляется.
И массив хранить тоже не требуется.
Например: Имея таблицу: 0-1000;1-1;2-0;3-0;4-0;5-1000 ... (это количество чисел каждого значения).
Я легко вычисляю что число в отсортированом массиве с номером 1000 равно нулю, с номером 1001 равно единице, с номером 1002 равно пяти, а также что первое число равное пяти находится на 1002 м месте.
Для этого никакой массив не нужен.
Для данной задачи не нужна никакая сортировка, да и массив не нужен.

Для случая когда с числами связаны какие-то данные тоже надо разжевать? Почему там не требуются алгоритмы сортировки с временем n*log(n) , а достаточно n ?
Особенности работы файла подкачки к оценке скорости работы алгоритма не имеют отношения.

[Yuri Gendelman]

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

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

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

Computer Simulation

Хорошо, что не Computer Science
Но все равно не понятно, зачем при этом сортировать $10^9$ вещественных чисел. Я предлагаю Вам подумать, а нельзя ли вообще обойтись без сортировки.

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

Zai писал(а):

Yuri Gendelman писал(а):

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

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

IMHO потому и недогружены, что программировать их не просто более сложно, а на порядок сложнее. Но конечно Вы правы, такого рода задача хорошо распараллеливается. К сожалению во многих университетах многопроцессорные системы - это Linux-кластеры, созданные CS-студентами в качестве курсовых проектов. Ни поддержки, ни стабильности они не гарантируют.

Судя по другим вопросам, автор темы познакомилась с программированием <шутка>где-то с месяц назад</шутка>. Заставлять человека изучать MPI просто негуманно.

[xaxa3217]

2Андрей АK мне ничего разжевывать в вашем сообщении не надо, только ответьте - для миллиарда различных чисел вы где такую таблицу хранить будете? откуда вы вообще взяли ограничение на 10 различных чисел?

Цитата:

Особенности работы файла подкачки к оценке скорости работы алгоритма не имеют отношения.

мда, давайте определимся. текущая тема практически никакого отношения к алгоритмам не имеет, поскольку, как вы сами отметили, алгоритмы к их реализациям тоже никак не относятся. но не нужно строить утопических иллюзий по поводу программирования, поскольку это ремесло напрямую связанно с работой за реальными машинами чьи аппаратные ограничения диктует реальность. я, например, не могу себе позволить хранить непосредственно в оперативной памяти даже миллиард байт. ваше же "решение" к задаче сортировки никак не относится, потому что алгоритмов сортировки с оценкой сложности O(n) не существует, то что это решает конкретную задачу с сильно ограниченной мощностью множества всех возможных хранимых чисел не значит что нам не требуются алгоритмы быстрее n*log(n). как вы думаете почему так много алгоритмов сортировки/поиска с одной оценкой? именно потому, что в реальности используются разные подходы. у вас же очень странный подход, которому не требуется ни компьютеров, ни файлов подкачек для гигабайт памяти, ни даже массивов для хранения массива чисел.

[Андрей АK]

xaxa3217 писал(а):

2Андрей АK мне ничего разжевывать в вашем сообщении не надо, только ответьте - для миллиарда различных чисел вы где такую таблицу хранить будете? откуда вы вообще взяли ограничение на 10 различных чисел?

Читайте внимательнее условия задачи. Третье сообщение начиная с первого.
При данных условиях задачи НИГДЕ ЭТОТ ОГРОМНЫЙ МАССИВ ЧИСЕЛ ХРАНИТЬ НЕ ТРЕБУЕТСЯ - достаточно хранить ТОЛЬКО МАССИВ ИЗ 10 ЧИСЕЛ - И ВСЁ.

Цитата:

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

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

Цитата:

ваше же "решение" к задаче сортировки никак не относится, потому что алгоритмов сортировки с оценкой сложности O(n) не существует

Если вы таких алгоритмов не знаете, то это ещё не значит что их не существует.
Вот можете почитать здесь про этот алгоритм: сортировка подсчётом

[Таня Тайс]

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

Судя по другим вопросам, автор темы познакомилась с программированием <шутка>где-то с месяц назад</шутка>.

Месяц назад я инсталлировала Linux Ubuntu на своем домашнем компьютере. Почти угадали

[xaxa3217]

2Андрей АK мало того что вы уже которое сообщение подряд пишете с тонной глупостей, так вы еще успеваете показать себя самым умным, а других дураками. я вам еще раз говорю - интервал от 0 до 10 содержит много больше 10-ти чисел.

Цитата:

Если вы таких алгоритмов не знаете, то это ещё не значит что их не существует.
Вот можете почитать здесь про этот алгоритм: сортировка подсчётом

сколько раз можно объяснять - это не сортировка. это скорее известный трюк.

[Андрей АK]

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

Цитата:

Цитата:

Если вы таких алгоритмов не знаете, то это ещё не значит что их не существует.
Вот можете почитать здесь про этот алгоритм: сортировка подсчётом

сколько раз можно объяснять - это не сортировка. это скорее известный трюк.

Какая-то новая терминология, кроме алгоритмов сортировки оказывается ещё есть алгоритмы-трюки.

[Таня Тайс]

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

Я предлагаю Вам подумать, а нельзя ли вообще обойтись без сортировки.

Я обошлась без сортировки.
Андрей АK, спасибо, натолкнули меня на мысль. Решение, как всегда, когда долго думаешь, оказалось очень простым. Задача сортировки продолжает казаться интересной...

Читаю 3 том Кнута.

Добавлено спустя 51 секунду:

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

ОООЧЕНЬ большой массив не поместится в RAM

А где лежат границы?

[Yuri Gendelman]

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

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

ОООЧЕНЬ большой массив не поместится в RAM

А где лежат границы?

Ваши $10^9$ чисел требуют около 4 (float) или 8 (double) гигабайт памяти.