how to handle very large array?

[H. S. Teoh]

On Wed, Feb 09, 2022 at 11:05:23AM -0800, Ali Çehreli via Digitalmars-d-learn wrote:
> On 2/9/22 10:38, MoonlightSentinel wrote:
> 
> > There's a way to use a much smaller array to manage the lanternfish
> > population...
> 
> As soon as I read your comment, I was reminded of a certain ingenious
> sorting algorithm that is O(N). ;) After reading the problem
> description, I see your hint was useful.
[...]

If you know beforehand that your data is discrete and bounded, you can
achieve O(N) sort complexity (as opposed to O(N log N), which is the
lower bound if you cannot make any assumptions about your data beyond
their ordering).  You can use pigeonhole sort, for example, i.e., create
an M-element array of counters where M is the number of distinct values
your elements may have, then just iterate over your data and increment
the counter corresponding to each element you find (using array indexing
for O(1) access to each counter). Then iterate over the array of
counters in order and replace the input data with that many copies of
each element. Your overall complexity then would be O(N+M), which would
be O(N) if M is about the same order of magnitude as N or less.

However, this algorithm quickly becomes impractical when M grows large,
because you will soon need to create many more slots than there are
input elements. For example, sorting a general int[] this way would
require 2^32 counters, which is usually overkill unless your input has
close to 2^32 elements. (You could do it if you knew your int's are ≤ M
for some small value of M, though. But it won't work for general int[]
that can contain any value.) And trying to sort a general ulong[] this
way will not work because you would need an array of 2^64 counters,
which would not only exhaust all available RAM in today's computers, but
also take a ridiculously long amount of time to iterate in the second
step.

The insight here is *taking advantage of additional structure in your
data*.  If you take the general, minimal-assumptions approach, the best
you can do is the general O(N log N) algorithm.  However, by exploiting
additional structure in your data, you can do better.  Similarly, if you
take the naïve approach to modelling your lanternfish, you'll end up
with an unwieldy array that's far too large to fit in RAM.  If you
exploit the additional structure in your data, however, you can
accomplish the same task with a much smaller array.


T

-- 
Latin's a dead language, as dead as can be; it killed off all the Romans, and now it's killing me! -- Schoolboy