Jetant les personnes les plus grosses d'un avion surchargé.

Disons que vous avez un avion et qu'il est faible en carburant. À moins que l'avion ne pèse 3000 livres de passagers, il ne pourra pas atteindre le prochain aéroport. Pour sauver le maximum de vies, nous aimerions d'abord jeter les personnes les plus lourdes hors de l'avion.

Et oh oui, il y a des millions de personnes dans l'avion, et nous aimerions un algorithme optimal pour trouver les passagers les plus lourds, sans nécessairement trier la liste entière.

Il s'agit d'un problème de proxy pour quelque chose que j'essaie de coder en C ++. Je voudrais faire un "partial_sort" sur le manifeste passager en poids, mais je ne sais pas de combien d'éléments je vais avoir besoin. Je pourrais implémenter mon propre algorithme "partial_sort" ("partial_sort_accumulate_until"), mais je me demande s'il existe un moyen plus simple de le faire en utilisant la norme STL.

Une façon serait d'utiliser un tas min ( std::priority_queueen C ++). Voici comment vous le feriez, en supposant que vous ayez eu un MinHeapcours. (Oui, mon exemple est en C #. Je pense que vous avez l'idée.)

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.

Selon les références standard, le temps de course devrait être proportionnel à n log k, où nest le nombre de passagers et kle nombre maximum d'articles sur le tas. Si nous supposons que le poids des passagers sera généralement de 100 livres ou plus, il est peu probable que le tas contienne plus de 30 articles à tout moment.

Le pire serait que les passagers soient présentés dans l'ordre, du poids le plus faible au plus élevé. Cela nécessiterait que chaque passager soit ajouté au tas et que chaque passager soit retiré du tas. Pourtant, avec un million de passagers et en supposant que le plus léger pèse 100 livres, cela équivaut n log kà un nombre raisonnablement petit.

Si vous obtenez les poids des passagers au hasard, les performances sont bien meilleures. J'utilise quelque chose comme ça pour un moteur de recommandation (je sélectionne les 200 premiers éléments d'une liste de plusieurs millions). Je me retrouve généralement avec seulement 50 000 ou 70 000 éléments réellement ajoutés au tas.

Je soupçonne que vous verrez quelque chose d'assez similaire: la majorité de vos candidats seront rejetés parce qu'ils sont plus légers que la personne la plus légère déjà sur le tas. Et Peekc'est une O(1)opération.

Pour plus d'informations sur les performances de la sélection de tas et de la sélection rapide, voir Quand la théorie rencontre la pratique . Version courte: si vous sélectionnez moins de 1% du nombre total d'articles, la sélection en tas est clairement gagnante par rapport à la sélection rapide. Plus de 1%, puis utilisez la sélection rapide ou une variante comme Introselect .

Cela n'aidera cependant pas votre problème de proxy:

Pour que 1000000 de passagers perdent 3000 livres de poids, chaque passager doit perdre (3000/1000000) = 0,003 lb par personne. Cela pourrait être réalisé en jetant la chemise ou les chaussures de chacun, ou probablement même des coupures d'ongles, sauvant tout le monde. Cela suppose une collecte et un largage efficaces avant que la perte de poids nécessaire n'augmente à mesure que l'avion utilise plus de carburant.

En fait, ils n'autorisent plus les coupe-ongles à bord, donc c'est fini.

Voici une implémentation assez simple de la solution simple. Je ne pense pas qu'il existe un moyen plus rapide qui soit 100% correct.

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

Cela fonctionne en remplissant l'ensemble des «morts» jusqu'à ce qu'il atteigne le seuil. Une fois le seuil atteint, nous continuons à parcourir la liste des passagers essayant de trouver ceux qui sont plus lourds que le mort le plus léger. Lorsque nous en avons trouvé un, nous les ajoutons à la liste, puis nous commençons à «enregistrer» les personnes les plus légères de la liste jusqu'à ce que nous ne puissions plus en enregistrer.

Dans le pire des cas, cela fonctionnera à peu près comme une sorte de liste entière. Mais dans le meilleur des cas (la "liste morte" est correctement remplie avec les X premières personnes), cela fonctionnera O(n).

En supposant que tous les passagers coopéreront: utilisez un réseau de tri parallèle . (voir aussi ceci )

Voici une démonstration en direct

Mise à jour: vidéo alternative (passer à 1h00)

Demander à des paires de personnes de comparer-échanger - vous ne pouvez pas aller plus vite que cela.

@Blastfurnace était sur la bonne voie. Vous utilisez la sélection rapide où les pivots sont des seuils de poids. Chaque partition divise un ensemble de personnes en ensembles et renvoie le poids total de chaque ensemble de personnes. Vous continuez à casser le seau approprié jusqu'à ce que vos seaux correspondant aux personnes dont le poids est le plus élevé dépassent 3000 livres, et votre seau le plus bas qui se trouve dans cet ensemble ait 1 personne (c'est-à-dire qu'il ne peut plus être divisé).

Cet algorithme est amorti en temps linéaire, mais dans le pire des cas quadratique. Je pense que c'est le seul algorithme de temps linéaire .

Voici une solution Python qui illustre cet algorithme:

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

Production:

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]

En supposant que, comme les poids des personnes, vous avez une bonne idée de ce que les valeurs maximales et minimales sont susceptibles d'être utilisées, utilisez un tri radix pour les trier dans O (n). Ensuite, travaillez simplement de l'extrémité la plus lourde de la liste vers la plus légère. Durée totale de fonctionnement: O (n). Malheureusement, il n'y a pas d'implémentation d'un tri radix dans la STL, mais c'est assez simple à écrire.

Pourquoi n'utilisez-vous pas un tri rapide partiel avec une règle d'abandon différente de "triée". Vous pouvez l'exécuter, puis utiliser uniquement la moitié supérieure et continuer jusqu'à ce que le poids dans cette moitié supérieure ne contienne plus le poids qui doit au moins être jeté, que de revenir en arrière d'une étape dans la récursivité et de trier la liste. Après cela, vous pouvez commencer à expulser les gens du haut de la liste triée.

Type de tournoi massivement parallèle: -

En supposant une norme de trois sièges de chaque côté de l'ailse: -

1. Demandez aux passagers assis dans le siège de fenêtre de se déplacer vers le siège du milieu s'ils sont plus lourds que la personne assise dans le siège de fenêtre.

2. Demandez aux passagers du siège central de changer de place avec le passager du siège côté couloir s'ils sont plus lourds.

3. Demandez au passager du siège de l'allée gauche de permuter avec le passager du siège de l'allée droite s'il est plus lourd.

4. Bulle trie les passagers dans le siège de l'allée droite. (Prend n étapes pour n lignes). - demander aux passagers assis dans l'allée droite d'échanger avec la personne devant n -1 fois.

5 Donnez-leur un coup de pied jusqu'à ce que vous atteigniez 3000 livres.

3 étapes + n étapes plus 30 étapes si vous avez une charge de passagers vraiment maigre.

Pour un avion à deux couloirs - les instructions sont plus complexes mais les performances sont à peu près les mêmes.

J'utiliserais probablement std::nth_elementpour séparer les 20 personnes les plus lourdes en temps linéaire. Ensuite, utilisez une méthode plus complexe pour trouver et heurter le plus lourd des lourds.

Vous pouvez faire un passage sur la liste pour obtenir la moyenne et l'écart type, puis l'utiliser pour approximer le nombre de personnes qui doivent y aller. Utilisez partial_sort pour générer la liste en fonction de ce nombre. Si la supposition était faible, utilisez à nouveau partial_sort sur le reste avec une nouvelle supposition.

@James a la réponse dans les commentaires: a std::priority_queuesi vous pouvez utiliser n'importe quel conteneur, ou une combinaison de std::make_heapet std::pop_heap(et std::push_heap) si vous voulez utiliser quelque chose comme a std::vector.

Voici une solution basée sur le tas utilisant le module heapq intégré de Python. Il est en Python, donc ne répond pas à la question d'origine, mais il est plus propre (à mon humble avis) que l'autre solution Python publiée.

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)

Si k = le nombre de passagers à lancer et N = le nombre de passagers, alors le meilleur cas pour cet algorithme est O (N) et le pire cas pour cet algorithme est Nlog (N). Le pire des cas se produit si k est proche de N pendant une longue période. Voici un exemple de la pire distribution:

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

Cependant, dans ce cas (jeter des gens hors de l'avion (avec un parachute, je présume)), alors k doit être inférieur à 3000, ce qui représente << "des millions de personnes". Le temps d'exécution moyen devrait donc être d'environ Nlog (k), qui est linéaire par rapport au nombre de personnes.