1

Имеется список сайтов.

Задача:

Если в списке есть домен второго уровня, напирмер, 2o7.net, то поддомены 012.2o7.net, www.2o7.net, blog.test.2o7.net и test.2o7.net должны быть из него вообще удалены.

Если в списке есть домен третьего уровня, напирмер server.2o8.com, то поддомены 1.server.2o8.com, 2.server.2o8.com, 3.server.2o8.com, test.1.server.2o8.com и 4.server.2o8.com должны быть из него вообще удалены.

И так далее по возрастающей и незаисимо от количества поддоменов в строке.

Как я решал: Сначала я отсортировал по возрастанию по количество доменов, с помощью sorted(). Не знаю какая у него сложность, так на Python не пишу, и не знаю, на основе какого алгоритма сортировки она построена, но в любом случае, сортировку можно достичь со сложность O(N * log N)

Затем обрабатывает каждый элемент отсортированного списка. Если количество доменов равен 2, то добавляем его в cache (для дальнейшего сравнения), а также выводим в файл success.

Иначе в цикле, состоящих из возможных вариантов доменов, начиная от 2, проверял его на наличие в cache, если он там присутствует, то на удаление. Если пройдя цикл, элемент не был удален, то добавляем его в cache и выводим в success.

Вот с этой этой части у меня проблема.

N - проход по всем элементам

K = количеству доменов - 2

В этом случае сложность этой части O(N * K)

И суммарная: N * Log N + N * K. Как вот эту часть оценить? Думаю N * Log N > N * K, так как количество доменов не такое большое, а количество элементов может быть больше.

Следовательно общая сложность будет равна O (N * log N)

Код:

import time
input_filename = "hosts.txt"
input_filename_test = "hosts_test.txt"
output_filename_success = "success.txt"
output_filename_delete = "delete.txt"

cache = {}



def load_file(input_filename):
    items = []
    start_time = time.time()
    print("Чтение файла")
    with open(input_filename, "r") as file:
        content = file.read().split("\n")
        for cont in content:
            if(cont.strip() != ""):
                items.append(cont)
    print("Чтение завершено. Время выполнения", time.time() - start_time, "c")
    return items

def sorted_list(items):
    start_time = time.time()
    print("Сортировка")
    sorted_item = sorted(items, key=lambda x: len(x.split(".")))
    print("Сортировка завершена. Время выполнения", time.time() - start_time, "c")
    return sorted_item

def get_cache(item):
    try:
        current_item = cache[item]
        return True
    except Exception as e:
        print(item, "не найден в cache")
        return False

def get_join(items):
    return '.'.join(items)

def processing_all(items):
    print("Обработка списка")
    start_time = time.time()
    for item in items:
        processing(item)
    print("Обработка завершена. Время выполнения", time.time() - start_time, "c")


def processing(item):
    print("Обработка ", item)

    blocks = item.split(".")
    if(len(blocks) == 2):
        save(item, output_filename_success)
        cache[item] = item
    else:
        #Проход по возможным вариациям
        for index in range(len(blocks) - 1).__reversed__():
            print(get_join(blocks[index:]))
            if(get_cache(get_join(blocks[index:]))):
                #Удаляем
                save(item, output_filename_delete)
                print(item, "Удален")
                return
            else:
                continue

        #Если не удалили, значит добавляем в cache
        save(item, output_filename_success)
        cache[item] = item


def save(item, filename):
    with open(filename, "a") as file:
        file.write(item + "\n")

if __name__ == '__main__':
    start_time = time.time()
    items = load_file(input_filename)
    items = sorted_list(items)
    processing_all(items)
а

Как думаете правильно оценил? И есть ли более лучший алгоритм по сложности?

2
  • Какой должен быть выходной список если на входе такой список: ["2o8.com", "1.server.2o8.com"] ? 9 ноя 2019 в 15:46
  • @MaxU 2o8.com в success и 1.server.2o8.com в delete
    – danilshik
    9 ноя 2019 в 15:55

1 ответ 1

1

Попробуйте так:

def is_subdomain(url, known_domains):
    tup = tuple(url.split("."))
    for i in range(len(tup)-1):
        if tup[i:] in known_domains:
            return True
    return False

items = [
  "2o7.net", "012.2o7.net", "www.2o7.net", "blog.test.2o7.net", "test.2o7.net",
  "server.2o8.com", "1.server.2o8.com", "2.server.2o8.com", "3.server.2o8.com", 
  "test.1.server.2o8.com", "4.server.2o8.com",
  "aaa.bbb.com", "user.blog.test.aaa.bbb.com"
]

seen = set()
selected = []
deleted = []

for x in sorted(items, key=lambda x: x.count(".")):
    if not is_subdomain(x, seen):
        selected.append(x)
    else:
        deleted.append(x)
    seen.add(tuple(x.split(".")))

Сложность: max(O(n * log(n)), O(n * m)), где m - максимальное число слов в URL минус 2. Т.е. если максимальное число слов в хостах - 6 (пример: user.blog.test.aaa.bbb.com), то сложность будет max(O(n * log(n)), O(n * 4)).

Таким образом если log(n) > m, то сложность будет O(n * log(n)), в противном случае: O(n * m)

PS не уверен что правильно посчитал сложность алгоритма...


результат:

In [55]: selected
Out[55]: ['2o7.net', 'server.2o8.com', 'aaa.bbb.com']

In [56]: deleted
Out[56]:
['012.2o7.net',
 'www.2o7.net',
 'test.2o7.net',
 'blog.test.2o7.net',
 '1.server.2o8.com',
 '2.server.2o8.com',
 '3.server.2o8.com',
 '4.server.2o8.com',
 'test.1.server.2o8.com',
 'user.blog.test.aaa.bbb.com']

In [57]: seen
Out[57]:
{('012', '2o7', 'net'),
 ('1', 'server', '2o8', 'com'),
 ('2', 'server', '2o8', 'com'),
 ('2o7', 'net'),
 ('3', 'server', '2o8', 'com'),
 ('4', 'server', '2o8', 'com'),
 ('aaa', 'bbb', 'com'),
 ('blog', 'test', '2o7', 'net'),
 ('server', '2o8', 'com'),
 ('test', '1', 'server', '2o8', 'com'),
 ('test', '2o7', 'net'),
 ('user', 'blog', 'test', 'aaa', 'bbb', 'com'),
 ('www', '2o7', 'net')}
6
  • компактно, но сложность же у него такая же, но какая?
    – danilshik
    9 ноя 2019 в 16:45
  • @danilshik, дополнил ответ. PS лучше всего сравнить время выполнения разных версий - скорость будет зависеть не только от сложности алгоритма, но и от реализации тоже) 9 ноя 2019 в 17:04
  • а если сделать словарь ? или в питоне не работает, как в php, что обращение по индексу линейно в отличие от поиска в списке?
    – splash58
    9 ноя 2019 в 18:08
  • @splash58, я для этого использовал set - сложность поиска по set - O(1) 9 ноя 2019 в 18:11
  • вот это я не знал, спс
    – splash58
    9 ноя 2019 в 18:14

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.