3

If I am loading a whole load of items (un-ordered words from a file or something) would it be more efficient to load them all to a Ruby array, and then use the built in sort! method or to do a binary lookup for the place of each item in the list as I load it, and add it in that position.

Basic code:

array = []
lines.each do |line|
    array.push line
end
array.sort!

vs

array = []
lines.each do |line|
    array.insert(find_index(line), line)
end

find_index() would lookup the correct index for the item in the array using a binary search.

1
  • 1
    Have you profiled them for a small data set? – user40980 Sep 20 '13 at 4:34
5

array.insert is O(n) for insertions in the middle (because it has to copy a part of the array), making the second variant O(n^2), while push is O(1), and sort! is O(n log n), so the first variant is only O(n log n). Also the first variant looks cleaner.

4
  • And there is no data structure that would minimise the insertions? – Will Richardson Sep 20 '13 at 5:05
  • You could use binary trees, but they, of course, have their own drawbacks (in terms of performance of certain operations, or memory footprint). And you do not need them for the particular task you have described here. – fjarri Sep 20 '13 at 5:12
  • I'm not 100% sure about this, but given its speed Ruby's sort is also probably written in C, not Ruby, so you'll get far better performance out of it than most anything you write by hand in Ruby to do a similar function. – KChaloux Sep 20 '13 at 12:56
  • fjarri had me at O(n log n). – unflores Nov 30 '16 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.