Created
April 5, 2013 02:03
-
-
Save mshuffett/5316046 to your computer and use it in GitHub Desktop.
Python timeit app for different methods of flattening a shallow list. list.extend is fastest across board. https://www.dropbox.com/s/lb7yojmcckndojm/flatten_graph.png
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python2.6 | |
#http://stackoverflow.com/questions/406121/flattening-a-shallow-list-in-python/408281#408281 | |
"""Usage: %prog item_count""" | |
from __future__ import print_function | |
import collections | |
import itertools | |
import operator | |
from timeit import Timer | |
import sys | |
import matplotlib.pyplot as pyplot | |
def itertools_flatten(iter_lst): | |
return list(itertools.chain(*iter_lst)) | |
def itertools_iterable_flatten(iter_iter): | |
return list(itertools.chain.from_iterable(iter_iter)) | |
def reduce_flatten(iter_lst): | |
return reduce(operator.add, map(list, iter_lst)) | |
def reduce_lambda_flatten(iter_lst): | |
return reduce(operator.add, map(lambda x: list(x), [i for i in iter_lst])) | |
def comprehension_flatten(iter_lst): | |
return list(item for iter_ in iter_lst for item in iter_) | |
def iadd_flatten(aList): | |
return reduce(operator.iadd, aList, []) | |
def list_iadd_flatten(aList): | |
return reduce(list.__iadd__, aList, []) | |
def list_comprehension_flatten( aList ): | |
return [y for x in aList for y in x] | |
def extend_flatten(aList): | |
result = [] | |
extend = result.extend | |
for sub in aList: | |
extend(sub) | |
return result | |
METHODS = ['itertools', 'itertools_iterable', | |
'comprehension', 'iadd', 'list_iadd', 'list_comprehension', 'extend'] | |
def _time_test_assert(iter_lst): | |
"""Make sure all methods produce an equivalent value. | |
:raise AssertionError: On any non-equivalent value.""" | |
callables = (globals()[method + '_flatten'] for method in METHODS) | |
results = [callable(iter_lst) for callable in callables] | |
if not all(result == results[0] for result in results[1:]): | |
raise AssertionError | |
def time_test(partition_count, item_count_per_partition, test_count=10000): | |
"""Run flatten methods on a list of :param:`partition_count` iterables. | |
Normalize results over :param:`test_count` runs. | |
:return: Mapping from method to (normalized) microseconds per pass. | |
""" | |
iter_lst = [[dict()] * item_count_per_partition] * partition_count | |
print('Partition count: ', partition_count) | |
print('Items per partition:', item_count_per_partition) | |
_time_test_assert(iter_lst) | |
test_str = 'flatten(%r)' % iter_lst | |
result_by_method = {} | |
for method in METHODS: | |
setup_str = 'from %s import %s_flatten as flatten' % (__name__, method) | |
t = Timer(test_str, setup_str) | |
per_pass = test_count * t.timeit(number=test_count) / test_count | |
print('%20s: %.2f usec/pass' % (method, per_pass)) | |
result_by_method[method] = per_pass | |
return result_by_method | |
if __name__ == '__main__': | |
if len(sys.argv) != 2: | |
raise ValueError('Need a number of items to flatten') | |
item_count = int(sys.argv[1]) | |
partition_counts = [] | |
pass_times_by_method = collections.defaultdict(list) | |
for partition_count in xrange(1, item_count): | |
if item_count % partition_count != 0: | |
continue | |
items_per_partition = item_count / partition_count | |
result_by_method = time_test(partition_count, items_per_partition) | |
partition_counts.append(partition_count) | |
for method, result in result_by_method.iteritems(): | |
pass_times_by_method[method].append(result) | |
for method, pass_times in pass_times_by_method.iteritems(): | |
pyplot.plot(partition_counts, pass_times, label=method) | |
pyplot.legend() | |
pyplot.title('Flattening Comparison for %d Items' % item_count) | |
pyplot.xlabel('Number of Partitions') | |
pyplot.ylabel('Microseconds') | |
pyplot.savefig('p%d.png' % item_count) | |
pyplot.show() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment