kealon(Ruslan)д0kХ,

я задачу не придумывал, такая была 20288078
учитывай что читать нужно весь объём Ln(S/MemBlockSize) раз

10 гб у меня сортировалось где то 4-5 минут, с учётом O(ln(n) * N) вроде как в твои параметры вписывается

Какой у тебя MemBlockSize ?

Dima Tд0kХ1. Не было ограничей по памяти,
20286712

д0kХ3 Как показывает практика однопоточная сортировка медленнее чем
современные шпиндельные
диски на мультиблочном ввводе выводе
ни один современный процессор не в силах сортировать поток
со скоростью с которой может читать SATA3 диск ( 60 - 90 мегабайт/сек)
Мне не интересна стандартная сортировка, которая O(N*log(N)) даже на сортированном файле. На сортированном хочу O(N), не надо мне *log ₂ (N), log ₂ (1Гб) = 30. Тут оно и есть, поэтому интересно.

Я не много о другом и
Я не понял причем тут вычислительная сложность к параметрам параллелизма ?

Я поступаю "тупо" , пытаюсь понять критерии при которых можно задействать
максимальное количество имеющихся ядер в системе в зависимости
от имеющейся производительности ввода вывода
не важно какой алгоритм они крутят O(N*log(N)) или O(N).

То есть адаптивно определить, что есть слабым местом конкретной вычислительной
системы процессор или ввод вывод.

Майтон ,

д0kХЯ поступаю "тупо" , пытаюсь понять критерии при которых можно задействать
максимальное количество имеющихся ядер в системе в зависимости
от имеющейся производительности ввода вывода
не важно какой алгоритм они крутят O(N*log(N)) или O(N).

То есть адаптивно определить, что есть слабым местом конкретной вычислительной
системы процессор или ввод вывод.

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


вот что нужно говорить майкрософту на собеседовании в ответ на постановку
задачи об абстрактной сортировке в вакуме )

kealon(Ruslan)д0kХ Какой у тебя MemBlockSize ? 1 Мб Ram больше использовать по условиям задачи нельзя

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

Я не помню что бы Майтон озвучивал однозначное
числовое ограничение на объем памяти.

Dima Tд0kХЯ не много о другом и
Я не понял причем тут вычислительная сложность к параметрам параллелизма ?

Я поступаю "тупо" , пытаюсь понять критерии при которых можно задействать
максимальное количество имеющихся ядер в системе в зависимости
от имеющейся производительности ввода вывода
не важно какой алгоритм они крутят O(N*log(N)) или O(N).
Я тоже немного о другом, меня сам алгоритм с деревом триплетов заинтересовал, я его попутно исследую:
1. Это отличный способ для решения задач типа "получить N минимальных элементов из несортированного массива". По сути в один проход строится дерево триплетов, а потом извлекай из него N элементов. Вычислительных операций будет пропорционально N, а не размеру всего массива, т.к. вычисление происходит в момент извлечения минимального.
2. Потом хочу сюда 20170548 добавить дерево триплетов. Я там как-раз искал что подобное, порешал уже, но пусть будет про запас.

д0kХТо есть адаптивно определить, что есть слабым местом конкретной вычислительной
системы процессор или ввод вывод.
Чтобы что-то определить надо сначала дорешать запустить и посмотреть что получилось. Может проц и не загрузится на 100%.
А потом уже рефакторингом заниматься.

Дима, я тебя не понимаю , ты говоришь о другом, а цитируешь размышления
об адаптивных параметрах параллелизма.

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

mayton2 All
д0kХЕсли задаче не определен режим открытия файлов и используется кеш файловой системы ,
то это не чесный тест.

1 Мб - это очень странная цифра. Она растет ногами разве-что из MS-DOS или Windows-95/98.
Да и вообще, в современных ОС и фреймворках все меньше и меньше возможностей
контролировать или явно разграничивать использование памяти. Неявных способов
выделить ее - вагон и маленькая тележка.

Я не помню что бы Майтон озвучивал однозначное
числовое ограничение на объем памяти.

(потирая лоб)

Я не знаю что вы от меня хотите услышать. Любая цифра - будет подвергнута критицизму.
Буду профанации. Будут фейковые решения.

Тут важна не цифра. А само понимание стека технологий и подход. К примеру если имеем
1 ядро + 1Гиг памяти + 1Терабайт диска = можем отсортировать (грубо) 500 Гиговый
текстовый файл за N секунд времени.

Имеем ту-же конфигурацию но 2 диска по 500 Гигов. То-же самое. Но степень
параллелизма для merge - будет выше. Докинем перформанса (грубо) порядка +30%.
(Разумеется если мы сумеем эту степень параллелизма грамотно подать на вход
алгоритму).

Имеем на том-же стеке 3 диска по 330 Гигов. То-же самое. +60% перформанса
на слияниях.

И это все без конкретных цифр. А только на соотношениях. 1:1000 в моем примере.

mayton , моя многолетняя практика работы с БД, постройки индексов,
сортировки в темппространстве БД и памяти,
просто сортировки в ОС любыми инструментами
однозначно говорит , что одно ядро не в состоянии сортировать
со скоростью потока с которой система может последовательно читать с диска.
Эта тенденция не меняется как минимум 15 лет

На один шпиндельный диск нужно в ~2 ядра , что бы система
была сбалансированной по производительности.
На SSD диск 3-4-5 ядер.

kealon(Ruslan)д0kХmayton , моя многолетняя практика работы с БД, постройки индексов,
сортировки в темппространстве БД и памяти,
просто сортировки в ОС любыми инструментами
однозначно говорит , что одно ядро не в состоянии сортировать
со скоростью потока с которой система может последовательно читать с диска.
в сортировке слияними фактически нет вычислений, так что процессор будет практически стоять
что я собственно и наблюдал, минимальна загрузка проца, 100% - диска

100% нагрузки на диске вы видели потому что у вас вероятнее
всего чтение было не последовательным.
я выше говорил о балансе последовательного чтения и количест операций seek ( позиционирование головок).

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

д0kХ

Это я к тому что на скорость дискового ввода вывода и баланса нагрузок
может влиять даже место размещения файлов на поверхрости шпинделя
center - самое быстрое позиционирование
inner edge и outer edge более медленное позиционирование.
в center укладываются файлы с рандомным характером доступа ,
в edge с последовательным.