По поводу сортировки файла в 3GB

Опубликовано Mar 7, 2012 в Алгоритмы и Структуры данных, Тестовые проекты (2-3 часа) | 16 коммент.

, , , ,

По поводу сортировки файла в 3GB

Анализ задачи

  1. В чем суть проблемы? 32-х битовая операционная система Windows не может выделить 3GB для процесса. Считается, что данный лимит – 2GB, но на самом деле выделять под собственно данные нужно еще меньше. Примем этот лимит равным 1,5GB, то есть можно считать, что за одну итерацию в оперативную память можно поднять половину данных. Отсюда следует неизбежная необходимость подгружать данные с диска в процессе их обработки.
  2. Что оптимизировать? Так как файловые операции несоизмеримо медленнее, чем работа с памятью, то нацеливаться нужно на уменьшение количества обращений к диску, а не на борьбу за создание алгоритма с меньшим Big O. Кроме того, очень затратной может оказаться реализация операции сравнения для больших строк, а в пределе возможна такая строка, которая сама будет иметь размер больше 1,5GB и даже в одиночку не влезет в память. А может быть очень много коротких строк, но тогда велика вероятность их повторения. Отсюда вывод, что для оптимизации общей производительности наверняка придется переключать алгоритмы в зависимости от статистики распределения длин строк и их количества.
  3. Можно ли использовать нечто готовое? Скорее да, чем нет, так как более классическую алгоритмическую задачу, чем сортировка, вряд ли можно найти.
    ВОПРОС: где же она решена именно в такой постановке?
    ОТВЕТ: в любой промышленной реляционной СУБД. Работа с объемами данных, большими чем лимит, установленный процессом, оптимизация работы с диском под эти задачи, индексы, основанные на самых производительных алгоритмах сортировки – все это может оказаться полезным, так как самые сложные части задачи будут переложены на чужие плечи, заслуживающие доверия. Решение задачи, основанное на использовании MS SQL Server видится, по крайней мере, интересным и его стоит попробовать поискать, а результаты сравнить с теми, которые будут предложены на основе применения подхода, где алгоритм сортировки и работа с файлами будут реализованы только стандартными средствами выбранного высокоуровневого языка.
  4. Как тестировать результаты? Очевидно, что полноценное тестирование данной задачи может быть выполнено только с применением средств автоматизации, так как исходные данные абсолютно необозримы. Значит, необходим тестовый скрипт. Кроме того, в нашей ситуации нереальной является передача тестовых файлов ввиду их огромного размера. Следовательно, нужны дополнительные скрипты генерации тестовых данных, которые можно будет пересылать.

Автор публикации: