将Scala范围拆分为均匀大小的连续子范围

浮点方法

一种方法是为每个桶生成一个小数(浮点)偏移量,然后通过压缩将它们转换为整数范围.空范围也需要过滤掉使用collect.

def splitRange(r: Range, chunks: Int): Seq[Range] = {
  require(r.step == 1, "Range must have step size equal to 1")
  require(chunks >= 1, "Must ask for at least 1 chunk")

  val m = r.length.toDouble
  val chunkSize = m / chunks
  val bins = (0 to chunks).map { x => math.round((x.toDouble * m) / chunks).toInt }
  val pairs = bins zip (bins.tail)
  pairs.collect { case (a, b) if b > a => a to b }
}

(该解决方案的第一个版本存在舍入问题,无法处理Int.MaxValue- 现在已基于Rex Kerr的递归浮点解决方案进行修复)

另一个浮点方法是递减范围,每次都偏离范围,所以我们不能错过任何元素.此版本可以Int.MaxValue正确处理.

def splitRange(r: Range, chunks: Int): Seq[Range] = {
  require(r.step == 1, "Range must have step size equal to 1")
  require(chunks >= 1, "Must ask for at least 1 chunk")

  val chunkSize = r.length.toDouble / chunks

  def go(i: Int, r: Range, delta: Double, acc: List[Range]): List[Range] = {  
    if (i == chunks) r :: acc 
      // ensures the last chunk has all remaining values, even if error accumulates
    else {
      val s = delta + chunkSize
      val (chunk, rest) = r.splitAt(s.toInt)
      go(i + 1, rest, s - s.toInt, if (chunk.length > 0) chunk :: acc else acc)
    }
  }

  go(1, r, 0.0D, Nil).reverse
} 

也可以递归来生成(开始,结束)对,而不是压缩它们.这是根据Rex Kerr 对类似问题的回答改编的

def splitRange(r: Range, chunks: Int): Seq[Range] = {
  require(r.step == 1, "Range must have step size equal to 1")
  require(chunks >= 1, "Must ask for at least 1 chunk")

  val m = r.length
  val bins = (0 to chunks).map { x => math.round((x.toDouble * m) / chunks).toInt }
  def snip(r: Range, ns: Seq[Int], got: Vector[Range]): Vector[Range] = {
    if (ns.length < 2) got
    else {
      val (i, j) = (ns.head, ns.tail.head)
      snip(r.drop(j - i), ns.tail, got :+ r.take(j - i))
    }
  }
 snip(r, bins, Vector.empty).filter(_.length > 0)
}

整数方法

最后,我意识到这可以通过调整Bresenham的线绘制算法来完成纯粹的整数运算,它解决了一个基本上等效的问题 - 如何在y行中均匀分配x像素,只使用整数运算!

我最初使用var和将伪代码转换为命令式解决方案ArrayBuffer,然后将其转换为尾递归解决方案:

def splitRange(r: Range, chunks: Int): List[Range] = {
  require(r.step == 1, "Range must have step size equal to 1")
  require(chunks >= 1, "Must ask for at least 1 chunk")

  val dy = r.length
  val dx = chunks

  @tailrec
  def go(y0:Int, y:Int, d:Int, ch:Int, acc: List[Range]):List[Range] = {
    if (ch == 0) acc
    else {
      if (d > 0) go(y0, y-1, d-dx, ch, acc)
      else go(y-1, y, d+dy, ch-1, if (y > y0) acc 
                                  else (y to y0) :: acc)
    }
  }

  go(r.end, r.end, dy - dx, chunks, Nil)
}

请参阅维基百科链接以获得完整的解释,但基本上该算法曲折线的斜率,或者添加y范围dy并减去x范围dx.如果它们没有精确划分,则会累积误差直到它精确分割,从而导致某些子范围中的额外像素.

splitRange(3 to 15, 5)                         
//> List(Range(3, 4), Range(5, 6, 7), Range(8, 9), 
//|      Range(10, 11, 12), Range(13, 14, 15))