Имеется список сайтов.
Задача:
Если в списке есть домен второго уровня, напирмер, 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)
а
Как думаете правильно оценил? И есть ли более лучший алгоритм по сложности?
["2o8.com", "1.server.2o8.com"]
? – MaxU 9 ноя '19 в 15:46