1 Вопрос: накопительный логический или внутри бункеров

вопрос создан в Thu, May 2, 2019 12:00 AM

Проблема

Я хочу определить, когда я встретил истинное значение, и сохранить это значение для остальной части массива ... для конкретного бина. С точки зрения Numpy это будет похоже на комбинацию numpy.logical_or.accumulate и numpy.logical_or.at.

Пример

Рассмотрим значения истинности в a, ячейки в b и ожидаемый результат в c.
Я использовал 0 для False и 1 для True, а затем преобразовал в bool для выравнивания значений массива.

a = np.array([0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0]).astype(bool)
b = np.array([0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 2, 3, 3, 0, 1, 2, 3])
# zeros       ↕  ↕  ↕              ↕  ↕  ↕           ↕
# ones                 ↕  ↕  ↕  ↕                       ↕
# twos                                      ↕              ↕
# threes                                       ↕  ↕           ↕
c = np.array([0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1]).astype(bool)
#             ╰─────╯     ↑           ↑           ↑        ↑
#  zero bin no True yet   │           │           │        two never had a True
#                one bin first True   │     three bin first True
#                           zero bin first True

Что я попробовал

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

tracker = np.zeros(4, bool)
result = np.zeros(len(b), bool)

for i, (truth, bin_) in enumerate(zip(a, b)):
    tracker[bin_] |= truth
    result[i] = tracker[bin_]

result * 1

array([0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1])

Но я надеялся на временное решение Numpy для O (n) . У меня есть возможность использовать JIT-оболочку, такую ​​как Numba, но я бы предпочел оставить ее только Numpy.

    
4
  1. Будут ли ячейки всегда сначала появляться в b в порядке возрастания?
    2019-05-02 15: 38: 35Z
  2. Допустим, да. Если я когда-нибудь столкнусь с ситуацией, когда это не так, я могу учесть.
    2019-05-02 15: 39: 58Z
1 ответ                              1                         

O (n) решение

def cumulative_linear_seen(seen, bins):
    """
    Tracks whether or not a value has been observed as
    True in a 1D array, and marks all future values as
    True for these each individual value.

    Parameters
    ----------
    seen: ndarray
      One-hot array marking an occurence of a value
    bins: ndarray
      Array of bins to which occurences belong

    Returns
    -------
    One-hot array indicating if the corresponding bin has
    been observed at a point in time
    """

    # zero indexing won't work with logical and, need to 1-index
    one_up = bins + 1

    # Next step is finding where each unique value is seen
    occ = np.flatnonzero(a)
    v_obs = one_up[a]

    # We can fill another mapping array with these occurences.
    # then map by corresponding index
    i_obs = np.full(one_up.max() + 1, seen.shape[0] + 1)
    i_obs[v_obs] = occ

    # Finally, we create the map and compare to an array of
    # indices from the original seen array
    seen_idx = i_obs[one_up]

    return (seen_idx <= np.arange(seen_idx.shape[0])).astype(int)

р>

array([0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1])

Вклад PiR

На основе представленных выше сведений

r = np.arange(len(b))
one_hot = np.eye(b.max() + 1, dtype=bool)[b]
np.logical_or.accumulate(one_hot & a[:, None], axis=0)[r, b] * 1

array([0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1])

Старые попытки

Просто для начала, вот решение, которое, хотя и векторизовано, является не O (n). Я считаю, что решение O (n), подобное этому, существует, я буду работать над сложностью: -)

Попытка 1

q = b + 1

u = sparse.csr_matrix(
    (a, q, np.arange(a.shape[0] + 1)), (a.shape[0], q.max()+1)
)

m = np.maximum.accumulate(u.A) * np.arange(u.shape[1])
r = np.where(m[:, 1:] == 0, np.nan, m[:, 1:])

(r == q[:, None]).any(1).view(np.int8)

р>

array([0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1], dtype=int8)

Попытка 2

q = b + 1
m = np.logical_and(a, q)
r = np.flatnonzero(u)
t = q[m]
f = np.zeros((a.shape[0], q.max()))
f[r, t-1] = 1
v = np.maximum.accumulate(f) * np.arange(1, q.max()+1)
(v == q[:, None]).any(1).view(np.int8)

р>

array([0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1], dtype=int8)
    
2
2019-05-02 20: 50: 44Z
  1. когда я cumulative_linear_seen(a, b), я получаю что-то другое ([0 0 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1]). Кроме того, я не понимаю q = b + 1. Для моего b это [1 1 1 2 2 2 2 1 1 1 3 4 4 1 2 3 4], в котором вся правда - True, который вы можете увидеть, если я вставлю это утверждение в вашу функцию print((seen == np.logical_and(seen, one_up)).all())
    2019-05-02 19: 37: 05Z
  2. Некоторое время назад я опубликовал неверную версию функции, которая должна быть исправлена ​​сейчас. Чтобы убедиться, что у вас есть новый, проверьте последнюю строку, она должна быть <= вместо <. Ваш второй комментарий полностью верен, я воссоздаю данные, которые у меня уже есть, обновляя их сейчас
    2019-05-02 19: 54: 28Z
  3. @ piRSquared здесь немного проверки repl.it /консолей REPL /BiodegradableSmoothQbasic
    2019-05-02 20: 01: 04Z
  4. Я добавил кое-что в ваш пост. Пожалуйста, измените по своему желанию. Я не хотел публиковать другой ответ.
    2019-05-02 20: 23: 29Z
источник размещен Вот