5
$\begingroup$

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?

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

1 Answer 1

Reset to default
7
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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