From: Mark Van Holstyn <mvette13@...>
Date: 2005-10-18T05:40:40+09:00
Subject: Re: How to get non-unique elements from an array?

------=_Part_86147_19898330.1129581637841
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Hey Sam,

I too tried a solution similar to...
a.select{|e| a.index(e) !=3D a.rindex(e)}.uniq

Then i tried the one which i wrote...
t=3D[]; a.select{ |e| r=3Dt.include?e; t<<e; r }.uniq

The second runs MUCH faster. The first one must search the array twice for
each element in in, and therefor runs something on the order of n^3 worst
case. The second only searches once for each and runs n^2 worst case. As fo=
r
the version with grep... Also, a.grep seems to run somewhere on the order o=
f
n^4.


Adding mine to ryan's bench mark i come out with...

a =3D [0,1,2,3,4,5,2,3]

BMN =3D 50000
bm(5) do |bx|
bx.report('index ') { BMN.times { a.select{|e| a.index(e) !=3D a.rindex(e)}=
.uniq
} }
bx.report('grep ') { BMN.times { a.select{|e| a.grep(e).length > 1}.uniq } =
}
bx.report('scan ') { BMN.times { a.sort.join('
').to_s.scan(/(\d+)\s(\1)+/).flatten.uniq } }
bx.report('inject ') { BMN.times { a.uniq.inject(a.dup) { |b,i| b.delete_at=
(
b.index(i)) ; b } } }
bx.report('gsub ') { BMN.times {
a.to_s.gsub(/(.)(?!.*\1)/,'').split('').map{|i|i.to_i}
} }
bx.report('include') { BMN.times { t=3D[]; a.select{ |e| r=3Dt.include?e; t=
<<e;
r }.uniq } }
end

user system total real
index 1.312000 0.000000 1.312000 ( 1.328000)
grep 3.594000 0.000000 3.594000 ( 3.625000)
scan 3.094000 0.000000 3.094000 ( 3.109000)
inject 1.406000 0.000000 1.406000 ( 1.407000)
gsub 2.844000 0.000000 2.844000 ( 2.843000)
include 1.109000 0.000000 1.109000 ( 1.110000)



Mark

On 10/17/05, Sam Kong <sam.s.kong@gmail.com> wrote:
>
> Hi!
>
> I'm the OP.
> I thank those who replied to my message.
> I learned a lot and seeing all different approaches was fun.
>
> Somebody emailed me with his own solution which I like very much.
> I want to share it with the group.
>
> a =3D [0,1,2,3,4,5,2,3]
> a.select{|e| a.index(e) !=3D a.rindex(e)}.uniq
>
> It is very brief and still very easy to understand.
> Don't you think so?
>
> I wonder if my slightly modified version works.
>
> a.select{|e| a.grep(e).length > 1}.uniq
>
> grep is for pattern but seems to work fine for integers.
> I'm not sure though. (Simple tests show it works.)
>
>
> In my opinion, using regex is too much for this problem (maybe
> slower?).
> Array#inject seems to be good but I get confused whenever I come across
> it (maybe I'm not smart enough).
>
> What do you think?
>
> Thanks all!
>
> Sam
>
>
>


--
Mark Van Holstyn
mvette13@gmail.com
http://lotswholetime.com

------=_Part_86147_19898330.1129581637841--