Последовательные цифры в обратном порядке

Question

У меня очень длинный массив, и я пытаюсь сделать следующее максимально эффективным образом:

Для каждого последовательно увеличивающегося фрагмента в списке я должен изменить его порядок.

Итак, для следующего массива:

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

Я хотел бы получить:

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

Мне было интересно, можно ли это векторизовать, используя numpy, возможно?

У меня уже были некоторые ответы в этом предыдущем вопросе, но результаты, хотя они и являются большими улучшениями, они все еще немного медленны.

Answer 1

Я не думаю, что вы получите намного быстрее, чем использование чистого цикла Python.

Например, вот решение numpy + itertools:

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]

Но, глядя на результаты теста скорости:

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 решение работает почти в 2 раза быстрее, чем моя тупая версия.

Answer 2

Можно ли использовать панд?

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

Вывод:

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

Answer 3

Другой вариант без зависимостей:

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

---

РЕДАКТИРОВАТЬ после того, как ответ был принят (Может быть, это полезно.)

Мне удалось получить результат так же легко и, по-видимому, немного быстрее кодирования в Ruby:

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

Итак, я удивляюсь, почему не существует itertool, как chunk_while. Затем я попытался закодировать один подобный, используя 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]

Выполнение выполняется очень быстро, но вместо списка возвращается генератор для итерации:

chunks = reverse_if_chunk_increases(array)
for chunk in chunks:
  print(chunk)
# [7, 5, 1]
# [3]
# [5, 2]
# [45, 4]
# [12, 10, 5, 1]

Его можно преобразовать в список, который является самым медленным процессом. Обратите внимание, что генератор можно вызвать один раз. При удалении [::-1] вы получите результат, аналогичный перечислителю / генератору Ruby chunk_while.

Answer 4

Как это? Кажется, быстрее, на самом деле, но не зная, как быстро достаточно быстро, трудно сказать наверняка

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)