Bdtjtk

I have a very long array, and I'm trying to do the following in a way as efficient as possible:

For each consecutively incrementing chunk in the list I have to reverse its order.

So, for the following array:

a = np.array([1,5,7,3,2,5,4,45,1,5,10,12])

I would like to obtain:

array([7,5,1,3,5,2,45,4,12,10,5,1])

I was wondering if this could be vectorized, using numpy perhaps?

I have already had some answers in this previous question, but the results, although they are big improvements, they are still a little slow.

Other option without dependencies:

array = [1,5,7,3,2,5,4,45,1,5,10,12]



res, memo = , 

for e in array:

  if len(memo) == 0 or e > memo[-1]: memo.append(e)

  else:

    res.extend(reversed(memo))

    memo = [e]

res.extend(reversed(memo))



res # => [7, 5, 1, 3, 5, 2, 45, 4, 12, 10, 5, 1]

def reverse_if_chunck_increases(array):

  res, memo, last_memo = , , None

  for e in array:

    if not last_memo or e > last_memo:

      last_memo = e

      memo.append(e)

    else:

      res.extend(memo[::-1])

      last_memo, memo = e, [e]

  res.extend(memo[::-1])

  return res



print(reverse_if_chunck_increases(array) == [7, 5, 1, 3, 5, 2, 45, 4, 12, 10, 5, 1])

#=> True

I was able to get the result so easily and apparently a bit faster coding in Ruby as:

array.chunk_while { |x, y| x < y }.flat_map{ |chunk| chunk.reverse }

So, I wondered why there isn't an itertool like chunk_while. Then I tried to code one similar using yield:

def reverse_if_chunk_increases(array):

  i, x, size, res = 0, 0, len(array), 

  while i < size-1:

    if array[i] > array[i+1]:

      yield array[x:i+1][::-1]

      x = i +1

    i += 1

  yield array[x:size][::-1]

The execution is superfast but it return a generator to iterate instead of a list:

chunks = reverse_if_chunk_increases(array)

for chunk in chunks:

  print(chunk)

# [7, 5, 1]

# [3]

# [5, 2]

# [45, 4]

# [12, 10, 5, 1]

It can be converted to a list, which is the slowest process.
Note that a generator can be called once.
Removing [::-1] you get a result similar to Ruby enumerator/generator chunk_while.

Can you use pandas?

import pandas as pd

a = [1,5,7,3,2,5,4,45,1,5,10,12]

aa = pd.Series(a)

aa.groupby(aa.diff().bfill().lt(0).cumsum()).apply(lambda x: x[::-1]).tolist()

Output:

[7, 5, 1, 3, 5, 2, 45, 4, 12, 10, 5, 1]

How is this? Seems to be faster afaik but without knowing how fast is fast enough its tough to tell for sure

all_l = 

sub_l = 

for i in a:

    if sub_l:

        if sub_l[0] > i:

            all_l.extend(sub_l)

            sub_l = [i]

        else:

            sub_l.insert(0, i)

    else:

        sub_l = [i]

all_l.extend(sub_l)

I don't think you're going to get much faster than using a pure python loop.

For instance, here is a numpy+itertools solution:

import numpy as np

from itertools import chain, groupby

from operator import itemgetter



def reverse_increasing_sequences_numpy(a):

    idx = (np.diff(np.concatenate([[a[0]], a]))<0).cumsum()

    return list(

        chain.from_iterable(

            (reversed([x[0] for x in g]) for v, g in groupby(zip(a, idx), itemgetter(1)))

        )

    )



print(reverse_increasing_sequences(a))

#[7, 5, 1, 3, 5, 2, 45, 4, 12, 10, 5, 1]

But looking at the speed test results:

b = np.random.choice(10, 100000)



%%timeit

reverse_increasing_sequences_numpy(b)

#47.1 ms ± 778 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)



%%timeit

reverse_increasing_sequences_iGian(b)

#40.3 ms ± 1.31 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)



%%%timeit

reverse_increasing_sequences_hchw(b)

#26.1 ms ± 1.35 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

@hchw's solution ran is almost 2 times faster than my numpy version.