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

Ответ 1

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

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

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

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

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

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

Ответ 2

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

(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    

Ответ 3

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

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

Ответ 4

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

Средний шаг:

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

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

Рандомизированный стержень:

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

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

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

Ответ 5

Подумайте просто... Пример 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)

Ответ 6

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

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

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

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

[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, те же рассуждения относятся к остальным двум случаям.

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

Ответ 7

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

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