объединить на месте без внешнего хранилища - PullRequest
Новая
       35

объединить на месте без внешнего хранилища

3 голосов
/ 20 февраля 2012

Я хочу объединить два массива с отсортированными значениями в один. Поскольку оба исходных массива хранятся как последующие части большого массива, мне интересно, знаете ли вы способ их объединения в большое хранилище. Смысл в месте слияния.

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

Я использую C #. Также приветствуются другие языки. Заранее спасибо!

Ответы [ 3 ]

4 голосов
/ 21 февраля 2012

AFAIK, объединение двух (даже отсортированных) массивов не работает на месте без значительного увеличения необходимого количества сравнений и перемещений элементов.См .: сортировка слиянием .Однако существуют заблокированные варианты, которые могут сортировать список длины n, используя временные массивы длины sqrt (n), как вы написали, сохраняя при этом число операций значительно меньшим. Это неплохо, но такжене "ничего" и, очевидно, лучшее, что вы можете получить.

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

2 голосов
/ 27 февраля 2012

Не заботьтесь о внешнем хранилище.sqrt (n) или даже больше не должны вредить вашей производительности.Вам просто нужно убедиться, что хранилище объединено.Особенно для больших данных.Особенно для объединения их в петли.В противном случае GC будет перегружен и потребляет значительную часть времени вашего процессора / пропускной способности памяти.

2 голосов
/ 21 февраля 2012

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

void  SortAndDedupe(Array<T> a)
{
    // Do an efficient in-place sort
    a.Sort();
    // Now deduplicate
    int lwm = 0; // low water mark
    int hwm = 1; // High water mark
    while(hwm < a.length)
    {
        // If the lwm and hwm elements are the same, it is a duplicate entry.
        if(a[lwm] == a[hwm])
        {
            hwm++;
        }else{
            // Not a duplicate entry - move the lwm up
            // and copy down the hwm element over the gap.
            lwm++;
            if(lwm < hwm){
                a[lwm] = a[hwm];
            }
            hwm++;
        }
    }
    // New length is lwm
    // number of elements removed is (hwm-lwm-1)
}

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

Редактировать: Это, конечно, можно улучшить, используя другой тип сортировки, а не встроенный, например, Quicksort, Heapsort или Smoothsort, в зависимости от того, что дает лучшую производительность на практике. Обратите внимание, что проблемы с аппаратной архитектурой означают, что практические сравнения производительности могут очень сильно отличаться от результатов анализа большого O.

На самом деле вам нужно профилировать его с помощью различных алгоритмов сортировки на вашей реальной аппаратной платформе / платформе ОС.

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

...