2
$\begingroup$

Given a huge list x of 0s and 1s and an increasing list i of positions, which partitions x into (possibly empty) sublists, I wish to return a list, which has 1 if the corresponding sublist contains a 1, and 0 otherwise. In other words, perform logical 'or' on sublists.

The following code does what I want, but is somewhat inefficient:

n=10^9; AbsoluteTiming@MaxMemoryUsed[x=RandomChoice[{0,0,0,0,0,0,1},n];
i=Sort[{1}~Join~RandomInteger[{0,n},n/10]~Join~{n}]]
AbsoluteTiming@MaxMemoryUsed[y=TakeList[x,i[[2;;]]-i[[;;-2]]]]
AbsoluteTiming@MaxMemoryUsed[y=Clip[Plus@@#& /@y]]

Is there a better way of doing this?

$\endgroup$
6
  • 1
    $\begingroup$ The most expensive computation seems to be the last one and it can be sped up considerably using Clip[Total /@ y]. $\endgroup$
    – C. E.
    Oct 8 '20 at 10:14
  • $\begingroup$ @C.E. Actually, Total seems to be slower than Plus, with the same RAM load. $\endgroup$
    – Leo
    Oct 8 '20 at 10:26
  • 1
    $\begingroup$ You could use : y =Boole[ Or[# == 1] & @@ y] instead of y=Clip[Plus@@#& /@y $\endgroup$ Oct 8 '20 at 10:33
  • $\begingroup$ @Leo OK, I did not check the RAM load, I did not know that was a problem. $\endgroup$
    – C. E.
    Oct 8 '20 at 10:34
  • 1
    $\begingroup$ y = Unitize[Total[y, {2}] (or y = Clip[Total[y, {2}]) is a little slower but reduces MaxMemoryUsed. $\endgroup$
    – kglr
    Oct 8 '20 at 13:06
2
$\begingroup$

Why not just use Accumulate on x and avoid creating the sublists (which is very slow because the sublists can't be packed). Your version (with $n=10^8$ because I'm not patient):

n=10^8; AbsoluteTiming@MaxMemoryUsed[x=RandomChoice[{0,0,0,0,0,0,1},n];
i=Sort[{1}~Join~RandomInteger[{0,n},n/10]~Join~{n}]]
AbsoluteTiming@MaxMemoryUsed[y=TakeList[x,i[[2;;]]-i[[;;-2]]]]
AbsoluteTiming@MaxMemoryUsed[y=Clip[Plus@@#& /@y]]

{2.35377, 1600000792}

{4.43064, 2257877552}

{18.8051, 640474752}

Using Accumulate on x instead:

AbsoluteTiming @ MaxMemoryUsed[
    z = Clip @ Differences @ Prepend[0] @ Accumulate[x][[Rest@If[i[[1]]==0,i+1,i]-1]];
]

{1.23973, 1040000832}

Check:

z == y

True

$\endgroup$
1
  • $\begingroup$ For x={0,0,1,0,0,1,1,0,0,1}; i={0,0,2,5,5,8,10,10}; your code returns errors. For some background, my data is a=SparseArray[{0 and 1 entries},{dims}]; x=a["NonzeroValues"]; i=a["RowPointers"], hence i can have repeated elements between 0 and n. A fix is Clip@Differences@Accumulate[{0}~Join~x][[i+1]], which is more efficient (CPU and RAM wise) than all previous suggestions. Thank you for this solution! $\endgroup$
    – Leo
    Oct 14 '20 at 11:35

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.