Improved the _prefix() method of t, and added a test utility to confirm the new method works and runs faster - the same code on Python 3.1 runs much faster.
https://bitbucket.org/dimo414/t-3.1/
author |
Michael Diamond@Artemis <dimo414@gmail.com> |
date |
Sat, 12 Jun 2010 15:47:19 -0700 |
parents |
(none) |
children |
(none) |
These are the cProfile results of running the original prefix function
against the new prefix function. The original function ran in ~O(n^2)
time, the new one runs in ~O(n) time.
You can also run prefixcheck.check_prefixes() to confirm there is no
regression from original to new.
It is worth noting that
-----
Size: 1
t_prefixes()
8 function calls in 0.000 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 prefixcheck.py:14(t_prefixes)
1 0.000 0.000 0.000 0.000 {any}
1 0.000 0.000 0.000 0.000 {len}
1 0.000 0.000 0.000 0.000 {map}
1 0.000 0.000 0.000 0.000 {method 'difference' of 'set' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 0.000 0.000 {range}
new_prefixes()
8 function calls in 0.000 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 prefixcheck.py:38(new_prefixes)
1 0.000 0.000 0.000 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 0.000 0.000 {method 'keys' of 'dict' objects}
1 0.000 0.000 0.000 0.000 {method 'values' of 'dict' objects}
1 0.000 0.000 0.000 0.000 {range}
1 0.000 0.000 0.000 0.000 {zip}
-----
Size: 10
t_prefixes()
2973 function calls in 0.009 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.009 0.009 <string>:1(<module>)
1 0.001 0.001 0.009 0.009 prefixcheck.py:14(t_prefixes)
1323 0.004 0.000 0.006 0.000 prefixcheck.py:29(<lambda>)
147 0.000 0.000 0.000 0.000 {any}
10 0.000 0.000 0.000 0.000 {len}
147 0.002 0.000 0.008 0.000 {map}
10 0.000 0.000 0.000 0.000 {method 'difference' of 'set' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1323 0.002 0.000 0.002 0.000 {method 'startswith' of 'str' objects}
10 0.000 0.000 0.000 0.000 {range}
new_prefixes()
30 function calls in 0.000 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 prefixcheck.py:38(new_prefixes)
10 0.000 0.000 0.000 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 0.000 0.000 {method 'keys' of 'dict' objects}
1 0.000 0.000 0.000 0.000 {method 'values' of 'dict' objects}
14 0.000 0.000 0.000 0.000 {range}
1 0.000 0.000 0.000 0.000 {zip}
-----
Size: 100
t_prefixes()
265303 function calls in 0.831 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.831 0.831 <string>:1(<module>)
1 0.009 0.009 0.830 0.830 prefixcheck.py:14(t_prefixes)
131175 0.397 0.000 0.597 0.000 prefixcheck.py:29(<lambda>)
1325 0.003 0.000 0.003 0.000 {any}
100 0.000 0.000 0.000 0.000 {len}
1325 0.221 0.000 0.817 0.001 {map}
100 0.001 0.000 0.001 0.000 {method 'difference' of 'set' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
131175 0.200 0.000 0.200 0.000 {method 'startswith' of 'str' objects}
100 0.000 0.000 0.000 0.000 {range}
new_prefixes()
257 function calls in 0.002 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.002 0.002 <string>:1(<module>)
1 0.001 0.001 0.002 0.002 prefixcheck.py:38(new_prefixes)
100 0.000 0.000 0.000 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 0.000 0.000 {method 'keys' of 'dict' objects}
1 0.000 0.000 0.000 0.000 {method 'values' of 'dict' objects}
151 0.000 0.000 0.000 0.000 {range}
1 0.000 0.000 0.000 0.000 {zip}
-----
Size: 1000
t_prefixes()
25827686 function calls in 79.873 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 79.873 79.873 <string>:1(<module>)
1 0.248 0.248 79.873 79.873 prefixcheck.py:14(t_prefixes)
12899060 38.676 0.000 58.231 0.000 prefixcheck.py:29(<lambda>)
13298 0.073 0.000 0.073 0.000 {any}
989 0.002 0.000 0.002 0.000 {len}
13298 21.266 0.002 79.497 0.006 {map}
989 0.050 0.000 0.050 0.000 {method 'difference' of 'set' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
12899060 19.555 0.000 19.555 0.000 {method 'startswith' of 'str' objects}
989 0.003 0.000 0.003 0.000 {range}
new_prefixes()
2534 function calls in 0.019 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.019 0.019 <string>:1(<module>)
1 0.011 0.011 0.019 0.019 prefixcheck.py:38(new_prefixes)
989 0.001 0.000 0.001 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 0.000 0.000 {method 'keys' of 'dict' objects}
1 0.000 0.000 0.000 0.000 {method 'values' of 'dict' objects}
1539 0.003 0.000 0.003 0.000 {range}
1 0.003 0.003 0.003 0.003 {zip}
-----
Size: 10000
Too big to run t_prefixes() efficiently. Would take several minutes.
new_prefixes()
25448 function calls in 0.212 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.001 0.001 0.212 0.212 <string>:1(<module>)
1 0.125 0.125 0.210 0.210 prefixcheck.py:38(new_prefixes)
9957 0.014 0.000 0.014 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.003 0.003 0.003 0.003 {method 'keys' of 'dict' objects}
1 0.001 0.001 0.001 0.001 {method 'values' of 'dict' objects}
15485 0.029 0.000 0.029 0.000 {range}
1 0.037 0.037 0.037 0.037 {zip}
-----
Size: 100000
Too big to run t_prefixes() efficiently. Would take several minutes.
new_prefixes()
253838 function calls in 3.780 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.021 0.021 3.780 3.780 <string>:1(<module>)
1 1.490 1.490 3.759 3.759 prefixcheck.py:38(new_prefixes)
99615 0.139 0.000 0.139 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.041 0.041 0.041 0.041 {method 'keys' of 'dict' objects}
1 0.016 0.016 0.016 0.016 {method 'values' of 'dict' objects}
154217 0.274 0.000 0.274 0.000 {range}
1 1.798 1.798 1.798 1.798 {zip}
-----
Size: 1000000
Too big to run t_prefixes() efficiently. Would take several minutes.
new_prefixes()
2530533 function calls in 151.824 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.256 0.256 151.824 151.824 <string>:1(<module>)
1 16.424 16.424 151.569 151.569 prefixcheck.py:38(new_prefixes)
996118 1.388 0.000 1.388 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.397 0.397 0.397 0.397 {method 'keys' of 'dict' objects}
1 0.159 0.159 0.159 0.159 {method 'values' of 'dict' objects}
1534409 2.731 0.000 2.731 0.000 {range}
1 130.471 130.471 130.471 130.471 {zip}