From: Robert Klemme <shortcutter@...>
Date: 2010-02-15T17:25:08+09:00
Subject: Re: Compare and delete element from an array

2010/2/15 Greg Ma <gregorylepacha@msn.com>:
> Hi,
> I try to compare an arroy of Tag and an array of string. I would like to
> remove from my array of Tag all element that are in the array of string.
> I,ve done the method below that should be working fine. When i look at
> the console result, the element are equals, so is should be deleted but
> it is not. I donc understand why??... :/
>
> #Method in Student Class
> def remove_tags(array_of_tags)
>    if !array_of_tags.empty?
>      array_of_tags.each do |tag|
>        tags.delete_if {
>          |x| x.name == tag
>          puts x.name + "-"+ x.name.length.to_s
>          puts tag + "-"+ tag.length.to_s
>          puts "-----"
>          }
>      end
>      puts tags
>    end
>  end

This algorithm has roughly effort O(n^2) because you compare all pairs
of elements.

I don't know sizes of your data structures but here's how I'd do it

require 'set'

def remove_tags(array_of_tags)
  unless array_of_tags.empty?
    aot = array_of_tags.to_set
    tags.delete_if {|t| aot.include? t.name}
  end

  self
end

The advantage is that Set has O(1) lookup because it uses hashing
internally.  It may not pay off for small data structures so you could
as well do

def remove_tags(array_of_tags)
  tags.delete_if {|t| array_of_tags.include? t.name} unless array_of_tags.empty?
  self
end

This one still has O(n^2) but since Array#include? is used which is
implemented in C chances are that is faster than the variant with Set
because the Set creation overhead is removed.

Kind regards

robert

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