Wyrzucanie najgrubszych ludzi z przeciążonego samolotu.

Powiedzmy, że masz samolot, który ma mało paliwa. O ile samolot nie zrzuci 3000 funtów wagi pasażera, nie będzie w stanie dotrzeć do następnego lotniska. Aby uratować maksymalną liczbę istnień ludzkich, chcielibyśmy najpierw zrzucić z samolotu najcięższych ludzi.

O tak, w samolocie są miliony ludzi i chcielibyśmy optymalnego algorytmu, aby znaleźć najcięższych pasażerów, bez konieczności sortowania całej listy.

To jest problem z proxy dla czegoś, co próbuję napisać w C ++. Chciałbym wykonać „częściową segregację” na podstawie manifestu pasażerskiego według wagi, ale nie wiem, ile elementów będę potrzebować. Mogę zaimplementować własny algorytm „częściowy_sort” („częściowy_sort_accumulate_until”), ale zastanawiam się, czy istnieje łatwiejszy sposób na wykonanie tego przy użyciu standardowego STL.

Jednym ze sposobów byłoby użycie sterty min ( std::priority_queuew C ++). Oto, jak byś to zrobił, zakładając, że masz MinHeapklasę. (Tak, mój przykład jest w języku C #. Myślę, że masz pomysł.)

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.

Zgodnie ze standardowymi odniesieniami czas pracy powinien być proporcjonalny do n log k, gdzie njest liczba pasażerów i kmaksymalna liczba elementów na stercie. Jeśli założymy, że waga pasażerów będzie zwykle wynosić 100 funtów lub więcej, to jest mało prawdopodobne, aby na stosie znajdowało się więcej niż 30 przedmiotów w dowolnym momencie.

W najgorszym przypadku pasażerowie są prezentowani w kolejności od najniższej wagi do najwyższej. Wymagałoby to dodania każdego stosu do stosu i każdego pasażera usuniętego ze stosu. Mimo to, z milionem pasażerów i przy założeniu, że najlżejszy waży 100 funtów, osiąga n log kto stosunkowo niewielką liczbę.

Jeśli losowo otrzymujesz wagi pasażerów, wydajność jest znacznie lepsza. Używam czegoś takiego do silnika rekomendacji (wybieram 200 najlepszych pozycji z listy kilku milionów). Zwykle mam tylko 50 000 lub 70 000 przedmiotów faktycznie dodanych do sterty.

Podejrzewam, że zobaczysz coś podobnego: większość twoich kandydatów zostanie odrzucona, ponieważ są lżejsi niż najlżejsza osoba już na stosie. I Peekjest O(1)operacją.

Aby uzyskać więcej informacji na temat wydajności wybierania stosu i szybkiego wybierania, zobacz Kiedy teoria spotyka się z praktyką . Krótka wersja: jeśli wybierasz mniej niż 1% ogólnej liczby przedmiotów, wybór sterty jest wyraźnym zwycięzcą w stosunku do szybkiego wyboru. Ponad 1%, a następnie użyj szybkiego wyboru lub wariantu takiego jak Introselect .

Nie pomoże to jednak w przypadku problemu z serwerem proxy:

Aby 1 000 000 pasażerów zrzuciło 3000 funtów wagi, każdy pasażer musi stracić (3000/1000000) = 0,003 funta na osobę. Można to osiągnąć, odrzucając każdą koszulę, buty, a może nawet odciski paznokci, ratując wszystkich. Zakłada to efektywne zbieranie i pomijanie zanim potrzebna utrata masy wzrośnie, gdy samolot zużyje więcej paliwa.

W rzeczywistości nie pozwalają już na obcinanie paznokci na pokładzie, więc nie ma.

Poniżej znajduje się dość prosta implementacja prostego rozwiązania. Nie sądzę, że istnieje szybszy sposób, który jest w 100% poprawny.

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());
        }
    }
 }

Działa to poprzez wypełnienie zestawu „martwych ludzi”, aż osiągnie próg. Po osiągnięciu progu przeglądamy listę pasażerów starających się znaleźć tych, którzy są ciężsi od najlżejszej zmarłej osoby. Kiedy go znajdziemy, dodajemy go do listy, a następnie rozpoczynamy „Zapisywanie” najlżejszych osób z listy, dopóki nie będziemy mogli więcej zapisać.

W najgorszym przypadku będzie to działać tak samo, jak rodzaj całej listy. Ale w najlepszym przypadku („martwa lista” jest poprawnie wypełniona pierwszymi X osobami), będzie działać O(n).

Zakładając, że wszyscy pasażerowie będą współpracować: Użyj równoległej sieci sortowania . (zobacz także to )

Oto demonstracja na żywo

Aktualizacja: Alternatywne wideo (przejdź do 1:00)

Poprosić pary ludzi o wymianę-wymianę - nie możesz być szybszy niż to.

@Blastfurnace był na dobrej drodze. Skorzystasz z szybkiego wyboru, gdzie osiami są progi masy. Każda partycja dzieli jeden zestaw osób na zestawy i zwraca całkowitą wagę dla każdego zestawu osób. Kontynuujesz łamanie odpowiedniego wiadra, dopóki twoje wiadra odpowiadające osobom o największej wadze nie przekroczą 3000 funtów, a twoje najniższe wiadro, które znajduje się w tym zestawie, ma 1 osobę (to znaczy, nie można go dalej podzielić).

Algorytm ten jest amortyzowany w czasie liniowym, ale w najgorszym przypadku jest kwadratowy. Myślę, że to jedyny algorytm czasu liniowego .

Oto rozwiązanie w języku Python ilustrujące ten algorytm:

#!/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)

Wynik:

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]

Zakładając, że podobnie jak masy ludzi, masz dobre wyobrażenie o tym, jakie wartości maksymalne i minimalne mogą być użyte w sortowaniu radix do posortowania ich w O (n). Następnie po prostu pracuj od najcięższego końca listy w kierunku najlżejszego. Całkowity czas pracy: O (n). Niestety w STL nie ma implementacji sortowania radix, ale napisanie jej jest dość proste.

Dlaczego nie użyjesz częściowego szybkiego sortowania z inną regułą przerwania niż „posortowane”. Możesz go uruchomić, a następnie użyć tylko wyższej połowy i kontynuować, dopóki waga w tej wyższej połowie nie będzie zawierała ciężaru, który należy przynajmniej wyrzucić, niż cofniesz się o jeden krok w rekurencji i posortujesz listę. Następnie możesz zacząć wyrzucać ludzi z wyższej półki tej posortowanej listy.

Sortowanie turniejów masowo równoległych: -

Zakładając standardowe trzy miejsca po każdej stronie linii:

1. Poproś pasażerów siedzących przy oknie, aby przenieśli się na środkowe siedzenie, jeśli są cięższe od osoby siedzącej przy oknie.

2. Poproś pasażerów na środkowym siedzeniu, aby zamienili się z pasażerem siedzącym w przejściu, jeśli są ciężsi.

3. Poproś pasażera siedzącego na lewym przejściu, aby zamienił się z pasażerem na prawym siedzeniu, gdy są cięższe.

4. Sortuj bąbelkowo pasażerów na prawym miejscu w przejściu. (Wykonuje n kroków dla n rzędów). - poproś pasażerów siedzących na prawym przejściu, aby zamienili się z osobą z przodu n -1 razy.

5 Wykop je przez drzwi, aż osiągniesz 3000 funtów.

3 kroki + n kroków plus 30 kroków, jeśli masz naprawdę chudy ładunek pasażerski.

W przypadku samolotu z dwoma nawami - instrukcje są bardziej złożone, ale wydajność jest prawie taka sama.

Prawdopodobnie użyłbym std::nth_elementdo podzielenia 20 najcięższych ludzi w czasie liniowym. Następnie użyj bardziej złożonej metody, aby znaleźć i zrzucić najcięższy z ciężkich.

Możesz wykonać jedno przejście przez listę, aby uzyskać średnią i standardowe odchylenie, a następnie użyć tego do przybliżenia liczby osób, które muszą odejść. Użyj częściowego sortowania, aby wygenerować listę na podstawie tej liczby. Jeśli domysły były niskie, ponownie użyj częściowego_sortowania dla pozostałych z nowym domysłem.

@James ma odpowiedź w komentarzach: a, std::priority_queuejeśli możesz użyć dowolnego kontenera lub kombinacji std::make_heapistd::pop_heap (i std::push_heap), jeśli chcesz użyć czegoś takiego jak std::vector.

Oto rozwiązanie oparte na stercie przy użyciu wbudowanego modułu heapq Pythona. Jest w Pythonie, więc nie odpowiada na oryginalne pytanie, ale jest czystszy (IMHO) niż inne opublikowane rozwiązanie Pythona.

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)

Jeśli k = liczba pasażerów do podrzucenia, a N = liczba pasażerów, najlepszym przypadkiem dla tego algorytmu jest O (N), a najgorszym przypadkiem dla tego algorytmu jest Nlog (N). Najgorszy przypadek występuje, gdy k jest przez długi czas blisko N. Oto przykład najgorszej obsady:

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

Jednak w tym przypadku (wyrzucanie ludzi z samolotu (przypuszczam, że ze spadochronem)) k musi być mniejsze niż 3000, co oznacza << „miliony ludzi”. Średni czas działania powinien zatem wynosić około Nlog (k), co jest liniowe względem liczby osób.