Wirf die dicksten Leute aus einem überladenen Flugzeug.

Nehmen wir an, Sie haben ein Flugzeug und es ist wenig Treibstoff. Wenn das Flugzeug nicht 3000 Pfund Passagiergewicht verliert, kann es den nächsten Flughafen nicht erreichen. Um die maximale Anzahl von Menschenleben zu retten, möchten wir zuerst die schwersten Menschen aus dem Flugzeug werfen.

Und oh ja, es gibt Millionen von Menschen im Flugzeug, und wir möchten einen optimalen Algorithmus, um die schwersten Passagiere zu finden, ohne unbedingt die gesamte Liste zu sortieren.

Dies ist ein Proxy-Problem für etwas, das ich in C ++ codieren möchte. Ich würde gerne eine "partielle Sortierung" des Passagiermanifests nach Gewicht durchführen, aber ich weiß nicht, wie viele Elemente ich benötigen werde. Ich könnte meinen eigenen "Partial_Sort" -Algorithmus ("Partial_Sort_accumulate_until") implementieren, aber ich frage mich, ob es einen einfacheren Weg gibt, dies mit Standard-STL zu tun.

Eine Möglichkeit wäre, einen minimalen Haufen zu verwenden ( std::priority_queuein C ++). So würden Sie es machen, vorausgesetzt, Sie hatten eine MinHeapKlasse. (Ja, mein Beispiel ist in C #. Ich denke, Sie haben die Idee.)

int targetTotal = 3000;
int totalWeight = 0;
// this creates an empty heap!
var myHeap = new MinHeap<Passenger>(/* need comparer here to order by weight */);
foreach (var pass in passengers)
{
    if (totalWeight < targetTotal)
    {
        // unconditionally add this passenger
        myHeap.Add(pass);
        totalWeight += pass.Weight;
    }
    else if (pass.Weight > myHeap.Peek().Weight)
    {
        // If this passenger is heavier than the lightest
        // passenger already on the heap,
        // then remove the lightest passenger and add this one
        var oldPass = myHeap.RemoveFirst();
        totalWeight -= oldPass.Weight;
        myHeap.Add(pass);
        totalWeight += pass.Weight;
    }
}

// At this point, the heaviest people are on the heap,
// but there might be too many of them.
// Remove the lighter people until we have the minimum necessary
while ((totalWeight - myHeap.Peek().Weight) > targetTotal)
{
    var oldPass = myHeap.RemoveFirst();
    totalWeight -= oldPass.Weight; 
}
// The heap now contains the passengers who will be thrown overboard.

Nach den Standardreferenzen, Laufzeit sollte proportional sein n log k, wobei ndie Anzahl der Passagiere und kist die maximale Anzahl der Elemente auf dem Heap. Wenn wir davon ausgehen, dass das Gewicht der Passagiere in der Regel 100 Pfund oder mehr beträgt, ist es unwahrscheinlich, dass der Haufen zu irgendeinem Zeitpunkt mehr als 30 Gegenstände enthält.

Der schlimmste Fall wäre, wenn die Passagiere in der Reihenfolge vom niedrigsten zum höchsten Gewicht präsentiert würden. Dies würde erfordern, dass jeder Passagier zum Haufen hinzugefügt und jeder Passagier vom Haufen entfernt wird. Mit einer Million Passagieren und der Annahme, dass das leichteste 100 Pfund wiegt, ist die n log kZahl jedoch relativ gering.

Wenn Sie die Gewichte der Passagiere zufällig ermitteln, ist die Leistung viel besser. Ich verwende so etwas für eine Empfehlungs-Engine (ich wähle die 200 besten Artikel aus einer Liste von mehreren Millionen aus). Normalerweise werden dem Haufen nur 50.000 oder 70.000 Artikel hinzugefügt.

Ich vermute, dass Sie etwas ganz Ähnliches sehen werden: Die Mehrheit Ihrer Kandidaten wird abgelehnt, weil sie leichter sind als die leichteste Person, die sich bereits auf dem Haufen befindet. Und Peekist einO(1) Operation.

Weitere Informationen zur Leistung von Heap-Auswahl und Schnellauswahl finden Sie unter Wenn Theorie auf Praxis trifft . Kurzversion: Wenn Sie weniger als 1% der Gesamtzahl der Elemente auswählen, ist die Heap-Auswahl ein klarer Gewinner gegenüber der Schnellauswahl. Mehr als 1%, dann verwenden Sie Quick Select oder eine Variante wie Introselect .

Dies hilft jedoch nicht bei Ihrem Proxy-Problem:

Damit 1.000.000 Passagiere 3000 Pfund an Gewicht verlieren, muss jeder Passagier (3000/1000000) = 0,003 Pfund pro Person verlieren. Dies könnte erreicht werden, indem jedes Hemd oder alle Schuhe oder wahrscheinlich sogar Fingernagelabschnitte weggeworfen werden, um alle zu retten. Dies setzt eine effiziente Sammlung und Entsorgung voraus, bevor der erforderliche Gewichtsverlust zunimmt, wenn das Flugzeug mehr Treibstoff verbraucht.

Eigentlich erlauben sie keine Fingernagelknipser mehr an Bord, also ist das raus.

Nachfolgend finden Sie eine recht einfache Implementierung der einfachen Lösung. Ich glaube nicht, dass es einen schnelleren Weg gibt, der zu 100% korrekt ist.

size_t total = 0;
std::set<passenger> dead;
for ( auto p : passengers ) {
    if (dead.empty()) {
       dead.insert(p);
       total += p.weight;
       continue;
    }
    if (total < threshold || p.weight > dead.begin()->weight)
    {
        dead.insert(p);
        total += p.weight;
        while (total > threshold)
        {
            if (total - dead.begin()->weight < threshold)
                break;
            total -= dead.begin()->weight;
            dead.erase(dead.begin());
        }
    }
 }

Dies funktioniert, indem die Gruppe der "Toten" aufgefüllt wird, bis die Schwelle erreicht ist. Sobald die Schwelle erreicht ist, gehen wir die Liste der Passagiere durch, die versuchen, diejenigen zu finden, die schwerer sind als die leichteste tote Person. Wenn wir eine gefunden haben, fügen wir sie der Liste hinzu und beginnen dann, die leichtesten Personen von der Liste zu "speichern", bis wir nicht mehr speichern können.

Im schlimmsten Fall entspricht dies in etwa der gesamten Liste. Aber im besten Fall (die "tote Liste" ist richtig mit den ersten X Personen gefüllt) wird es ausgeführt O(n).

Angenommen, alle Passagiere kooperieren: Verwenden Sie ein paralleles Sortiernetz . (siehe auch das )

Hier ist eine Live-Demonstration

Update: Alternatives Video (Sprung auf 1:00)

Bitten Sie zwei Personen, Vergleiche auszutauschen - schneller geht es nicht.

@Blastfurnace war auf dem richtigen Weg. Sie verwenden die Schnellauswahl, wenn die Drehpunkte Gewichtsschwellen sind. Jede Partition teilt eine Gruppe von Personen in Gruppen auf und gibt das Gesamtgewicht für jede Gruppe von Personen zurück. Sie brechen den entsprechenden Eimer weiter, bis Ihre Eimer, die den Personen mit dem höchsten Gewicht entsprechen, mehr als 3000 Pfund wiegen und Ihr niedrigster Eimer in diesem Satz 1 Person hat (das heißt, er kann nicht weiter aufgeteilt werden).

Dieser Algorithmus ist linear amortisiert, aber quadratischer Worst-Case. Ich denke, es ist der einzige lineare Zeitalgorithmus .

Hier ist eine Python-Lösung, die diesen Algorithmus veranschaulicht:

#!/usr/bin/env python
import math
import numpy as np
import random

OVERWEIGHT = 3000.0
in_trouble = [math.floor(x * 10) / 10
              for x in np.random.standard_gamma(16.0, 100) * 8.0]
dead = []
spared = []

dead_weight = 0.0

while in_trouble:
    m = np.median(list(set(random.sample(in_trouble, min(len(in_trouble), 5)))))
    print("Partitioning with pivot:", m)
    lighter_partition = []
    heavier_partition = []
    heavier_partition_weight = 0.0
    in_trouble_is_indivisible = True
    for p in in_trouble:
        if p < m:
            lighter_partition.append(p)
        else:
            heavier_partition.append(p)
            heavier_partition_weight += p
        if p != m:
            in_trouble_is_indivisible = False
    if heavier_partition_weight + dead_weight >= OVERWEIGHT and not in_trouble_is_indivisible:
        spared += lighter_partition
        in_trouble = heavier_partition
    else:
        dead += heavier_partition
        dead_weight += heavier_partition_weight
        in_trouble = lighter_partition

print("weight of dead people: {}; spared people: {}".format(
    dead_weight, sum(spared)))
print("Dead: ", dead)
print("Spared: ", spared)

Ausgabe:

Partitioning with pivot: 121.2
Partitioning with pivot: 158.9
Partitioning with pivot: 168.8
Partitioning with pivot: 161.5
Partitioning with pivot: 159.7
Partitioning with pivot: 158.9
weight of dead people: 3051.7; spared people: 9551.7
Dead:  [179.1, 182.5, 179.2, 171.6, 169.9, 179.9, 168.8, 172.2, 169.9, 179.6, 164.4, 164.8, 161.5, 163.1, 165.7, 160.9, 159.7, 158.9]
Spared:  [82.2, 91.9, 94.7, 116.5, 108.2, 78.9, 83.1, 114.6, 87.7, 103.0, 106.0, 102.3, 104.9, 117.0, 96.7, 109.2, 98.0, 108.4, 99.0, 96.8, 90.7, 79.4, 101.7, 119.3, 87.2, 114.7, 90.0, 84.7, 83.5, 84.7, 111.0, 118.1, 112.1, 92.5, 100.9, 114.1, 114.7, 114.1, 113.7, 99.4, 79.3, 100.1, 82.6, 108.9, 103.5, 89.5, 121.8, 156.1, 121.4, 130.3, 157.4, 138.9, 143.0, 145.1, 125.1, 138.5, 143.8, 146.8, 140.1, 136.9, 123.1, 140.2, 153.6, 138.6, 146.5, 143.6, 130.8, 155.7, 128.9, 143.8, 124.0, 134.0, 145.0, 136.0, 121.2, 133.4, 144.0, 126.3, 127.0, 148.3, 144.9, 128.1]

Angenommen, Sie haben wie die Gewichte von Personen eine gute Vorstellung davon, welche Maximal- und Minimalwerte wahrscheinlich mit einer Radix-Sortierung in O (n) sortiert werden. Dann arbeiten Sie einfach vom schwersten Ende der Liste zum leichtesten. Gesamtlaufzeit: O (n). Leider gibt es keine Implementierung einer Radix-Sortierung in der STL, aber das Schreiben ist ziemlich einfach.

Warum verwenden Sie nicht einen Teil-Quicksort mit einer anderen Abbruchregel als "sortiert"? Sie können es ausführen und dann nur die höhere Hälfte verwenden und fortfahren, bis das Gewicht in dieser höheren Hälfte nicht mehr das Gewicht enthält, das mindestens mehr weggeworfen werden muss, als Sie einen Schritt in der Rekursion zurückgehen und die Liste sortieren. Danach können Sie Leute aus dem oberen Bereich dieser sortierten Liste werfen.

Massively Parallel Tournament Sort: -

Angenommen, standardmäßig drei Sitze auf jeder Seite der Ailse: -

1. Bitten Sie die Passagiere auf dem Fensterplatz, sich auf den mittleren Sitz zu bewegen, wenn sie schwerer sind als die Person auf dem Fensterplatz.

2. Bitten Sie die Passagiere auf dem mittleren Sitz, mit dem Passagier auf dem Gangplatz zu tauschen, wenn sie schwerer sind.

3. Bitten Sie den Passagier auf dem linken Gang, mit dem Passagier auf dem rechten Gang zu tauschen, wenn er schwerer ist.

4. Blasensortierung der Passagiere auf dem rechten Gangplatz. (Führt n Schritte für n Zeilen aus). - Bitten Sie die Passagiere auf dem rechten Gangplatz, n -1 Mal mit der Person vor ihnen zu tauschen.

5 Treten Sie sie aus der Tür, bis Sie 3000 Pfund erreichen.

3 Schritte + n Schritte plus 30 Schritte, wenn Sie eine wirklich dünne Passagierlast haben.

Für eine Ebene mit zwei Gängen sind die Anweisungen komplexer, aber die Leistung ist ungefähr gleich.

Ich würde wahrscheinlich verwenden std::nth_element, um die 20 schwersten Leute in linearer Zeit abzutrennen. Verwenden Sie dann eine komplexere Methode, um den schwersten der Schweren zu finden und abzustoßen.

Sie können die Liste einmal durchlaufen, um den Mittelwert und die Standardabweichung zu erhalten, und diese dann verwenden, um die Anzahl der Personen zu schätzen, die gehen müssen. Verwenden Sie Partial_Sort, um die Liste basierend auf dieser Nummer zu generieren. Wenn die Vermutung niedrig war, verwenden Sie teilweise_sort für den Rest erneut mit einer neuen Vermutung.

@James hat die Antwort in den Kommentaren: a std::priority_queuewenn Sie einen beliebigen Container verwenden können, oder eine Kombination aus std::make_heapund std::pop_heap(und std::push_heap), wenn Sie so etwas wie a verwenden möchten std::vector.

Hier ist eine Heap-basierte Lösung, die das in Python integrierte Heapq-Modul verwendet. Es ist in Python, beantwortet also nicht die ursprüngliche Frage, ist aber sauberer (IMHO) als die andere veröffentlichte Python-Lösung.

import itertools, heapq

# Test data
from collections import namedtuple

Passenger = namedtuple("Passenger", "name seat weight")

passengers = [Passenger(*p) for p in (
    ("Alpha", "1A", 200),
    ("Bravo", "2B", 800),
    ("Charlie", "3C", 400),
    ("Delta", "4A", 300),
    ("Echo", "5B", 100),
    ("Foxtrot", "6F", 100),
    ("Golf", "7E", 200),
    ("Hotel", "8D", 250),
    ("India", "8D", 250),
    ("Juliet", "9D", 450),
    ("Kilo", "10D", 125),
    ("Lima", "11E", 110),
    )]

# Find the heaviest passengers, so long as their
# total weight does not exceeed 3000

to_toss = []
total_weight = 0.0

for passenger in passengers:
    weight = passenger.weight
    total_weight += weight
    heapq.heappush(to_toss, (weight, passenger))

    while total_weight - to_toss[0][0] >= 3000:
        weight, repreived_passenger = heapq.heappop(to_toss)
        total_weight -= weight


if total_weight < 3000:
    # Not enough people!
    raise Exception("We're all going to die!")

# List the ones to toss. (Order doesn't matter.)

print "We can get rid of", total_weight, "pounds"
for weight, passenger in to_toss:
    print "Toss {p.name!r} in seat {p.seat} (weighs {p.weight} pounds)".format(p=passenger)

Wenn k = die Anzahl der zu werfenden Passagiere und N = die Anzahl der Passagiere ist, ist der beste Fall für diesen Algorithmus O (N) und der schlechteste Fall für diesen Algorithmus ist Nlog (N). Der schlimmste Fall tritt auf, wenn k für lange Zeit in der Nähe von N ist. Hier ist ein Beispiel für die schlechteste Besetzung:

weights = [2500] + [1/(2**n+0.0) for n in range(100000)] + [3000]

In diesem Fall (Leute aus dem Flugzeug werfen (mit einem Fallschirm, nehme ich an)) muss k jedoch kleiner als 3000 sein, was << "Millionen von Menschen" ist. Die durchschnittliche Laufzeit sollte daher etwa Nlog (k) betragen, was linear zur Anzahl der Personen ist.