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?

• 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}}}? Dec 21, 2013 at 13:41
• Is it 16/3 times as slow or much much worse than that? Dec 21, 2013 at 13:44
• @Mr.Wizard The latter. Dec 21, 2013 at 18:16
• @Ymareth much much worse (I didn't even try to wait for the end). Dec 21, 2013 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. Dec 21, 2013 at 19:40

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}];

Rule @@@ 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 *)
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.

• @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? Dec 21, 2013 at 19:39
• 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}. Dec 21, 2013 at 20:01
• I also noticed that simply transposing a list this large is very slow. Dec 22, 2013 at 5:33
• @level1807 How does my recommendation (list[[All, 0]] = Rule;) work for you? Dec 22, 2013 at 7:43
• Not better... I guess I will have to implement a different algorithm for the whole problem and avoid such large graphs. Dec 22, 2013 at 11:07