Для каждой метки в одном массиве установите для первых k вхождений значение False в другом массиве.

Question

У меня есть два (отсортированных) массива, A и B, разной длины, каждая из которых содержит уникальные метки, которые повторяются несколько раз. Количество для каждой метки в A меньше или равно количеству в B. Все метки в A будут в B, но некоторые метки в B не появляются в A.

Мне нужен объект такой же длины, как B, где для каждой метки i в A (что происходит k_i раз), первые k_i вхождения метки i в B должны быть установлены на False. Остальные элементы должны быть True.

Следующий код дает мне то, что мне нужно, но если A и B большие, это может занять много времени:

import numpy as np

# The labels and their frequency
A = np.array((1,1,2,2,3,4,4,4))
B = np.array((1,1,1,1,1,2,2,3,3,4,4,4,4,4,5,5))

A_uniq, A_count = np.unique(A, return_counts = True)
new_ind = np.ones(B.shape, dtype = bool)
for i in range(len(A_uniq)):
    new_ind[np.where(B == A_uniq[i])[0][:A_count[i]]] = False

print(new_ind)
#[False False  True  True  True False False False  True False False False
#  True  True  True  True]

Есть ли более быстрый или эффективный способ сделать это? Я чувствую, что могу упустить какое-то очевидное вещательное или векторизованное решение.

Answer 1

Это решение вдохновлено решением @Divakar, использующим itertools.groupby :

import numpy as np
from itertools import groupby
A = np.array((1, 1, 2, 2, 3, 4, 4, 4))
B = np.array((1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 5, 5))

indices = [key + i for key, group in groupby(np.searchsorted(B, A)) for i, _ in enumerate(group)]
result = np.ones_like(B, dtype=np.bool)
result[indices] = False

print(result)

выход

[False False  True  True  True False False False  True False False False
  True  True  True  True]

Идея состоит в том, чтобы использовать np.searchsorted , чтобы найти позицию вставки каждого элемента A, так как равные элементы будут иметь одинаковую позицию вставки, которую вы должны сместить на одну из них, следовательно группа. Затем создайте массив True и установите для значений indices значение False.

Если вы можете использовать pandas, вычислите indices следующим образом:

values = np.searchsorted(B, A)
indices = pd.Series(values).groupby(values).cumcount() + values

Answer 2

Пример без numpy

A = [1,1,2,2,3,4,4,4]
B = [1,1,1,1,1,2,2,3,3,4,4,4,4,4,5,5]

a_i = b_i = 0
while a_i < len(A):
  if A[a_i] == B[b_i]:
    a_i += 1
    B[b_i] = False
  else:
    B[b_i] = True
  b_i += 1
# fill the rest of B with True
B[b_i:] = [True] * (len(B) - b_i)
# [False, False, True, True, True, False, False, False, True, False, False, False, True, True, True, True]

Answer 3

Вот один с np.searchsorted -

idx = np.searchsorted(B, A_uniq)
id_ar = np.zeros(len(B),dtype=int)
id_ar[idx] = 1
id_ar[A_count+idx] -= 1
out = id_ar.cumsum()==0

Мы можем продолжить оптимизацию для вычисления A_uniq,A_count, используя его отсортированную природу вместо использования np.unique, вот так -

mask_A = np.r_[True,A[:-1]!=A[1:],True]
A_uniq, A_count = A[mask_A[:-1]], np.diff(np.flatnonzero(mask_A))