стратегия трех значений

Question

Какова медиана из трех стратегий для выбора значения разворота в быстрой сортировке?

Я читаю это в Интернете, но не могу понять, что именно это?А также, как это лучше, чем рандомизированная быстрая сортировка.

Answer 1

В медиане трех вы смотрите на первый, средний и последний элементы массива и выбираете медиану этих трех элементов в качестве оси.

Чтобы получить «полный эффект» медианыиз трех, это также важно, чтобы рода эти три элемента, а не просто использовать медиану как стержень - это не влияет на то, что выбрано в качестве оси поворота в текущей итерации, но может / будет влиять на то, что используетсякак стержень в следующем рекурсивном вызове, который помогает ограничить плохое поведение для нескольких начальных упорядочений (во многих случаях, который оказывается особенно плохим, это отсортированный массив, за исключением наличия наименьшего элемента в верхнем концемассив (или самый большой элемент в нижнем конце). Например:

По сравнению со случайным выбором стержня:

1. Это гарантирует, что один общий случай (полностью отсортированные данные) остается оптимальным.
2. Сложнее манипулировать, чтобы выдать наихудший случай.
3. ГСЧ часто бывает относительно медленным.

Этот второй пункт, вероятно, имеет немного больше объяснений.Если вы использовали очевидный (rand()) генератор случайных чисел, то довольно легко (во всяком случае, во всяком случае) для кого-то расположить элементы так, что он будет постоянно выбирать плохие опорные точки.Это может быть серьезной проблемой для чего-то вроде веб-сервера, который может сортировать данные, введенные потенциальным злоумышленником, который может организовать атаку DoS, заставляя ваш сервер тратить много времени на сортировку данных.В таком случае вы могли бы использовать действительно случайное начальное число, или вы могли бы включить собственный PRNG вместо использования rand () - или вы использовали Median of three, что также имеет другие упомянутые преимущества.

С другой стороны, если вы используете достаточно случайный генератор (например, аппаратный генератор или шифрование в режиме счетчика), вероятно, на больше будет трудно форсировать плохое дело, чем длямедиана трех отборов.В то же время достижение этого уровня случайности обычно имеет свои собственные издержки, поэтому, если вы действительно не ожидаете нападения в этом случае, это, вероятно, не стоит (и если вы это сделаете, то, вероятно, стоит хотя бы рассмотретьальтернатива, которая гарантирует O (N log N) в худшем случае, например сортировка слиянием или сортировка кучи.

Answer 2

Реализация Median of Three, которую я нашел, хорошо работает в моих быстрых сортировках.

(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    

Answer 3

Эта стратегия состоит в том, чтобы выбрать три числа детерминированным или случайным образом, а затем использовать их медиану в качестве точки разворота.

Это было бы лучше, потому что это уменьшает вероятность нахождения "плохих" точек.

Answer 4

Думай просто ... Пример Python ....

def bigger(a,b): #Find the bigger of two numbers ...
    if a > b:
        return a
    else:
        return b

def biggest(a,b,c): #Find the biggest of three numbers ...
    return bigger(a,bigger(b,c))

def median(a,b,c): #Just dance!
    x = biggest(a,b,c)
    if x == a:
        return bigger(b,c)
    if x == b:
        return bigger(a,c)
    else:
        return bigger(a,b)

Answer 5

Обычная / ванильная быстрая сортировка выбирает в качестве оси самый правый элемент. Это приводит к тому, что он демонстрирует патологические показатели O (N ²) для ряда случаев. В частности отсортированные и обратно отсортированные коллекции. В обоих случаях самый правый элемент является наихудшим из возможных элементов для выбора в качестве точки разворота. В идеале мне кажется, что стержень находится в середине раздела. Предполагается, что разбиение данных делит данные с помощью оси на две секции: низкую и верхнюю. Низкая секция ниже, чем ось, а верхняя секция выше.

Медиана-тройка Выбор разворота:

• выберите крайний левый, средний и правый элемент
• упорядочить их до левого раздела, центра и правого раздела. Используйте стержень так же, как обычную быструю сортировку.

Распространенные патологии O (N²) отсортированных / обратно отсортированных входов смягчаются этим. По-прежнему легко создавать патологические данные для медианы трех. Но это нецелевое и злонамеренное использование. Не естественный порядок.

Рандомизированный пивот:

• выберите случайный пивот. Используйте это как обычный элемент поворота.

Если случайный, это не демонстрирует патологическое поведение O (N²). Случайный шарнир обычно весьма вероятен в вычислительном отношении для общего вида и как таковой нежелателен. И если это не случайно (то есть srand (0);, rand (), предсказуемо и уязвимо для того же эксплойта O (N²), как указано выше.

Обратите внимание, что случайный пивот не выигрывает от выбора более одного элемента. Главным образом потому, что влияние медианы уже присуще, а случайное значение требует больших вычислительных ресурсов, чем упорядочение двух элементов.

Answer 6

Мы можем понять стратегию медианы трех на примере, предположим, что нам дан массив:

[8, 2, 4, 5, 7, 1]

Таким образом, самый левый элемент - 8, а самый правый элемент - 1.Средний элемент равен 4, поскольку для любого массива длиной 2k мы выберем k th-й элемент.

И затем мы отсортируем эти три элемента влибо в порядке возрастания, либо в порядке убывания, что дает нам:

[1, 4, 8]

Таким образом, медиана равна 4.И мы используем 4 в качестве нашего стержня.

На стороне реализации у нас может быть:

// 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];
}

Другой способ реализовать это вдохновлен @kwrl, и я бы хотелЧтобы объяснить это немного яснее:

    // 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;
    }

Рассмотрим функцию findMedian, первый элемент будет возвращаться только тогда, когда second Element > first Element > third Element и third Element > first Element > second Element, и в обоих случаях: (second - first) * (third - first) < 0, то же самоеРассуждения применимы к оставшимся двум случаям.

Преимущество использования второй реализации в том, что она может иметь лучшее время выполнения.

Answer 7

Думайте быстрее ... C пример ....

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

Используется оператор XOR like.Таким образом, вы читаете:

• a больше, чем один из других?return a
• b больше, чем один из других?return b
• Если ничего из вышеперечисленного: return c

Срединный подход быстрее, потому что он приведет к более равномерному разделению в массиве, так как разделение основано на сводной точкезначение.

В худшем случае со случайным выбором или фиксированным выбором вы бы разбили каждый массив на массив, содержащий только сводную точку, и другой массив с остальными, что привело бы к сложности O (n²).

Используя медианный подход, вы убедитесь, что этого не произойдет, но вместо этого вы вводите накладные расходы для вычисления медианы.

РЕДАКТИРОВАТЬ:

Тесты результатыshow XOR в 24 раза быстрее, чем Bigger, хотя я немного оптимизировал Bigger:

Answer 8

Я думаю, что перестановка значений в массиве не нужна только для трех значений.Просто сравните их все, вычитая;тогда вы можете решить, какое из них является медианным значением:

// javascript:
var median_of_3 = function(a, b, c) {
    return ((a-b)*(b-c) > -1 ? b : ((a-b)*(a-c) < 1 ? a : c));
}