Scala:如何通过分组(或Binning)获得Iterable的顶级N元素

Question

我使用了前面提到的here解决方案来高效地获得Scala的前n个元素。

最后的例子：

scala> val li = List (4, 3, 6, 7, 1, 2, 9, 5)
li: List[Int] = List(4, 3, 6, 7, 1, 2, 9, 5)

scala> top (2, li)
res0: List[Int] = List(2, 1)

现在，假设我想得到分辨率较低的前n个元素。整数的范围可以以某种方式被划分/绑定/分组到子范围，如模2：{0-1，2-3，4-5，.}，在每个子范围中，我不区分整数，例如0和1对我来说都是一样的。因此，上述示例中的顶部元素仍然是1，但下一个元素要么是2，要么是3。

scala> top (2, li)
res0: List[Int] = List(2, 1)

scala> top (2, li)
res0: List[Int] = List(3, 1)

1. 我如何改变这个很好的功能来满足这些需求？
2. 我的直觉正确吗?这种感觉应该更快吗？因为排序是在回收箱/组上，然后取下所有或部分元素，没有具体的顺序，直到我们得到n个元素。

评论：

1. 绑定/分组是一些简单而固定的东西，比如模k，不需要像允许不同长度的子范围那样是通用的。
2. 在每个垃圾箱里，假设我们只需要一些元素，我们可以只取第一个元素，甚至是一些随机元素，而不必是某个特定的系统。

Answer 1

根据评论，你只是在改变比较。

在这个版本中，4和3比较相等，4是第一个。

object Firstly extends App {

  def firstly(taking: Int, vs: List[Int]) = {
    import collection.mutable.{ SortedSet => S }

    def bucketed(i: Int) = (i + 1) / 2

    vs.foldLeft(S.empty[Int]) { (s, i) =>
      if (s.size < taking) s += i
      else if (bucketed(i) >= bucketed(s.last)) s
      else {
        s += i
        s -= s.last
      }
    }
  }

  assert(firstly(taking = 2, List(4, 6, 7, 1, 9, 3, 5)) == Set(4, 1))
}

编辑:排序桶的示例，而不是保持排序"top N"：

scala> List(4, 6, 7, 1, 9, 3, 5).groupBy(bucketed).toList.sortBy {
     | case (i, vs) => i }.flatMap {
     | case (i, vs) => vs }.take(5)
res10: List[Int] = List(1, 4, 3, 6, 5)

scala> List(4, 6, 7, 1, 9, 3, 5).groupBy(bucketed).toList.sortBy {
     | case (i, vs) => i }.map {
     | case (i, vs) => vs.head }.take(5)
res11: List[Int] = List(1, 4, 6, 7, 9)

不知道你喜欢哪一种结果，最后两种。

至于分类桶是否更好，这取决于有多少桶。

Answer 2

在使用原始算法之前，用整数除法进行映射如何？

def top(n: Int, li: List[Int]) = li.sorted.distinct.take(n)

val li = List (4, 3, 6, 7, 1, 2, 9, 5)

top(2, li) // List(1, 2)

def topBin(n: Int, bin: Int, li: List[Int]) =
  top(n, li.map(_ / bin))  // e.g. List(0, 1)
  .map(i => (i * bin) until ((i + 1) * bin))

topBin(2, 2, li)  // List(0 to 1, 2 to 3)