Чередование двух массивов индексных индексов, по одному элементу из каждого массива
У меня есть два упорядоченных массива, и я хочу чередовать их, чтобы я взял один элемент из первого массива, затем другой из второго, а затем обратно к первому - взяв следующий элемент, который больше, чем тот, который я только что взял из второй и тд. На самом деле это массивы индексов для других массивов, и я буду в порядке при работе с исходными массивами, пока операция векторизована (но, конечно, работа с индексным массивом как векторная операция будет потрясающей).
Пример (можно предположить, что пересечение массивов пусто)
a = array([1,2,3,4,7,8,9,10,17])
b = array([5,6,13,14,15,19,21,23])
Я хотел бы получить [1,5,7,13,17,19]
5 ответов
Векторизованное решение (педагогический стиль, легко понятный)
Мы можем векторизовать это, увеличив массивы индексом дискриминатора, таким образом, чтобы a помечен 0 а также b помечен 1:
a_t = np.vstack((a, np.zeros_like(a)))
b_t = np.vstack((b, np.ones_like(b)))
Теперь давайте объединяем и сортируем:
c = np.hstack((a_t, b_t))[:, np.argsort(np.hstack((a, b)))]
array([[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14, 15, 17, 19, 21, 23],
[ 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1]])
Вы можете видеть, что теперь элементы в порядке, но сохраняют свои теги, поэтому мы можем видеть, какие элементы пришли a и из b,
Итак, давайте выберем первый элемент и каждый элемент, с которого меняется тег 0 (за a) чтобы 1 (за b) и обратно
c[:, np.concatenate(([True], c[1, 1:] != c[1, :-1]))][0]
array([ 1, 5, 7, 13, 17, 19])
Эффективное векторизованное решение
Вы можете сделать это немного эффективнее, храня элементы и их теги в отдельных (но параллельных) массивах:
ab = np.hstack((a, b))
s = np.argsort(ab)
t = np.hstack((np.zeros_like(a), np.ones_like(b)))[s]
ab[s][np.concatenate(([True], t[1:] != t[:-1]))]
array([ 1, 5, 7, 13, 17, 19])
Это немного более эффективно, чем приведенное выше решение; Я получаю в среднем 45, а не 90 микросекунд, хотя ваши условия могут отличаться.
Вы можете разбить проблему на две части:
- Делать
aа такжеbитераторы, которые дают значения, только если они больше, чем некоторыеthreshold, - использование
itertools(по существу, рецепт круглого робота Джорджа Саккиса) для чередования двух итераторов.
import itertools
import numpy as np
a = np.array([1,2,3,4,7,8,9,10,17])
b = np.array([5,6,13,14,15,19,21,23])
def takelarger(iterable):
for x in iterable:
if x > takelarger.threshold:
takelarger.threshold = x
yield x
takelarger.threshold = 0
def alternate(*iterables):
# Modified version of George Sakkis' roundrobin recipe
# http://docs.python.org/library/itertools.html#recipes
pending = len(iterables)
nexts = itertools.cycle(iter(it).next for it in iterables)
while pending:
try:
for n in nexts:
yield n()
except StopIteration:
# Unlike roundrobin, stop when any iterable has been consumed
break
def interleave(a, b):
takelarger.threshold = 0
return list(alternate(takelarger(a),takelarger(b)))
print(interleave(a,b))
доходность
[1, 5, 7, 13, 17, 19]
Я думаю, вам будет трудно подать заявку numpy векторизация к этой проблеме и поддерживать линейную производительность. Это требует сохранения достаточного количества состояния: текущий индекс в aтекущий индекс в bи текущий threshold, numpy не предоставляет много сохраняющих состояние векторизованных функций. На самом деле, единственное, что я могу придумать, - это ufunc.reduce, которая не очень подходит для этой проблемы - хотя, конечно, это может быть включено в работу.
Фактически, сразу после того, как я опубликовал это, мой браузер обновился с отличным векторизованным решением. Но это решение требует сортировки, которая является O(n log n); и действительно, после некоторого тестирования я вижу, что приведенное ниже решение на чистом Python быстрее для всех входных данных!
def interleave_monotonic(a, b):
try:
a = iter(a)
threshold = next(a)
yield threshold
for current in b:
if current > threshold:
threshold = current
yield threshold
while current <= threshold:
current = next(a)
threshold = current
yield threshold
except StopIteration:
return
Обратите внимание, что если a пусто, возвращает пустую итерацию, но если b пуст, возвращает итерацию из одного элемента, содержащую первое значение a, Я думаю, что это соответствует вашему примеру, но это крайний случай, в котором я не уверен. Так же numpyрешение на основе немного отличается поведение, всегда начиная с меньшего a[0] а также b[0]в то время как выше всегда начинается с первого значения a, несмотря на. Я изменил вышеупомянутое, чтобы проверить это для следующих тестов, которые ясно показывают, что решение на чистом питоне является самым быстрым.
Определения:
def interleave_monotonic_np(a, b):
ab = np.hstack((a, b))
s = np.argsort(ab)
t = np.hstack((np.zeros_like(a), np.ones_like(b)))[s]
return ab[s][np.concatenate(([True], t[1:] != t[:-1]))]
def interleave_monotonic(a, b):
a, b = (a, b) if a[0] <= b[0] else (b, a)
try:
a = iter(a)
threshold = next(a)
yield threshold
for current in b:
if current > threshold:
threshold = current
yield threshold
while current <= threshold:
current = next(a)
threshold = current
yield threshold
except StopIteration:
return
def interleave_monotonic_py(a, b):
return numpy.fromiter(interleave_monotonic(a, b), dtype='int64')
def get_a_b(n):
rnd = random.sample(xrange(10 ** 10), n * 2)
return sorted(rnd[0::2]), sorted(rnd[1::2])
тесты:
>>> for e in range(7):
... a, b = get_a_b(10 ** e)
... print (interleave_monotonic_np(a, b) ==
... interleave_monotonic_py(a, b)).all()
... %timeit interleave_monotonic_np(a, b)
... %timeit interleave_monotonic_py(a, b)
...
True
10000 loops, best of 3: 85.6 us per loop
100000 loops, best of 3: 5.53 us per loop
True
10000 loops, best of 3: 91.7 us per loop
100000 loops, best of 3: 9.19 us per loop
True
10000 loops, best of 3: 144 us per loop
10000 loops, best of 3: 46.5 us per loop
True
1000 loops, best of 3: 711 us per loop
1000 loops, best of 3: 445 us per loop
True
100 loops, best of 3: 6.67 ms per loop
100 loops, best of 3: 4.42 ms per loop
True
10 loops, best of 3: 135 ms per loop
10 loops, best of 3: 55.7 ms per loop
True
1 loops, best of 3: 1.58 s per loop
1 loops, best of 3: 654 ms per loop
a = [1,2,3,4,7,8,9,10,17]
b = [5,6,13,14,15,19,21,23]
c=[]
c.append(a[0]) #add the first element to c
i=True #breaking condition
loop=2 #initially we to choose b
while i:
if loop==2:
val=c[-1]
temp_lis=d([x-val for x in b]) #find the difference between every
# element and the last element of c and
# pick the smallest positive value.
for k,y in enumerate(temp_lis):
if y>0:
c.append(b[k])
break
else:
i=False #use for-else loop for determining the breaking condition
loop=1 #change the loop to 1
elif loop==1:
val=c[-1]
temp_lis=[x-val for x in a]
for k,y in enumerate(temp_lis):
if y>0:
c.append(a[k])
break
else:
i=False
loop=2
print c
выход:
[1, 5, 7, 13, 17, 19]
Вдохновленный другими постами, у меня была другая идея чистого кода на Python, который требует предварительного заказа, но который симметричен a и b
def myIterator4(a, b):
curr = iter(a)
next = iter(b)
try:
max = curr.next()
tmp = next.next() # Empty iterator if b is empty
while True:
yield max
while tmp<=max:
tmp = next.next()
max = tmp
curr, next = next, curr
except StopIteration:
return
Возвращает пустой итератор, если a или b пусто.