Время работы программы очень длинное, возможна ли реализация з помощью хэш-таблиц?

Question

Для программы используется список на 1млн чисел, нужно при складывании чисел x и y, то-есть A[i] и A[j] получить число s, которое лежит в диапазоне от -1000 до 1000, и найти количество уникальных чисел. Программа работает правильно, но проблема в длительности выполнения програми, которое достигает нескольки часов, возможно ли реализовать с помощью хэш-таблиц, чтобы сократить время работы? Вот код

A = []
with open("input.txt") as f:
    for line in f:
        A.append(int(line))
n=len(A)
checker = []
s = A[0]+A[1]
checker.append(s)
print('Start')
for i in range(0, n-1):
    for j in range(1, n):
        if A[i]+A[j]>=-1000 and A[i]+A[j]<=1000:
            s = A[i]+A[j]
            if s not in checker:
                checker.append(s)
                print(checker)
del checker[0]
print('res:', len(checker))
print(checker)
print('End')

Answer 1

Программа работает правильно

правильно не значит оптимально :)

        if s not in checker:
            checker.append(s)

начнем с того, что раз вы каждый раз делаете поиск в checker, то он не должен быть списком, в котором поиск занимает O(n), делайте его сразу множеством, в котором поиск занимает O(log(n)) и не парьтесь с поиском - сразу добавляйте элемент в множество, а выведите элементы потом

checker = set()
...
checher.add(s)

далее, чем меньше условий - тем лучше

вместо

if A[i]+A[j]>=-1000 and A[i]+A[j]<=1000:

можно сделать

if (A[i] + A[j]) * (A[i] + A[j]) <= 1000000

если предварительно отсортировать список, то можно еще быстрее сделать

В общем надо просто полностью переписать код :)

Answer 2

вот такой код:

100.000 записей где-то за 7 секунд перемалывает, 1000.000 за 2,5 минуты, но оптимизировать еще можно и наверное еще на порядок можно ускорить легко

его конечно надо допилить, но основные принципы более-менее тут раскрыты

исходный список сортируем по возрастанию
для каждого элемента списка определяем диапазон left..right сумма с числом из которого будет меньше 1000
поскольку список отсортирован, то бинарным поиском определяем индекс начиная с которого все числа больше left и индекс начиная с которого все числа меньше right
дальше (в идеале) нам надо просто занести в множество все числа по индексам i_left..i_right

я код писал на коленке, так что бинарный поиск немного недоработан :) но есть куда расти - главное - ПРИНЦИП

код:

import random

count = 1000000

arr = [random.randint(-1000000, 1000000) for i in range(count)]

print("start")

arr.sort()

res = set()

for i in range(len(arr)):

    # определить границы диапазона
    left = -1000 - arr[i]
    right = 1000 - arr[i]

    # бинарным поиском найти граничные элементы
    border_l = 0
    border_r = len(arr) - 1

    pos_l = (border_r + border_l) // 2
    old = -1

    while True:
        value = arr[pos_l]

        if value < left:
            border_l = pos_l
        elif value > left:
            border_r = pos_l

        old = pos_l
        pos_l = (border_r + border_l) // 2

        if pos_l == old:
            break

    border_l = 0
    border_r = len(arr) - 1

    pos_r = (border_r + border_l) // 2
    old = -1

    while True:
        value = arr[pos_r]

        if value < left:
            border_r = pos_r
        elif value > left:
            border_l = pos_r

        old = pos_r
        pos_r = (border_r + border_l) // 2

        if pos_r == old:
            break


    for j in range(pos_l, pos_r + 1):

        value = arr[j]

        if value < left:
            continue

        if value > right:
            break

        res.add(arr[i] + arr[j])

print(len(res))

БЛОГ НА HUSL

Время работы программы очень длинное, возможна ли реализация з помощью хэш-таблиц?

Ответы (2 шт):