Reverse order sequential digits

Admin 1
Viewed 115

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.

numpy python
4 Answers

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

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]

Modified version which is a bit faster:

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

EDIT after the answer was accepted (Maybe it's useful.)

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.

user_52390300

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)
user_44311940

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.

user_58588510
Related