MathGroup Archive 2001

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

Search the Archive

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


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