Wat is de mediaan van drie strategieën om de spilwaarde bij snel sorteren te selecteren?
Ik lees het op internet, maar ik kan er niet achter komen wat het precies is? En ook hoe het beter is dan de gerandomiseerde snelle sortering.
Antwoord 1, autoriteit 100%
De mediaan van drie laat je kijken naar de eerste, middelste en laatste elementen van de array, en de mediaan van die drie elementen kiezen als de spil.
Om het “volledige effect” van de mediaan van drie te krijgen, is het ook belangrijk om die drie items te sorteren, niet alleen de mediaan als draaipunt te gebruiken — dit heeft geen invloed op wat wordt gekozen als de spil in de huidige iteratie, maar kan/zal van invloed zijn op wat wordt gebruikt als de spil in de volgende recursieve aanroep, wat helpt om het slechte gedrag voor een paar initiële bestellingen te beperken (een die in veel gevallen bijzonder slecht blijkt te zijn, is een array dat is gesorteerd, behalve dat het kleinste element aan de bovenkant van de array staat (of het grootste element aan de onderkant). Bijvoorbeeld:
Vergeleken met het willekeurig kiezen van de spil:
- Het zorgt ervoor dat één algemeen geval (volledig gesorteerde gegevens) optimaal blijft.
- Het is moeilijker om te manipuleren om het ergste te geven.
- Een PRNG is vaak relatief traag.
Dat tweede punt verdient waarschijnlijk wat meer uitleg. Als je de voor de hand liggende (rand()) generator voor willekeurige getallen hebt gebruikt, is het vrij eenvoudig (in veel gevallen in ieder geval) voor iemand om de elementen te ordenen, zodat het voortdurend slechte pivots kiest. Dit kan een ernstige zorg zijn voor zoiets als een webserver die gegevens sorteert die zijn ingevoerd door een potentiële aanvaller, die een DoS-aanval zou kunnen uitvoeren door uw server veel tijd te laten verspillen aan het sorteren van de gegevens. In een dergelijk geval zoueen echt willekeurige seed kunnen worden gebruikt, of u kunt uw eigen PRNG opnemen in plaats van rand() — of u gebruikt Mediaan van drie, wat ook de andere voordelen heeft genoemd.
Aan de andere kant, als u een generator gebruikt die voldoende willekeurig is (bijv. een hardwaregenerator of versleuteling in de tellermodus), is het waarschijnlijk meermoeilijk om een slechte zaak te forceren dan voor een mediaan van drie selectie. Tegelijkertijd heeft het bereiken van dat niveau van willekeur meestal nogal wat eigen overhead, dus tenzij je echt verwacht dat je in dit geval wordt aangevallen, is het waarschijnlijk niet de moeite waard (en als je dat doet, is het waarschijnlijk de moeite waard om op zijn minst een alternatief dat O(N log N) in het slechtste geval garandeert, zoals een merge sort of heap sort.
Antwoord 2, autoriteit 39%
Denk sneller… C voorbeeld….
int medianThree(int a, int b, int c) {
if ((a > b) ^ (a > c))
return a;
else if ((b < a) ^ (b < c))
return b;
else
return c;
}
Dit gebruikt de bitsgewijze XOR-operator. Dus je zou lezen:
- Is
agroter dan uitsluitend een van de andere?return a - Is
bkleiner dan uitsluitend een van de andere?return b - Als geen van bovenstaande:
return c
Merk op dat door de vergelijking voor bom te schakelen, de methode ook alle gevallen dekt waarin sommige invoer gelijk is. Ook op die manier herhalen we dezelfde vergelijking a > bis hetzelfde als b < a, slimme compilers kunnen dat hergebruiken en optimaliseren.
De mediaanbenadering is sneller omdat dit zou leiden tot een meer gelijkmatige verdeling in de array, aangezien de verdeling is gebaseerd op de spilwaarde.
In het ergste geval zou je met een willekeurige keuze of een vaste keuze elke array opdelen in een array die alleen de spil bevat en een andere array met de rest, wat leidt tot een O(n²) complexiteit.
Als u de mediaanbenadering gebruikt, zorgt u ervoor dat dit niet gebeurt, maar introduceert u een overhead voor het berekenen van de mediaan.
BEWERKEN:
Benchmarksresultaten laten zien dat XOR32 keer sneller is dan Biggerhoewel ik Groter een beetje heb geoptimaliseerd:
Je moet niet vergeten dat XOReigenlijk een zeer eenvoudige operator is van de rekenkundige logische eenheid (ALU) van de CPU, en hoewel het in C misschien een beetje hacky lijkt, is het onder de motorkap aan het compileren naar de zeer efficiënte XORmontage-operator.
Antwoord 3, autoriteit 35%
Een implementatie van Median of Three die ik heb gevonden, werkt goed in mijn snelle soorten.
(Python)
# Get the median of three of the array, changing the array as you do.
# arr = Data Structure (List)
# left = Left most index into list to find MOT on.
# right = Right most index into list to find MOT on
def MedianOfThree(arr, left, right):
mid = (left + right)/2
if arr[right] < arr[left]:
Swap(arr, left, right)
if arr[mid] < arr[left]:
Swap(arr, mid, left)
if arr[right] < arr[mid]:
Swap(arr, right, mid)
return mid
# Generic Swap for manipulating list data.
def Swap(arr, left, right):
temp = arr[left]
arr[left] = arr[right]
arr[right] = temp
Antwoord 4, autoriteit 13%
De common/vanilla quicksortselecteert als pivot het meest rechtse element. Dit heeft tot gevolg dat het voor een aantal gevallen pathologische prestatie O(N²) vertoont. Met name de gesorteerde en omgekeerd gesorteerde collecties. In beide gevallen is het meest rechtse element het slechtst mogelijke element om als spil te selecteren. De spil wordt volgens mij idealiter in het midden van de scheidingswand geplaatst. De partitionering wordt verondersteld de gegevens met de spil in twee secties te splitsen, een lage en een hoge sectie. Het lage gedeelte is lager dan het draaipunt, het hoge gedeelte is hoger.
Mediaan-van-driepivot-selectie:
- selecteer het meest linkse, middelste en meest rechtse element
- bestel ze in de linker partitie, pivot en rechter partitie. Gebruik de pivot op dezelfde manier als gewone quicksort.
De veelvoorkomende pathologieën O(N²) van gesorteerde/omgekeerd gesorteerde invoer worden hierdoor verzacht. Het is nog steeds gemakkelijk om pathologische inputs te creëren voor mediaan-van-drie. Maar het is een geconstrueerd en kwaadaardig gebruik. Geen natuurlijke volgorde.
Gerandomiseerdepivot:
- selecteer een willekeurige pivot. Gebruik dit als een normaal spilelement.
Indien willekeurig, vertoont dit geen pathologisch O(N²)-gedrag. De willekeurige spil is meestal zeer waarschijnlijk rekenintensief voor een generieke soort en als zodanig ongewenst. En als het niet willekeurig is (d.w.z. srand(0); , rand(), voorspelbaar en kwetsbaar voor dezelfde O(N²)-exploitatie als hierboven.
Merk op dat de willekeurige draaipunt niet profiteren van het selecteren van meer dan één element. Vooral omdat het effect van de mediaan al intrinsiek is, en een willekeurige waarde is meer rekenkundig intensief dan het bestellen van twee elementen.
Antwoord 5, Autoriteit 11%
Denk eenvoudig … Python Voorbeeld ….
Def grotere (A, B): # Vind de grotere van twee cijfers ...
Als A & GT; B:
Retourneer een
anders:
retour b
DEF GROOTSTE (A, B, C): # Vind de grootste van drie nummers ...
Retourneer groter (A, grotere (B, C))
Def Median (A, B, C): #Just Dance!
x = grootste (a, b, c)
Als x == A:
Retourneer groter (B, C)
Als x == B:
Retourneer groter (A, C)
anders:
Retourneer groter (A, B)
Antwoord 6, Autoriteit 9%
Deze strategie bestaat uit het bepalen van drie getallen determistisch of willekeurig en gebruik dan hun mediaan als draaipunt.
Dit zou beter zijn omdat het de kans op het vinden van “slechte” draaipelen vermindert.
Antwoord 7, Autoriteit 7%
We kunnen de strategie van mediaan van drie door een voorbeeld begrijpen, veronderstel dat we een array krijgen:
[8, 2, 4, 5, 7, 1]
Dus het meest linkse element is 8en het meest rechtse element is 1. Het middelste element is 4, aangezien voor elke reeks lengte 2K , de K TH-element kiezen.
En dan sorteren we deze drie elementen in oplopende volgorde of aflopende volgorde die ons geeft:
[1, 4, 8]
Dus de mediaan is 4. En we gebruiken 4als onze draaipunt.
Aan de implementatiezijde kunnen we:
// javascript
function findMedianOfThree(array) {
var len = array.length;
var firstElement = array[0];
var lastElement = array[len-1];
var middleIndex = len%2 ? (len-1)/2 : (len/2)-1;
var middleElement = array[middleIndex];
var sortedArray = [firstElement, lastElement, middleElement].sort(function(a, b) {
return a < b; //descending order in this case
});
return sortedArray[1];
}
Nog een manier om te implementeren is geïnspireerd door @kwl, en ik wil het een beetje duidelijker uitleggen:
// javascript
function findMedian(first, second, third) {
if ((second - first) * (third - first) < 0) {
return first;
}else if ((first - second) * (third - second) < 0) {
return second;
}else if ((first - third)*(second - third) < 0) {
return third;
}
}
function findMedianOfThree(array) {
var len = array.length;
var firstElement = array[0];
var lastElement = array[len-1];
var middleIndex = len%2 ? (len-1)/2 : (len/2)-1;
var middleElement = array[middleIndex];
var medianValue = findMedian(firstElement, lastElement, middleElement);
return medianValue;
}
Overweeg de functie findMedian, eerste element zal alleen terugkeren wanneer second Element > first Element > third Elementen third Element > first Element > second Element, en in beide gevallen: (second - first) * (third - first) < 0, dezelfde redenering van toepassing op de resterende twee gevallen.
Het voordeel van het gebruik van de tweede implementatie is dat het een betere looptijd kan hebben.
Antwoord 8
Ik denk dat het opnieuw rangschikken van de waarden in de array is niet nodig voor slechts drie waarden. Vergelijk ze allemaal door af te trekken; Dan kunt u beslissen welke de mediane waarde is:
// javascript:
var median_of_3 = function(a, b, c) {
return ((a-b)*(b-c) > -1 ? b : ((a-b)*(a-c) < 1 ? a : c));
}