Re: Intersection and element counts
- To: mathgroup at smc.vnet.net
- Subject: [mg20690] Re: [mg20615] Intersection and element counts
- From: BobHanlon at aol.com
- Date: Sun, 7 Nov 1999 02:10:19 -0500
- Sender: owner-wri-mathgroup at wolfram.com
Arturas,
Below I have included a second method (myIntersection2) which does not use a
Sort and a minor improvement to the first method (myIntersection1). However,
the timing is the same even for large lists which have been shuffled. I
prefer the second method because it is shorter and cleaner, but the speed
does not appear to improve.
Bob Hanlon
__________________________
shuffle[inList_List] :=
Module[{oldList = inList, newList = {}, ptr},
Do[ptr = Random[Integer, {1, Length[oldList]}];
newList = Append[newList, oldList[[ptr]]];
oldList = Drop[oldList, {ptr}], {Length[inList]}]; newList];
runs[aList_List?VectorQ] := {First[#], Length[#]} & /@ Split[Sort[aList]];
myIntersection1[list1_List?VectorQ, list2_List?VectorQ] := Module[
{intr = Intersection[list1, list2]},
Flatten[
Transpose[{Select[runs[list1], MemberQ[intr, #[[1]]] &],
Select[runs[list2], MemberQ[intr, #[[1]]] &]}] /. {{x_,
m_Integer}, {x_, n_Integer}} :> Table[x, {Min[m, n]}]]];
myIntersection2[list1_List?VectorQ, list2_List?VectorQ] :=
Flatten[Table[#, {Min[Count[list1, #], Count[list2, #]]}] & /@
Intersection[list1, list2]];
list1 = shuffle[
Join[Table[a, {1000}], Table[b, {200}], Table[c, {750}],
Table[d, {500}]]];
list2 = shuffle[
Join[Table[a, {200}], Table[b, {750}], Table[c, {100}],
Table[e, {500}]]];
Check equivalence
Sort[myIntersection1[list1, list2]] === Sort[myIntersection2[list1, list2]]
True
Baseline time
Timing[Intersection[list1, list2] === Intersection[list2, list1]]
{0.0166667 Second, True}
Timing[myIntersection1[list1, list2] === myIntersection1[list2, list1]]
{0.0833333 Second, True}
Timing[myIntersection2[list1, list2] === myIntersection2[list2, list1]]
{0.0833333 Second, True}
In a message dated 11/5/1999 4:57:53 AM, acus at itpa.lt writes:
>Thank You very much for the code.
>
>I noticed, however the use of Sort function.
>The assymptotic therefore will not be good.
>
>Also I wonder if there is a possibility
>to subtract one set from another:
>{a,a,b}-{a,b}={a}.
>Many of Mathematica functions list manipulation
>(Cases, Select,...) do not distinquish
>the same elements. They select all elements
>with the given property. The general
>problem is therefore to delete
>just one element with the given propery.
>
>I hope the algorithms for such manipulation should be
>even faster, as they can stop after one succeeding
>event and therefore there are no need to find or delete
>all alements with a given property.
>
>Thank You very much, I would be very thankful
>if You could think about these problems and
>fast implementation with Mathematica:
>I realy very need a fast (at least theoretical speed)
>implementation algorithm for this intersection
>