string - 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") 

你会怎么写？

附言我正在这样写 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，但是矢量版本可能会更快一些大多数情况。

基准

我们可以整天推测性能，但运行一些快速的 JMH 微基准测试非常容易，我们不妨这样做(完整来源 here)。我将以下面的一对字符串作为一个简单的例子:

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

我们可以为您的原始版本(既是原样又返回 List)测量此输入的吞吐量，我的简洁版本，我的快速版本(返回 IndexedSeq和 List)，以及 Tim 的递归版本:

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

简而言之:就性能而言，您的原始实现确实很差(我猜更多是因为所有分配而不是多次遍历)，我的简洁实现与(可以说可读性较差的)递归相比具有竞争力其中一个的吞吐量是原来的六倍，命令式实现的速度接近其他任何一个的两倍。