有效限制合并两个列表

Question

我想合并两个数组/列表，其中每个数组元素必须进行比较。如果他们两个都有相同的元素，我会将它们的总数增加1。这些数组都是2D的，其中每个元素都有一个计数器用于出现。我知道这两个数组都可以与O（n^2）中的double for for循环进行比较，但是我受O（nlogn）的限制。最终的阵列将所有来自这两个列表中的元素与其增加柜台的，如果有一个以上发生

Array A[][] = [[8,1],[5,1]] 
Array B[][] = [[2,1],[8,1]] 

合并完成后，我应该得到一个数组，像这样

Array C[][] = [[2,1],[8,2],[8,2],[5,1]] 

的元素的排列不是必须的。

从阅读材料中，Mergesort需要O(nlogn)来合并两个列表，但是我目前处于一个与我绑定的问题的障碍。任何伪代码视觉将不胜感激。

Answer 1

我很喜欢Stepanov's Efficient Programming虽然他们比较慢。在会议6和7中（如果我没有记错的话），他讨论了算法add_to_counter()和reduce_counter()。当然，这两种算法都是微不足道的，但可以用来实现非递归合并分类，而不需要太多的工作。唯一可能的非显而易见的见解是组合操作可以将两个元素减少为一个序列而不仅仅是一个元素。为了实现这些操作，您实际上将使用合适的类来存储迭代器（即数组中的指针）以表示数组的局部视图。

我还没有看过第7次会议之后的会议（实际上甚至没有完成第7次会议），但我完全认为他实际上介绍了如何使用会话7中产生的counter来实现合并-分类。当然，合并分类的运行时复杂度为O(n ln n)，使用计数器方法时，它将使用O(ln n)辅助空间。

Answer 2

您可以编写一个算法来合并它们，方法是按顺序按顺序遍历两个序列，并在适当的位置插入。

我选择一个（貌似更贴切）数据结构在这里：std::map<Value, Occurence>：

#include <map> 
using namespace std; 

using Value  = int; 
using Occurence = unsigned; 
using Histo  = map<Value, Occurence>; 

如果你坚持连续的存储，boost::flat_map<>这里应该是你的朋友（和简易替换）。

算法（与你的输入测试，阅读说明注释）：

void MergeInto(Histo& target, Histo const& other) 
{ 
    auto left_it = begin(target), left_end = end(target); 
    auto right_it = begin(other), right_end = end(other); 
    auto const& cmp = target.value_comp(); 

    while (right_it != right_end) 
    { 
     if ((left_it == left_end) || cmp(*right_it, *left_it)) 
     { 
      // insert at left_it 
      target.insert(left_it, *right_it); 
      ++right_it; // and carry on 
     } else if (cmp(*left_it, *right_it)) 
     { 
      ++left_it; // keep left_it first, so increment it 
     } else 
     { 
      // keys match! 
      left_it->second += right_it->second; 
      ++left_it; 
      ++right_it; 
     } 
    } 
} 

这真的很直截了当！

测试程序：看到它Live On Coliru

#include <iostream> 

// for debug output 
static inline std::ostream& operator<<(std::ostream& os, Histo::value_type const& v) { return os << "{" << v.first << "," << v.second << "}"; } 
static inline std::ostream& operator<<(std::ostream& os, Histo const& v) { for (auto& el : v) os << el << " "; return os; } 
// 

int main(int argc, char *argv[]) 
{ 
    Histo A { { 8, 1 }, { 5, 1 } }; 
    Histo B { { 2, 1 }, { 8, 1 } }; 

    std::cout << "A: " << A << "\n"; 
    std::cout << "B: " << B << "\n"; 

    MergeInto(A, B); 
    std::cout << "merged: " << A << "\n"; 
} 

印刷：

A: {5,1} {8,1} 
B: {2,1} {8,1} 
merged: {2,1} {5,1} {8,2} 

---

你可以洗牌接口的情况下，一点点你真的想要合并到一个新的对象（C）：

// convenience 
Histo Merge(Histo const& left, Histo const& right) 
{ 
    auto copy(left); 
    MergeInto(copy, right); 
    return copy; 
} 

现在你可以只写

Histo A { { 8, 1 }, { 5, 1 } }; 
Histo B { { 2, 1 }, { 8, 1 } }; 
auto C = Merge(A, B); 

请参阅Live on Coliru, too

Answer 3

一个简单的算法，需要两倍的内存将订购两个输入端（O（N日志N）），然后从两个列表的头部顺序选取元素并进行合并（O（n））。总的成本将是为O（n log n）的用O（n）的额外内存

Answer 4

这里（最小的两个输入额外的大小）是基于桶计数

我的算法

时间复杂度：O（N）

存储器复杂度：O（最大），其中max是阵列中的最大元件

输出： [8,2] [5,1] [2,1] [8,2]

代码：

#include <iostream> 
#include <vector> 
#include <iterator> 

int &refreshCount(std::vector<int> &counters, int in) { 
    if((counters.size() - 1) < in) { 
     counters.resize(in + 1); 
    } 
    return ++counters[in]; 
} 

void copyWithCounts(std::vector<std::pair<int, int> >::iterator it, 
        std::vector<std::pair<int, int> >::iterator end, 
        std::vector<int> &counters, 
        std::vector<std::pair<int, int&> > &result 
        ) { 
    while(it != end) { 
     int &count = refreshCount(counters, (*it).first); 
     std::pair<int, int&> element((*it).first, count); 
     result.push_back(element); 
     ++it; 
    } 
} 

void countingMerge(std::vector<std::pair<int, int> > &array1, 
        std::vector<std::pair<int, int> > &array2, 
        std::vector<std::pair<int, int&> > &result) { 
    auto array1It = array1.begin(); 
    auto array1End = array1.end(); 
    auto array2It = array2.begin(); 
    auto array2End = array2.end(); 

    std::vector<int> counters = {0}; 

    copyWithCounts(array1It, array1End, counters, result); 
    copyWithCounts(array2It, array2End, counters, result); 
} 

int main() 
{ 
    std::vector<std::pair<int, int> > array1 = {{8, 1}, {5, 1}}; 
    std::vector<std::pair<int, int> > array2 = {{2, 1}, {8, 1}}; 

    std::vector<std::pair<int, int&> > result; 
    countingMerge(array1, array2, result); 

    for(auto it = result.begin(); it != result.end(); ++it) { 
     std::cout << "[" << (*it).first << "," << (*it).second << "] "; 
    } 

    return 0; 
} 

简短说明： 因为你提到过，那最后的安排是没有必要的，我做了简单的合并（没有排序，谁要求排序？）与计数，其中结果包含对计数器的引用，所以不需要走过数组来更新计数器。