Эффективно удалять строки, содержащие повторяющиеся элементы между различными строками - PullRequest
Новая
       18

Эффективно удалять строки, содержащие повторяющиеся элементы между различными строками

1 голос
/ 29 января 2020

Для двумерного массива у меня может быть строка с индексом i , в которой может быть одно или несколько чисел, найденных в другой строке с индексом j . Мне нужно удалить эти строки i и j из массива. Также в любой строке числа всегда уникальны для этой строки. У меня есть решение уже без l oop, Numpy на основе. Вот единственное решение, которое я придумал: 

def filter_array(arr):
    # Reshape to 1D without hard copy
    arr_1d = arr.ravel()
    # Make a count of only the existing numbers (faster than histogram)
    u_elem, c = np.unique(arr_1d, return_counts=True)
    # Get which elements are duplicates.
    duplicates = u_elem[c > 1]
    # Get the rows where these duplicates belong
    dup_idx = np.concatenate([np.where(arr_1d == d)[0] for d in duplicates])
    dup_rows = np.unique(dup_idx //9)
    # Remove the rows from the array
    b = np.delete(arr, dup_rows, axis=0)
    return b

Вот (упрощенный) пример входного массива: 

a = np.array([
    [1, 3, 23, 40, 33],
    [2, 8, 5, 35, 7],
    [9, 32, 4, 6, 3],
    [72, 85, 32, 48, 53],
    [3, 98, 101, 589, 208],
    [343, 3223, 4043, 65, 78]
])

Отфильтрованный массив дает ожидаемый результат, хотя я не исчерпывающе проверил, работает ли это во всех моих возможных случаях: 

[[   2    8    5   35    7]
 [ 343 3223 4043   65   78]]

Мои типичные размеры массива составляют от 10 ^ 5 до 10 ^ 6 строк с фиксированным числом 9 столбцов. % timeit дает около 270 мс для фильтрации каждого из таких массивов. У меня есть сто миллионов из них. Я пытаюсь ускорить это на одном процессоре, прежде чем рассматривать другие способы (например, графические процессоры)

Эти данные могут уже находиться в Pandas кадре данных.

1 Ответ

2 голосов
/ 29 января 2020

Мы могли бы добиться существенного ускорения, используя np.isin после нахождения уникальных значений и их количества и используя результат для индексации массива: 

u, c = np.unique(a, return_counts=True)
a[np.isin(a, u[c == 1]).all(1)]

array([[   2,    8,    5,   35,    7],
       [ 343, 3223, 4043,   65,   78]])

Сроки: 

def filter_array(arr):
    arr_1d = arr.ravel()
    u_elem, c = np.unique(arr_1d, return_counts=True)
    duplicates = u_elem[c > 1]
    dup_idx = np.concatenate([np.where(arr_1d == d)[0] for d in duplicates])
    dup_rows = np.unique(dup_idx //9)
    b = np.delete(arr, dup_rows, axis=0)
    return b

def yatu(arr):
    u, c = np.unique(arr, return_counts=True)
    return arr[np.isin(arr, u[c == 1]).all(1)]

a_large = np.random.randint(0, 50_000, (10_000, 5))

%timeit filter_array(a_large)
# 433 ms ± 25.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit yatu(a_large)
# 7.81 ms ± 443 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
...