Scala中如何对数组同公共前缀项仅取最大值求和

完全不需要写两层循环，利用Scala原生集合API就可以写出时间复杂度O(n)的实现，性能和可读性都远优于双层循环写法。

实现思路 #

• 先把每个字符串拆成「前缀-浮点值」的键值对
• 直接按前缀做聚合，始终保留同前缀下的最大浮点值，不需要存同前缀的所有元素
• 最后把所有前缀对应的最大值累加即可

注意：split方法入参是正则表达式，|属于正则特殊字符，必须用双反斜杠转义写成\\|\\|才能正确匹配分隔符，否则会出现拆分错误。

推荐写法（Scala 2.13+） #

用原生groupMapReduce方法，一次遍历就完成分组+取最大值的聚合逻辑，代码最简洁：

val y = Array("Zara||6.0", "Nuha||4.0","Zara||2.0","Zara||0.1")

val sumResult = y
  .map(item => {
    // split加limit=2，避免值部分带||时拆分出错
    val Array(prefix, valueStr) = item.split("\\|\\|", 2)
    prefix -> valueStr.toDouble
  })
  // 按前缀分组，同组值聚合时直接取最大值
  .groupMapReduce(_._1)(_._2)(math.max)
  .values
  .sum

println(sumResult) // 输出10.0，符合预期

兼容旧版本Scala的写法 #

如果是2.13以下的版本，可以用foldLeft边遍历边维护每个前缀的最大值，全程只遍历一次数组，内存占用更低：

val sumResult = y
  .foldLeft(Map.empty[String, Double]) { (aggMap, item) =>
    val Array(prefix, valueStr) = item.split("\\|\\|", 2)
    val currentValue = valueStr.toDouble
    aggMap.updatedWith(prefix) {
      case Some(existMax) => Some(math.max(existMax, currentValue))
      case None => Some(currentValue)
    }
  }
  .values
  .sum

写法说明 #

• 以上两种实现的时间复杂度都是O(n)，双层循环的时间复杂度是O(n²)，数据量越大性能差距越明显
• 聚合过程中只维护每个前缀对应的当前最大值，不需要存储同前缀的所有历史值，内存开销远低于先groupBy再遍历分组取最大值的写法
• split方法加limit=2参数是鲁棒性优化，避免后续业务变更导致值部分携带||字符时出现数组越界异常

内容的提问来源于stack exchange，提问作者code