9
$\begingroup$

I would like to have the following simple function GetKey[] on a very large association.

(* The actual Association is very large, this is just small example *) 
assoc = <|{1,1} -> 2, {1,2} -> 3, {2,1}->4, {2,2}->5|>;
GetKey[assoc, 1]
GetKey[assoc, 4]

(* output *) 
{1,1}
{2,2}

That is, I want to access keys based on their position in the association. Any way this can be done efficiently for a large association? I know one can use the Keys[assoc][[position]] function but this is too slow for a large association.

EDIT: Based on the comments below I am giving you the timing information for the function I know that does the job.

a = 1024*1024;
keys = Table[i, {i, a}];
values = RandomReal[{0, 1000000}, {a}];
assoc = Association[MapThread[Rule, {keys, values}]];
AbsoluteTiming[k = Keys[assoc][[10000]];]

(* output *)
{0.548738, Null}

This is too slow for say a hundred thousand accesses.

|improve this question
$\endgroup$
  • $\begingroup$ which version of Mathematica are you using? I do not have GetKey in my mathematica and I am using 11.1.1 if this is meant to be your own function, then it is better to use LowerFirstCaseLetter to reduce confusion from someone thinking it is build-in function. $\endgroup$ – Nasser Aug 13 '17 at 19:13
  • $\begingroup$ I am sorry I should have pointed that out, GetKey is the function I want. It's not built in. $\endgroup$ – Iconoclast Aug 13 '17 at 19:14
  • $\begingroup$ I do not think position on association has any sematics to it. This is like a hash table. So asking for position does not seem to be well defined here. But I am not an expert with association. I do not use it. You can ask about a position of an entry for a list for example. $\endgroup$ – Nasser Aug 13 '17 at 19:16
  • $\begingroup$ I understand your point. But I am using association in two ways. One as a lookup table for indices of the form $\{i, j\}$ and the other a way to index into these indices based on their order or position in an array. I am doing this for efficiency reasons the primary of which is that dropping keys (key-value pairs) is way more efficient than deleting those keys stored in an array based on first finding their positions. $\endgroup$ – Iconoclast Aug 13 '17 at 19:20
  • $\begingroup$ It would be good provide an example that we can use as a benchmark since this is apparently a question about finding a function that performs better than one that you already have. You can generate the association programmatically and provide the code. Then provide a code that uses AbsoluteTiming to find out how fast the function you found is, and then we can see if we can do better. $\endgroup$ – C. E. Aug 13 '17 at 19:28
12
$\begingroup$

Perhaps:

GetKey[assoc_, index_] := First @ Keys @ Take[assoc, {index}]

Your first example:

assoc = <|{1,1} -> 2, {1,2} -> 3, {2,1}->4, {2,2}->5|>;

GetKey[assoc, 1]
GetKey[assoc, 4]

{1, 1}

{2, 2}

Your large example:

a = 1024*1024;
keys = Table[i, {i, a}];
values = RandomReal[{0, 1000000}, {a}];
assoc = Association[MapThread[Rule, {keys, values}]];

AbsoluteTiming[Keys[assoc][[10000]]]
AbsoluteTiming[GetKey[assoc, 10000]]

{0.373301, 10000}

{0.003779, 10000}

|improve this answer
$\endgroup$
  • $\begingroup$ Thanks a lot. I failed to realize/recall that Take can be used on associations. $\endgroup$ – Iconoclast Aug 13 '17 at 20:05
10
$\begingroup$

This is one of those questions where I suspect it wasn't put enough thought in the data-structures. You use associations for fast access to values based on a key. The association data structure is just not optimized for what you try to do.

Nevertheless, I believe Carl's solution is already very good if you want a function that purely works on your association. If you need to access the same association very often, I would prefer to extract the keys and directly access them. A simple function could look like this:

KeyGet[a_Association] := Module[{keys = Keys[a]},
  KeyGet[i_Integer] := keys[[i]]
]

You use it by initializing it once with your association and then you provide only the integers (or ranges).

assoc = Association @@ Flatten@Table[{x, y} -> RandomInteger[100], {x, 1024}, {y, 1024}];

KeyGet[assoc];
KeyGet[1234]
KeyGet[{1,10,34}]
KeyGet[45;;100]

The first call of KeyGet needs about 0.44 seconds here. As soon as you need to access several thousand indices, it will be faster than using Take like in Carls example, but in general, I would prefer his solution.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ The problem with this code as written is that you can only use it for one assoc at a time. But instead, you can return a pure function: KeyGet[a_Association] := Module[{keys = Keys[a]},Function[i, keys[[i]]]], in which case you can use it on any number of assocs as the same time. $\endgroup$ – Leonid Shifrin Aug 13 '17 at 20:39
  • $\begingroup$ @LeonidShifrin Yes, I was aware of that. I didn't know how large the real application of the OP was. His large example was 1024^2 keys. If his real application is 1024^3, then we are already dealing with GB of keys. That was the reason I didn't present a solution returning a pure function with all keys. $\endgroup$ – halirutan♦ Aug 13 '17 at 21:21
  • $\begingroup$ @Leonid My only point here was that (a) I'm not sure he is dealing with the right data-structure in the first place and (b) that holding the keys separately in a list increases speed. Btw, I haven't forgotten your email and the draft of about 2 pages lies around for 2 weeks. I really have much to say and I want to answer each point. Now I have some free days and you will get it soon. $\endgroup$ – halirutan♦ Aug 13 '17 at 21:26
  • 1
    $\begingroup$ "Btw, I haven't forgotten your email and the draft of about 2 pages lies around for 2 weeks" - no worries at all, please take your time. Everyone is busy as hell these days. Somehow I am having a hard time realizing that another month passed by, time flies :). $\endgroup$ – Leonid Shifrin Aug 13 '17 at 21:56
  • $\begingroup$ @halirutan But the problem is that my association randomly gets KeyDroppedFrom very often, which is why I am using an association in the first place (it's faster to drop keys from an association than to search for the position of an entry in a list and delete it). So I think your static KeyGet function will not work for me as is. $\endgroup$ – Iconoclast Aug 13 '17 at 23:40
5
$\begingroup$

Refresh your memory about how Part works and then observe:

assoc = <|{1, 1} -> 2, {1, 2} -> 3, {2, 1} -> 4, {2, 2} -> 5|>;

assoc[[{1}]]

assoc[[{4}]]

<|{1, 1} -> 2|>

<|{2, 2} -> 5|>

This is equivalent to Take[assoc, {i}] and syntactically shorter. So I would write:

getKey[a_Association, p_Integer] := a[[{p}]] // Keys // First
|improve this answer
$\endgroup$

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.