이것은 내 previous question의 후속 조치입니다.zip을 사용하여 스칼라의 두 문자열 사이의 차이 찾기
두 문자열을 조작하면 (예 : 가장 긴 공통 접두어를 얻고 두 문자열 간의 차이를 계산하는 등) zip (예 : (s1 zip s2)...)을 사용하는 경향이 있다는 것을 알게되었습니다.
멋지지만 비효율적 일 수 있습니다 (필수 코드와 비교하여). 맞습니까? 아마도 성능이 중요 할 경우 명령형 알고리즘을 사용해야합니다.
이제 두 개의 문자열이 다른지 확인하려고합니다. 당신은 zip을 사용하는 것이 좋겠습니까?
튜플을 만들 필요가 없기 때문에 (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)
fold-with-escape 절없이 LCP를 계산하기 위해 명령형 또는 재귀 적 기능 코드를 작성하는 것만큼이나 논란의 여지가 있습니다.
그러나 매번 저급 문자열을 수작업으로 작성하는 것만 큼 빨라야합니다. (벌금은 (작은) LcpFind 개체를 매번 생성해야하며, 호출간에 result을 0으로 재설정하여 다시 사용하거나 StrFold 및 strfold을 구현하여 reset 메서드를 호출하고 호출 할 수 있습니다. 입력 매개 변수는 zero이며 별도의 result 메서드가 있습니다.
네, 두 가지 이유로 효율성이 떨어집니다.
더 짧은 문자열과 같은 길이의 문자 목록을 만듭니다. 원래의 두 문자열보다 훨씬 많은 공간이 필요합니다. 가장 긴 공통 접두사를 찾거나 한 문자에서 문자열이 다른지 확인하는 일반적인 방법은 어떤 추가 메모리도이 필요하지 않습니다.
LCP를 찾을 때 반드시 전체 문자열을 반복 할 필요는 없습니다. zip이 필요하기 때문에 처음에는 압축하는 것이 덜 효율적입니다.
그러나 이것은 명령형 알고리즘을 사용해야한다는 것을 의미하지는 않습니다. 일반 꼬리 재귀 함수형 알고리즘도 마찬가지로 수행됩니다.
멋지지만 비효율적입니다 (명령형 코드와 비교하여).
복사한다 모두 입력하므로 긴 공통 프리픽스는 O (1)에 기억 될 수 찾는 시간 동안은 (N) O 스페이스 효과적이다. 또한 O (len (LCP)) 시간이 충분하지만 (최악의 경우 O (n) 시간이지만) 메모리 할당을 수행하는 동안 O (n) 시간이 걸립니다. 그건 비싼 수술입니다.
이제 두 문자열이 정확히 한 문자가 다른지 확인하려고합니다. 당신은
zip을 사용하는 것이 좋겠습니까?
문자열의 길이와 성능이 중요한지 여부에 따라 다릅니다. 첫 번째 촬영에서는 zip을 사용하는 것이 좋습니다.
zip을 수행 할 때 view을 사용하면 지연 평가를받을 수 있습니다 (취할 항목 만 압축하므로).