Вы можете уменьшить количество проходов по заданному списку, создав список заданных индексов, связанных с каждым значением. Затем, один дополнительный проход по списку наборов, вы можете определить, какие наборы имеют наиболее распространенные значения, составив число индексов для каждого значения набора.
В некоторых случаях это повысит производительность, но, в зависимости от плотность данных, это не может быть огромной разницей.
Вот пример использования defaultdict и Counter из модуля сборов.
from collections import defaultdict,Counter
def top5Matches(setList):
valueSets = defaultdict(list)
for i,aSet in enumerate(setList):
for v in aSet: valueSets[v].append(i)
results = []
for i,aSet in enumerate(setList):
counts = Counter()
for v in aSet: counts.update(valueSets[v])
counts[i] = 0
top5 = [setList[j] for j,_ in counts.most_common(5)]
results.append((aSet,top5))
return results
Чтобы сравнить время выполнения, я взял свобода встраивания вашего решения в функцию. Мне также пришлось сделать исправление для случаев, когда два набора не имели бы пересечения вообще:
from heapq import heappush, heappop
def OPSolution(my_sets):
results = []
for i in range(len(my_sets)):
neighbor_heap = []
for j in range(len(my_sets)):
if i == j: continue
heappush(neighbor_heap, (1 / max(1,len(my_sets[i] & my_sets[j])), j))
top5 = []
while len(top5) < 5:
j = heappop(neighbor_heap)[1]
top5.append(my_sets[j])
results.append((my_sets[i],top5))
return results
Обе функции возвращают список кортежей, содержащих исходный набор, и список 5 лучших наборов на основе числа общих значений.
Обе функции дают одинаковые результаты, хотя первые 5 наборов могут не совпадать, если количество пересечений одинаково для 6-го (или более) дополнительных наборов.
from random import randrange
my_sets = [ set(randrange(50) for _ in range(20)) for _ in range(20) ]
opResults = OPSolution(my_sets)
print("OPSolution: (matching counts)")
for i,(aSet,top5) in enumerate(opResults):
print(i,"Top 5:",[len(aSet&otherSet) for otherSet in top5])
print("")
print("top5Matches: (matching counts)")
t5mResults = top5Matches(my_sets)
for i,(aSet,top5) in enumerate(t5mResults):
print(i,"Top 5:",[len(aSet&otherSet) for otherSet in top5])
print("")
Вывод:
OPSolution: (matching counts)
0 Top 5: [8, 7, 7, 7, 6]
1 Top 5: [7, 6, 6, 6, 6]
2 Top 5: [8, 7, 6, 6, 6]
3 Top 5: [8, 7, 7, 6, 6]
4 Top 5: [9, 8, 8, 8, 8]
5 Top 5: [7, 6, 6, 6, 6]
6 Top 5: [8, 8, 8, 7, 6]
7 Top 5: [8, 8, 7, 7, 7]
8 Top 5: [9, 7, 7, 7, 6]
9 Top 5: [8, 8, 8, 7, 7]
10 Top 5: [8, 8, 7, 7, 7]
11 Top 5: [8, 8, 7, 7, 6]
12 Top 5: [8, 7, 7, 7, 7]
13 Top 5: [8, 8, 8, 6, 6]
14 Top 5: [9, 8, 8, 6, 6]
15 Top 5: [6, 6, 5, 5, 5]
16 Top 5: [9, 7, 7, 6, 6]
17 Top 5: [8, 7, 7, 7, 7]
18 Top 5: [8, 8, 7, 6, 6]
19 Top 5: [7, 6, 6, 6, 6]
top5Matches: (matching counts)
0 Top 5: [8, 7, 7, 7, 6]
1 Top 5: [7, 6, 6, 6, 6]
2 Top 5: [8, 7, 6, 6, 6]
3 Top 5: [8, 7, 7, 6, 6]
4 Top 5: [9, 8, 8, 8, 8]
5 Top 5: [7, 6, 6, 6, 6]
6 Top 5: [8, 8, 8, 7, 6]
7 Top 5: [8, 8, 7, 7, 7]
8 Top 5: [9, 7, 7, 7, 6]
9 Top 5: [8, 8, 8, 7, 7]
10 Top 5: [8, 8, 7, 7, 7]
11 Top 5: [8, 8, 7, 7, 6]
12 Top 5: [8, 7, 7, 7, 7]
13 Top 5: [8, 8, 8, 6, 6]
14 Top 5: [9, 8, 8, 6, 6]
15 Top 5: [6, 6, 5, 5, 5]
16 Top 5: [9, 7, 7, 6, 6]
17 Top 5: [8, 7, 7, 7, 7]
18 Top 5: [8, 8, 7, 6, 6]
19 Top 5: [7, 6, 6, 6, 6]
Сравнение времени выполнения для различных комбинаций настроек показывает, что индексирование по значению работает лучше для больших наборов данных (хотя и в некоторых случаях незначительно):
[РЕДАКТИРОВАТЬ] Добавлено решение Криса Холла для измерения улучшений скорости, обеспечиваемых путем ограничения функциональности наборами значений в последовательном диапазоне. Мне также пришлось встроить его в функцию и проверить, чтобы результаты были одинаковыми. При этом я понял, что, по сути, у нас был такой же подход. Основное отличие состоит в том, что Крис использует список вместо словаря, который ограничивает значения диапазоном (), для которого должен быть указан размер.
def chrisHall(my_sets,valueRange):
results = []
my_inv_sets = [[] for i in range(valueRange)]
for i in range(len(my_sets)):
for j in range(valueRange):
if j in my_sets[i]:
my_inv_sets[j].append(i)
for i in range(len(my_sets)):
counter = Counter()
for j in my_sets[i]:
counter.update(my_inv_sets[j])
top5 = [my_sets[j] for j,_ in counter.most_common(6)[1:]]
results.append((my_sets[i],top5))
return results
Тесты производительности также были встроены в функцию, чтобы избежать повторения код шаблона:
from random import randrange
from timeit import timeit
def compareSolutions(title,setCount,setSize,valueRange,count=1):
print("-------------------")
print(title,setCount,"sets of",setSize,"elements in range 0 ...",valueRange)
testSets = [ set(randrange(valueRange) for _ in range(setSize)) for _ in range(setCount) ]
t = timeit(lambda: chrisHall(testSets,valueRange),number=count)
print("chrisHall",t)
t = timeit(lambda: top5Matches(testSets),number=count)
print("top5Matches",t)
t = timeit(lambda: OPSolution(testSets),number=count)
print("OPSolution",t)
compareSolutions("SIMPLE TEST SET",20,20,50,count=100)
compareSolutions("MORE SETS:",2000,20,50)
compareSolutions("FEWER INTERSECTIONS:",2000,20,500)
compareSolutions("LARGER SETS:",2000,200,500)
compareSolutions("SETTING FROM COMMENTS:",10000,200,1000)
Результаты:
-------------------
SIMPLE TEST SET 20 sets of 20 elements in range 0 ... 50
chrisHall 0.0766431910000005
top5Matches 0.07549873900000037
OPSolution 0.05089954700000021
-------------------
MORE SETS: 2000 sets of 20 elements in range 0 ... 50
chrisHall 1.274499733999999
top5Matches 1.2646208220000013
OPSolution 3.796912927000001
-------------------
FEWER INTERSECTIONS: 2000 sets of 20 elements in range 0 ... 500
chrisHall 0.4685694170000012
top5Matches 0.42844527900000173
OPSolution 3.5187148479999983
-------------------
LARGER SETS: 2000 sets of 200 elements in range 0 ... 500
chrisHall 8.538208329
top5Matches 8.51855685
OPSolution 23.192823251999997
-------------------
SETTING FROM COMMENTS: 10000 sets of 200 elements in range 0 ... 1000
chrisHall 190.55364428999997
top5Matches 176.066835327
OPSolution 829.934181724