Führen Sie eine logische oder Unterliste einer Liste effizient aus

Question

Angesichts einer riesigen Liste xvon 0s und 1s und einer zunehmenden Liste ivon Positionen, die xin (möglicherweise leere) Unterlisten unterteilt sind, möchte ich eine Liste zurückgeben, die 1 enthält, wenn die entsprechende Unterliste eine 1 enthält, und ansonsten 0. Mit anderen Worten, führen Sie ein logisches 'oder' für Unterlisten aus.

Der folgende Code macht, was ich will, ist aber etwas ineffizient:

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]]

Gibt es einen besseren Weg, dies zu tun?

Answer 1

Warum nicht einfach Accumulateauf xund vermeiden Sie die Teil - Listen zu schaffen (was sehr langsam ist , weil die Unterlisten nicht verpackt werden können). Ihre Version (mit$n=10^8$ weil ich nicht geduldig bin):

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}

Verwenden Sie stattdessen Accumulateon x:

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

{1.23973, 1040000832}

Prüfen:

z == y

Wahr