5
$\begingroup$

I was comparing RAM and CPU efficiency for List, Rule, Association, Function. The following code

n=10^6; 
tbl=Table[2i,{i,n}];                    ByteCount[tbl]
rls=Table[2i->i,{i,n}];                 ByteCount[rls]
asc=Association@Table[2i->i,{i,n}];     ByteCount[asc]
Do[fnc[2i]=i,{i,n}];                    ByteCount[fnc]
AbsoluteTiming[Position[tbl,2n][[1,1]]]
AbsoluteTiming[2n/.rls]
AbsoluteTiming[asc[2n]]
AbsoluteTiming[fnc[2n]]

gave the following results:

8000144

96000080

128382000

0

{0.142235, 1000000}

{0.805691, 1000000}

{0.00001, 1000000}

{4.*10^-6, 1000000}

Thus Function is the fastest, but how do I get its real memory requirement?

$\endgroup$
3
$\begingroup$

Since you are using positive integer labels with rather high density in their range you should also try a classical array as lookup table. A further variant that works well when the keys are integers or lists of integers with fixed length is by using a BSP tree like with Nearest:

n = 10^6;
tbl = Table[2 i, {i, n}]; ByteCount[tbl]
rls = Table[2 i -> i, {i, n}]; ByteCount[rls]
rls2 = Dispatch[rls]; ByteCount[rls2]
asc = AssociationThread[Range[2, 2 n, 2], Range[n]]; ByteCount[asc]
ClearAll[fnc];
Do[fnc[2 i] = i, {i, n}]; ByteCount[DownValues[fnc]]
lookuptable = ConstantArray[0, 2 n];
lookuptable[[2 ;; ;; 2]] = Range[1, n]; ByteCount[lookuptable]
nf = Nearest[Range[2, 2 n, 2] -> Automatic];values = Range[n];ByteCount[nf] + ByteCount[values]

8000144

96000080

126473520

126473432

192000080

16000144

16000488

a = 2 RandomInteger[{1, n}, 100000];
RepeatedTiming[r2 = a /. rls2][[1]]
RepeatedTiming[r3a = asc /@ a][[1]]
RepeatedTiming[r3b = Lookup[asc, a]][[1]]
RepeatedTiming[r4 = fnc /@ a][[1]]
RepeatedTiming[r5 = lookuptable[[a]]][[1]]
RepeatedTiming[r6 = values[[Flatten[nf[a, 1]]]]][[1]]
r2 = r3a == r3b == r4 == r5 == r6

0.907

0.8451

0.614

1.0

0.011

0.11

True

Also notice that these methods behave very differently to each other when looking up invalid keys.

| improve this answer | |
$\endgroup$
  • $\begingroup$ What a nice overview of methods. $\endgroup$ – Mr.Wizard Sep 17 '18 at 7:49
  • $\begingroup$ Thanks! When you say that, I really appreciate it! $\endgroup$ – Henrik Schumacher Sep 17 '18 at 8:39
4
$\begingroup$

DownValues should get close to the actual value I believe.

ByteCount[DownValues[fnc]]
192000080

You could also use MaxMemoryUsed during the construction:

ClearAll[fnc]

MaxMemoryUsed[Do[fnc[2 i] = i, {i, 10^6}];]
168327840
| improve this answer | |
$\endgroup$
  • $\begingroup$ DownValues returns way more, than only the right hand side. Is it a fair comparison? I guess all memory structures should be compared by DownValues then. $\endgroup$ – Johu Aug 25 '18 at 18:17
  • $\begingroup$ @Johu I think it's a good first order approximation at least. I did provide a second method that I presume is more accurate. $\endgroup$ – Mr.Wizard Aug 25 '18 at 18:18
4
$\begingroup$

In your example the value of the argument is a part of the definition. Value of fnc[2 i], where i is a symbol, is not defined in your MWE.

Total@Table[ByteCount[fnc[2 i]], {i, n}]

16 000 000

(Edit: note, that my solution only gives only the size of the right hand side and probably underestimates the real memory cost. See the other solution.)

Note also, that your timing measurement lead to misleading results as you apply it to so simple operations. Compare to

n2 = 10;
AbsoluteTiming[Position[tbl, #] & /@ (2 RandomInteger[n, n2])] // First
AbsoluteTiming[Replace[rls] /@ (2 RandomInteger[n, n2]);] // First
2.19423    
1.8028    

Both of these approaches are very slow, as they require going through the whole list to fine the element.

These are much much faster:

n2 = 100000;
AbsoluteTiming[fnc /@ (2 RandomInteger[n, n2]);] // First
AbsoluteTiming[asc /@ (2 RandomInteger[n, n2]);] // First
AbsoluteTiming[Lookup[asc, 2 RandomInteger[n, n2]];] // First

> 0.267781
> 0.226777
> 0.171752

I think it is misleading to call fnc[i] a function, as a function usually is evaluated runtime. In your MWE you save a precomputed value. This technique is referred to as memoization.

When you wonder which one you should use, I would always use what makes sense semantically, because the engineers behind the kernel and native commands have but a lot of effort into finding a balance between all the features one usually needs from a List, Rules, Associations and Symbols. Associations and Symbols are the ones, which require fast random access.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Hmm, this is very low RAM usage, comparable to Table, yet faster than all of them. Why wouldn't one use Function instead of Table or Association? $\endgroup$ – Leo Aug 25 '18 at 17:21
  • $\begingroup$ Please see the updated answer. $\endgroup$ – Johu Aug 25 '18 at 17:43
  • 1
    $\begingroup$ Your problem is that foo /@ 2 RandomInteger[n, n2] is parsed as (foo /@ 2) RandomInteger[n, n2]. $\endgroup$ – Carl Woll Aug 25 '18 at 20:42
  • $\begingroup$ @CarlWoll oh lord. how stupid. $\endgroup$ – Johu Aug 25 '18 at 22:36
  • $\begingroup$ I fixed it now and adjusted my conclusions. I did think it had to be impossible for the lookup from List to be that fast. Now it all makes sense. $\endgroup$ – Johu Aug 25 '18 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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