Forum: Ruby Array comparison.. why does this work.

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Jean N. (Guest)
on 2007-03-01 04:45
How does Ruby do Array comparision?

[code]
old_inventory = [ 'a', 'b', 'd' ]
new_inventory = [ 'a','e', 'c' ]

puts "The following files have been added: "
puts new_inventory - old_inventory
puts ""
puts "The following files have been deleted: "
puts old_inventory - new_inventory
[/code]

Notice the output is correct so it's not a case of element 0's being
compared in each array.

So...

Does Ruby sort arrays in memory first? or is a scan done 1 element at a
time?

Thanks.
unknown (Guest)
on 2007-03-01 04:58
(Received via mailing list)
Hi --

On Thu, 1 Mar 2007, Jean N. wrote:

> How does Ruby do Array comparision?

One element at a time.

>
> Notice the output is correct so it's not a case of element 0's being
> compared in each array.
>
> So...
>
> Does Ruby sort arrays in memory first? or is a scan done 1 element at a
> time?

You're not doing comparison, though; you're doing subtraction.
Subtraction doesn't depend on order.  You can think of it as
"without":

   [1,2,3] - [1]    => [2,3]  # [1,2,3] without 1
   [1,2,3,1] - [1]  => [2,3]  # [1,2,3,1] without 1
   [1,2,3] - [2]    => [1,3]  # [1,2,3] without 2

etc.


David
Jean N. (Guest)
on 2007-03-01 06:21
>
> You're not doing comparison, though; you're doing subtraction.
> Subtraction doesn't depend on order.  You can think of it as
> "without":
>
>    [1,2,3] - [1]    => [2,3]  # [1,2,3] without 1
>    [1,2,3,1] - [1]  => [2,3]  # [1,2,3,1] without 1
>    [1,2,3] - [2]    => [1,3]  # [1,2,3] without 2
>
> etc.
>
>
> David

Sorry, when I mentioned comparison I meant "Under the hood". (I realise
'-' is subtractions ), but the interpreter needs to perform comparisoin
to see if an element exists somewhere.

I was curious if it just interates through one array looking for that
element in the second, or does it (internally) sort the array, iterate
each array performing comparision and if a > b skipping the equality
determination to save CPU cycles and doing a 'next'.

I guess what I"m saying (Makes more sense when you see pseudo code) is
how does it work in the interpreter.
Daniel S. (Guest)
on 2007-03-01 07:34
(Received via mailing list)
> I was curious if it just interates through one array looking for that
> element in the second, or does it (internally) sort the
> array, iterate
> each array performing comparision and if a > b skipping the equality
> determination to save CPU cycles and doing a 'next'.

I would guess that it would just do an include? call on the second array
and delete the element if it is true.

Doing the sort first would probably not be faster - a sort operation is
not a cheap operation, and there is no guarantee that the members of an
array are mutually sortable anyway (["a", 1, Object.new] for example) -
there is no way in which the '-' method would be able to rely on calling
the '<=>' method on its contents.

Dan.
Justin C. (Guest)
on 2007-03-01 08:04
(Received via mailing list)
Daniel S. wrote:
> Doing the sort first would probably not be faster - a sort operation is
> not a cheap operation, and there is no guarantee that the members of an
> array are mutually sortable anyway (["a", 1, Object.new] for example) -
> there is no way in which the '-' method would be able to rely on calling
> the '<=>' method on its contents.
>
> Dan.
>

Don't forget, you can always just look at the source[1].
It looks to me like it converts the second array to a hash, then
iterates through the first array, checking if each element is in the
newly created hash.
If it is, it skips it. If not, the value goes in the new array.

-Justin

[1] http://ruby-doc.org/core/classes/Array.src/M002261.html
Jean N. (Guest)
on 2007-03-01 08:30
>
> Don't forget, you can always just look at the source[1].
> It looks to me like it converts the second array to a hash, then
> iterates through the first array, checking if each element is in the
> newly created hash.
> If it is, it skips it. If not, the value goes in the new array.
>
> -Justin
>
> [1] http://ruby-doc.org/core/classes/Array.src/M002261.html

Awesome I didn't now where to find the sources to read them.

Thanks!
This topic is locked and can not be replied to.