алгоритмы и анализ времени выполнения

Question

Файл (входит в два примера) представляет собой список запрещенных интервалов номеров. Строка, которая содержит, например, 12-18, указывает, что все цифры от 12 до (включительно) 18 запрещены. Интервалы могут перекрываться. Мы хотим знать, какое минимальное количество. Используйте переменные для анализа времени выполнения (не обязательно все они нужны):

• N: максимальное (не максимально допустимое) число; Таким образом, числа находятся в диапазоне от 0 до N

• K: количество интервалов в файле

• M: ширина максимального интервала.

A. Существует очевидный способ решения этой проблемы: мы проверяем все числа, пока не столкнемся с наименьшим допустимым. • Насколько быстрым является такой алгоритм?

B. Вероятно, вы можете представить другой простой алгоритм, который использует N байтов (или битов) памяти. (Подсказка: зачеркнутый.) • Опишите это словами. Например, вы можете сделать свое собственное назначение (скажем, несколько интервалов с номерами от 0 до 20) и показать алгоритм на них. Тем не менее, он также составляет общее описание. • Насколько быстр этот алгоритм? Размышляя, используйте N, K и M (если вам это нужно).

C. Создайте алгоритм, который не потребляет дополнительную память (точнее: потребление памяти должно быть независимым от N, K и M), но он быстрее, чем алгоритм в пункте A. • Опишите это. • Как быстро это? Это быстрее, чем алгоритм B?

D. Теперь нас интересует, сколько чисел разрешено (от 0 до N). Как бы вы скорректировали приведенные выше алгоритмы для этого вопроса? Что происходит с их ставками?

file = "0-19.txt"
intervals = [tuple(map(int, v.split("-"))) for v in open(file)]
#example# intervals = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]#

мой текущий код просто выполняет программу, но лучшие алгоритмы для кода, который я пока не определил, все еще требуют большой работы, чтобы понять, мне нужен быстрый код / ​​алгоритм решения для примеров A, B и C и, возможно, D. Тогда я могу самостоятельно изучить анализ времени. Ценю помощь!

def generator_intervala(start, stop, step):
    forbidden_numbers = set()
    while start <= stop:
        forbidden_numbers.add(start)
        start += step
    return (forbidden_numbers)


mnozica = set()
for interval in intervals:
    a, b = interval
    values = (generator_intervala(a, b, 1))
    for i in values:
        mnozica.add(i)



allowed_numbers = set()
N = max(mnozica)
for i in range(N):
    if i not in mnozica:
        allowed_numbers.add(i)




print(intervals)
print(mnozica)
print(min(allowed_numbers))
print(max(mnozica))

Output:

[(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14, 15, 16, 17, 18, 19}
10
19

Answer 1

Ваш комплексный подход неоправданно сложен:

N = 100
ranges = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]

do_not_use = set()

for (a,b) in ranges: 
    do_not_use.update(range(a,b+1))          

print(do_not_use)  

print( min(a for a in range(N+1) if a not in do_not_use))

Это все, что нужно. Выход:

set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14, 15, 16, 17, 18, 19])
10

Это не зависит от N, зависит только от количества чисел в диапазонах.

Хранение только запрещенных чисел в наборе требует O (1) для проверки с использованием встроенной функции min() в диапазоне, чтобы получить минимум.

Вы можете сделать это быстрее, если вы сначала отсортируете свои кортежи, а затем итерируете их, пока не найдете первый пробел, делающий его Θ (N log N) для сортировки, а затем Θ (N) для поиска:

def findme():
    ranges = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
    ranges.sort()  # inplace sort, no additional space requirements
    if ranges[0][0]>0: 
        return 0

    for ((a_min,a_max),(b_min,b_max)) in zip(ranges,ranges[1:]):
        if a_max < b_min-1:
            return a_max+1

    return ranges[-1][1]+1  # might give you N+1 if no solution in 0-N exists

---

timeit ваш против моего:

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

N = 100

def findme():
    ranges = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
    ranges.sort()
    if ranges[0][0]>0: 
        return 0

    for ((a_min,a_max),(b_min,b_max)) in zip(ranges,ranges[1:]):
        if a_max < b_min-1:
            return a_max+1

    return ranges[-1][1]+1

def mine():
    ranges = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
    N = 100
    do_not_use = set()

    for (a,b) in ranges: 
        do_not_use.update(range(a,b+1))          

    return min(a for a in range(N+1) if a not in do_not_use)

def yours():
    ranges = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
    def generator_intervala(start, stop, step):
        forbidden_numbers = set()
        while start <= stop:
            forbidden_numbers.add(start)
            start += step
        return (forbidden_numbers)

    mnozica = set()
    for interval in ranges:
        a, b = interval
        values = (generator_intervala(a, b, 1))
        for i in values:
            mnozica.add(i)

    allowed_numbers = set()
    N = max(mnozica)
    for i in range(N):
        if i not in mnozica:
            allowed_numbers.add(i)

    return min(allowed_numbers)

import timeit
print("yours", timeit.timeit(yours,number=100000))  
print("mine", timeit.timeit(mine,number=100000))
print("findme", timeit.timeit(findme,number=100000))

Выход:

yours 1.3931225209998956
mine 1.263602267999886
findme 0.1711935210005322