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

StackOverflow https://stackoverflow.com/questions/9359840

  •  28-10-2019
  •  | 
  •  

Вопрос

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

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

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

Это было полезно?

Решение

AFAIK, объединение двух (даже отсортированных) массивов не работает на месте, не значительно увеличивая необходимое количество сравнений и шагов элементов. Видеть: Сортировка слиянием. Анкет Однако существуют заблокированные варианты, которые способны сортировать список длины n, используя временные массивы Lenght SQRT (n) - как вы писали - все еще сохраняя количество операций значительно низким .. это неплохо - но также это также Не «ничего» и, очевидно, лучшее, что вы можете получить.

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

Другие советы

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

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, в зависимости от того, что дает лучшую производительность на практике. Обратите внимание, что проблемы с аппаратной архитектурой означают, что практические сравнения производительности вполне могут сильно отличаться от результатов анализа Big O.

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top