Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I am trying to build a very large graph with approximately $16\,000\,000$ edges, each being a two-dimensional integer vector. I have a list of edges in the form $\{\{e_{11}, e_{12}\}, \{e_{21}, e_{22}\}, \dotsc\}$, where $e_{11} = \{n, m\}$, etc. To convert it into a usable edge-list I need to turn every element of this list into a rule:

edgeList = MapThread[Rule, Transpose[edgelist]];

This works fast enough when there are $3\,000\,000$ edges but is too slow for $16\,000\,000$. What is the best way to speed up the threading?

share|improve this question
    
Please clarify: is edgelist of the form {{{6, 6}, {7, 0}, {9, 1}, {7, 8}, {3, 6}} or {{{6, 9}, {2, 1}}, {{7, 2}, {9, 5}}, {{8, 3}, {1, 1}}, {{4, 0}, {0, 1}}, {{9, 9}, {3, 6}}}? –  Mr.Wizard Dec 21 '13 at 13:41
2  
Is it 16/3 times as slow or much much worse than that? –  Ymareth Dec 21 '13 at 13:44
    
@Mr.Wizard The latter. –  level1807 Dec 21 '13 at 18:16
    
@Ymareth much much worse (I didn't even try to wait for the end). –  level1807 Dec 21 '13 at 18:17
    
I updated my answer. I think it is possible that memory consumption is an issue. Please try the in-place method and see if it works. –  Mr.Wizard Dec 21 '13 at 19:40

1 Answer 1

With the correct data dimensions I don't believe my original recommendation of Inner is (easily) applicable. Further, Oleksandr revealed that it is not the fastest even in that case in later versions. Instead I'll just offer a few options and an observation:

list = RandomInteger[999, {2*^6, 2, 2}];

MapThread[Rule, Transpose[list]]              // ByteCount
Rule @@@ list                                 // ByteCount
Thread[Rule @@ Transpose[list]]               // ByteCount
(list2 = list; list2[[All, 0]] = Rule; list2) // ByteCount
640000032

640000032

640000032

432000032

It can be seen that on my system the last method uses about a third less memory than the others. I don't yet know why. More memory can be conserved by this method, comparatively, if the original list may be modified in place:

list = RandomInteger[999, {2*^6, 2, 2}];  (* in a fresh Kernel *)
list = MapThread[Rule, Transpose[list]];
MaxMemoryUsed[]
1022926416
list = RandomInteger[999, {2*^6, 2, 2}];
list[[All, 0]] = Rule;
MaxMemoryUsed[]
350925448

We get by using about one third of the memory used by the original method. If your code is failing because of memory consumption this may solve the problem.

share|improve this answer
    
@Oleksandr I had to rewrite the answer since I used the wrong data the first time. Would you mind running timings for the present operations? –  Mr.Wizard Dec 21 '13 at 19:39
1  
Oh yes, I didn't notice that either. Here they are again. Version 9: all methods use 870MB of memory except the last which uses 290MB (using undocumented new in 9 MaxMemoryUsed[code_]); ByteCounts are 608M and 480M and normalized timings are {1.000000, 0.957547, 0.976415, 0.806604} in the order that you show them. In version 8 the ByteCounts are 823M (first three) and 544M (last) and the timings are {1.000000, 0.995714, 0.959714, 0.656286}. –  Oleksandr R. Dec 21 '13 at 20:01
    
I also noticed that simply transposing a list this large is very slow. –  level1807 Dec 22 '13 at 5:33
    
@level1807 How does my recommendation (list[[All, 0]] = Rule;) work for you? –  Mr.Wizard Dec 22 '13 at 7:43
    
Not better... I guess I will have to implement a different algorithm for the whole problem and avoid such large graphs. –  level1807 Dec 22 '13 at 11:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.