Сортировка слиянием, инструментованных для подсчета читает и пишет


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

public void doMergeSort(int[] array)
{
    doMergeSort(array, 0, array.length - 1);
}

public void doMergeSort(int[] array, int low, int high)
{   
    // If Low Bound Is Geater/Equal Than High Bound, Child Arrays Have Been Split As Far As They Can 
    if(low < high)
    {   
        int middle = low + (high - low) / 2;

        doMergeSort(array, low, middle);
        doMergeSort(array, middle + 1, high);

        merge(array, low, middle, high);
    }
}

private void merge(int[] parentArray, int low, int middle, int high)
{
    int pIndex = low;
    int lIndex = 0;
    int rIndex = 0;

    // Declare Arrays For The First And Second Half Of The Parent Array
    int[] leftArray = new int[(middle + 1) - low];
    int[] rightArray = new int[high - middle];

    // Populate The Left/Right Arrays
    populateArray(parentArray, leftArray, low, middle);
    populateArray(parentArray, rightArray, middle + 1, high);   

    // Loop While The Left/Right Array 'Search' Indices Are Less Than The Arrays Lengths
    while(lIndex < leftArray.length && rIndex < rightArray.length)
    {
        // Check If The Left Array Value If Smaller Than The Right Array Value (Value At Respective Index)
        reads += 2;
        if(leftArray[lIndex] < rightArray[rIndex])
        {
            reads++;
            writes++;
            parentArray[pIndex] = leftArray[lIndex];

            lIndex++;
        }
        else
        {
            reads++;
            writes++;
            parentArray[pIndex] = rightArray[rIndex];

            rIndex++;
        }

        pIndex++;
    }

    // If Looped Over All Right Array Values, Populate The Rest Of The Parent Array With Left Array Values
    while(lIndex < leftArray.length)
    {
        reads++;
        writes++;
        parentArray[pIndex] = leftArray[lIndex];

        lIndex++;
        pIndex++;
    }

    // If Looped Over All Left Array Values, Populate The Rest Of The Parent Array With Right Array Values
    while(rIndex < rightArray.length)
    {
        reads++;
        writes++;
        parentArray[pIndex] = rightArray[rIndex];

        rIndex++;
        pIndex++;
    }
}

private void populateArray(int[] originalArray, int[] newArray, int start, int end)
{
    int i = 0;

    for(int j = start; j <= end; j++)
    {
        reads ++;
        writes++;
        newArray[i] = originalArray[j];

        i++;
    }
}


Комментарии
2 ответа

Незначительная "ошибка"

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

По этой причине, сравнение в merge() должно быть реализовано:

if (leftArray[lIndex] <= rightArray[rIndex])

... так что он предпочитает брать от leftArray во-первых, если есть галстук.

Для intы, это не имеет никакого практического значения, вроде стабильна, потому что два intчто равны неразличимы. Но это все еще хорошая идея, чтобы использовать <= а не < для сравнения, оставаться верными сортировка слиянием алгоритм.

Конвенции границ

В Java общепринятым нормам, чтобы указать диапазон, используя включено нижних индексов и эксклюзивные верхние индексы. Примеры этого соглашения можно увидеть в Arrays.copyOfRange(<em>original</em>, <em>from</em>, <em>to</em>) и <em>string</em>.substring(<em>beginIndex</em>, <em>endIndex</em>). Основное преимущество этой конвенции является то, что endIndex - beginIndex - количество элементов в этом диапазоне, что часто приводит к меньше ± 1 корректировки в код.

Например, с этой конвенции, вы хотели избавиться от неудобного array.length - 1 в doMergeSort()и пару экземпляров (middle + 1) в merge(). Кроме того, populateArray() бы j < end как петли условии, что более идиоматические. (Чтобы быть справедливым, вы должны изменить тест в doMergeSort() для if (low + 1 < high).)

Копирование элементов массива

populateArray() следует заменить Arrays.copyOfRange() (или, возможно, оболочку Arrays.copyOfRange() если вам нужны приборы для подсчета читает и пишет). Аналогично, петлями, чтобы скопировать остатки leftArray и rightArray элементы могут быть заменены System.arraycopy(). Оба метода не только сэкономить несколько строк кода, но также может быть немного быстрее, чем рукописный петли.

Пост-инкремент оператор удобен для обновления счетчиков индекса с меньшим количеством слов:

if (leftArray[lIndex] <= rightArray[rIndex]) {
parentArray[pIndex++] = leftArray[lIndex++];
} else {
parentArray[pIndex++] = rightArray[rIndex++];
}

В общем, я не вижу ничего, что может быть сделано о количестве операций чтения и записи, потому что это просто, как алгоритм сортировка слиянием работает. Но вы могли бы сократить код немного, и выдавить из себя крошечные (чаще незначительный) прирост производительности.

2
ответ дан 14 марта 2018 в 06:03 Источник Поделиться

Сделать выделение времени темп массива и избегая копирования в функции merge, меняя направление слияния в зависимости от уровня рекурсии для сверху вниз или снизу вверх будет пройти для ускорения сортировки слиянием. Это позволит уменьшить количество операций чтения / записи примерно в 2.

1
ответ дан 15 марта 2018 в 11:03 Источник Поделиться