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

В Numpy, есть ли питонный способ создания array3 с настраиваемыми диапазонами из array1 и array2 без цикла? Простое решение итерации по диапазонам работает, но так как мои массивы состоят из миллионов элементов, я ищу более эффективное решение (возможно, синтаксический сахар тоже).

Например,

array1 = np.array([10, 65, 200]) 
array2 = np.array([14, 70, 204])
array3 = np.concatenate([np.arange(array1[i], array2[i]) for i in
                         np.arange(0,len(array1))])

print array3

результат:[10,11,12,13,65,66,67,68,69,200,201,202,203].

 Divakar16 июн. 2016 г., 20:10
Еще один дружеский запрос на напоминание: какое-либо из решений сработало для вас?
 Divakar18 июн. 2016 г., 19:25
@snowmonkey Ах, не беспокойся! И, наконец, рад получить ответ от вас! :)
 hpaulj04 июн. 2016 г., 03:01
Если это работает, понятно и быстродовольноЭто «питон».numpy-onic требует устранения явного цикла. :)
 snowmonkey18 июн. 2016 г., 18:59
@Divakar Извините за поздний ответ. Все ответы хороши, и в конечном итоге я использовал ваше решение. Очень элегантно, я должен сказать и поблагодарить вас за то, что вы поделились своим мыслительным процессом. Данные на работе, и я был в отпуске до сегодняшнего дня. Я хотел собрать все функции для запуска своих данных и проверить их производительность, поэтому пока не отвечал.

Ответы на вопрос(4)

Вы имеете в виду это?

In [440]: np.r_[10:14,65:70,200:204]
Out[440]: array([ 10,  11,  12,  13,  65,  66,  67,  68,  69, 200, 201, 202, 203])

или обобщая:

In [454]: np.r_[tuple([slice(i,j) for i,j in zip(array1,array2)])]
Out[454]: array([ 10,  11,  12,  13,  65,  66,  67,  68,  69, 200, 201, 202, 203])

Хотя это включает двойной цикл, явный для генерации срезов и один внутриr_ преобразовать ломтики вarange.

    for k in range(len(key)):
        scalar = False
        if isinstance(key[k], slice):
            step = key[k].step
            start = key[k].start
                ...
                newobj = _nx.arange(start, stop, step)

Я упоминаю об этом, потому что это показывает, чтоnumpy Разработчики считают ваш тип итераций нормальным.

Я ожидаю, что умник @ unutbu, хотя и несколько тупой (я еще не понял, что он делает), решение - ваш лучший шанс на скорость.cumsum это хороший инструмент, когда вам нужно работать с диапазонами, которые могут варьироваться по длине. Это, вероятно, выигрывает больше всего при работе со многими маленькими диапазонами. Я не думаю, что это работает с перекрывающимися диапазонами.

================

np.vectorize использованияnp.frompyfunc, Так что эта итерация также может быть выражена с помощью:

In [467]: f=np.frompyfunc(lambda x,y: np.arange(x,y), 2,1)

In [468]: f(array1,array2)
Out[468]: 
array([array([10, 11, 12, 13]), array([65, 66, 67, 68, 69]),
       array([200, 201, 202, 203])], dtype=object)

In [469]: timeit np.concatenate(f(array1,array2))
100000 loops, best of 3: 17 µs per loop

In [470]: timeit np.r_[tuple([slice(i,j) for i,j in zip(array1,array2)])]
10000 loops, best of 3: 65.7 µs per loop

С @ Дарияvectorize решение:

In [474]: timeit result = np.concatenate(ranges(array1, array2), axis=0)
10000 loops, best of 3: 52 µs per loop

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

Решение @ unutbu не является особенным с этим маленькимarray1.

In [478]: timeit using_flatnonzero(array1,array2)
10000 loops, best of 3: 57.3 µs per loop

ОП решение, итеративное без моегоr_ средний человек хорош

In [483]: timeit array3 = np.concatenate([np.arange(array1[i], array2[i]) for i in np.arange(0,len(array1))])
10000 loops, best of 3: 24.8 µs per loop

Часто бывает так, что при небольшом числе циклов понимание списка происходит быстрее, чем нужноnumpy операции.

Для большего тестового примера @ unutbu мои тайминги соответствуют его - с 17-кратным ускорением.

===================

Для небольших выборочных массивов решение @ Divakar медленнее, но для больших в 3 раза быстрее, чем у @ unutbu. Таким образом, он имеет большую стоимость установки, но масштабируется медленнее.

 Darius M.04 июн. 2016 г., 10:35
Мне нравятся твои сравнения.

векторизовать а такжесцеплять:

Реализация:

import numpy as np

array1, array2 = np.array([10, 65, 200]), np.array([14, 70, 204])

ranges = np.vectorize(lambda a, b: np.arange(a, b), otypes=[np.ndarray])
result = np.concatenate(ranges(array1, array2), axis=0)

print result
# [ 10  11  12  13  65  66  67  68  69 200 201 202 203]

Спектакль:

%timeit np.concatenate(ranges(array1, array2), axis=0)

100000 циклов, лучшее из 3: 13,9 мкс на цикл

 hpaulj04 июн. 2016 г., 02:20
Я ждуvectorize будет иметь небольшое улучшение скорости по сравнению со списком списков, может быть, 20%. Это все еще повторяется.

что диапазоны не перекрываются, вы можете создать маску, отличную от нуля, где индекс находится между диапазонами, указанными какarray1 а такжеarray2 а затем использоватьnp.flatnonzero получить массив индексов - желаемыйarray3:

import numpy as np

array1 = np.array([10, 65, 200]) 
array2 = np.array([14, 70, 204])

first, last = array1.min(), array2.max()
array3 = np.zeros(last-first+1, dtype='i1')
array3[array1-first] = 1
array3[array2-first] = -1
array3 = np.flatnonzero(array3.cumsum())+first
print(array3)

доходность

[ 10  11  12  13  65  66  67  68  69 200 201 202 203]

Для большихlen(array1), using_flatnonzero может быть значительно быстрее, чемusing_loop:

def using_flatnonzero(array1, array2):
    first, last = array1.min(), array2.max()
    array3 = np.zeros(last-first+1, dtype='i1')
    array3[array1-first] = 1
    array3[array2-first] = -1
    return np.flatnonzero(array3.cumsum())+first

def using_loop(array1, array2):
    return np.concatenate([np.arange(array1[i], array2[i]) for i in
                           np.arange(0,len(array1))])


array1, array2 = (np.random.choice(range(1, 11), size=10**4, replace=True)
                  .cumsum().reshape(2, -1, order='F'))


assert np.allclose(using_flatnonzero(array1, array2), using_loop(array1, array2))
In [260]: %timeit using_loop(array1, array2)
100 loops, best of 3: 9.36 ms per loop

In [261]: %timeit using_flatnonzero(array1, array2)
1000 loops, best of 3: 564 µs per loop

Если диапазоны перекрываются, тоusing_loop вернетarray3 который содержит дубликаты.using_flatnonzero возвращает массив без дубликатов.

объяснение: Давайте посмотрим на небольшой пример с

array1 = np.array([10, 65, 200]) 
array2 = np.array([14, 70, 204])

Цель состоит в том, чтобы создать массив, который выглядит какgoalниже. 1 расположены в значениях индекса[ 10, 11, 12, 13, 65, 66, 67, 68, 69, 200, 201, 202, 203] (Т.е.array3):

In [306]: goal
Out[306]: 
array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1,
       1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], dtype=int8)

Когда у нас естьgoal массив,array3 можно получить с помощью звонкаnp.flatnonzero:

In [307]: np.flatnonzero(goal)
Out[307]: array([ 10,  11,  12,  13,  65,  66,  67,  68,  69, 200, 201, 202, 203])

goal имеет ту же длину, что иarray2.max():

In [308]: array2.max()
Out[308]: 204

In [309]: goal.shape
Out[309]: (204,)

Таким образом, мы можем начать с выделения

goal = np.zeros(array2.max()+1, dtype='i1')

а затем заполняя 1 в индексных местах, заданныхarray1 и -1 в индексах, данныхarray2:

In [311]: goal[array1] = 1
In [312]: goal[array2] = -1
In [313]: goal
Out[313]: 
array([ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0, -1,  0,  0,
        0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
        0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
        0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,
        0,  0, -1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
        0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
        0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
        0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
        0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
        0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
        0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
        0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,
       -1], dtype=int8)

Сейчас подаю заявкуcumsum (накопленная сумма) производит желаемоеgoal массив:

In [314]: goal = goal.cumsum(); goal
Out[314]: 
array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1,
       1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0])

In [315]: np.flatnonzero(goal)
Out[315]: array([ 10,  11,  12,  13,  65,  66,  67,  68,  69, 200, 201, 202, 203])

Это основная идеяusing_flatnonzero, Вычитаниеfirst было просто сэкономить немного памяти.

Решение Вопроса
Перспективный подход

Возьмите образец, указанный в вопросе. У нас есть -

array1 = np.array([10, 65, 200])
array2 = np.array([14, 70, 204])

Теперь посмотрим на желаемый результат -

result: [10,11,12,13,65,66,67,68,69,200,201,202,203]

Давайте вычислим длины групп, которые нам понадобятся для объяснения подхода к решению.

In [58]: lens = array2 - array1

In [59]: lens
Out[59]: array([4, 5, 4])

Идея состоит в том, чтобы использовать1Инициализированный массив, который при суммировании по всей длине даст нам желаемый результат. Это кумулятивное суммирование будет последним шагом к нашему решению. Зачем1инициализирован? Ну, потому что у нас есть массив, который увеличивается с шагом1За исключением определенных мест, где у нас есть смены, соответствующие приходу новых групп.

Теперь, так какcumsum будет последним шагом, поэтому шаг до того, как он должен дать нам что-то вроде -

array([ 10,   1,   1,   1,  52,   1,   1,   1,   1, 131,   1,   1,   1])

Как уже говорилось ранее, это1заполнен[10,52,131] в определенных местах. Тот10 кажется, приходит с первого элемента вarray1а как насчет остальных? Второй52 пришел как65-13 (глядя наresult) и в нем13 пришел в группу, которая началась с10 и побежал из-за длины первой группы4, Итак, если мы сделаем65 - 10 - 4, мы получим51 а затем добавить1 чтобы разместить для пограничной остановки, мы бы52, который является желаемым значением сдвига. Точно так же мы бы получили131.

Таким образом, теshifting-values может быть вычислено, вот так -

In [62]: np.diff(array1) - lens[:-1]+1
Out[62]: array([ 52, 131])

Далее, чтобы получить теshifting-places там, где происходят такие сдвиги, мы можем просто сделать кумулятивное суммирование по длинам групп -

In [65]: lens[:-1].cumsum()
Out[65]: array([4, 9])

Для полноты нам нужно предварительно добавить0 с массивомshifting-places а такжеarray1[0] заshifting-values.

Итак, мы готовы представить наш подход в пошаговом формате!

Положить обратно кусочки

1] Получить длины каждой группы:

lens = array2 - array1

2] Получите индексы, при которых происходят сдвиги, и значения, которые нужно поместить в1Инициализированный массив:

shift_idx = np.hstack((0,lens[:-1].cumsum()))
shift_vals = np.hstack((array1[0],np.diff(array1) - lens[:-1]+1))

3] Настройка1Инициализированный массив идентификаторов для вставки этих значений в индексы, перечисленные в предыдущем шаге:

id_arr = np.ones(lens.sum(),dtype=array1.dtype)
id_arr[shift_idx] = shift_vals

4] Наконец, выполните кумулятивное суммирование в массиве ID:

output = id_arr.cumsum() 

Перечисленные в формате функции, мы бы

def using_ones_cumsum(array1, array2):
    lens = array2 - array1
    shift_idx = np.hstack((0,lens[:-1].cumsum()))
    shift_vals = np.hstack((array1[0],np.diff(array1) - lens[:-1]+1))
    id_arr = np.ones(lens.sum(),dtype=array1.dtype)
    id_arr[shift_idx] = shift_vals
    return id_arr.cumsum()

И это работает на перекрывающихся диапазонах тоже!

In [67]: array1 = np.array([10, 11, 200]) 
    ...: array2 = np.array([14, 18, 204])
    ...: 

In [68]: using_ones_cumsum(array1, array2)
Out[68]: 
array([ 10,  11,  12,  13,  11,  12,  13,  14,  15,  16,  17, 200, 201,
       202, 203])

Испытание во время выполнения

Давайте время предложенного подхода против другого векторизованного подхода в@unutbu's flatnonzero based solution, который уже оказался намного лучше, чем тупой подход -

In [38]: array1, array2 = (np.random.choice(range(1, 11), size=10**4, replace=True)
    ...:                   .cumsum().reshape(2, -1, order='F'))

In [39]: %timeit using_flatnonzero(array1, array2)
1000 loops, best of 3: 889 µs per loop

In [40]: %timeit using_ones_cumsum(array1, array2)
1000 loops, best of 3: 235 µs per loop
Улучшение!

Теперь codewise NumPy не любит добавлять. Итак, теnp.hstack можно было бы избежать вызовов для слегка улучшенной версии, как указано ниже -

def get_ranges_arr(starts,ends):
    counts = ends - starts
    counts_csum = counts.cumsum()
    id_arr = np.ones(counts_csum[-1],dtype=int)
    id_arr[0] = starts[0]
    id_arr[counts_csum[:-1]] = starts[1:] - ends[:-1] + 1
    return id_arr.cumsum()

Давайте время против нашего оригинального подхода -

In [151]: array1,array2 = (np.random.choice(range(1, 11),size=10**4, replace=True)\
     ...:                                      .cumsum().reshape(2, -1, order='F'))

In [152]: %timeit using_ones_cumsum(array1, array2)
1000 loops, best of 3: 276 µs per loop

In [153]: %timeit get_ranges_arr(array1, array2)
10000 loops, best of 3: 193 µs per loop

Итак, у нас есть30% прирост производительности там!

 unutbu04 июн. 2016 г., 11:50
Вот это да. Brilliant!
 Divakar04 июн. 2016 г., 13:23
@unutbu Спасибо! Ваш тоже был довольно умен! :)

Ваш ответ на вопрос