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, 2013 at 4:34

1 Answer 1

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? Sep 20, 2013 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, 2013 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, 2013 at 12:56
  • fjarri had me at O(n log n).
    – unflores
    Nov 30, 2016 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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