Diff двух струн в Scala - PullRequest
Новая
       13

Diff двух струн в Scala

0 голосов
/ 16 февраля 2019

Предположим, я пишу 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)
}

Ответы [ 2 ]

0 голосов
/ 17 февраля 2019

Немного более лаконично

Прежде всего, вот как я бы реализовал этот метод на макушке: 

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, что мы могли бы сделать это вместо этого (полный исходный код здесь ).В качестве простого примера я возьму следующую пару строк: 

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

Короче говоря: ваша исходная реализация действительно очень плохая, что касается производительности (яЯ догадываюсь больше из-за всех распределений, чем из нескольких обходов), моя краткая реализация конкурирует с (возможно, менее читабельной) рекурсивной и получает примерно в шесть раз большую пропускную способность, чем оригинал, а императивная реализация близка к вдвое быстреелюбой другой.

0 голосов
/ 16 февраля 2019

[см. Оригинальный ответ ниже]

Это можно сделать с помощью рекурсивного алгоритма: 

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, но это явно вопрос вкуса и того, с чем вам довелось быть знакомым.Я думаю, что это более гибко, потому что, например, его можно легко изменить, чтобы сгенерировать одну строку ошибки для всех неопределенных / пропущенных символов.

Если важна эффективность, тогда эта версия использует 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)
}

Спасибо Брайану МакКатчону за указание на проблему с использованием String вместо List[Char] и АндреюТюкина за то, что он побудил меня опубликовать более эффективное решение.

Оригинальный ответ

Рекурсивная реализация не слишком страшна: 

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, а затем, при необходимости, поменять местами в конце, но это сделает код менее понятным.

...