V>Есть файл большого размера (нельзя загрузить в оперативную память). Его нужно отсортировать побайтно. Причем число операций чтения допускается порядка O(NlogN), а число записей порядка O(N). V>Как правило предлагается qsort, но ему необходимо O(NlogN) чтений и записей. V>Были бы интересны любые идеи.
Побайтно — это как? Отсортировать по одному байту? Тогда сортировка подсчетом.
E>А как догнать число чтений до O(N lnN)? Похоже всё-таки. что задачка какая-то другая...
а зачем, если "число операций чтения допускается порядка O(NlogN)" ? Разве "Допускается" это не значит "не больше чем"?
Есть файл большого размера (нельзя загрузить в оперативную память). Его нужно отсортировать побайтно. Причем число операций чтения допускается порядка O(NlogN), а число записей порядка O(N).
Как правило предлагается qsort, но ему необходимо O(NlogN) чтений и записей.
Были бы интересны любые идеи.
V>Есть файл большого размера (нельзя загрузить в оперативную память). Его нужно отсортировать побайтно. Причем число операций чтения допускается порядка O(NlogN), а число записей порядка O(N). V>Как правило предлагается qsort, но ему необходимо O(NlogN) чтений и записей. V>Были бы интересны любые идеи.
Radix sort?
Здравствуйте, vdttf, Вы писали:
V>Есть файл большого размера (нельзя загрузить в оперативную память). Его нужно отсортировать побайтно. Причем число операций чтения допускается порядка O(NlogN), а число записей порядка O(N). V>Как правило предлагается qsort, но ему необходимо O(NlogN) чтений и записей. V>Были бы интересны любые идеи.
Посчитать количество вхождений для каждого байта, а потом записать, начиная с 00 и до ff.
Здравствуйте, SergH, Вы писали:
SH>Посчитать количество вхождений для каждого байта, а потом записать, начиная с 00 и до ff.
А как догнать число чтений до O(N lnN)? Похоже всё-таки. что задачка какая-то другая...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
SH>>Посчитать количество вхождений для каждого байта, а потом записать, начиная с 00 и до ff.
E>А как догнать число чтений до O(N lnN)? Похоже всё-таки. что задачка какая-то другая...
Здравствуйте, Socrat, Вы писали:
E>>А как догнать число чтений до O(N lnN)? Похоже всё-таки. что задачка какая-то другая...
S>пустыми циклами
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, SergH, Вы писали:
SH>Перепроверять результаты чтения?
SH>Подождём автора вопроса, может прояснит.
боюсь не смогу, задача на подумать, по этим условиям проходит только radix, но у него чтений O(N). Мне кажется не имеет смысла O(NlogN) чтений при возможности O(N) записей (учитывая недостаток оперативки). Но такая вот задача )
Если же это было сказано для красного словца... то неплохо бы уточнить, что имелось в виду.
Видимо, подразумевается, что файл состоит из элементов одинаковой длины, а отношение порядка над ними совпадает с отношением порядка над байтовыми векторами.
V> Причем число операций чтения допускается порядка O(NlogN), а число записей порядка O(N). V>Как правило предлагается qsort, но ему необходимо O(NlogN) чтений и записей. V>Были бы интересны любые идеи.
Алгоритмы сортировки больших объёмов возникали ещё со времён ленточных накопителей, так что можно как следует прошурудить классику.
Если элементы достаточно длинные, то может статься, что исходный файл в память не влезает, а массив индексов — влезает.
Тогда можно выполнить сортировку индексов, основываясь на сравнении указуемых элементов, — выполнив обещанные N log N операций чтения; а затем прицельно сделать N операций записи.
Ещё один интересный вопрос: а сколько места на диске? Всё-таки последовательный доступ к файлу — куда быстрее произвольного. Это я в сторону сортировки слиянием.
Здравствуйте, evjiii, Вы писали:
E>а зачем, если "число операций чтения допускается порядка O(NlogN)" ? Разве "Допускается" это не значит "не больше чем"?
Ну в умных и хороших задачах обычно "без запаса" указывают...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Перекуём баги на фичи!
