Эффективный способ получить объединение множества векторов в Numpy

Question

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

В основном:

results = set()
for result in search():
  results = results.union(result)

Но такиекод на самом деле не будет работать с массивами Numpy, поэтому мы используем np.union1d для этой цели:

results = np.array([])
for result in search():
    result = np.union1d(results, result)

Код выше на самом деле тоже не работает, так как если у нас есть, например, два вектора a = [1,2,3]и b=[3,4,5], np.union1d(a, b) вернется:

[1, 2, 3, 4, 5]

Но я хочу, чтобы он вернулся:

[[1, 2, 3], [3,4,5]]

Так какне являются повторяющимися векторами, если бы мы имели, например, union([[1, 2, 3], [3,4,5]], [1,2,3]), возвращаемое значение должно остаться:

[[1, 2, 3], [3,4,5]]

---

Так что я бы сказал, что мне требуется массив numpyна основе объединения .

Я также рассмотрел использование np.append(a, b), а затем np.unique(x), но обе функции проецируют массив более низкой размерности в массив более высокой.np.append также имеет свойство axis=0, в котором сохраняется размерность всех вставленных массивов, но я не смог эффективно реализовать его без ошибки измерения.

Вопрос:

Как эффективно реализоватьвекторный набор?Таким образом, точки в объединении будут рассматриваться как векторы, а не скаляры, и будут сохранять свою векторную форму и размерность.

Answer 1

Вот некоторые основные операции над множествами.

Определите пару списков (они могут быть np.array([1,2,3]), но это не то, что вы показываете.

In [261]: a = [1,2,3]; b=[3,4,5]

Список нескольких из этих:

In [263]: alist = [a, b, a]
In [264]: alist
Out[264]: [[1, 2, 3], [3, 4, 5], [1, 2, 3]]

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

In [265]: set([tuple(i) for i in alist])
Out[265]: {(1, 2, 3), (3, 4, 5)}

Я также могу преобразовать этот список в двумерный массив:

In [266]: arr = np.array(alist)
In [267]: arr
Out[267]: 
array([[1, 2, 3],
       [3, 4, 5],
       [1, 2, 3]])

и получите уникальные строки с unique и параметром оси:

In [269]: np.unique(arr, axis=0)
Out[269]: 
array([[1, 2, 3],
       [3, 4, 5]])

Сравните время

In [270]: timeit np.unique(arr, axis=0)
46.5 µs ± 142 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [271]: timeit set([tuple(i) for i in alist])
1.01 µs ± 1.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Преобразование массива в список или список вМассив добавляет некоторое время, но базовый шаблон остается.

In [272]: timeit set([tuple(i) for i in arr.tolist()])
1.53 µs ± 13.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
In [273]: timeit np.unique(alist, axis=0)
53.3 µs ± 90.3 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Для больших реалистичных источников относительное время может немного измениться, но я ожидаю, что набор кортежей останется лучшим.numpy сильная точка. unique выполняет сортировку с последующим удалением дубликатов. set использует метод хеширования, аналогичный тому, который Python использует для словарей.

Если вы должны собирать значения итеративно изsource, я бы предложил создать список и сделатьe set/unique один раз.

alist = []
for x in source():
    alist.append(x)

или один из:

alist = [x for x in source()]
alist = list(source())
alist = [tuple(x) for x in source()]
alist = [tuple(x.tolist()) for x in source()]