Python: очень медленный вложенный цикл - PullRequest
Новая
       23

Python: очень медленный вложенный цикл

0 голосов
/ 18 февраля 2019

у меня ок.266680 пользователей (значение моей переменной user_num равно 266680) и карта со значением ключа индекса пользователя и списком бизнес-индексов.Например: users_businesses[0] = 1,5,7,9,11,15 означает, что пользователь с индексом 0 уже проголосовал за предприятия с индексом 1,5,7,9,11,15.Моя задача состоит в том, чтобы создать пограничный список между пользователями, которые имеют по крайней мере 5 общих рейтинговых компаний.Так, например, если: users_businesses[1] = 1,5,7,9,11,13 -> (0,1) будет преимуществом, потому что 0 и 1 пользователи имеют 5 общих рейтинговых компаний.

Я пробовал следующее: 

def Length_Elements(element_list):
    num=0
    for element in element_list:
        num=num+1
    return num

def More_Than_Five_Common_Businesses(list1, list2):
    common_elements = list(set(list1).intersection(list2))
    num = Length_Elements(common_elements)
    if(num >= 5):
        return True
    return False

tuple_list = []
for user1 in range(user_num):
    for user2 in range(user_num):
        if(More_Than_Five_Common_Businesses(users_businesses[user1],users_businesses[user2])):
            tuple_list.append((user1,user2))

Конечно, это оченьмедленный, потому что вложенный цикл повторяется 266680 * 266680 раз.Не могли бы вы дать мне лучшее решение?Буду признателен.Спасибо!

Ответы [ 3 ]

0 голосов
/ 18 февраля 2019

У меня нет лучшего алгоритма для этого, но я вижу две проблемы.

Первое: основной цикл выполняет двойную дополнительную работу.Лучший пользователь, например, такой: 

In [3]: for x in range(5):
   ...:     for y in range(1, 5-x):
   ...:         print x,y+x
   ...:         
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4

Второй: используйте язык программирования, который вы хорошо знаете. len (s) , Типы последовательностей - список, кортеж, диапазон

0 голосов
/ 18 февраля 2019

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

Таким образом, по сути вам нужно 3 цикла for:

  1. Первый цикл for - это создание списка пользователей для каждой компании.
  2. Второй цикл for - это циклическая проверка предприятий и подключение всех пользователей в этом списке бизнеса.Это можно сделать, сохранив карту кортежей для каждого пользователя, где каждый кортеж содержит идентификатор пользователя и количество соединений.
  3. Третий цикл зацикливается на пользователях, а затем для каждого цикла пользователя над кортежами.и добавьте ребро, если число больше или равно 5.

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

0 голосов
/ 18 февраля 2019

Вы можете использовать filter.

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

import numpy as np
import time
import itertools

def compare(t):
    a, b = t
    return a > b

a1 = np.random.randint(0, 100, size=2000)

start = time.time()
result = filter(compare, itertools.product(a1, a1))
print(time.time() - start) # takes 0.0s

result2 = []
start = time.time()
for i in range(a1.shape[0]):
    for j in range(a1.shape[0]):
        if a1[i] > a1[j]:
            result2.append((a1[i], a1[j]))
print(time.time() - start) # takes 5.867310285568237s

print(len(list(result))) #1979249
print(len(list(result2))) #1979249
...