Какой самый быстрый алгоритм поиска максимального значения в большом файле?

Question

[m1t9.(；]

Привет.
Допустим, есть файл, в котором лежит по числу в каждой строке. При этом сам файл может быть крайне большим (например, размером несколько сотен гигабайт) . Как быстрее всего найти максимальное (минимальное) значение в данном файле?
Спасибо.

Answer 1

[Rsa97]

Просмотрев все значения. Ваш К.О.

Comments

[Дмитрий]

Ну посмотрели вы и что дальше? Переведете строку в число и сравните?

[Rsa97]

Дмитрий, Для целых чисел первое сравнение по длине строки, для строк одинаковой длины - посимвольное сравнение.
Для вещественных в классической нотации сначала сравнение по позиции точки, потом посимвольное.
Для научной нотации сравнение экспонент, затем мантисс.
Если есть отрицательные числа, то проверка на минус в первом символе.

[Дмитрий]

Rsa97, А если миллиард чисел по 10 символов, а последнее 11. Получится вы сделали миллиард ненужных посимвольных сравнений...
Тут много нюансов, где нашему К.О. неплохо бы немного подумать и не принимать кажущееся очевидным за единственную реальность.

[Rsa97]

Дмитрий, И что? Как вы в общем случае гарантированно найдёте это число не прочитав все?

[Дмитрий]

Rsa97, Что надо читать все это само собой, вопрос же что делать с прочитанным, чтобы было быстрее. И здесь не так все очевидно, мне кажется.

[Rsa97]

Дмитрий, Думаю, что нет.
Контрпример: два числа, 9 и 10.
Вы нашли первое число, оно самое длинное на данный момент, начинается на 9. Значит следующее число 10 ваш поиск пропустит.

[Дмитрий]

Rsa97, Да, я уже стер, я понял.

[Rsa97]

Дмитрий, Единственный способ ускорения здесь - распараллеливание. Завести несколько потоков, каждый из которых обрабатывает только часть файла. Потом свести все результаты и выбрать из них наибольший.
Деление на части можно делать приблизительное, просто встаём на середину файла и ищем следующий конец строки. Затем каждую из двух частей делим таким же образом примерно пополам и т.д. Получаем 2ⁿ частей, позицию и длину каждой пишем в очередь для обработки воркерами.

[Дмитрий]

Rsa97, Хорошо, как вы будете делать само считывание? Можете привести код на чем-нибудь?

[Rsa97]

Дмитрий, Учитывая, что чтение здесь линейное, принципиальной разницы нет. Можно и напрямую с диска читать, особенно если SSD, и через буфер в памяти.

[Lynn «Кофеман»]

Что то вы загоняетесь. По сравнению со скоростью чтения все эти сравнения это копейки.

Answer 2

[Евгений Самсонов]

MapReduce

Answer 3

[Дмитрий]

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

Если чисел наибольшей размерности набирается слишком много для хранения их в оперативке, тогда можно пройтись по ним циклом и оставить наибольшее...И так далее.

Answer 4

[Алексей]

Думаю самый оптимальный вариант пройтись по файлу один раз при помощи reduce таким образом время работы алгоритма будет линейным к количеству элементов. O(n). Сортировки и прочие способы требуют множество проходов по списку, что потребует большего времени работы алгоритма. Хотя наверное лучше циклом пройтись, поскольку reduce рекурсивный по своей природе, а у вас +100500 элементов в списке, что приведет к огромному потреблению памяти.

Comments

[Роман]

У автора файл может вообще в оперативке не уместиться. О каком reduce вы говорите?

Answer 5

[xmoonlight]

1. Делим файл по смещению с поправкой на конец строки на столько частей, сколько потоков мы будем использовать для поиска значений в асинхронном режиме.
2. Зпускаем асинхронно нужное количество потоков: 1 (или несколько!) потоков на каждую часть файла.
3. После того, как всё отработает - мы сравниваем максимальные и минимальные значения между потоками.