Оптимизация моего кода

Question

У меня есть задание на python:

(*) Необходимо из списка чисел путем вычеркивания некоторых чисел, не меняя порядка остальных, составить максимально длинный новый список чисел, образующих арифметическую прогрессию. Будем считать, что два любых числа (или одно для списка из одного элемента) всегда образуют такую прогрессию. Если можно составить несколько таких списков одинаковой максимальной длины, разрешается составить любой, например:

{ 11, 3, 2, 5, 4, 7, 7, 1, 4, 6, 9, 8, 8, 7, 1, 3, 2 } → { 3, 5, 7, 9 }

или { 2, 4, 6, 8 }

или { 5, 4, 3, 2 }

проблема в том что мой код слишком тяжелый, с тем же массивом { 11, 3, 2, 5, 4, 7, 7, 1, 4, 6, 9, 8, 8, 7, 1, 3, 2 } компьютер не выдерживает, подскажите, пожалуйста, как можно ускорить его работу, чтобы он работал нормально не только с маленькими массивами

def read_numbers_from_file(filename):
try:
    with open(filename, 'r') as file:
        numbers_str = file.read()
        numbers = [int(num) for num in numbers_str.split()]
        return numbers
except FileNotFoundError:
    print(f"Файл '{filename}' не найден.")
    return []


def solution(arr):
    max_progression = []
    arr_set = set(arr)


progressions = {}
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        progression = [arr[i], arr[j]]
        diff = arr[j] - arr[i]
        next_term = arr[j] + diff
        length = 2

        while next_term in arr_set:
            progression.append(next_term)
            next_term += diff
            length += 1

     
        if length > progressions.get(tuple(progression), 0):
            progressions[tuple(progression)] = length
            if length > len(max_progression):
                max_progression = progression

return max_progression


numbers = read_numbers_from_file('input.txt')
print("Числа из файла:", numbers)

res = solution(numbers)
print("Максимально длинная арифметическая прогрессия:", res)

Answer 1

нашел решение похожей задачи на js,переделал на python,теперь выглядит как то так

def search(a):
    # Если в последовательности всего один элемент, он и будет прогрессией
    if len(a) == 1:
        return a

    max_progression = []

    for start in range(len(a)):
        for i in range(start + 1, len(a)):
            step = a[i] - a[start]
            progression = [a[start], a[i]]

            for j in range(i + 1, len(a)):
                if a[j] - step == progression[-1]:
                    progression.append(a[j])

            if len(progression) > len(max_progression):
                max_progression = progression

    return max_progression


def read_numbers_from_file(filename):
    try:
        with open(filename, 'r') as file:
            numbers_str = file.read()
            numbers = [int(num) for num in numbers_str.split()]
            return numbers
    except FileNotFoundError:
        print(f"Файл '{filename}' не найден.")
        return []


def write_progression_to_file(filename, progression):
    with open(filename, 'w') as file:
        file.write(", ".join(map(str, progression)) + "\n")


filename = 'input.txt'
arr1 = read_numbers_from_file(filename)
res1 = search(arr1)

output_filename = 'output.txt'
write_progression_to_file(output_filename, res1)

# Вывод результата в консоль
print("Максимально длинная арифметическая прогрессия:", res1)

теперь для { 11, 3, 2, 5, 4, 7, 7, 1, 4, 6, 9, 8, 8, 7, 1, 3, 2 } выводится верный результат { 3, 5, 7, 9 }

Answer 2

Оптимизация кубического алгоритма. Я верю но не умею это доказывать что она работает за O(n²·log n). Внешний цикл перебирает первые элементы прогрессий. Внутрений цикл хранит прогрессии в словаре вида

{<следующее значение в прогрессии>: [(<длина прогрессии>, <шаг прогрессии>), ...]}.

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

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

import sys


def max_ap(a):
    n = len(a)
    if n <= 1:
        return a

    max_len = 1
    max_ap = 0, a[0]
    for i, ai in enumerate(a):
        futures = {}
        d_set = set()
        for j in range(i + 1, n):
            aj = a[j]
            for m, d in futures.pop(aj, []):
                futures.setdefault(aj + d, []).append((m + 1, d))

            d = aj - ai 
            if d not in d_set:
                d_set.add(d)
                futures.setdefault(aj + d, []).append((2, d))

        m, d = max(
            (md for aps in futures.values() for md in aps),
            default=(1, 0)
        )
        if m > max_len:
            max_len = m
            max_ap = d, ai

    d, a_next = max_ap
    ap = []
    for ai in a:
        if ai == a_next:
            ap.append(ai)
            a_next += d
    return ap


def main():
    a = tuple(int(word) for line in sys.stdin for word in line.split())
    print(*max_ap(a))


main()

БЛОГ НА HUSL

Оптимизация моего кода

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