Wenn Sie eine Liste von Personen mit ihren Geburts- und Endjahren (alle zwischen 1900 und 2000 ) angeben, finden Sie das Jahr mit der höchsten Anzahl an lebenden Personen.
Hier ist meine etwas brutale Lösung:
%Vor% Ich versuche, eine effizientere Möglichkeit zu finden, dieses Problem in Python zu lösen. Beide - readability und efficiency zählt. Außerdem wird mein Code aus irgendeinem Grund [1938, 1939] nicht ausgeben, solange es sollte.
Aktualisieren
Eingabe ist ein list von Tupeln, wobei das erste Element eines Tupels ein year ist, wenn eine Person geboren wurde, und das zweite Element eines tuple das Jahr des Todes ist.
Update 2
Das Endjahr (zweiter Teil des Tupels) zählt ebenso wie ein Jahr des Lebens der Person (wenn also die Person in Sept 1939 stirbt (uns interessiert der Monat nicht), lebt er tatsächlich 1939, zumindest einen Teil davon). Das sollte die 1939 'fehlenden Ergebnisse beheben.
Beste Lösung?
Während die Lesbarkeit zugunsten von @ joran-beasley zählt, wurde der effizienteste Algorithmus für größere Eingaben von @ njzk2 . Danke @ hannes-ovrén für die Bereitstellung von Analysen in IPython-Notizbuch auf Gist
Ich würde so gehen:
unborn list) alive -Liste alive -Liste, die zuerst stirbt, entfernen Sie sie aus der Liste. alive -Liste in ein dict unborn und alive leer sind Die Komplexität sollte ungefähr O((m + n) * log(m)) sein (jedes Jahr wird nur einmal betrachtet und jede Person nur zweimal, multipliziert mit den Einfügekosten in der alive -Liste)
Eine andere Lösung, die ich gerade von:
birthdates und deathdates . Die Gesamtkomplexität ist O(n)
Wir können auch numpy slicing verwenden, das ziemlich ordentlich ist, und sollte auch ziemlich effizient sein:
%Vor% BEARBEITEN Es sieht so aus, als ob das Nametuple ein wenig Overhead hinzufügt. Um also ein bisschen mehr zu beschleunigen, entfernen Sie das Nametuple und tun Sie es
for birth, death in people: stattdessen.
Wie wäre es mit diesem:
%Vor%Es ist nicht von der Jahresspanne betroffen, aber es ist nlogn in | pop | (es sei denn, Sie würden eine Radix-Sortierung durchführen, die ~ 10n für eine Jahrtausendspanne wäre und für | pop | & gt; 1000 schneller sein sollte). Kann nicht beides haben. Eine sehr allgemeine Lösung müsste zuerst scannen und basierend auf der gemessenen Jahresspanne und | pop | entscheiden, welcher Algorithmus verwendet werden soll.
Ich kam über den folgenden Code, der genau das ist, was Sie brauchen.
Nehmen wir an, der Bereich der Jahre ist 1900 - 2000
Kredit "Brian Schmitz" hier