在没有外部存储的情况下就地合并

本文关键字：情况下 合并 存储 外部 | 更新日期: 2023-09-27 18:25:14

我想将两个具有排序值的数组合并为一个。由于两个源阵列都存储为大型阵列的后续部分，我想知道您是否知道将它们合并到大型存储中的方法。意味着就地合并。

我找到的所有方法都需要一些外部存储。它们通常需要sqrt（n）临时数组。没有它有有效的方法吗？

我正在使用C#。也欢迎使用其他语言。提前感谢！

在没有外部存储的情况下就地合并

AFAIK，如果不显著增加元素的必要比较和移动次数，合并两个（甚至排序的）数组就无法就地工作。请参阅：merge-sort。然而，存在阻塞的变体，它们能够通过使用长度为sqrt（n）的临时数组对长度为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，具体取决于哪种排序在实践中具有更好的性能。请注意，硬件架构问题意味着实际性能比较可能与大O分析的结果非常不同。

实际上，您需要在实际的硬件/OS平台上使用不同的排序算法对其进行配置。

注意：我在这个答案中并不是试图给出一个学术性的答案，我是在假设你试图解决一个真正的问题的情况下给出一个实用的答案。

不要关心外部存储。sqrt（n）或更大的值不应该损害您的性能。您只需要确保存储池已池化。尤其是对于大数据。尤其是将它们合并为循环。否则，GC将承受压力，并占用相当大一部分CPU时间/内存带宽。

相关文章：