Обработка большого списка с использованием Python

Question

Так что я пытаюсь решить проблему и зашел в тупик. Мое решение работает, когда список маленький или средний, но когда он превышает 50000. Это просто «тайм-аут»

a = int(input().strip())
b = list(map(int,input().split()))


result = []
flag = []

for i in range(len(b)):
    temp = a - b[i]
    if(temp >=0 and temp in flag):
        if(temp<b[i]):
            result.append((temp,b[i]))
        else:
            result.append((b[i],temp))
        flag.remove(temp)
    else:
        flag.append(b[i])
    result.sort()


for i in result:
    print(i[0],i[1])

Где

а = 10

и b = [2, 4, 6, 8, 5]

Сумма решения любых двух элементов в b , что соответствует a

** Редактировать: ** Обновлен полный код

Answer 1

flag - список, потенциально того же порядка, что и b. Итак, когда вы делаете temp in flag, это линейный поиск: он должен проверять каждое значение в flag, чтобы увидеть, является ли это значение == temp. Итак, это 50000 сравнений. И вы делаете это один раз за цикл в линейном обходе b. Итак, ваше общее время квадратично: 50,000 * 50,000 = 2,500,000,000. (И flag.remove равно также линейное время.)

Если вы замените flag на набор, вы можете проверить его на членство (и удалить из него) в постоянное время. Таким образом, ваше общее время падает с квадратичного на линейный или 50,000 шагов, что намного быстрее, чем 2 миллиарда:

flagset = set(flag)
for i in range(len(b)):
    temp = a - b[i]
    if(temp >=0 and temp in flagset):
        if(temp<b[i]):
            result.append((temp,b[i]))
        else:
            result.append((b[i],temp))
        flagset.remove(temp)
    else:
        flagset.add(b[i])
flag = list(flagset)

Если flag необходимо сохранить повторяющиеся значения, то это мультимножество, а не набор, что означает, что вы можете реализовать с помощью Counter:

flagset = collections.Counter(flag)
for i in range(len(b)):
    temp = a - b[i]
    if(temp >=0 and flagset[temp]):
        if(temp<b[i]):
            result.append((temp,b[i]))
        else:
            result.append((b[i],temp))
        flagset[temp] -= 1
    else:
        flagset[temp] += 1
flag = list(flagset.elements())

---

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

Сортировка занимает логарифмическое время. Поскольку вы делаете это до 50000 раз, это около log(50;000) * 50,000 * 50,000, или около 30 миллиардов шагов.

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

Но вам это не нужно для того, чтобы до конца. Итак, намного проще, просто переместите result.sort из цикла и сделайте это в конце.