Message Boards Message Boards


Reduce the complexity of a code

Posted 8 years ago
4 Replies
6 Total Likes

Dear all,

I wrote the simple code reported above. Basically, this code acts on set of bi-dimensional vectors (in particular, a set of 32 bi-dimensional vectors). To each vector is associated a position (that is calculated with the istruction Pos[] defined previously). The aim of the code is to find the smallest vector (in lexicographical order) that holds a possible position.

As you can see in code, I implemented a double nested For loop. For each element i of the set, the code:

1) Creates a boolean vector VV that contains the results of the istruction: Pos[TPal[[i]]] != Pos[TPal[[j]]]. This vector VV is then used to calculate if the element i of the set holds an univocal position (If[VV // Reduce, AppendTo[TPau, TPal[[i]]]]).

2) Compares the vector position (Pos[TPal[[i]]]) with all the other ones (Pos[TPal[[j]]]). If two vectors with the same position are found, they are stored in a set Gmin that will be sort at the end of the second loop. Finally, the duplicate elements are removed.

This code works well for shorter set (as the one shown in the example reported). But its complexity is very high, so if I move to longer set, the elaboration time increses very quickly. In particular, I need to increase the set length by a factor 8 for each elaboration (e.g., 32, 256, 2048, 16384, ecc.). Currently, the set 2048 long requires about 8 hour. My question if is it would be possible to reduce the complexity of the code in order to increase the maximum number of evaluations that I can do with a normal computer.

I hope I made myself clear and I thank you very much for your kind replies.


TPa = Table[{x, y}, {x, 1, 4}, {y, 1, 8}];

TPal = ArrayReshape[TPa, {8*4, 2}]

TPa // TraditionalForm

Table[Pos[{x, y}], {x, 1, 4}, {y, 1, 8}] // TraditionalForm

TPau = {{0, 0}};

 i = 1,
 i <= 32,

 VV = {True};

Gmin = {TPal[[i]]};

  j = 1,
  j <= 32,

  If[j != i, AppendTo[VV, Pos[TPal[[i]]] != Pos[TPal[[j]]]]];

 If[j != i && Pos[TPal[[i]]] == Pos[TPal[[j]]], 
   AppendTo[Gmin, TPal[[j]]]];

 If[VV // Reduce, AppendTo[TPau, TPal[[i]]], 
  AppendTo[TPau, (Gmin // Sort)[[1]]]];


Drop[TPau, 1];
TPauFin = % // DeleteDuplicates
POSTED BY: Fabio Rondelli
4 Replies
Posted 8 years ago

Dear Paul,

thank you very much for your kind reply. I am going to try with your advices and I will back to you for an update.

Thanks again Fabio

POSTED BY: Fabio Rondelli
Posted 8 years ago

Dear Fabio,

This may be of help with your problem, and as the Proff says AppendTo is very slow above a few thousand deep, I use the following Commands, Sow and Reap, the little snippet of code shows an example of its use.

Timing[vv = Reap[Do[Sow[{n, 2 n, 3 n}], {n, 1, 2000000}]]; 
 vv = Flatten[vv[[2]], 1]; Length[vv]]

{2.418016, 2000000}

Extracting the second part of the list removes the null statement part and flattening it reduces the 2 deep list to 1. Maybe this could be implemented in your code.


POSTED BY: Paul Cleary
Posted 8 years ago

Dear Prof. Mutze,

thank you very much for your kind reply. It is a very good advice. I think that maybe it is possible to remove the AppendTo by defining an oversized array before the loop. I will work on it.
Please, if you have any other advice to reduce the code complexity, let me know, I am very grateful.

Many thanks again Fabio

POSTED BY: Fabio Rondelli

Dear Fabio, my experience (also the advice of experienced collegues) is that AppendTo is a performance-killer. If ever possible find the required array length first (probably a bit too large if only an upper bound for this length can be found) and then fill in the quantities which you allways append. The problem with appending is that it typically involves re-allocation of the array. Unfortunately I'm in a hurry and not able to work out whether this advice acan be followed in your case.

POSTED BY: Ulrich Mutze
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract