7
$\begingroup$

I asked a similar question previously (https://bit.ly/3llhmFE). This one is similar, but different.

I have a list comprising a sequence of digits 1, 0 and -1, for example:

l = {0, 0, 1, 1, 1, 1, -1, -1, -1, 0 , 1, 1}

I want a function to return the result:

    {0, 0, 1, 0, 0, 0, -1, 0 , 0,  0, 1, 0}

Essentially I want the sequence of first changes of sign.

These sequences may be tens or hundreds of thousands in length, so I need to find an efficient solution that doesn't involve looping - using foldlist, perhaps.

$\endgroup$
1
  • $\begingroup$ Does Sign[Differences[l]] do what you are looking for? $\endgroup$ – bill s Oct 7 '20 at 19:01
7
$\begingroup$

I think you'll find this pretty snappy:

fn = Sign[Prepend[Differences[#], 0] Abs[#]] &;

There is ambiguity in the question as to the disposition of the first result element. Should it be zero (there is no initial sign change from "nothing before") or the sign of the first target element.

If the latter, this does so at no performance cost:

fn2 = Sign[Prepend[Differences[#], #[[1]]] Abs[#]] &;
$\endgroup$
5
$\begingroup$

Slightly faster versions of ciao's fn and fn2:

f0 = # Unitize @ Prepend[Differences @ #, 0]  &;

f0 @ l
{0, 0, 1, 0, 0, 0, -1, 0, 0, 0, 1, 0}
f1 = # Unitize @ Prepend[Differences @ #, #[[1]]] &;

f1 @ l
{0, 0, 1, 0, 0, 0, -1, 0, 0, 0, 1, 0}
$\endgroup$
4
$\begingroup$

You could do this with a FoldPairList or a tortured FoldList, but the easiest way to get a fast function is probably to just Compile a table:

cf = Compile[{
   {list, _Integer, 1}
   },
  Module[{prev = 0},
   Table[
    Which[
     i == 0, prev = i; 0,
     i > prev, prev = i; 1,
     i < prev, prev = i; -1,
     True, 0
     ],
    {i, list}
    ]
   ]
 ]

Timing:

l = RandomInteger[{-1, 1}, 10^7];
cf[l]; // AbsoluteTiming

{0.822968, Null}

$\endgroup$
4
$\begingroup$
findFirstZeroes[l_] := Unitize[Prepend[Rest[l] - Most[l], 0] + 1]

findFirstInSequence[l_] := Module[{a, b},
  a = Unitize[l - 1];
  b = Unitize[l + 1];
  Abs[findFirstZeroes[a] - 1] + (findFirstZeroes[b] - 1)
  ]

l = RandomInteger[{-1, 1}, 10^7];
findFirstInSequence[l]; // AbsoluteTiming

{0.225284, Null}

Sjoerd's solution takes about 0.36 on my computer.

$\endgroup$
2
$\begingroup$

I can get there with the following code:

op=Foldlist[If[#2==0,@1,#2]&]; 
op@l;
Join[{0},Sign@Differences[%]]

which produces:

{0, 0, 1, 0, 0, 0, -1, 0, 1, -1, 0}  

as required.

But I cant figure out how to string it all together in a single, elegant function.

The following function is about as fast as the compiled looping procedure:

foo[l_]:=Module[{t},
t=FoldList[If[#2==0, #1, #2]&]@l;
Join[{0},Sign@Differences[t]]]

l = RandomInteger[{-1,1}, 10^7};
foo[l];//AbsoluteTiming
{0.803403, Null}
$\endgroup$
1
  • $\begingroup$ Your function foo can be compiled as well to gain a small speed boost. If you have a C compiler, you should be able to get a much more significant performance increase. $\endgroup$ – Sjoerd Smit Oct 7 '20 at 19:42

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.