From: Josh Cheek Date: 2011-03-04T19:36:07+09:00 Subject: Re: Extracting the shortest string from an array --0023545bd4d8f440b9049da5b1be Content-Type: text/plain; charset=ISO-8859-1 On Fri, Mar 4, 2011 at 4:11 AM, Robert Klemme wrote: > On Thu, Mar 3, 2011 at 7:18 PM, Josh Cheek wrote: > > On Thu, Mar 3, 2011 at 11:35 AM, Robert Klemme > > wrote: > > > >> On 03.03.2011 16:02, Thorsten Hater wrote: > >> > >>> in Ruby 1.9 this should work: > >>> > >>> arr.sort_by(&:length)[0] > >>> > >> > >> Inefficient as it creates a new array. Better do > >> > >> irb(main):001:0> ["qwe", "qwerty"].min_by(&:length) > >> => "qwe" > >> > >> > >> or more portable/readable (1.8 compatible): > >>> > >>> arr.sort_by{|s| s.length }[0] > >>> > >> > >> Inefficient as well (see above). > > > They're also O( n lg n ) where the correct solution, using min, is O(n) > > How do you know that it's O(n * log n)? A reasonable implementation > of min_by would look like this: > > def min_by(enum, &c) > min = nil > val = nil > > enum.each do |e| > e_val = c[e] > > if val.nil? || e_val < val > min = e > val = e_val > end > end > > min > end > > As far as I can see this is O(n). > > Right. This was my point: using min is O(n), using sort is O(n lg n) > Also, big O isn't everything. Usually object allocation is very > expensive (compared to other operations) because of the GC > housekeeping overhead. > > I don't contest this. I was pointing out that in addition to creating more objects, as you previously mentioned, using sort also has a worse time complexity. --0023545bd4d8f440b9049da5b1be--