9
$\begingroup$

I was wondering, why is extracting from an Association slightly faster than extracting from a List?

assoc = Association[Table[i -> i^2, {i, 1000}]];
list = Table[i^2, {i, 1000}];
list[[10]] // RepeatedTiming
assoc[10] // RepeatedTiming
(* I'm not posting outputs because of the variance but the 2nd is usually faster *)

I would have expected nothing to be faster than extraction from a List since it should be just a memory access vs a more computationally-expensive lookup for Association.

MMA 11.2 Linux.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ I was going to mention something about unpacking, but the version using ulst = Developer`FromPackedArray[list] is even slower. Huh. $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Apr 1, 2018 at 3:33
  • $\begingroup$ I am not convinced that association-lookup is really faster. It could be some timing artefact. It is not easy to time such extremely short operations accurately. list[[#]] & /@ Range[100] is 9 times faster on my machine than assoc /@ Range[100]. $\endgroup$
    – Szabolcs
    Commented Apr 1, 2018 at 9:20
  • 3
    $\begingroup$ The benchmark in my comment above is flawed. Part is faster because of auto-compilation. Change Range[100] to Range[99] and association lookup becomes almost precisely 2x faster than list indexing. I wonder if it has any significance that the factor is almost precisely 2. $\endgroup$
    – Szabolcs
    Commented Apr 1, 2018 at 9:28
  • 2
    $\begingroup$ Lookup[assoc, 10] is consistently a little faster than assoc[10] for me. $\endgroup$
    – Michael E2
    Commented Apr 1, 2018 at 17:30

2 Answers 2

Reset to default
5
$\begingroup$

Recall that Mathematica is an interpreter language, so there is significant overhead in each single call. Only bulk access to data can show that Lists are significantly faster than Associations.

n = 1000;
assoc = AssociationThread[Range[n], Range[n]^2];
list = Range[n]^2;
idx = RandomInteger[{1, n}, 100000];
Do[x = list[[i]], {i, idx}]; // AbsoluteTiming
Do[y = assoc[i], {i, idx}]; // AbsoluteTiming
a = Table[assoc[i], {i, idx}]; // AbsoluteTiming
b = Table[list[[i]], {i, idx}]; // AbsoluteTiming
c = list[[idx]]; // AbsoluteTiming
d = Lookup[assoc, idx]; // AbsoluteTiming
a == b == c == d

{0.047621, Null}

{0.044828, Null}

{0.029103, Null}

{0.001618, Null}

{0.000347, Null}

{0.008003, Null}

True

(Mathematica 11.3 for macos)

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ Well, I am not an expert in dictionaries but the basic idea is to have a hash function f that maps keys to memory adresses. In order to lower the chances of collision, this hash function has to be rather "discontinuous", that means that f[key1] and f[key2] should map to different adresses, even if key1 and key2 are similar. Still, collision cannot completely avoided. So, compared to simple arrays, there is some overhead i) in computing f[key] and ii) in handling these collisions. $\endgroup$
    – Henrik Schumacher
    Commented Apr 1, 2018 at 17:14
  • 1
    $\begingroup$ The advantage over arrays is that you do not have to rely on consecutive integer indices and that appending entries and dropping entries of a dictionary is of low cost. $\endgroup$
    – Henrik Schumacher
    Commented Apr 1, 2018 at 17:15
  • 1
    $\begingroup$ I am not sure what you mean by "overhead during a list call". All I can say is that both Part and Lookup certainly have compiled libraries as backends and that the communication between the MathKernel and these libraries can be reduced by sending as few queries as possible. $\endgroup$
    – Henrik Schumacher
    Commented Apr 1, 2018 at 17:31
  • 2
    $\begingroup$ Note that Table[list[[i]]...] is compiled, which greatly speeds up the performance, and there are differences in speed between packed and unpacked list and idx, for all four combinations. (Compilation can be prevented with SetSystemOptions["CompileOptions" -> "TableCompileLength" -> Infinity].) $\endgroup$
    – Michael E2
    Commented Apr 1, 2018 at 17:43
  • 3
    $\begingroup$ @anderstood The Mathematica Association is a hash array mapped trie, per mathematica.stackexchange.com/questions/52393/…. $\endgroup$
    – Patrick Stevens
    Commented Apr 1, 2018 at 20:52
1
$\begingroup$

Association key-value pairs are indexed objects. Lists are not. As you increase the dimensionality of your association vs list comparison you will quickly see best practice is to put everything in associations and datasets.

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ That's not true - at least for purely numerical data. $\endgroup$
    – Henrik Schumacher
    Commented Apr 1, 2018 at 9:00
  • $\begingroup$ @Henrik Schumacher - right, but I can't remember the last time I worked pure numerical list, so my lack of qualification. My context is n-dimensions with characteristic variables. Since M10 Association and Dataset have been a valuable help to my work saving lots of custom work indexing data and cpu cycles working on the data. $\endgroup$
    – Mitch
    Commented Apr 3, 2018 at 5:58

Your Answer

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

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