MathGroup Archive 1997

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

Search the Archive

Re: How to select unique elements in a list?

  • To: mathgroup at
  • Subject: [mg8307] Re: How to select unique elements in a list?
  • From: Robert Villegas <villegas>
  • Date: Sun, 24 Aug 1997 04:46:52 -0400
  • Organization: Wolfram Research
  • Sender: owner-wri-mathgroup at

About my order-restoring function that I used on the singletons:

RestoreOrder[subset_, list_] :=
  Last /@
    Sort[ {Position[list, #, {1}, 1][[1, 1]], #}& /@

I just remembered that Todd Gayley and I realized a far faster indexing
method for a somewhat similar problem several months ago:  build a rule
table mapping each element to its position.  Here is the new, faster

RestoreOrder[subset_, list_] :=
With[{elemIndex = Dispatch @ Thread[list -> Range @ Length[list]]},
  Last /@
    Sort[{Replace[#, elemIndex], #}& /@ subset]

Here's a timing comparison on a 15,000-element list with lots of singletons:

bigList = Table[Random[Integer, {1, 10*^3}], {15*^3}];

Timing[oldResult = Singletons[bigList];]

{50.93 Second,Null}

Timing[newResult = SingletonsNew[bigList];]

{0.96 Second,Null}

oldResult === newResult




What you sacrifice with the big hash table, of course, is memory.
MaxMemoryUsed[] increases by a couple megabytes or more when this
is run on a list of 10,000 integers.  MemoryInUse[] doesn't change
that much, which means the memory used by the temporary hash table
is available for future Mathematica use, but not for other

   If you're going to re-order many times with respect to the same master
list, you might want RestoreOrder to remember the hash table so it
doesn't have to regenerate it each time.  Generating a hash table is
pretty fast, so don't bother unless you need it quite a few times or
you're on a slow machine.  Perhaps something like the following:


Options[RestoreOrder] = {Remember -> False};

RestoreOrder[subset_, list_, opts___] :=
With[{record = $RestoreOrderRecord[list]},
With[{elemIndex =
          _$RestoreOrderRecord :>
            Dispatch @ Thread[list -> Range @ Length[list]]
  If[(Remember /. Flatten[{opts, Options[RestoreOrder]}]) &&
      Head[record] === $RestoreOrderRecord,
    $RestoreOrderRecord[list] = elemIndex

  Last /@
    Sort[{Replace[#, elemIndex], #}& /@ subset]

Now use the option Remember -> True for individual cases or do
SetOptions[RestoreOrder, Remember -> True] to make it remember all
future hash tables (then you'll be sacrificing MemoryInUse[] as well
as MaxMemoryUsed[]).

Maybe there's a more elegant way to implement the remembering mechanism,
but this works.

Robby Villegas

  • Prev by Date: Re: Need package for Lyapunov exponents
  • Next by Date: Re: color space curve
  • Previous by thread: Re: How to select unique elements in a list?
  • Next by thread: Re: How to select unique elements in a list?