How to look for the 10^5th largest element in an array of 10^10 elements?

Question

Use the PRNG with seed 4020 (first 3 numbers are -2123524894 961034805 1071375651) to generate 10^10 integers. Print the 10^5th largest element among the numbers generated.

Of course if the problem was at a smaller scale, I would have been able to solve it in a click, but I cannot figure out how to solve it. One approach was using the median using heaps method(BAD IDEA), then tried to div the input into chunks and try finding it in those, but none of those approaches are to work. I think I am getting stuck on the wrong things , there is no way this problems solution requires a supercomputer to calculate, so of course my thinking is wrong, can you help point me in the right direction as to what I can do to solve this?

Answer 1

Notice that 10^10 is much (100,000 times) larger than 10^5, so avoid storing all 10^10 integers.

One approach could be this:

• For the first 10^5 integers, insert them into an array
• Sort the array
• For the remaining integers: if the integer is larger than the smallest integer of the array, discard the smallest integer and insert the new integer in its sorted place in the array. Otherwise, discard the integer. Notice that the size of the array will remain 10^5
• After all 10^10 integers have been processed, the result is the smallest integer in the resulting array

Answer 2

Assuming your random numbers are in the range -2³¹...2³¹-1, you will get a pretty dense distribution - each integer will be repeated 2-3 times. Let's say N times. So you can estimate what the answer should be: M - 10⁵/N, where M is the maximum.

Then allocate an array of counters for ±500 numbers around your estimated answer. Count how many times each of these numbers is generated, as well as how many times larger or smaller numbers are generated. If the count of larger numbers at the end is less than 10⁵, you can analyze your small array of counters to get the exact answer. If you "missed" your expected answer - bad but not too bad! Update your estimate and generate the numbers again.

Answer 3

Use a Binary Heap.

1. Collect first 10^5 samples for PRNG.

2. Form a MINIMUM binary heap.

3. For every number from the rest of 10^10-10^5 numbers.

   • If it is smaller than or equal to heap's minimum then discard the sample
   • If it is larger than heap's minimum
     • extract the minimum from the heap
     • push a new sample into the heap

4. Dump the minimum from the heap.

Assuming N to be the length of the sequence (i.e. 10^10) and M to the rank of sought value (i.e. 10^5):

• Memory Complexity is O(M)
• Time complexity is O(N * log M)

EDIT

Assuming that the PRNG can be restart, the algorithm could be further improved.

1. Split the range of PRNG's values R (i.e. 2^32) to S = sqrt(R)ranges.
2. For each value V in the sequence update increment a bucket at position floor(V / R).
3. Find the bucket where M-th largest element lies, call it k.
4. Split k-th bucket into S sub-buckets, each representing a single integer.
5. Reset PRNG.
6. For each value V in the sequence:
   • if it does not belong to range of k-th bucket, just ignore it
   • otherwise increment sub-bucket at position V % R
7. Find the sub-bucket with the desired element.

The time complexity will be O(N + sqrt(R)) = O(N), and memory complexity will be O(sqrt(R)).

Answer 4

For a sequence of N items where you want to find the Tth largest value in the sequence where storing N items is unmanageable (ala 10 billion), but storing T items is manageable (like 100000), then a sorted map data structure that maps between values in the sequence to the number of occurrences seen for that value can be used.

Sorted maps are often implemented as (binary) trees and have the keys in sorted order. Most programming languages have some variation of this data structure in their standard library.

Algorithm is this:

Create an empty sorted map that maps between a value
to the number of occurrences that value was seen in the
sequence
 
For each index from 0 to T-1:
    Generate a new random sequence value => V
    Store V as the key in the map:
        if V is not in the map already, then map[V] = 1
        if V is already in the map, then map[V] = map[V] + 1

Then assess what the smallest number, S, seen so far is in the map.

For each index from T to N-1:
    Generate a new sequence value => V
    if (V <= S):
       skip;
    else:
        decrement the smallest value, S, from the map. If map[S] goes to 0, then remove S entirely from the map.
        insert V in the same manner as above
        Reassess what S is by inspecting what the smallest (first) item in the map is.

After the second for loop, the Tth largest element is the
smallest value in the map.

Here's a C++ implementation that leverages std::map for a sorted table.

int main() {

    long long N = 10'000'000'000LL;
    long long T = 100'000;  // want the Tth largest number in the sequence
    long long smallest = LLONG_MAX;
    long long removals = 0;

    std::map<long long, long long> table; // hash table that maps between a random value and the number of occurrences
    std::vector<long long> largestNumbers;

    seedRandomNumberGenerator();

    for (long long i = 0; i < N; i++) {

        if (i % 1'000'000LL == 0) {
            std::cout << i << std::endl;
        }

        long long value = getNextRandomNumber();
        if (i < T) {
            table[value]++; // this will implictly insert table[value]=1 if value isn't in the table, otherwise increments the count
            if (value < smallest) {
                smallest = value;
            }
        } else {

            // at this point there are 100000 items tracked in the hash table
            // any time we encounter a value greater than the smallest item
            // then we push the smallest item out

            if (value > smallest) {
                removals++;
                auto itor = table.begin();
                if ((--itor->second) == 0) {
                    table.erase(itor);
                    table[value]++;
                    smallest = table.begin()->first;
                }
            }
        }
    }

    long long tValue = table.begin()->first;
    std::cout << "the " << T << "th largest value in the sequence is" << tValue << "\n";
    std::cout << "there were " << removals << "from the table\n";
}

• Each insert and lookup where table[value]++ is invoked is typically O(lg(T)). So the cost of the first T inserts is O(T*lg(T))

• Removals, where table.erase is invoked, into the map in C++ is understood to be O(T). When i is small, the probability of value > smallest is high and the cost of a removal from the map is paid. As i approaches N, then the probability of a removal goes way down to T/N probability or .00001 in the case of 100K/10B. It my simulation of N=10B and T=100K, there was about 1 million removals.

• table->begin() is O(1)

The above code, when compiled as a release build with optimizations takes about 3-5 minutes to run on my new Core-i9 workstation. I'm using a modified rand() algorithm on as the implementation for getNextRandomNumber().

I think there are several optimizations that can be done to beat the performance of std::map at the expense of using slightly more memory. I'll have to sleep on that.

Answer 5

can you help point me in the right direction as to what I can do to solve this?

OK, so minimal code provided.

How to look for the 10⁵th largest element in an array of 10¹⁰ elements?

Form a priority queue of size 10⁵ (least is highest priority). Priority queues are really quite simply. This can be as simple as:

void PQ_add(int value);// TBD for OP. It should be O(log(length))
int PQ_pop_top(void);  // TBD for OP. It should be O(log(length))
int PQ_top(int value); // pq[0]
size_t PQ_length(void);// length
size_t PQ_size(void);  // PQ_N

#define PQ_N 100000
int pq[PQ_N];
size_t length = 0;

Then loop 10¹⁰ times considering to insert the new random value. Each insertion/deletion costs O(length*log(length)) time. When length < PQ_N, simply insert. After the first PQ_N, first pull the lowest value out if it is smaller than the new value and then add the new value.

The top of the queue will be the 100,000th greatest one.

We really do not need the array of 10¹⁰ elements. Simply a loop the generates the 10¹⁰ values.

Finding the N greatest value and with M as the count of random values, the overall time cost O(M*log(N)) and space cost O(N).

Deeper

Review selection algorithms.