Created
August 1, 2017 21:56
-
-
Save Felhamed/d815e7ab50dd325ddbc2366a166cfc75 to your computer and use it in GitHub Desktop.
Python algorithm to find year with max people alive
This file contains hidden or 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
| from collections import Counter, namedtuple | |
| from itertools import chain | |
| from bisect import insort | |
| import numpy as np | |
| import timeit | |
| # Generate random dataset of Birth,Death years | |
| def person_data(): | |
| datab=np.random.randint(1800, 2017,size=(100,1)) | |
| datad=datab+np.random.randint(0, 80,size=(100,1)) | |
| data=np.concatenate((datab,datad), axis=1) | |
| return data | |
| # First algorithm using iterative method | |
| def most_alive(people, single=True): | |
| birth = map(lambda x: x[0], people) | |
| death = map(lambda x: x[1] + 1, people) | |
| b = Counter(birth) | |
| d = Counter(death) | |
| alive = 0 | |
| years = {} | |
| for year in range(min(birth), max(death) + 1): | |
| alive = alive + b[year] - d[year] | |
| years[year] = alive | |
| return max(years, key=years.get) if single else \ | |
| [key for key, val in years.iteritems() if val == max(years.values())] | |
| # Second method using iterative tools chain | |
| def most_alive_v2(people): | |
| pop_func = chain.from_iterable(xrange(i, j+1) for i, j in people) | |
| return Counter(pop_func).most_common() | |
| # Test methods for checking speed | |
| def test_most_alive(): | |
| most_alive(person_data(), False) | |
| def test_most_alive_v2(): | |
| most_alive_v2(person_data()) | |
| if __name__ == '__main__': | |
| print most_alive(person_data(), False) | |
| print most_alive_v2(person_data())[0:1] | |
| print 'First Method test time: ' +\ | |
| str(timeit.timeit(stmt="test_most_alive()", | |
| setup="from __main__ import test_most_alive", | |
| number=10000)) | |
| print 'Second Method test time: ' +\ | |
| str(timeit.timeit(stmt="test_most_alive_v2()", | |
| setup="from __main__ import test_most_alive_v2", | |
| number=10000)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment