Message Boards Message Boards

GROUPS:

Create the large size of SparseArray

Posted 2 months ago
487 Views
|
3 Replies
|
0 Total Likes
|

Hi Communities

I am trying to create a large size of sparsearray as following

base = Permutations[{1, 1, 1, 1, 1, 0, 0, 0, 0, 0}];
dim = Length[base]
AbsoluteTiming[
 test = SparseArray[{i_, 
      j_} /; (Total@Abs[base[[i]] - base[[j]]] == 0 || 
       Total@Abs[base[[i]] - base[[j]]] == 2 || 
       Total@Abs[base[[i]] - base[[j]]] == 4) -> 1, dim {1, 1}]]

The ideal of above code is that only the element at diagonal of the matrix and only two and four element differ between two bases have the value of 1. The above code took only ~0.6 second to complete.

However, if I change the base to following:

base = Select[
  Permutations[{1, 1, 1, 1, 1, 0, 0, 0, 0, 0,  1, 1, 1, 1, 1, 1, 1, 1,
     1, 1,   1, 1, 1, 1, 1, 0}], 
  5 <= Total@#[[1 ;; 10]] <= 7 && 5 <= Total@#[[11 ;; 15]] <= 5 &]

It ran out all of my computer's memory (~6GB) and makes the such computation being impossible. The length of this new base is only 34122. It is not very large. So did I make any thing wrong? Are there any solutions to this ?

Thank you for reading this.

3 Replies
Posted 2 months ago

The Combinatorica package was available with earlier versions of Mathematica. You might see if it is included in your version. That included a NextPermutation function which would generate each subsequent permutation, one at a time, instead of creating all the permutations at once. If that works then you might trade longer execution time for less memory usage.

If you got NextPermutation working then you could generate and test each permutation and only save those which satisfied your conditions. I once found the source to the Combinatorica package on the net and was able to extract that single function for a problem I was working on. If you try this then please test it very carefully to make certain that it is correct for your problem.

Different idea, do not know whether this will help or not, probably not as much. Is

5 <= Total@#[[11 ;; 15]] <= 5

equivalent to

Total@#[[11 ;; 15]]==5

or perhaps even

#[[11 ;; 15]]=={1,1,1,1,1}

Another idea. Could you generate the permutations not including those 5 1's in columns 11-15 which might make for fewer permutations to generate and test. Perhaps something like

base = Select[Permutations[{0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0}],5<=Total@#[[1 ;; 10]]<=7&]

and adjust your code to understand that columns 11-15 are not present or you insert those 5 1's into the middle of each permutation after you generate it if needed.

Many thanks for your reply. I think my main problem is not from generating the base with Permutations. This computation was done within 0.7 second. But after put the base in SparseArray, it quickly ran out of all computer's memories.

However, the interesting thing is that if one try

base = Select[
   Permutations[{1, 1, 1, 1, 1, 0, 0, 0, 0, 0,  1, 1, 1, 1, 1, 1, 1, 
     1, 1, 1,   1, 1, 1, 1, 1, 0}], 
   5 <= Total@#[[1 ;; 10]] <= 7 && 5 <= Total@#[[11 ;; 15]] <= 5 &];
dim = Length[base];
data = <||>;
AbsoluteTiming[
 Do[
  If[Total@Abs[base[[i]] - base[[j]]] == 0 || 
    Total@Abs[base[[i]] - base[[j]]] == 2 || 
    Total@Abs[base[[i]] - base[[j]]] == 4, 
   AssociateTo[data, {i, j} -> 1]], {i, 1, dim}, {j, 1, dim}];
 test = SparseArray[Normal@data]]

It works!!! Just using this way is very inefficient. It took hours to create a not too big sparse array. So I'm actually truing to figure out a way to speed up such the computation. Any suggestions/ideals would be much appreciated.

Posted 2 months ago

It is possible that AssociateTo behaves in a way similar to AppendTo. If that is true then for each new key->value that you add to your association makes a new copy of the the existing key->value pairs and then inserts or updates one new key. That may mean it takes approximately c*34122^2 time to complete this.

An alternative might be to create a single list of all key->value pairs in a list and then do Association@list. If that will work then the result might take approximately c*34122 to complete.

Another possible optimization might be, because you seem to only be interested in the absolute value of the difference of two permutations, to only associate i,j for i less than or equal to j. That may eliminate approximately half your key->value pairs and you would modify your code to reverse i and j if i were greater than j when you want to look up an association.

Another probably much smaller optimization might be

Do[
  diff=Total@Abs[base[[i]]-base[[j]]]
  If[diff=0 || dif==2 || diff=4,
  ....

That seems to reduce by about 2/3 the number of value extractions from lists of 34122 items. That may or may not make any significant difference.

You could perhaps use the Outer function to compare all permutations with all permutations, but it looks like you want to associate an index with each permutation and that takes a little more knowledge to accomplish that when using Outer.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract