3

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

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

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

4

3 回答 3

4

AFAIK，合并两个（甚至排序的）数组在不显着增加必要的比较次数和元素移动的情况下无法就地工作。请参阅：合并排序。但是，存在阻塞的变体，它们能够通过使用长度为 sqrt(n) 的临时数组对长度为 n 的列表进行排序 - 正如您所写 - 通过仍然保持操作数量相当低。它还不错 - 但它也不是“什么都没有”，显然是你能得到的最好的。

对于实际情况，如果您负担得起，您最好使用临时数组来合并您的列表。

于 2012-02-20T20:05:49.003 回答
2

如果这些值存储为较大数组的后续部分，您只想对数组进行排序，然后删除相等的连续值。

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)
}

在您断定这将太慢之前，请实施它并对其进行分析。这应该需要大约十分钟。

编辑：这当然可以通过使用不同的排序而不是内置排序来改进，例如快速排序、堆排序或平滑排序，这取决于在实践中提供更好的性能。请注意，硬件架构问题意味着实际的性能比较可能与大 O 分析的结果大相径庭。

确实，您需要在实际硬件/操作系统平台上使用不同的排序算法对其进行分析。

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

于 2012-02-21T10:49:55.397 回答
2

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

于 2012-02-27T14:42:18.670 回答