Самый быстрый способ создания декартового произведения без дублирующих элементов внутри пары

Question

У меня есть список индексов изображений, и его длина составляет 60000. Я хочу создать еще один список, который содержит случайные пары индексов. Ограничение здесь заключается в том, что каждый элемент набора продуктов должен содержать различные индексы. Другими словами, я не хочу связывать индекс с этим самостоятельно.

В настоящее время я использую itertools.product метод с for петля.

pairs = []
for pair in itertools.product(indexes, indexes):
    if pair[0]!=pair[1]:
        pairs.append(pair)

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

Есть ли лучший способ сделать это?

Answer 1

Вы можете сделать это лениво, не сохраняя их:

pairs = filter(lambda x: x[0] != x[1], itertools.product(indexes, indexes))

использование itertools.ifilter при использовании python2

Идея использования itertools состоит в том, что вам не нужно предварительно вычислять все, а просить вычислять его по одному элементу (вычислению) за раз.

Я сделал сравнение времени, предложенное @Deepak Saini, которое здесь живет:

import numpy as np
import itertools

indexes = np.arange(1000)

def pairs(indexes):
  pairs = []
  for pair in itertools.product(indexes, indexes):
      if pair[0]!=pair[1]:
          pairs.append(pair)
  return pairs

def iter_pairs(indexes):
  return filter(lambda x: x[0] != x[1], itertools.product(indexes, indexes))

def iter_pairs_no_lambda(indexes):
  def comp(x):
    return x[0] != x[1]
  return filter(comp, itertools.product(indexes, indexes))

import time
for f in (pairs, iter_pairs, iter_pairs_no_lambda):
  print(f.__name__)
  t1 = time.time()
  res = f(indexes)
  print("Took {}".format(time.time() -  t1))

Который приводит к:

pairs
Took 1.012538194656372
iter_pairs
Took 0.04567384719848633
iter_pairs_no_lambda
Took 0.0002455711364746094

Answer 2

import numpy as np

a = np.asarray(indexes)
b = np.copy(a)

while np.any(a == b):
    b = np.random.choice(a, size=a.shape[0], replace=False)

И должно быть очень быстро

Answer 3

Numpy решение с использованием tile, repeat а также transpose,

temp = np.transpose([np.tile(indexes, len(indexes)), np.repeat(indexes, len(indexes))])
pairs = temp[temp[:,0] != temp[:,1]]

Сроки сравнения: я сравниваю время с

# @Netwave solution
list(filter(lambda x: x[0] != x[1], itertools.product(indexes, indexes)))

Нам нужно преобразовать генератор в список для честного сравнения.

На

indexes = np.arange(5000)

сроки:

Netwave решение: 20,623 с

Numpy решение: 3.302 с

Answer 4

Убедитесь, что у вас есть уникальные значения, а затем выберите комбинацию из двух из них.

      list(itertools.combinations(set(indexes), 2))