8
$\begingroup$

What is the most efficient way to get component rules from ArrayComponents, so additionaly to

data = {"a", "b", "a"};
cmp = ArrayComponents[data]
 {1,2,1}

I would like to get:

Thread[data -> cmp] // DeleteDuplicates
{"a"->1, "b"->2}

(or reversed), and the point is that the data is big and I don't want to compare it again to get those relations.

Failed to find the solution in documentation or here.

$\endgroup$
  • $\begingroup$ But you can run it once to generate the ArrayComponents?, so use temp = Flatten@ Trace[ArrayComponents[{"a", "b", "d", "c", "a"}], Replace]; and then Extract[]? $\endgroup$ – Feyre Jan 26 '17 at 11:05
  • $\begingroup$ Slower than goldberg's answer, already ran comparison. $\endgroup$ – Feyre Jan 26 '17 at 11:38
  • $\begingroup$ Is the reason that "a" gets 1 and "b" gets 2 that "a" occurs first in your list, or that "a" occurs before "b" in the alphabetical order? $\endgroup$ – Jacob Akkerboom Jan 26 '17 at 11:44
  • $\begingroup$ @JacobAkkerboom occurence matters I suppose. $\endgroup$ – Kuba Jan 26 '17 at 11:48
8
$\begingroup$

What about this:

data = {"a", "b", "a"};
AssociationThread[data, ArrayComponents[data]] // Normal

{"a" -> 1, "b" -> 2}

I suggest this because building an association automatically removes duplicates. It should be fairly fast because it is hashing.

$\endgroup$
7
$\begingroup$

Here are three functions that do the job relatively fast.

<< Developer`
ranFirstPos =
 Compile[
  {{ints, _Integer, 1}, {max, _Integer}},
  Block[
   {res, ii}
   ,
   ii = 1;
   Table[
    While[
     ints[[ii]] != jj
     ,
     ii++
     ];
    ii
    ,
    {jj, 1, max}
    ]
   ]
  ]

jacobFu[data_] :=
 Module[
  {cmp, max, dataDD},
  cmp = ToPackedArray@ArrayComponents@data;
  max = Max@cmp;
  dataDD = data[[ranFirstPos[cmp, max]]];
  Thread[Rule[dataDD, Range[max]]]
  ]

Or

kubaImprovedFu[data_] :=
 Module[
  {cmp}
  ,
  cmp = ArrayComponents[data];
  Thread[DeleteDuplicates /@ Rule[data, cmp]]
  ]

The following alternative does not really answer the question of "how to deal with the result of ArrayComponents", as it doesn't use ArrayComponents. This one can be made slightly faster by using System`Utilities`HashTable rather than an Association.

jacobFuAssocHash[data_] :=
 Module[{jj, assoc},
   assoc = Association[];
   jj = 1;
   Reap[
    Do[
     If[
      ! KeyExistsQ[assoc, elem],
      assoc[elem] = True;
      Sow[elem -> jj];
      jj++
      ]
     ,
     {elem, data}
     ]
    ]
   ][[2, 1]]

Timing comparison

From other posts, we define

kubaFu[data_] :=
 Module[
  {cmp}
  ,
  cmp = ArrayComponents[data];
  Thread[data -> cmp] // DeleteDuplicates
  ]

goldbergFu[data_] :=
 AssociationThread[data, ArrayComponents[data]] // Normal

This gives us

nn = 10^7;
data = FromCharacterCode /@ RandomInteger[{0, 65536 - 1}, nn];
jacobRes = jacobFu[data];//Timing//First
jacobAsHaRes = jacobFuAssocHash[data]; // Timing // First
kubaImRes = kubaImprovedFu[data];//Timing//First
goldbergRes = goldbergFu[data]; // Timing // First
kubaRes = kubaFu[data]; // Timing // First
jacobRes === jacobAsHaRes === kubaImRes === kubaRes === goldbergRes
7.20605
9.41933
10.207
12.3219
21.7913
True
$\endgroup$
5
$\begingroup$

Inspired by @Feyre's comment, we can modify the behavior of Dispatch before running ArrayComponents to capture the rules:

componentRules[list_] := Internal`InheritedBlock[{Dispatch, flag=True},
    Unprotect[Dispatch];
    a_Dispatch /; flag := Block[{flag=False}, Throw[Normal[a][[4;;]]]];
    Catch @ ArrayComponents[list]
]

A brief speed comparison:

nn = 10^7;
data = FromCharacterCode /@ RandomInteger[{0,65536-1}, nn];
r1 = jacobFu[data]; //AbsoluteTiming
r2 = componentRules[data]; //AbsoluteTiming

r1 === r2

{7.67635, Null}

{3.21433, Null}

True

Note that this answer and @MrWizard's answer are the only ones that work for matrices or arrays with rank greater than 1.

$\endgroup$
  • $\begingroup$ In v10.1 I seem to need an Unprotect[Dispatch]; in there to get things working. Thanks for demonstrating such an interesting approach! $\endgroup$ – Mr.Wizard Aug 26 '17 at 6:18
  • $\begingroup$ @Mr.Wizard Thanks, fixed. $\endgroup$ – Carl Woll Aug 26 '17 at 6:46
3
$\begingroup$

It seems that ArrayComponents itself can be a bit slow. Seeking an alternative I tried this:

data = FromCharacterCode @ RandomInteger[{97, 122}, {500000, 4}];

r1 = componentRules[data]; // RepeatedTiming   (* Carl Woll's function *)

r2 = 
   Thread[# -> Range@Length@#] &@DeleteDuplicates[Flatten@data]; // RepeatedTiming

r1 === r2
{0.84, Null}

{0.260, Null}

True
$\endgroup$
  • $\begingroup$ This gives an incorrect answer. For instance, result is {"a"->1, "a"->2} for the list {"a", "a", "b"}. $\endgroup$ – Carl Woll Aug 26 '17 at 5:43
  • $\begingroup$ @CarlWoll Thanks! I thought I was missing something but I couldn't see it. Embarrassing. <:-o $\endgroup$ – Mr.Wizard Aug 26 '17 at 6:15
  • 2
    $\begingroup$ Much better. Note that ArrayComponents is written in top-level, so I'm not surprised that you can do better. $\endgroup$ – Carl Woll Aug 26 '17 at 6:44
1
$\begingroup$

SparseArray, like Assocoation, takes the first of repeated entries:

data = {"a", "b", "a"};
cmp = ArrayComponents[data];
Most@ArrayRules@SparseArray[cmp -> data]

{{1} -> "a", {2} -> "b"}

To get rid of braces

MapAt[## & @@ # &, %, {{All, 1}}]

{1 -> "a", 2 -> "b"}

Also:

sa = SparseArray[cmp -> data];
Thread[Flatten@sa["NonzeroPositions"] ->  sa["NonzeroValues"]]

{1 -> "a", 2 -> "b"}

$\endgroup$
  • $\begingroup$ Not particularly fast, at least in 10.1, but an interesting approach. The Thread method just added is faster. $\endgroup$ – Mr.Wizard Aug 26 '17 at 5:05
  • $\begingroup$ @Mr.Wizard, haven't checked timings. (I suspect ArrayRules is the culprit). $\endgroup$ – kglr Aug 26 '17 at 5:09

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.