Wyrzucanie najgrubszych ludzi z przeciążonego samolotu.

200

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.

IvyMike
źródło
5
Jeśli istnieje analogia do człowieka, możesz zacząć od zrzucenia ludzi ważących więcej niż X, na przykład 120 kg, ponieważ są oni najprawdopodobniej jednymi z najgrubszych.
RedX,
132
Czy wszyscy pasażerowie współpracowaliby z dowolnym krokiem algorytmu?
Lior Kogan,
34
tematy takie jak to, dlaczego kocham IT.
Markus
14
Czy mogę zapytać, dla której linii lotniczej to jest? Chcę się upewnić, że latam z nimi dopiero przed sezonem wakacyjnym - nie po tym, jak sobie na to pozwolę.
jp2code
24
Współpraca pasażerów nie jest wymagana przy odpowiednim wyposażeniu (takim jak fotele wypychaczy z wbudowanymi wagami).
Jim Fred

Odpowiedzi:

102

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 .

Jim Mischel
źródło
1
SoapBox opublikował szybszą odpowiedź.
Mooing Duck,
7
Moim zdaniem odpowiedź SoapBox jest moralnym odpowiednikiem odpowiedzi Jima Mischela. SoapBox napisał swój kod w C ++, dlatego używa std :: set, który ma taki sam czas dodawania dziennika (N) jak MinHeap.
IvyMike,
1
Istnieje liniowe rozwiązanie czasowe. Dodam to.
Neil G
2
Istnieje klasa STL dla min-sterty:std::priority_queue
bdonlan
3
@MooingDuck: Być może źle zrozumiałeś. Mój kod tworzy pustą stertę, podobnie jak kod SoapBox tworzy pusty zestaw. Główną różnicą, jak widzę, jest to, że jego kod przycina zestaw nadwagi w miarę dodawania przedmiotów o większej wadze, podczas gdy mój utrzymuje nadmiar i przycina go na końcu. Jego zestaw potencjalnie zmniejszy się, gdy będzie poruszał się po liście, znajdując cięższych ludzi. Mój stos pozostaje taki sam po osiągnięciu progu masy i przycinam go po sprawdzeniu ostatniego elementu na liście.
Jim Mischel
119

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.

aportr
źródło
14
Uwielbiam umiejętność przeglądania problemu i znajdowania naprawdę lepszego sposobu.
fncomp
19
Jesteś geniuszem. :)
Jonathan
3
Myślę, że same buty by to pokryły
Kaczka Mooing
0,003 funta to 0,048 uncji, czyli nieco mniej niż 1/20 uncji. Więc jeśli zaledwie jedna na sześćdziesiąt osób w samolocie korzysta z zasady trzech uncji szamponu, możesz uratować ten dzień, wyrzucając cały ten szampon.
Ryan Lundy,
43

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).

SoapBox
źródło
1
Myślę, że musisz zaktualizować totalobok pozycji continue; Poza tym, to jest odpowiedź, którą zamierzałem opublikować. Super szybkie rozwiązanie
Mooing Duck,
2
To jest poprawna odpowiedź, to najszybsza odpowiedź, to także odpowiedź o najniższej złożoności.
Xander Tulip
Prawdopodobnie mógłbyś wycisnąć z niego trochę więcej, buforując dead.begin () i zmieniając nieco ustawienia, aby zminimalizować rozgałęzienia, co na nowoczesnych procesorach jest dość powolne
Wug
dead.begin () jest najprawdopodobniej trywialny i prawie na pewno byłby przeznaczony tylko do dostępu do danych. Ale tak, poruszanie się po kilku ifach pozwoliłoby uzyskać nieco większą wydajność poprzez redukcję gałęzi ... ale prawdopodobnie przy dużym koszcie czytelności.
SoapBox,
1
Jest to logicznie eleganckie i spełnia WSZYSTKIE wymagania PO, w tym nie zna liczby pasażerów z przodu. Mimo że spędziłem większość ostatnich 5 miesięcy na pracy z mapami i zestawami STL, jestem pewien, że szerokie użycie iteratorów obniżyłoby wydajność. Wystarczy wypełnić zestaw, a następnie iterować od prawej do lewej, aż suma najcięższych ludzi będzie większa niż 3000. Zestaw 1 miliona elementów, przedstawionych w losowej kolejności, będzie ładował się z prędkością ~ 30 milionów / s na rdzeniach i5 || i7 3,4 Ghz. Iteracja co najmniej 100 razy wolniejsza. KISS wygra tutaj.
user2548100
32

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.

Lior Kogan
źródło
1
To wciąż jest rodzaj i będzie O (nlogn). Z pewnością możesz dostać się szybciej, jako O (nlogk), gdzie k << n, zostało dostarczone rozwiązanie.
Adam
1
@Adam: To sortowanie równoległe. Sortowanie ma dolną granicę kroków O (nlog n) SEKWENCYJNYCH. Jednak mogą być równoległe, więc złożoność czasu może być znacznie niższa. patrz na przykład cs.umd.edu/~gasarch/ramsey/parasort.pdf
Lior Kogan
1
Cóż, OP mówi: „To jest problem z proxy dla czegoś, co próbuję napisać w C ++”. Więc nawet jeśli pasażerowie będą współpracować, nie będą dla ciebie obliczać. To fajny pomysł, ale założenie tego papieru, że masz nprocesory, nie ma zastosowania.
Adam
@LiorKogan - film demonstracyjny na żywo nie jest już dostępny na youtube
Adelin
@Adelin: Dziękuję, dodano alternatywne wideo
Lior Kogan,
21

@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]
Neil G.
źródło
3
+1. To ciekawy pomysł, choć nie jestem pewien, czy jest dość liniowy. O ile mi czegoś nie brakuje, musisz iterować przedmioty, aby obliczyć całkowitą masę wiadra, i musisz ponownie obliczyć wysokie wiadro (przynajmniej częściowo) za każdym razem, gdy się dzielisz. W dalszym ciągu będzie to szybsze niż moje podejście oparte na stercie, ale myślę, że nie doceniasz złożoności.
Jim Mischel,
2
@Jim: Powinna mieć taką samą złożoność jak szybki wybór . Wiem, że opis na wikipedii nie jest najlepszy, ale powodem, dla którego jest to liniowy amortyzowany czas, jest to, że za każdym razem, gdy wykonujesz partycję, pracujesz tylko z jedną stroną partycji. Nie rygorystycznie, wyobraź sobie, że każda partycja dzieli grupę ludzi na dwie części. Następnie pierwszy krok zajmuje O (n), następnie O (n / 2) itd. I, n + n / 2 + n / 4 + ... = 2n.
Neil G
2
@Jim: W każdym razie twój algorytm ma najlepszy najgorszy przypadek, podczas gdy mój ma najlepszy średni czas. Myślę, że oba są dobrymi rozwiązaniami.
Neil G
2
@JimMischel, NeilG: codepad.org/FAx6hbtc Sprawdziłem, że wszystkie mają takie same wyniki i poprawiłem Jima. FullSort: 1828 tyknięć. JimMischel: 312 tyknięć. SoapBox 109 tyka. NeilG: 641 tyknięć.
Mooing Duck
2
@NeilG: codepad.org/0KmcsvwD Użyłem std :: partition, aby znacznie przyspieszyć moją implementację algorytmu. stdsort: 1812 tyknięć. FullHeap 312 tyków. Soapbox / JimMichel: 109 kleszczy, NeilG: 250 kleszczy.
Mooing Duck
11

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.

Keith Irwin
źródło
Nie użyłbym jednak ogólnego sortowania radix, ponieważ nie trzeba w pełni sortować listy, aby uzyskać odpowiedź.
Mooing Duck,
1
Aby to wyjaśnić, dobrym pomysłem jest sortowanie radix . Tylko pamiętaj, aby napisać zoptymalizowany zoptymalizowany.
Mooing Duck
1
@Mooing: To prawda, że ​​nie musisz wykonywać pełnego sortowania radix, ale w momencie, gdy to opublikowałem, nie opublikowano żadnych algorytmów O (n) i było to łatwe do zauważenia. Myślę, że odpowiedź Neila G. jest najlepsza teraz, gdy wyjaśnił ją pełniej i wyraźnie zaczął używać mediany jako punktu zwrotnego w swojej selekcji. Ale użycie standardowego sortowania radix jest nieco łatwiejsze i mniej prawdopodobne jest, że wystąpią subtelne błędy implementacyjne, więc zostawię swoją odpowiedź. Wykonanie niestandardowego sortowania częściowego na pewno byłoby szybsze, ale nie asymptotycznie.
Keith Irwin
6

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.

Sim
źródło
To Zasadnicza idea algorytmu Neil G I pomyśleć .
Mooing Duck
taka jest esencja szybkiego wyboru, którego używa Neil G.
Michael Donohue
6

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.

James Anderson
źródło
taka sama jak odpowiedź Liora Kogana, ale o wiele więcej szczegółów.
Mooing Duck,
7
„Wystarczająco dobrym” rozwiązaniem byłoby zaoferowanie „darmowych hot dogów” i wyrzucenie pierwszych piętnastu, którzy dotarli do przodu. Nie zapewni optymalnego rozwiązania za każdym razem, ale działa w zwykłym „O”.
James Anderson
Czy nie lepiej byłoby wyrzucić ostatnie 15, ponieważ cięższe będą prawdopodobnie wolniejsze?
Peter
@Patriker - Uważam, że celem jest zrzucenie 3000 funtów przy minimalnej liczbie osób. Chociaż możesz zoptymalizować algorytm, zmieniając krok 4 na „zamień się z osobą z n - 29 razy”, co spowoduje przesunięcie 30 najbardziej porowatych na przód, ale nie w ścisłej kolejności wagowej.
James Anderson
4

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.

Blastfurnace
źródło
3

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.

Mark Ransom
źródło
2

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.

Andrew Dalke
źródło