Scala中两个字符串的差异

Question

假设我正在编写diff(s1: String, s2: String): List[String]以检查是否s1== s2并返回错误列表:

• s1[i] != s2[i] 错误是 s1[i] != s2[i]
• s1[i]如果i >= s2.length错误是s1[i] is undefined
• s2[i]如果i >= s1.length错误是s2[i] is missing

例如:

diff("a", "a")     // returns Nil
diff("abc", "abc") // Nil
diff("xyz", "abc") // List("x != a", "y != b", "z != c")
diff("abcd", "ab") // List("c is undefined", "d is undefined")
diff("ab", "abcd") // List("c is missing", "d is missing")
diff("", "ab")     // List("a is missing", "b is missing")  
diff("axy", "ab")  // List("x != b", "y is undefined") 

你会怎么写的？

PS我写的diff是这样的:

def compare(pair: (Option[Char], Option[Char])) = pair match { 
  case (Some(x), None)    => Some(s"$x is undefined")
  case (None, Some(y))    => Some(s"$y is missing")
  case (Some(x), Some(y)) => if (x != y) Some(s"$x != $y") else None 
  case _ => None
}

def diff(s1: String, s2: String) = {
  val os1 = s1.map(Option.apply)
  val os2 = s2.map(Option.apply)
  os1.zipAll(os2, None, None).flatMap(compare)
}

Answer 1

更简洁一点

首先,这是我如何实现这个方法:

def diff(s1: String, s2: String): List[String] =
  (s1, s2).zipped.collect {
    case (x, y) if x != y => s"$x != $y"
  }.toList ++
    s1.drop(s2.length).map(x => s"$x is undefined") ++
    s2.drop(s1.length).map(y => s"$y is missing")

它的大小只是原始实现的一半,在我看来,它至少是可读的.你可以说这个drop技巧有点过于聪明,你可能是对的,但我认为一旦你得到它就会很好看.

效率更高一点

像这样的方法是自包含的并且易于测试,并且如果有可能在性能很重要的情况下使用它,则必须考虑必要的实现.这是我如何做的快速草图:

def diffFast(s1: String, s2: String): IndexedSeq[String] = {
  val builder = Vector.newBuilder[String]

  def diff(short: String, long: String, status: String) = {
    builder.sizeHint(long.length)
    var i = 0

    while (i < short.length) {
      val x = s1.charAt(i)
      val y = s2.charAt(i)
      if (x != y) builder += s"$x != $y"
      i += 1
    }

    while (i < long.length) {
      val x = long.charAt(i)
      builder += s"$x is $status"
      i += 1
    }
  }

  if (s1.length <= s2.length) diff(s1, s2, "missing")
    else diff(s2, s1, "undefined")

  builder.result
}

您可以通过暗示大小等来更快地实现这一点.[更新:我继续并添加了这个],但这个版本可能非常接近最佳,我也觉得它很可读 - 它不是那么清晰无论是我上面的简短实现还是你的原始实现,我觉得它比其他答案中的递归实现要好得多.

请注意,这会返回一个IndexedSeq,而不是一个List.在此,它遵循您的原始实现,而不是您的第一句中的签名.如果你需要一个,List你可以Vector.newBuilder改为List.newBuilder,但对于大多数情况,矢量版本可能会快一点.

基准

我们可以推测表现了一整天,但它是如此轻松运行一些简单的江铃控股有限公司微基准,我们不妨这样做,而不是(完整的源代码在这里).我将把以下一对字符串作为一个简单的例子:

val example1: String = "a" * 1000
val example2: String = "ab" * 100

我们可以测量吞吐量该输入您的原始版本(既因为它是和返回List),我的简洁版,我的快速版本(返回都IndexedSeq和List),以及蒂姆的递归版本:

Benchmark                 Mode  Cnt       Score     Error  Units
DiffBench.checkConcise   thrpt   20   47412.127 ± 550.693  ops/s
DiffBench.checkFast      thrpt   20  108661.093 ± 371.827  ops/s
DiffBench.checkFastList  thrpt   20   91745.269 ± 157.128  ops/s
DiffBench.checkOrig      thrpt   20    8129.848 ±  59.989  ops/s
DiffBench.checkOrigList  thrpt   20    7916.637 ±  15.736  ops/s
DiffBench.checkRec       thrpt   20   62409.682 ± 580.529  ops/s

所以简而言之:就性能而言,你的原始实现真的很差(我猜的更多是因为所有的分配而不是多次遍历),我的简洁实现与(可以说是不太可读的)递归的竞争相比具有竞争力吞吐量大约是原始吞吐量的六倍,并且命令式实施的速度接近其他任何一种.