2
$\begingroup$

I have some sorted data:

data = Sort[RandomInteger[{0, 15}, 10]] 

and I want to generate a duplicate array where a counter is increased each time we discover a different element in the data array. By example:

data:      {0, 3, 3, 3, 6, 7, 10, 11, 11, 14}
duplicate: {1, 2, 2, 2, 3, 4,  5,  6,  6,  7}

In a procedural programming approach, a possible procedure would be:

createDuplicateForLoop[data_List] := 
  Block[{dup, count, n},
   n = Length[data];
   If[n == 0, Return[{}];];
   count = 1;
   dup = ConstantArray[count, n];
   For[i = 2, i <= n, i++,
    If[data[[i - 1]] == data[[i]], 
      dup[[i]] = count, 
      dup[[i]] = ++count];
    ];
   Return[dup];
  ];

However in MMA loops are not efficient. That's why I tried to find an equivalent solution using built-in MMA functions and more in a functional style. I got this:

createDuplicate[data_List] := 
  Block[{dup}, 
   dup = Tally[Range[Length[data]], (data[[#1]] == data[[#2]]) &];
   dup = Flatten[
     MapThread[
      ConstantArray[#1, #2] &, 
      {Range[Length[dup]], Part[dup, All, 2]}
     ]
   ];
   Return[dup];
  ];

Now benchmarking:

n = 100000;
data = Sort[RandomInteger[{0, 15}, n]];
t0 = First@Timing[r0 = createDuplicateForLoop[data];]
t1 = First@Timing[r1 = createDuplicate[data];]
Print["For loop is ", t0/t1, "x slower"]
r0 == r1

I get:

0.694893
0.022270
For loop is 31.20x slower
True

So clearly the "for loop" solution is slower, however I find it much more readable than the version using the Tally function.

Question: I am curious to know if someone has an idea for a solution keeping not only efficiency but also readability?


A summary of the comments:

n = 100000;
data = Sort[RandomInteger[{0, 15}, n]];
t0 = First@Timing[r0 = createDuplicateForLoop[data];]
t1 = First@Timing[r1 = createDuplicate[data];]
t2 = First@Timing[r2 = 1 + ArrayComponents@data;]
t3 = First@
  Timing[r3 = Accumulate[Prepend[Unitize[Differences[data]], 1]];]
Print["For loop is ", t0/t1, "x slower"]
r0 == r1

0.590431
0.022422
0.021350
0.003437
For loop is 26.33x slower
True

Thanks to Kuba & Henrik, I learned a lot!

$\endgroup$
  • 2
    $\begingroup$ 1 + ArrayComponents @ data; let me know if you disagree with closing. $\endgroup$ – Kuba Jan 31 at 22:14
  • $\begingroup$ @Kuba Awesome! I did not know this function! If you put this in an anwser I will be happy to accept it. I feel a little embarrassed with my long question now :-/ $\endgroup$ – Picaud Vincent Jan 31 at 22:17
  • 1
    $\begingroup$ I did also not know this function; I'd rather have used Accumulate[Prepend[Unitize[Differences[data]], 1]]... which turns out to produce the same result 10 times faster. $\endgroup$ – Henrik Schumacher Jan 31 at 22:25
  • 2
    $\begingroup$ @PicaudVincent it is fine to be a duplicate :) it is a roadsign for a future visitors. $\endgroup$ – Kuba Jan 31 at 22:31
  • 1
    $\begingroup$ Well, ArrayComponents can do more than the code that I posted; but as often, a specialized approach can be faster. My approach utilizes the fact that due to preordering, the resulting array is monotonically increasing. This avoids all lookups and thus allows for using vectorized approaches. $\endgroup$ – Henrik Schumacher Jan 31 at 22:43

Your Answer

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

Browse other questions tagged or ask your own question.