# perform logical or on sublist of a list efficiently

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?

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

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}

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

• 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!
– Leo
Oct 14 '20 at 11:35