MathGroup Archive 2001

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

Search the Archive

Re: Swiftest code to turn list of ordered pairs into Markov matrix

  • To: mathgroup at smc.vnet.net
  • Subject: [mg29721] Re: [mg29683] Swiftest code to turn list of ordered pairs into Markov matrix
  • From: "Fred Simons" <f.h.simons at tue.nl>
  • Date: Wed, 4 Jul 2001 18:43:40 -0400 (EDT)
  • References: <200107030840.EAA12085@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

What will be the swiftest code seems to depend on the order of magnitude of
your data. Your solution is, apart from a misprint in the second argument in
Extract, pretty fast for small values of z. For some reason it tremendously
slows down when z increases, much faster than I would expect. Below you find
another solution for the problem with some comparisons.

In[1]:=
z = 10; n = 30000;
oplist = Sort /@ Partition[ Table[Random[Integer, {1, z}], {2n}], 2];

In[2]:=
Fold[ReplacePart[#1,Extract[#1,#2]+1,#2]&,Table[0,{z},{z}],oplist]; //
Timing

Out[2]=
{1.49 Second,Null}

In[3]:=
mat = Array[0&, {z, z}];
Part[mat, Sequence @@ #]++ & /@ oplist;//Timing

Out[3]=
{3.95 Second,Null}

In[4]:=
z = 400; n = 30000;
oplist = Sort /@ Partition[ Table[Random[Integer, {1, z}], {2n}], 2];

In[5]:=
Fold[ReplacePart[#1,Extract[#1,#2]+1,#2]&,Table[0,{z},{z}],oplist]; //
Timing

Out[5]=
{1333.1 Second,Null}

In[6]:=
mat = Array[0&, {z, z}];
Part[mat, Sequence @@ #]++ & /@ oplist;//Timing

Out[6]=
{4.07 Second,Null}

Regards,

Fred Simons
Eindhoven University of Technology

----- Original Message -----
From: Seth Chandler <SChandler at Central.UH.Edu>
To: mathgroup at smc.vnet.net
Subject: [mg29721] [mg29683] Swiftest code to turn list of ordered pairs into Markov
matrix


> 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 value
s
> 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 Map
  • Next by Date: Re: Swiftest code to turn list of ordered pairs into Markov matrix [using Sequence]
  • Previous by thread: Re: Swiftest code to turn list of ordered pairs into Markov matrix
  • Next by thread: Re: Swiftest code to turn list of ordered pairs into Markov matrix