algorithm - Scala:测试数组中等间隔频率的惯用方法是什么？

Question

我有一个 Scala 应用程序并且有以下用例。给出 numberOfDates: Int和一个 optimalFrequencyInDays: Int我需要以天为单位找到最接近此最佳频率的天数频率，以便在此天数内给我均匀间隔的触发器。作为额外条件，触发器也必须在开始和结束时发生；此外，任何两次触发之间的天数不能小于最佳频率，例如

val numberOfDays = 260
val optimalFrequencyInDays = 2
// equally spaced answer is 3 i.e. 87 triggers Seq(0, 3, 6, 9, .. , 255, 259)

val numberOfDays = 260
val optimalFrequencyInDays = 124
// equally spaced answer is 130 i.e. 3 triggers Seq(0, 130, 259)

我认为解决这个问题的规则是:

val solution = (numberOfDates % optimalFrequencyInDays ) match {
  case 0 => numberOfDates / (((numberOfDates / optimalFrequencyInDays) / 2) + 1)
  case _ => numberOfDates / (((numberOfDates / optimalFrequencyInDays + 1) / 2) + 1)
}

换句话说，公式(length / 2 + 1)给了我奇数的范围，这些奇数将产生我需要一个均匀间隔的解决方案的触发器数量，例如20 将是​​ 20 / 2 + 1 = 11, 9, 7, 5, 3, 2如果我将长度除以该公式的结果，我将得到我需要的均匀间隔的频率。

此用例的输出被编码为 Array(1, 0, 0, 1, ..., 1, 0, 0, 1) 形式的 bool 数组。意思是在该指数的当天是否有触发因素。什么是惯用的 Scala 方法来测试触发器是否等距，除了最后一个可以等距 +- 1，因为没有完美契合。

Answer 1

您有一个 1 和 0 的集合，您想要测试 1 是否均匀分布，除了可能是异常值的最终间距。

triggers.mkString        // one long string of 0's and 1's
        .split("(?=1)")  // multiple strings, all starting with '1'
        .dropRight(2)    // drop the final `1` and the possible outlier
        .sliding(2)      // pair up the rest
        .forall{         // all the same?
           case Array(a,b) => a == b
           case Array(_) => true  // too few to matter
        }

这将处理一个空的 triggers 集合以及一个或多个 1 的集合(没有 0)。

更新

这将与 Array[Boolean] 一起工作，通过将其映射到 Array[Int] 或通过更改 split() > 模式到 split("(?=true)")。

您可以通过在 split() 之后保存中间集合并针对其 测试其 head 来测试“离群值”的差一条件>init.last.