Используя zip, чтобы найти разницу между двумя строками в Scala

Question

Это продолжение моего предыдущего вопроса .

Я заметил, что если я манипулирую двумя строками (например, чтобы получить самый длинный общий префикс, вычисляю разницу между двумя строками и т. Д.), Я склонен использовать zip (как в (s1 zip s2)...).

Это выглядит красиво, но, вероятно, неэффективно (по сравнению с императивным кодом). Это правильно? Возможно, если производительность имеет значение, я должен использовать императивный алгоритм.

Теперь я пытаюсь выяснить, отличаются ли две строки. Вы бы порекомендовали использовать zip для этого?

Answer 1

Несколько эффективнее использовать (s1,s2).zipped, чем (s1 zip s2), поскольку вам не нужно создавать кортежи; вместо этого вы создаете функции, которые принимают два аргумента.

Еще лучше для эффективности, но не для простоты использования - это определение собственной пользовательской специализированной папки строк:

abstract class StrFold[@specialized T](var result: T) {
  def apply(c1: Char, c2: Char): Unit
  def done: Boolean
}
def strfold[@specialized T](s1: String, s2: String)(folder: StrFold[T]): T = {
  var i = 0
  val L = math.min(s1.length, s2.length)
  while (i < L) {
    folder(s1.charAt(i), s2.charAt(i))
    if (folder.done) return folder.result
    i += 1
  }
  folder.result
}

Теперь, если вы хотите найти длину самого длинного общего префикса, вы

class LcpFind extends StrFold(0) {
  var done = false
  def apply(c1: Char, c2: Char) { if (c1 == c2) result += 1 else done = true }
}
def lcp(s1: String, s2: String) = strfold(s1,s2)(new LcpFind)

Это довольно трудоемкий труд - возможно, почти такой же, как просто написание императивного или рекурсивного функционального кода для вычисления LCP без предложения сгиба с escape-выражением.

Но это должно быть почти так же быстро, как каждый раз писать низкоуровневые строки. (Единственным штрафом должно быть создание (крошечного) LcpFind объекта каждый раз, и, если вы действительно этого хотите, вы можете использовать его повторно, сбросив result на ноль между вызовами, или вы можете изменить StrFold и strfold на реализовать и вызвать метод reset, изменив входной параметр с именем zero и имея отдельный метод result.)

Answer 2

Это выглядит красиво, но, вероятно, неэффективно (по сравнению с императивным кодом).

Он копирует оба входа, поэтому он эффективно занимает пространство O ( n ), в то время как нахождение самого длинного общего префикса может быть временем в памяти O (1). Кроме того, требуется время O ( n ), тогда как времени O (len (LCP)) будет достаточно (хотя в худшем случае это время O ( n )), и он выделяет память ; это дорогая операция.

Теперь я пытаюсь выяснить, отличаются ли две строки ровно одним символом. Вы бы порекомендовали использовать zip для этого?

Зависит от длины строк и от того, насколько важна производительность. Для первого выстрела, вероятно, можно использовать zip.

Answer 3

Да, это будет менее эффективно по двум причинам.

1. Вы создаете список пар символов той же длины, что и более короткая строка. Это займет значительно больше места, чем две исходные строки. Обычные способы найти самый длинный общий префикс или проверить, отличаются ли строки одним символом, не требуют любой дополнительной памяти.

2. При поиске LCP необязательно выполнять итерацию по всем строкам. Поскольку zip действительно нужно это сделать, очевидно, будет менее эффективно сначала сжать их.

Но это не значит, что вы должны использовать императивные алгоритмы: обычный хвостовой рекурсивный функциональный алгоритм будет работать так же хорошо.

Answer 4

Вы можете использовать view, чтобы выполнять ленивый анализ при выполнении zip (поэтому он будет архивировать только то, что вы берете).