MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Intersection and element counts

  • To: mathgroup at
  • Subject: [mg20690] Re: [mg20615] Intersection and element counts
  • From: BobHanlon at
  • Date: Sun, 7 Nov 1999 02:10:19 -0500
  • Sender: owner-wri-mathgroup at


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]}, 
        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]]


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 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:
>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

  • Prev by Date: Re: Intersection and element counts
  • Next by Date: Re:Color of GridLines
  • Previous by thread: Re: Intersection and element counts
  • Next by thread: Re: Intersection and element counts