Scala 中两个字符串的差异

Question

假设我正在写 diff(s1: String, s2: String): List[String] 来检查 s1 == s2 和 return 错误列表：

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

你会怎么写？

P.S。我这样写 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(a: String, b: String): List[String] = {
  @annotation.tailrec
  def loop(l: List[Char], r: List[Char], res: List[String]): List[String] =
    (l, r) match {
      case (Nil, Nil) =>
        res.reverse
      case (undef, Nil) =>
        res.reverse ++ undef.map(c => s"$c is undefined")
      case (Nil, miss) =>
        res.reverse ++ miss.map(c => s"$c is missing")
      case (lh :: lt, rh :: rt) if lh != rh =>
        loop(lt, rt, s"$lh != $rh" +: res)
      case (_ :: lt, _ :: rt) =>
        loop(lt, rt, res)
    }

  loop(a.toList, b.toList, Nil)
}

我个人认为这比使用 Option/zipAll/flatMap 更明显，但这显然是个人喜好问题，也是您碰巧熟悉的问题。我认为这更灵活，因为例如，它可以很容易地修改为所有 undefined/missing 个字符生成一个错误字符串。

如果效率很重要，那么此版本使用 Iterator 来避免创建临时列表，并使用嵌套 if/else 而不是 match:

def diff(a: String, b: String): List[String] = {
  val l = a.toIterator
  val r = b.toIterator

  @annotation.tailrec
  def loop(res: List[String]): List[String] =
    if (l.isEmpty) {
      res.reverse ++ r.map(c => s"$c is missing")
    } else {
      if (r.isEmpty) {
        res.reverse ++ l.map(c => s"$c is undefined")
      } else {
        val lhead = l.next()
        val rhead = r.next()

        if (lhead == rhead) {
          loop(res)
        } else {
          loop(s"$lhead != $rhead" +: res)
        }
      }
    }

  loop(Nil)
}

感谢 Brian McCutchon 指出使用 String 而不是 List[Char] 的问题，感谢 Andrey Tyukin 鼓励我 post 一个更有效的解决方案。

原回答

递归实现并不太可怕：

def diff(a: String, b: String): List[String] = {
  @annotation.tailrec
  def loop(l: String, r: String, res: List[String]) : List[String] = (l, r) match {
    case ("", "") =>
      res
    case (lrem, "") =>
      res ++ lrem.map(c => s"$c is undefined")
    case ("", rrem) =>
      res ++ rrem.map(c => s"$c is missing")
    case _ if l.head != r.head =>
      loop(l.tail, r.tail, res :+ s"${l.head} != ${r.head}")
    case _ =>
      loop(l.tail, r.tail, res)
  }

 loop(a, b, Nil)
}

这应该执行正常，除非有很多错误，在这种情况下追加到 res 会变得昂贵。您可以通过在 res 之前添加然后在最后反转（如有必要）来解决此问题，但这会使代码不那么清晰。

Answer 2

简洁一点

首先，这是我如何立即实施此方法：

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
}

您可以通过提示大小等方式使稍微更快。[更新：我继续并添加了这个]，但这个版本可能非常接近优化，而且我也发现它非常可读——在我看来，它不像我上面的简短实现或你的原始实现那样清晰，但我发现它比另一个答案中的递归实现要好得多。

请注意，此 returns 是 IndexedSeq，而不是 List。在此它遵循您的原始实现，而不是您第一句话中的签名。如果您需要 List，您只需将 Vector.newBuilder 更改为 List.newBuilder，但在大多数情况下矢量版本可能会更快一些。

基准

我们可以整天推测性能，但是运行一些快速的 JMH 微基准测试非常容易，我们不妨这样做（完整来源 here）。我将以下面的一对字符串为例：

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

我们可以为您的原始版本（按原样返回 List）、我的简洁版本、我的快速版本（同时返回 IndexedSeq 和 [=16] 测量此输入的吞吐量=]), 和蒂姆的递归版本:

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

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

Scala 中两个字符串的差异

Diff of two strings in Scala

string

collections

diff

scala

原回答

简洁一点

效率高一点

基准