What is the fastest algorithm for finding the maximum value in a large file?

Question

Mathematics

Hello.
Let's say there is a file that contains a number on each line. In this case, the file itself can be extremely large (for example, several hundred gigabytes in size). What is the fastest way to find the maximum (minimum) value in a given file?
Thank you.

Answer 1

Looking at all values. Your K.O.

Answer 2

MapReduce

Answer 3

The main optimization, provided that the numbers can be of any size, is to read the dimension of the numbers, storing the numbers with the largest at the moment in the array, or to read their positions if the file is available for reading completely and not sequentially. As soon as a number of greater bit depth is found, all other previously saved data can be reset without comparison.
If there are too many numbers of the highest dimension to store them in the RAM, then you can loop through them and leave the largest one ... And so on.

Answer 4

I think the best option is to go through the file once using reduce, so the algorithm's running time will be linear to the number of elements. O(n). Sorting and other methods require many passes through the list, which will require more time for the algorithm to run. It's probably better to loop though, since reduce is recursive in nature, and you have +100500 items in the list, which will result in a huge memory consumption.

Answer 5

1. Divide the file by offset, adjusted for the end of the line, into as many parts as the number of threads we will use to search for values ​​in asynchronous mode.
2. Run the required number of threads asynchronously: 1 (or several!) threads for each part of the file.
3. After everything works out, we compare the maximum and minimum values ​​​​between threads.