Перемещая два массива индексов numpy, по одному элементу из каждого массива

Ответ 1

Векторное решение (педагогический стиль, легко понятный)

Мы можем векторизовать это, увеличивая массивы с помощью индекса дискриминатора, так что 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 микросекунд, хотя ваши условия могут отличаться.

Ответ 2

Вы можете разбить проблему на две части:

• Сделайте итераторы a и b, которые дают значения, только если они больше чем threshold.
• Используйте itertools (по сути, рецепт Roundrobin от Джорджа Саккиса), чтобы чередовать два итератора.

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]

Ответ 3

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]

Ответ 4

Я думаю, вам будет сложно применить векторию numpy к этой проблеме и поддерживать линейную производительность. Для этого требуется хранить справедливый бит состояния: текущий индекс в a, текущий индекс в b и текущий threshold. numpy не предоставляет много векторизованных функций с сохранением состояния. На самом деле, единственное, что я могу вспомнить от головы, - это ufunc.reduce, что не подходит для этой проблемы, хотя, конечно, это может быть обучено работе.

Фактически, сразу после того, как я опубликовал это, мой браузер обновлен с помощью отличного векторизованного решения. Но это решение требует сортировки, которая является O (n log n); и действительно, после некоторого тестирования я вижу, что решение на чистом питоне ниже для всех входов быстрее!

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, независимо. Я изменил приведенное выше, чтобы проверить это на следующие тесты, которые показывают, что чистое решение python является самым быстрым.

Определения:

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

Ответ 5

Вдохновленный другими сообщениями, у меня было другое представление о чистом питонном коде, который требует предварительного упорядочения, но который симметричен 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 пуст.