StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Their solution does not test for nil when it tries to find the top. </p> <p>They use the @top value as the index of the topmost element and increment and decrement it whenever a new element gets added or removed. This is done through the <code>@top.succ</code> and <code>@top.pred</code> method calls.</p> <p><strike>There is no particular reason, why they fill their stack with nils, when something gets popped. In theory they could just decrease the @top counter and leave whatever was at that stack position stay there.</strike> As @Jan Dvorak pointed out the stack is filled with nils again to prevent memory leaking from the garbage collector.</p> <p>Your version relies on the implementation of Array.pop and Array.push. Those may very well not actually shrink the allocated space, when popping a value, although I do not know the specific implementations of them.</p> <p>Why constantly changing the size of an Array is a performance problem:</p> <p>Lets say you want to create an Array of size 2. To do this ruby has to ask the operating system for a chunk of memory that is continuously unused and big enough to hold an Array of size 2. Lets say this requires 24 bytes.</p> <p>So if you now want to push 3 values instead of only 2 you will have to request another chunk of memory from the operating system that now can hold the data for an Array of size 3. Lets say this requires 32 bytes. This new location might not be at the same place as your previous chunk of memory as it may be that after your previous 24 bytes another program has stored his own value. Now you have to copy your Array of size 2 to the new location and only then can you add your 3rd value to that array.</p> <p>Now the point is that rubys Array class doesn't actually behave this way. It will very likely always request more memory than you initially tell it to from the operating system and will not decrease that memory after every pop. Furthermore it will probably not increase the requested memory by 1 Array element if it gets to big, but maybe just try to get twice as much memory at once when it runs out of memory.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload