As you’re coding in a language, particularly a high-level language like Ruby, you may worry about the efficiency of various operations—particularly if you were once a DOS programmer working on extremely-limited machines at one time.
For example, the Ruby Array type has push, pop and shift operations. Push and pop add an element to the end of the array and remove it, respectively, of course. As you might expect, the capacity of the array is increased in blocks large enough so that the vector does not need to be reallocated for every push. As you might also expect, popping an element off the array merely retrieves the value and decrements the length.
However, what about shift, which pops an element off the beginning of the array? I was pleasantly surprised to find that Ruby does the equivalent of a pop—after retrieving the element, it increments the pointer and decrements the length.
The only operation of the set with performance implications is unshift, which prepends an element to the array. This operation always involves moving a block off memory, which I’m sure is fairly optimized, but it is still an O(n) rather than an O(1) operation.
