Суммарные значения словаря Python (сложность времени / пространства)

Question

Я пытаюсь решить следующую проблему:

Учитывая список дат рождения и дат смерти, найдите год, в котором большинство людей были живы.

Вот мой код:

b = [1791, 1796, 1691, 1907, 1999, 2001, 1907] # birth dates
d = [1800, 1803, 1692, 1907, 1852, 1980, 2006] # death dates

year_dict = {} # populates dict key as year, val as total living/dead
for birth in b:
    year_dict.setdefault(birth,0) # sets default value of key to 0 
    year_dict[birth] += 1 # will add +1 for each birth and sums duplicates
for death in d:
    year_dict.setdefault(death,0) # sets default value of key to 0
    year_dict[death] += -1 # will add -1 for each death and sums duplicates

Возвращает следующий код:

{1791: 1, 1796: 1, 1691: 1, 1907: 1, 1999: 1, 2001: 1, 1800: -1, 1803: -1, 1692: -1, 1852: -1, 1980: -1, 2006: -1}

Сейчас я ищу способ создать промежуточную сумму, чтобы определить, в каком году проживает больше всего людей, например:

Изображение желаемого результата

Как мы видим, результат показывает, что в 1796 году большинство людей было живым на основе данных наборов данных. У меня возникли проблемы с получением части текущей суммы, которая должна была бы принимать каждое значение ключа и суммировать его с предыдущим значением. Я пробовал несколько разных циклов и перечислений, но сейчас застрял. Как только я найду лучший способ решения этой проблемы, я создам функцию для повышения эффективности.

Если есть более эффективный способ сделать это с учетом сложности времени / пространства, пожалуйста, дайте мне знать. Я пытаюсь научиться эффективности с Python. Я очень ценю вашу помощь!!!

Answer 1

Я бы использовал pandas и использовал бы его DataFrame объект:

Создайте план данных года рождения и года смерти людей: *

born = [1791, 1796, 1691, 1907, 1999, 2001, 1907] # birth dates
died = [1800, 1803, 1692, 1907, 1852, 1980, 2006] # death dates
people = pd.DataFrame({'born': born, 'died': died} for born, died in zip(born, died))

Создайте план данных, включающий все годы между первым указанным рождением и последним указанным смертью:

years = pd.DataFrame(index=np.arange(people['born'].min(), people['died'].max() + 1))

Найдите общее количество людей, живущих за каждый из этих лет:

for year in years.index:
    num_living = ((year > people['born']) & (year < people['died'])).sum()
    years.loc[year, 'total_living'] = num_living

Вызов years.tail() дает следующее:

    total_living
2002    1.0
2003    1.0
2004    1.0
2005    1.0
2006    0.0

Оттуда вы можете просто сделать argmax в столбце 'total_living'.

Для ясности, я предположил логическую ситуацию, когда люди умирают после их рождения и (следовательно), что никогда не бывает отрицательного числа живых людей.

Answer 2

Есть ли конкретная структура данных, в которой вы хотите разместить результат? Я получил тот же результат, что и ссылка imgur для печати на терминал. Хотя записать его в словарь не составит труда.

from collections import OrderedDict

b = [1791, 1796, 1691, 1907, 1999, 2001, 1907] # birth dates
d = [1800, 1803, 1692, 1907, 1852, 1980, 2006] # death dates

year_dict = {} # populates dict key as year, val as total living/dead
for birth in b:
    year_dict.setdefault(birth,0) # sets default value of key to 0 
    year_dict[birth] += 1 # will add +1 for each birth and sums duplicates
for death in d:
    year_dict.setdefault(death,0) # sets default value of key to 0
    year_dict[death] += -1 # will add -1 for each death and sums duplicates

year_dict = OrderedDict(sorted(year_dict.items(), key=lambda t: t[0]))
solution_dict = {}

total = 0
print('year net_living running_sum')
for year in year_dict:
    total += year_dict[year]
    solution_dict.update({year:{'net_living': year_dict[year],
                                'running_sum': total}
                                })
    print('{} {:4} {:10}'.format(year, year_dict[year], total))

Выходы:

year net_living running_sum
1691    1          1
1692   -1          0
1791    1          1
1796    1          2
1800   -1          1
1803   -1          0
1852   -1         -1
1907    1          0
1980   -1         -1
1999    1          0
2001    1          1
2006   -1          0

Вывод решения_дикта

{
1691: {'net_living':  1, 'running_sum':  1},
1692: {'net_living': -1, 'running_sum':  0},
1791: {'net_living':  1, 'running_sum':  1},
1796: {'net_living':  1, 'running_sum':  2},
1800: {'net_living': -1, 'running_sum':  1},
1803: {'net_living': -1, 'running_sum':  0},
1852: {'net_living': -1, 'running_sum': -1},
1907: {'net_living':  1, 'running_sum':  0},
1980: {'net_living': -1, 'running_sum': -1},
1999: {'net_living':  1, 'running_sum':  0},
2001: {'net_living':  1, 'running_sum':  1},
2006: {'net_living': -1, 'running_sum':  0}
}