So I’m reading your code and trying to figure out what cracked the
problem. Could you share some insights? Why to disable the GC? What idea
should one take away from other parts of your code?
Here is the code again. I will put comments inline to try to give
insight
into what I was thinking:
GC.disable
This is a real cheat. By turning off the garbage collector, you don’t
let
the ruby interpreter reclaim memory by deallocating objects that are no
longer used. Normally, the Ruby interpreter periodically runs a garbage
collection loop where it runs through all allocated objects and if they
are
not referenced any more, may free the memory, giving it back to the OS.
During the loop, your code will not run. By turning it off, your
program
can consume lots of memory, especially if it creates many throw away
objects.
n = STDIN.gets.to_i
a = Array.new(1e6+1) {|n| “”}
The above creates an Array of 1,000,001 slots. The block syntax lets
you
provide a default object dynamically. The first time you reference a
particular index in the array, the block is called to allocate the
default
object at that position.
while n > 0
i_str = STDIN.gets
i = i_str.to_i
a[i] << i_str
Here we append a string representation of the value read to string at
the
position in the index. We are creating garbage objects here. Each
string
produced by STDIN.gets, after it is appended (copied) to the string at
position i in the array, is no longer referenced anywhere. Since we
turned
off the garbage collector, the memory used by this string just hangs
around
in the ruby process.
Another interesting thing to note: Thanks to the way we created the
array
above, we start out with a new empty string for each position referenced
in
the array. If we had made the mistake of creating it like this:
a = Array.new(1e6+1, “”)
we would have an array where every position gets the same empty string
as
the default value. We would thus append all values in the input to the
same string … not what we intend.
n -= 1
end
n = 0
while n < 1_000_001
STDOUT.write a[n]
n += 1
end
This just goes through the array and writes out the value at the
position.
If we had used the wrong Array initializer, we would basically be
outputting the entire input set 1,000,000 times.
Hope that helps …
-Doug
