Extracting the shortest string from an array

  • Thread starter Iñaki Baz Castillo
  • Start date
I

Iñaki Baz Castillo

Hi, given the following array:

array =3D ["qwe", "qwerty"]

How to get the shortest element ("qwe") from the array?
I whink I must inspect all the elements within the array and manually
select the shortest string, do I miss some cool feature of Array class
or Enumerable module?

Thanks a lot.

--=20
I=C3=B1aki Baz Castillo
<[email protected]>
 
T

Thorsten Hater

Hi,

in Ruby 1.9 this should work:

arr.sort_by(&:length)[0]

or more portable/readable (1.8 compatible):

arr.sort_by{|s| s.length }[0]


Am 03.03.2011 15:47, schrieb Iñaki Baz Castillo:
 
P

Paul McKibbin

Hi,

You could use

array.min {|x,y| x.size <=3D> y.size}

to force a min to use sizes rather then their natural order

Mac
 
R

Robert Klemme

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).

Cheers

robert
 
P

Paul McKibbin

[Note: parts of this message were removed to make it a legal post.]

Very true

array.min_by{|a| a.size} would also do the trick.

Paul
 
J

Josh Cheek

[Note: parts of this message were removed to make it a legal post.]

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).

Cheers

robert
They're also O( n lg n ) where the correct solution, using min, is O(n)
 
R

Robert Klemme

in Ruby 1.9 this should work:

=A0 =A0arr.sort_by(&:length)[0]

Inefficient as it creates a new array. =A0Better do

irb(main):001:0> ["qwe", "qwerty"].min_by(&:length)
=3D> "qwe"


=A0or more portable/readable (1.8 compatible):
=A0 =A0arr.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 =3D nil
val =3D nil

enum.each do |e|
e_val =3D c[e]

if val.nil? || e_val < val
min =3D e
val =3D e_val
end
end

min
end

As far as I can see this is O(n).

Also, big O isn't everything. Usually object allocation is very
expensive (compared to other operations) because of the GC
housekeeping overhead.

Cheers

robert

--=20
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/
 
J

Josh Cheek

[Note: parts of this message were removed to make it a legal post.]

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.
 
R

Robert Klemme

On Thu, Mar 3, 2011 at 11:35 AM, Robert Klemme

On 03.03.2011 16:02, Thorsten Hater wrote:

in Ruby 1.9 this should work:

=A0 =A0arr.sort_by(&:length)[0]


Inefficient as it creates a new array. =A0Better do

irb(main):001:0> ["qwe", "qwerty"].min_by(&:length)
=3D> "qwe"


=A0or more portable/readable (1.8 compatible):

=A0 =A0arr.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=
)

Right. This was my point: using min is O(n), using sort is O(n lg n)

OK, now I get what you mean. You were referring to the sorts. That
wasn't clear to me.
I don't contest this. I was pointing out that in addition to creating mor= e
objects, as you previously mentioned, using sort also has a worse time
complexity.

Yep, sorry for the noise.

Cheers

robert


--=20
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top