MathGroup Archive 2001

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

Search the Archive

Re: Swiftest code to turn list of ordered pairs into Markov matrix [using Sequence]

  • To: mathgroup at smc.vnet.net
  • Subject: [mg29725] Re: Swiftest code to turn list of ordered pairs into Markov matrix [using Sequence]
  • From: "Allan Hayes" <hay at haystack.demon.co.uk>
  • Date: Wed, 4 Jul 2001 18:43:42 -0400 (EDT)
  • References: <9hs1a0$bs9$1@smc.vnet.net> <9hugrb$f10$1@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

Care with Sequence

z= 100;
oplist= Table[Random[Integer,{1,z}],{100000},{2}];

Here I use  Sequence@@{x,y}  to get Sequence[x,y]

(b1=Table[0,{z},{z}];
      MapThread[(b1[[Sequence@@#1]]=#2)&,
            {First/@#,Length/@#
              }]&[
        Split[Sort[oplist]]]);//Timing

{8.79 Second,Null}

This is neat, but if I use  {x,y}[[1]], {x,y}[[2]], I get a significant
speed up.

(b2=Table[0,{z},{z}];
      MapThread[(b2[[#[[1]],#[[2]]]]=#2)&,
            {First/@#,Length/@#
              }]&[
        Split[Sort[oplist]]]);//Timing

{6.59 Second,Null}

A speed up can similarly be obtained in David Park's code.
Andrzej Kozlowski's helper function

        matrixSet[{i_, j_}, k_] := a[[i, j]] = k;

in his Markov2 code performs a similar function

Of course if we have to convert lists of different lenghts then Sequence
must be used.


The last form is still slower than Daavid Lichtblau's solution.

convertToMarkovMatrix = Compile[{{n,_Integer}, {edges,_Integer,2}},
Module[{mat = Table[0,{n},{n}]},
Map[(mat[[#[[1]],#[[2]]]] += 1)&, edges];
mat
]];


 convertToMarkovMatrix[n, oplist];//Timing

{4.94 Second,Null}

--
Allan
---------------------
Allan Hayes
Mathematica Training and Consulting
Leicester UK
www.haystack.demon.co.uk
hay at haystack.demon.co.uk
Voice: +44 (0)116 271 4198
Fax: +44 (0)870 164 0565

"Allan Hayes" <hay at haystack.demon.co.uk> wrote in message
news:9hugrb$f10$1 at smc.vnet.net...
> Seth,
>
> z= 50;
>
> oplist= Table[Random[Integer,{1,z}],{100000},{2}];
>
>
a=Fold[ReplacePart[#,Extract[#,#2]+1,#2]&,Table[0,{z},{z}],oplist];//Timing
>
>         {44.6 Second,Null}
>
> (*I replaced {#2} with #2 -- the former gave trouble that I have not yet
> tracked down*)
>
> (b=Table[0,{z},{z}];
>       MapThread[(b[[Sequence@@#1]]=#2)&,
>             {First/@#,Length/@#
>               }]&[
>         Split[Sort[oplist]]]);//Timing
>
>         {4.84 Second,Null}
>
> a===b
>
>         True
> --
> Allan
> ---------------------
> Allan Hayes
> Mathematica Training and Consulting
> Leicester UK
> www.haystack.demon.co.uk
> hay at haystack.demon.co.uk
> Voice: +44 (0)116 271 4198
> Fax: +44 (0)870 164 0565
>
> "Seth Chandler" <SChandler at Central.UH.Edu> wrote in message
> news:9hs1a0$bs9$1 at smc.vnet.net...
> > Suppose one has a list of ordered pairs oplist such as
> > {{1,5},{1,6},{2,3},{2,3} ... }. All the values in the list are positive
> > integers. The highest value in oplist is known to be some value z.
> >
> > Now one wishes to form a matrix such that the value at element i,j is
> equal
> > to
> > Count[oplist,{i,j}]. One terribly slow way to do this is
> >
> > Table[Count[oplist,{i,j}],{i,1,z},{j,1,z}]
> >
> > A faster way to do this is as follows:
> > Fold[ReplacePart[#,Extract[#,#2]+1,{#2}]&,Table[0,{z},{z}],oplist]
> >
> > Does anyone have a considerably faster way? A speed up of 100% or more
> would
> > be very helpful.
> >
> > For what it's worth Count[oplist,{something_,_}] is the same for all
> values
> > of something.
> >
> > P.S. The problem arises in converting a representation of a directed
graph
> > into a Markov transition matrix.
> >
> > Thanks,
> >
> > Seth J. Chandler
> > Associate Professor of Law
> > University of Houston Law Center
> >
> >
> >
> >
>
>
>




  • Prev by Date: Re: Swiftest code to turn list of ordered pairs into Markov matrix
  • Next by Date: freebsd and mathematica
  • Previous by thread: RE Map
  • Next by thread: freebsd and mathematica