-
-
Notifications
You must be signed in to change notification settings - Fork 44
/
test_complexity.py
108 lines (94 loc) · 3.19 KB
/
test_complexity.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
import io
import itertools
import math
import re
import string
import unittest
import zipfile
import zipp
from jaraco.functools import compose
from more_itertools import consume
from ._support import import_or_skip
big_o = import_or_skip('big_o')
pytest = import_or_skip('pytest')
class TestComplexity(unittest.TestCase):
@pytest.mark.flaky
def test_implied_dirs_performance(self):
best, others = big_o.big_o(
compose(consume, zipp.CompleteDirs._implied_dirs),
lambda size: [
'/'.join(string.ascii_lowercase + str(n)) for n in range(size)
],
max_n=1000,
min_n=1,
)
assert best <= big_o.complexities.Linear
def make_zip_path(self, depth=1, width=1) -> zipp.Path:
"""
Construct a Path with width files at every level of depth.
"""
zf = zipfile.ZipFile(io.BytesIO(), mode='w')
pairs = itertools.product(self.make_deep_paths(depth), self.make_names(width))
for path, name in pairs:
zf.writestr(f"{path}{name}.txt", b'')
zf.filename = "big un.zip"
return zipp.Path(zf)
@classmethod
def make_names(cls, width, letters=string.ascii_lowercase):
"""
>>> list(TestComplexity.make_names(1))
['a']
>>> list(TestComplexity.make_names(2))
['a', 'b']
>>> list(TestComplexity.make_names(30))
['aa', 'ab', ..., 'bd']
>>> list(TestComplexity.make_names(17124))
['aaa', 'aab', ..., 'zip']
"""
# determine how many products are needed to produce width
n_products = max(1, math.ceil(math.log(width, len(letters))))
inputs = (letters,) * n_products
combinations = itertools.product(*inputs)
names = map(''.join, combinations)
return itertools.islice(names, width)
@classmethod
def make_deep_paths(cls, depth):
return map(cls.make_deep_path, range(depth))
@classmethod
def make_deep_path(cls, depth):
return ''.join(('d/',) * depth)
def test_baseline_regex_complexity(self):
best, others = big_o.big_o(
lambda path: re.fullmatch(r'[^/]*\\.txt', path),
self.make_deep_path,
max_n=100,
min_n=1,
)
assert best <= big_o.complexities.Constant
@pytest.mark.flaky
def test_glob_depth(self):
best, others = big_o.big_o(
lambda path: consume(path.glob('*.txt')),
self.make_zip_path,
max_n=100,
min_n=1,
)
assert best <= big_o.complexities.Linear
@pytest.mark.flaky
def test_glob_width(self):
best, others = big_o.big_o(
lambda path: consume(path.glob('*.txt')),
lambda size: self.make_zip_path(width=size),
max_n=100,
min_n=1,
)
assert best <= big_o.complexities.Linear
@pytest.mark.flaky
def test_glob_width_and_depth(self):
best, others = big_o.big_o(
lambda path: consume(path.glob('*.txt')),
lambda size: self.make_zip_path(depth=size, width=size),
max_n=10,
min_n=1,
)
assert best <= big_o.complexities.Linear