将已排序集合合并到新的已排序集合中的最有效方法？

问题描述 投票：0回答：2

我必须将已排序的各种集合合并到一个已排序的集合中。此操作需要针对不是很大的集合（大约 5 个元素）且来源不多（可能大约 10 个）来完成，但输出应该快速计算（非阻塞服务器）。

在两个源集合的情况下，这非常简单，但是当源集合数量增加时，需要考虑不同的策略（

n
源集合，每个源集合都有
m
元素）：

  • 连接，然后排序。它具有 
    O(n*m*log(n*m))
    复杂性（快速排序 
    n*m
    元素）。
  • 扫描所有头，选择最低的，将其推送到目标集合。我猜它有
    O(n*n*m)
    复杂度（扫描
    n
    头
    n*m
    次，即元素总数）。
  • 线性地成对合并集合，直到只有一个集合，例如
    Merge(c3,Merge(c2,Merge(c1,c0)))
    。我猜它也有 
    O(n*n*m)
    的复杂性（进行 
    n-1
    合并阶段，每个阶段最多有 
    n*m
    个元素）。
  • 对相同大小的对进行平衡合并，例如
    Merge(Merge(c3,c2),Merge(c1,c0))
    。在这种情况下，我们有 
    log2(n)
    级合并，在每个级别中，我们将集合数量减半，但元素数量加倍，因此应该是 
    O(log(n)*n*m)
    。
  • 将集合保留在最小堆中（使用头作为键），删除最小堆并在每一步中使用下一个头重新添加集合。我猜这有
    O(log(n)*n*m)
    （堆删除和插入操作是
    log(n)
    ，并且完成了
    n*m
    次）。

因此，每次基于堆的复杂选择最小元素的计算复杂度（如果我没有犯任何错误）似乎是最好的。从内存角度来看，堆可能对垃圾收集器更友好，因为它不需要那么多中间临时收集。

我是否错过了什么（计算复杂性时出错或错过任何替代方法）？我的实现很可能是用 Javascript 或 Scala 完成的，因此欢迎任何可能适用于这些执行环境的运行时问题！

顺便说一句，这是不相关：合并集合保持顺序的最有效方法？

javascript algorithm scala sorting merge
2个回答
3
投票

由于您的数据集很小，因此您的渐近考虑因素几乎无关紧要（尽管是正确的），因为更重要的因素将是微优化。我建议您至少比较以下选项，按照实施它们所需的努力的顺序递增：

  • 连接并仅使用内置排序算法。这很好，因为对于短数组来说它可能非常快，而且对于 Javascript，它是用宿主语言编写的，并且可能比任何给定的纯 JS 解决方案快得多（即使使用 JIT 编译）
  • 连接并使用插入排序。下降次数是
    O(k)
    。对于 5 个大小均为 10 的列表，
    k
    最坏的情况是 1000。但实际上它会少得多。您甚至可以防止最坏的情况，例如按照增加第一个元素的顺序对列表进行预排序，或者只是随机化顺序。
  • 将源分为两组，将每组连接起来并使用插入排序对它们进行排序（对于 25 个元素，插入排序可能是整体最快的比较排序），然后合并结果。
  • 对于 10 个源，以二叉树方式合并它们（将 1 与 2、3 与 4 等合并，然后对大小为 20 的结果列表重复）。本质上，这只是合并排序的第二阶段

这些是一般性建议。根据您的数据集，可能有更好的定制选项。例如，如果输入的数字足够小，请使用计数排序。也许对较大的数字使用基数排序，但这可能不会比插入排序提供更快的速度。如果输入中有任何模式，请利用它。

2
投票

tl；博士

合并。

完整版

没有什么比测试更好的了。

假设您的基础集合是 

List
。我们将它们存储在 
Array
.

val test = Array(
  List("alpha", "beta", "gamma", "delta", "epsilon"),
  List("one", "two", "three", "four", "five", "six"),
  List("baby", "child", "adult", "senior"),
  List("red", "yellow", "green"),
  List("red", "orange", "yellow", "green", "blue", "indigo", "violet"),
  List("tabby", "siamese", "manx", "persian"),
  List("collie", "boxer", "bulldog", "rottweiler", "poodle", "terrier"),
  List("budgie", "cockatiel", "macaw", "galah", "cockatoo"),
  List("Alabama", "California", "Georgia", "Maine", "Texas", "Vermont", "Wyoming"),
  List("I", "have", "to", "merge", "into")
).map(_.sorted)

那么您最初的想法可能就是压平和排序。

scala> val ans = th.pbench{ test.flatten.sorted.toList }
Benchmark (20460 calls in 183.2 ms)
  Time:    8.246 us   95% CI 8.141 us - 8.351 us   (n=18)
  Garbage: 390.6 ns   (n=1 sweeps measured)
ans: List[String] = List(Alabama, California, Georgia, I, Maine, ...)

或者您可以实现自定义的展平和排序：

def flat(ss: Array[List[String]], i0: Int, i1: Int): Array[String] = {
  var n = 0
  var i = i0
  while (i < i1) {
    n += ss(i).length
    i += 1
  }
  val a = new Array[String](n)
  var j = 0
  i = i0
  while (i < i1) {
    var s = ss(i)
    while (s ne Nil) {
      a(j) = s.head
      j += 1
      s = s.tail
    }
    i += 1
  }
  a
}

def mrg(ss: Array[List[String]]): List[String] = {
  val a = flat(ss, 0, ss.length)
  java.util.Arrays.sort(a, new java.util.Comparator[String]{
    def compare(x: String, y: String) = x.compare(y)
  })
  a.toList
}

scala> val ans = th.pbench{ mrg(test) }
Benchmark (20460 calls in 151.7 ms)
  Time:    6.883 us   95% CI 6.850 us - 6.915 us   (n=18)
  Garbage: 293.0 ns   (n=1 sweeps measured)
ans: List[String] = List(Alabama, California, Georgia, I, Maine, ...)

或者自定义成对合并

def mer(s1: List[String], s2: List[String]): List[String] = {
  var s3 = List.newBuilder[String]
  var i1 = s1
  var i2 = s2
  while (true) {
    if (i2.head < i1.head) {
      s3 += i2.head
      i2 = i2.tail
      if (i2 eq Nil) {
        do {
          s3 += i1.head
          i1 = i1.tail
        } while (i1 ne Nil)
        return s3.result
      }
    }
    else {
      s3 += i1.head
      i1 = i1.tail
      if (i1 eq Nil) {
        do {
          s3 += i2.head
          i2 = i2.tail
        } while (i2 ne Nil)
        return s3.result
      }
    }
  }
  Nil  // Should never get here
}

接下来是分而治之的策略

def mge(ss: Array[List[String]]): List[String] = {
  var n = ss.length
  val a = java.util.Arrays.copyOf(ss, ss.length)
  while (n > 1) {
    var i,j = 0
    while (i < n) {
      a(j) = if (i+1 < n) mer(a(i), a(i+1)) else a(i)
      i += 2
      j += 1
    }
    n = j
  }
  a(0)
}

然后你就看到了

scala> val ans = th.pbench{ mge(test) }
Benchmark (40940 calls in 141.1 ms)
  Time:    2.806 us   95% CI 2.731 us - 2.882 us   (n=19)
  Garbage: 146.5 ns   (n=1 sweeps measured)
ans: List[String] = List(Alabama, California, Georgia, I, Maine, ...)

那么，就这样吧。对于您指定的大小的数据，以及使用列表（非常干净地合并），一个好的选择确实是分治合并。 （由于维护堆的额外复杂性，堆可能不会更好，甚至可能更糟；出于同样的原因，堆排序往往比合并排序慢。）

（注意：

th.pbench
是对我的微基准测试实用程序的调用，
Thyme
。）

一些额外的建议涉及插入排序：

def inst(xs: Array[String]): Array[String] = {
  var i = 1
  while (i < xs.length) {
    val x = xs(i)
    var j = i
    while (j > 0 && xs(j-1) > x) {
      xs(j) = xs(j-1)
      j -= 1
    }
    xs(j) = x
    i += 1
  }
  xs
}

但是这些与合并排序相比，无论是一次扫描都没有竞争力：

scala> val ans = th.pbench( inst(flat(test, 0, test.length)).toList )
Benchmark (20460 calls in 139.2 ms)
  Time:    6.601 us   95% CI 6.414 us - 6.788 us   (n=19)
  Garbage: 293.0 ns   (n=1 sweeps measured)
ans: List[String] = List(Alabama, California, Georgia, I, Maine, ...)

或两个：

scala> th.pbench( mer(inst(flat(test, 0, test.length/2)).toList,
                      inst(flat(test, test.length/2,test.length)).toList) )
Benchmark (20460 calls in 119.3 ms)
  Time:    5.407 us   95% CI 5.244 us - 5.570 us   (n=20)
  Garbage: 390.6 ns   (n=1 sweeps measured)
res25: List[String] = List(Alabama, California, Georgia, I, Maine,
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.