我们能在这里减少时间复杂度吗？
我们能在这里减少时间复杂度吗？
提问于 2022-12-04 12:51:47
我遇到了一个AoC问题，在这里我得到了以下数据：
data = """2-4,6-8
2-3,4-5
5-7,7-9
2-8,3-7
6-6,4-6
2-6,4-8"""我需要找到完全包含另一对的对的数目。例如，2-8完全包含3-7，而6-6完全包含在4-6中。
我使用以下代码解决了这个问题：
def aoc_part1(self, data):
counter = 0
for lines_data in data.splitlines():
lines_data = lines_data.strip()
first_range, second_range = self.__get_first_second_list_of_elements(lines_data)
check_first_side_if_returns_true = all(item in first_range for item in second_range)
check_second_side_if_returns_true = all(item in second_range for item in first_range)
if check_first_side_if_returns_true or check_second_side_if_returns_true:
counter += 1
return counter
def __get_first_second_list_of_elements(self, data):
first_elf, second_elf = data.split(",")[0], data.split(",")[1]
first_range_start, first_range_end = map(int, first_elf.split("-"))
second_range_start, second_range_end = map(int, second_elf.split("-"))
first_range = list(range(first_range_start, first_range_end + 1))
second_range = list(range(second_range_start, second_range_end + 1))
return first_range, second_range我只是想知道这里时间的复杂性。我认为这里应该是一个brute force，因为每次迭代，all都会运行另一个循环。如何优化这个解以获得线性时间复杂度？
first_range和second_range属于int类型。check_first_side_if_returns_true和check_second_side_if_returns_true是检查列表是否完全包含的boolean变量。基于此，它返回True或False。
回答 2
Stack Overflow用户
发布于 2022-12-04 19:00:14
你的解决方案看起来很复杂。为什么不做这样的事情：
data = """2-4,6-8
2-3,4-5
5-7,7-9
2-8,3-7
6-6,4-6
2-6,4-8
"""
def included(line):
(a1, b1), (a2, b2) = (map(int, pair.split("-")) for pair in line.strip().split(","))
return (a1 <= a2 and b2 <= b1) or (a2 <= a1 and b1 <= b2)
print(sum(included(line) for line in data.splitlines()))我在AoC上做了一些计时--第4天的输入(1000行)：
from timeit import timeit
# Extract the interval boundaries for the pairs
boundaries = [
[tuple(map(int, pair.split("-"))) for pair in line.strip().split(",")]
for line in data.splitlines()
]
# Version 1 with simple comparison of boundaries
def test1(boundaries):
def included(pairs):
(a1, b1), (a2, b2) = pairs
return (a1 <= a2 and b2 <= b1) or (a2 <= a1 and b1 <= b2)
return sum(included(pairs) for pairs in boundaries)
# Version 2 with range-subset test
def test2(boundaries):
def included(pairs):
(a1, b1), (a2, b2) = pairs
numbers1, numbers2 = set(range(a1, b1 + 1)), set(range(a2, b2 + 1))
return numbers1 <= numbers2 or numbers2 <= numbers1
return sum(included(pairs) for pairs in boundaries)
# Test for identical result
print(test1(boundaries) == test2(boundaries))
# Timing
for i in 1, 2:
t = timeit(f"test{i}(boundaries)", globals=globals(), number=1_000)
print(f"Duration version {i}: {t:.1f} seconds")结果在平庸机器(repl.it)上：
Duration version 1: 0.4 seconds
Duration version 2: 5.4 secondsStack Overflow用户
发布于 2022-12-04 18:51:53
你真是个无赖。使它在当前的方法中变得过于复杂。如果你把这对分成两组--例如。然后你就可以轻松地做一个集合操作了。检查是否存在重叠。那应该比你的快。
就像这一行：
# some input reading, and split to a, b sets.
# count = 0
if set(range(a, b + 1)) & set(range(x, y + 1)):
count += 1 # that's part1 answer.# part 2
for line in open('04.in'):
a, b, x, y = map(int, line.replace(",", "-").split("-"))
if set(range(a, b + 1)) & set(range(x, y + 1)):
ans += 1前面有关于这种方法的内存效率的问题，我已经运行了一些分析，这是要共享的结果--考虑到这个谜题的输入大小，应该没有问题。
Filename: day04.py
Line # Mem usage Increment Occurrences Line Contents
=============================================================
27 43.758 MiB 43.758 MiB 1 @profile
28 def part2(file):
29 43.762 MiB 0.004 MiB 1 ans = 0
30
31 43.770 MiB 0.000 MiB 1001 for line in open(file):
32 43.770 MiB 0.004 MiB 1000 a, b, x, y = map(int, line.replace(",", "-").split("-"))
33 43.770 MiB 0.000 MiB 1000 if set(range(a, b + 1)) & set(range(x, y + 1)):
34 43.770 MiB 0.004 MiB 847 ans += 1
35
36 43.770 MiB 0.000 MiB 1 return ans页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/74675785
复制相关文章
相似问题
腾讯云开发者
