[#16113] Strange idea... exporting from a scope — "Hal E. Fulton" <hal9000@...>

Hello...

33 messages 2001/06/01

[#16364] Re: Garbage Collection? — Michael Davis <mdavis@...>

Windows 2000 and linux (RedHat 6.2). I have run these tests on both OSs.

12 messages 2001/06/09

[#16400] Symbolic Computation III — Mathieu Bouchard <matju@...>

14 messages 2001/06/11

[#16502] Playing with Ruby Syntax (was: Initial thoughts about Ruby From a Smalltalk Programmer) — jweirich@...

Michael> Hi Everyone, I have to say I'm utterly fascinated by Ruby

9 messages 2001/06/15

[#16661] Problem running irb with Ruby 1.6.4 under FreeBSD 4.0 — Bob Alexander <balexander@...>

I've installed Ruby 1.6.4 on a FreeBSD 4.0 machine, and get the

11 messages 2001/06/20

[#16686] opening db files made by apache dbmmanage — Fritz Heinrichmeyer <fritz.heinrichmeyer@...>

14 messages 2001/06/21

[#16801] rb_define_class() vs Class.new() — Kero van Gelder <kero@...4050.upc-d.chello.nl>

Hi,

18 messages 2001/06/23
[#16802] Re: rb_define_class() vs Class.new() — ts <decoux@...> 2001/06/23

>>>>> "K" == Kero van Gelder <kero@d4050.upc-d.chello.nl> writes:

[#16841] RE: national characters is strings — "Aleksei Guzev" <aleksei.guzev@...>

Next week I'll try to rebuild Ruby with Unicode strings. But it would be

15 messages 2001/06/25
[#16842] Re: national characters is strings — matz@... (Yukihiro Matsumoto) 2001/06/25

Hi,

[#16843] Re: national characters is strings — "Aleksei Guzev" <aleksei.guzev@...> 2001/06/25

That's good enough. But I'm afraid this could ( not would ) cause string

[#16868] Something strange with Ruby's inheritance mechanism — Eric Jacoboni <jaco@...>

As Ruby beginner, i try some "canonical" OO scripts. Doing so, I've

14 messages 2001/06/25
[#16873] RE: Something strange with Ruby's inheritance mechanism — "Aleksei Guzev" <aleksei.guzev@...> 2001/06/26

[#16879] Re: Something strange with Ruby's inheritance mechanism — Mathieu Bouchard <matju@...> 2001/06/26

On Tue, 26 Jun 2001, Aleksei Guzev wrote:

[#16869] Something strange with Ruby's inheritance mechanism — Eric Jacoboni <jaco@...>

As Ruby beginner, i try some "canonical" OO scripts. Doing so, I've

12 messages 2001/06/25

[#16881] — "Aleksei Guzev" <aleksei.guzev@...>

32 messages 2001/06/26
[#16916] Re: Method overloading (option) Was: Re: — "Wayne Blair" <wayne.blair@...> 2001/06/26

[#16920] Re: Method overloading (option) Was: Re: — matz@... (Yukihiro Matsumoto) 2001/06/26

Hi,

[#16888] finalizers, destructors and whatnot — "David Leal" <david@...>

Hi all,

16 messages 2001/06/26

[#17037] keeping an Exception object alive — David Alan Black <dblack@...>

Hello --

19 messages 2001/06/28
[#17055] Re: keeping an Exception object alive — matz@... (Yukihiro Matsumoto) 2001/06/29

Hi,

[#17066] RCR: Exception methods (was: Re: Re: keeping an Exception object alive) — David Alan Black <dblack@...> 2001/06/29

Hello --

[#17076] Re: RCR: Exception methods (was: Re: Re: keeping an Exception object alive) — matz@... (Yukihiro Matsumoto) 2001/06/29

Hi,

[#17079] Re: RCR: Exception methods (was: Re: Re: keeping an Exception object alive) — David Alan Black <dblack@...> 2001/06/29

Hello --

[#17138] Re: RCR: Exception methods (was: Re: Re: keeping an Exception object alive) — matz@... (Yukihiro Matsumoto) 2001/07/02

Hi,

[#17141] Re: RCR: Exception methods (was: Re: Re: keeping an Exception object alive) — David Alan Black <dblack@...> 2001/07/02

Hello --

[#17142] Re: RCR: Exception methods (was: Re: Re: keeping an Exception object alive) — ts <decoux@...> 2001/07/02

>>>>> "D" == David Alan Black <dblack@candle.superlink.net> writes:

[ruby-talk:16708] e: bag difference

From: Christian Szegedy <szegedy@...>
Date: 2001-06-21 14:57:10 UTC
List: ruby-talk #16708
Hugh Sasse Staff Elec Eng wrote:

> >     def delete_first(x)
> >  
> >         if (i = self.index(x))
> >             self.delete_at(i)
> >         end
> >  
> >     end
> >  
> >     def bag_minus(other)
> >  
> >         difference = Array.new
> >         unwanted  = other.clone
> >  
> >         self.each do |x|
> >             if !unwanted.delete_first(x)
> >                 difference.push(x)
> >             end
> >         end
> >  
> >         return difference
> >     end
[...]
> Thank you.  I was a bit confused by the other solution too, but it seemed
> to rely on going through the array more than once.  Anyway, I 
> settled on this:
[...]
> class Array
>    def bag_subtract!(other)
>       other.each {
>          |value|
>          i = index(value)
>          delete_at(i) if i
>      }
>      self
>   end
> end

Both soultions are quadratic, because index is linear.
It could be solved in n*log(n) time.
It does not matter for small arrays  
but can be quite slow even if self has only 100 elements.

Christian

In This Thread

Prev Next