Scala中相邻相似最短前缀元素分组的性能优化咨询

输入示例 #

val test: String = "1,1,12,1,1,12,13"
val test2: String = "1,1,12,1,1,12,13,1,1,12"

期望输出 #

test --> 2{1,1,12},13
test2 --> 2{1,1,12},13,2{1},12

当前实现代码 #

def shorten_prefix(pfx:String, sfx: String): (Integer, String, String) = {
  var count = 1
  var _sfx = sfx
  while (_sfx.startsWith(pfx)) {
    count = count + 1
    _sfx = _sfx.splitAt(pfx.length)._2
  }
  val _tmp =  s"$count{${pfx}}"
  (count, _tmp, _sfx)
}
def find_shortest_repr(input: String): String= {
  var possible_variants: mutable.ListBuffer[String] = new mutable.ListBuffer[String]()
  if (input.isEmpty) {
    return ""
  }

  val size = input.length
  for (i <- 1 until  size + 1){
    val (prefixes, suffixes) = input.splitAt(i)
    val (counter, shortened, new_ending) = shorten_prefix(prefixes, suffixes)

    val shortest_ending: String = find_shortest_repr(new_ending)
    val tmp = shortened ++ shortest_ending
    possible_variants += (tmp)
  }
  possible_variants.minBy(f => f.length)
}

def compress(x: String)= {
  val _tmp = find_shortest_repr(x)
  val regex = "(,\\})"
  val subst = "},"
  _tmp.replaceAll(regex, subst).dropRight(1)
}

println(compress(test))
println(compress(test2))

性能问题 #

当前递归枚举所有前缀的方案，随着输入字符串长度增加，计算量呈指数级增长，耗时急剧上升。

优化技巧与方法 #

1. 记忆化缓存 #

递归函数find_shortest_repr会重复计算相同子串的最短表示，比如不同前缀拆分后可能得到相同的new_ending子串，多次重复计算完全没必要。用哈希表缓存已计算的子串结果，避免重复递归：

import scala.collection.mutable

def find_shortest_repr(input: String, cache: mutable.HashMap[String, String]): String= {
  if (input.isEmpty) return ""
  if (cache.contains(input)) return cache(input)
  
  var possible_variants: mutable.ListBuffer[String] = new mutable.ListBuffer[String]()
  val size = input.length
  for (i <- 1 until size + 1){
    val (prefixes, suffixes) = input.splitAt(i)
    val (counter, shortened, new_ending) = shorten_prefix(prefixes, suffixes)
    val shortest_ending: String = find_shortest_repr(new_ending, cache)
    val tmp = shortened ++ shortest_ending
    possible_variants += tmp
  }
  val result = possible_variants.minBy(_.length)
  cache.put(input, result)
  result
}

def compress(x: String)= {
  val cache = mutable.HashMap[String, String]()
  val _tmp = find_shortest_repr(x, cache)
  val regex = "(,\\})"
  val subst = "},"
  _tmp.replaceAll(regex, subst).dropRight(1)
}

2. 限制前缀的有效范围 #

• 前缀长度上限：前缀长度不能超过输入字符串长度的一半，因为至少要重复一次才会有压缩收益，超过一半的前缀无法找到重复后缀，直接跳过。
• 基于元素拆分前缀：输入是逗号分隔的元素序列，先拆分为元素列表，枚举完整的元素子序列作为前缀，避免拆分到元素中间（比如不要把12拆成1和2），减少无效计算：

val elements = input.split(",").toList
// 枚举元素子序列长度，而非原始字符串字符长度
for (elemCount <- 1 to elements.length/2) {
  val prefixElems = elements.take(elemCount)
  val prefixStr = prefixElems.mkString(",")
  // 后续检测重复逻辑
}

3. 提前剪枝 #

在生成候选结果时，若当前临时字符串长度已经大于已知的最短长度，直接跳过该分支的递归计算，避免不必要的开销。比如维护一个当前最短长度变量，当shortened.length + 已知最短后缀长度超过当前最小值，就停止处理该前缀。

4. 改用动态规划代替递归 #

用动态规划数组dp[i]表示前i个元素的最短压缩结果，通过迭代计算每个位置的最优解，避免递归栈开销和重复计算：

def compressDP(input: String): String = {
  val elements = input.split(",").toList
  val n = elements.length
  val dp = Array.fill(n+1)("")
  
  for (i <- 1 to n) {
    dp(i) = elements.take(i).mkString(",")
    for (j <- 1 until i) {
      val subSeq = elements.slice(j, i)
      val subLen = subSeq.length
      var count = 1
      var pos = j - subLen
      while (pos >= 0 && elements.slice(pos, pos+subLen) == subSeq) {
        count +=1
        pos -= subLen
      }
      if (count > 1) {
        val candidate = s"$count{${subSeq.mkString(",")}},${dp(pos+subLen)}"
        if (candidate.length < dp(i).length) {
          dp(i) = candidate
        }
      }
      val candidate2 = s"${dp(j)},${elements.slice(j, i).mkString(",")}"
      if (candidate2.length < dp(i).length) {
        dp(i) = candidate2
      }
    }
  }
  dp(n).replaceAll(",}", "}").stripSuffix(",")
}

5. 优化重复前缀检测 #

当前shorten_prefix用startsWith循环检测效率低，可改用KMP算法的前缀函数，预先计算字符串的重复周期，快速判断前缀是否重复多次，减少循环次数。

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