Попарное сравнение элементов множества

Question

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

Мой код приведен ниже.Похоже, работает правильно;однако, как вы можете догадаться, это очень медленно (занимает 6-7 часов).

Интересно, есть ли другой способ создать это подмножество быстрее, чем эта реализация?

dataset = [a,b,c,d,e,f,g,...] #an example sorted dataset. real size is 20K
subset = [] #my diverse set. Desired size is 200

for ind, element in enumerate(dataset):
  if ind == 0:
    subset.append(element[ind]) #since the dataset is sorted I can directly add the first element
  else:
    similarities = []
    for member in subset:
      similarities.append(compute_similarity(element[ind], member))

    if not any(similarities): #if the candidate is not similar to any of the existing members
      subset.append(element[ind])

  if len(subset) >= 200:
    break

Answer 1

Главное улучшение, которое я вижу, состоит в том, чтобы сломаться, как только вы обнаружите, что текущий элемент похож на некоторый элемент уже в вашем наборе.Это позволяет упростить ваш код, даже устраняя необходимость в дополнительной проверке первого элемента.

dataset = [a,b,c,d,e,f,g,...] #an example sorted dataset. real size is 20K
subset = [] #my diverse set. Desired size is 200

for candidate in dataset:
  for member in subset:
    if compute_similarity(candidate, member):
      break
  else:
    subset.append(candidate)
    if len(subset) >= 200:
      break

Обратите внимание на конструкцию for-else, которая выполняет ветвь else, только если for-цикл не прервался.

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