스칼라 관용적 코딩 스타일은 비효율적 인 코드 작성을위한 멋진 함정일까요?
저는 Scala 커뮤니티가 "간결한", "멋진", "스칼라 관용적" , "한 줄짜리"코드 작성에 약간 큰 집착을 가지고 있다고 생각합니다 . 이것은 즉시 Java / 명령어 / 추악한 코드와 비교됩니다.
이것은 (때때로) 코드를 이해하기 쉽게 만들지 만 99 %의 개발자에게는 비효율적 인 코드로 이어집니다. 이것이 바로 Java / C ++가 이길 수없는 부분입니다.
이 간단한 문제를 고려하십시오. 정수 목록이 주어지면 가장 큰 요소를 제거하십시오. 주문은 보존 할 필요가 없습니다.
여기에 내 버전의 솔루션이 있습니다 (가장 크지는 않을 수 있지만 평균적인 록 스타 개발자가 아닌 개발자가 수행하는 작업입니다).
def removeMaxCool(xs: List[Int]) = {
val maxIndex = xs.indexOf(xs.max);
xs.take(maxIndex) ::: xs.drop(maxIndex+1)
}
Scala 관용적이고 간결하며 몇 가지 멋진 목록 함수를 사용합니다. 또한 매우 비효율적입니다. 목록을 최소한 3-4 회 순회합니다.
여기 내 완전히 쿨하지 않은 Java와 같은 솔루션이 있습니다. 또한 합리적인 Java 개발자 (또는 Scala 초보자)가 작성하는 내용이기도합니다.
def removeMaxFast(xs: List[Int]) = {
var res = ArrayBuffer[Int]()
var max = xs.head
var first = true;
for (x <- xs) {
if (first) {
first = false;
} else {
if (x > max) {
res.append(max)
max = x
} else {
res.append(x)
}
}
}
res.toList
}
완전히 비 Scala 관용적, 비 기능적, 비 간결하지만 매우 효율적입니다. 목록을 한 번만 탐색합니다!
따라서 Java 개발자의 99 %가 Scala 개발자의 99 %보다 더 효율적인 코드를 작성하면 Scala 채택을 늘리기 위해 교차하는 데 큰 장애물이됩니다. 이 함정에서 빠져 나갈 방법이 있습니까?
구현을 명확하고 간결하게 유지하면서 이러한 "비효율적 인 함정"을 피할 수있는 실용적인 조언을 찾고 있습니다.
설명 : 이 질문은 실제 시나리오에서 비롯되었습니다. 복잡한 알고리즘을 작성해야했습니다. 먼저 Scala로 작성한 다음 Java로 다시 작성해야했습니다. Java 구현은 두 배나 길고 명확하지는 않지만 동시에 두 배나 빨랐습니다. 스칼라 코드를 효율적으로 다시 작성하려면 시간이 좀 걸리고 스칼라 내부 효율성에 대해 좀 더 깊이 이해해야합니다 (예 : 맵 대 접기 등).
질문의 오류에 대해 논의 해 보겠습니다.
따라서 Java 개발자의 99 %가 Scala 개발자의 99 %보다 더 효율적인 코드를 작성하면 Scala 채택을 늘리기 위해 교차하는 데 큰 장애물이됩니다. 이 함정에서 빠져 나갈 방법이 있습니까?
이것은 그것을 뒷받침하는 증거가 전혀없는 것으로 추정됩니다. 거짓이면 의문의 여지가 있습니다.
반대의 증거가 있습니까? 글쎄요, 질문 자체를 생각해 봅시다. 그것은 아무것도 증명하지 못하지만 상황이 명확하지 않다는 것을 보여줍니다.
완전히 비 Scala 관용적, 비 기능적, 비 간결하지만 매우 효율적입니다. 목록을 한 번만 탐색합니다!
첫 번째 문장의 네 가지 주장 중 처음 세 가지는 참이고 사용자 unknown에 의해 표시된 네 번째 주장은 거짓입니다! 그리고 그것은 왜 거짓입니까? 두 번째 문장이 말하는 것과 달리 목록을 두 번 이상 탐색하기 때문입니다.
코드는 다음 메서드를 호출합니다.
res.append(max)
res.append(x)
과
res.toList
먼저 고려해 봅시다 append.
appendvararg 매개 변수를 사용합니다. 즉max,x먼저 어떤 유형의 시퀀스 (WrappedArray실제로 는 a)로 캡슐화되고 매개 변수로 전달됩니다. 더 나은 방법은+=.알겠습니다 .에 위임하는을
append호출++=합니다+=. 그러나 먼저를 호출합니다ensureSize. 이것은 두 번째 실수입니다 (+=도++=마찬가지로 호출합니다 . 여러 요소에 대해 최적화합니다). 이 때문에Array그 의미 고정 된 크기의 컬렉션, 각 크기 조정에서 전체입니다Array복사해야합니다!
그래서 이것을 고려해 봅시다. 크기를 조정할 때 Java는 먼저 각 요소에 0을 저장하여 메모리를 지우고 Scala는 이전 배열의 각 요소를 새 배열로 복사합니다. 크기가 매번 두 배가되기 때문에 이것은 log (n) 번 발생하며 복사되는 요소의 수가 발생할 때마다 증가합니다.
예를 들어 n = 16입니다.이 작업을 4 번 수행하여 각각 1, 2, 4 및 8 요소를 복사합니다. 자바는 이러한 배열의 각을 취소 할 수 있으며, 각 요소를 읽을 수 있어야하기 때문에 하고 작성, 복사 각 요소 요소의 4 개 순회를 나타냅니다. 우리가 가진 (n-1) * 4 또는 전체 목록의 대략 4 번의 순회를 추가합니다. 사람들이 종종 잘못하는 것처럼 읽기 및 쓰기를 단일 패스로 계산하면 여전히 세 번의 순회입니다.
ArrayBuffer하나의 요소를 버릴 것이기 때문에 읽을 목록과 동일한 초기 크기에서 1을 뺀 값 으로 초기화하여이 문제를 개선 할 수 있습니다. 하지만이 크기를 얻으려면 목록을 한 번 탐색해야합니다.
이제 고려해 봅시다 toList. 간단히 말해서 전체 목록을 탐색하여 새 목록을 만듭니다.
따라서 알고리즘에 대해 1 회 순회, 크기 조정을위한 3 ~ 4 회 순회, toList. 4 ~ 5 번의 순회입니다.
때문에 원래의 알고리즘 분석하는 비트 곤란 take, drop및 :::요소의 가변 수를 통과. 그러나 모두 더하면 3 번의 순회에 해당합니다. 사용 된 경우 splitAt2 회 순회로 감소됩니다. 최대 값을 얻기 위해 2 번 더 순회하면 5 번 순회를 얻을 수 있습니다.이 순회는 작동하지 않고 간결하지 않은 알고리즘과 같은 숫자입니다!
따라서 개선 사항을 고려해 봅시다.
명령형 알고리즘 번 사용하는 경우 ListBuffer와 +=, 모든 방법은 하나의 통과로 감소 상수 시간이다.
기능 알고리즘에서는 다음과 같이 다시 작성할 수 있습니다.
val max = xs.max
val (before, _ :: after) = xs span (max !=)
before ::: after
이는 세 번의 순회의 최악의 경우로 축소됩니다. 물론 한 번의 순회에서 문제를 해결하는 재귀 또는 접기를 기반으로하는 다른 대안이 있습니다.
그리고 무엇보다도 가장 흥미로운 것은 이러한 모든 알고리즘이 O(n)이며, 최악의 복잡성에서 (우연히) 거의 발생하는 유일한 알고리즘은 (배열 복사로 인해) 명령 적 알고리즘 이었습니다. 반면에 명령형 의 캐시 특성은 데이터가 메모리에서 연속적이기 때문에 더 빠르게 만들 수 있습니다. 그러나 그것은 big-Oh 또는 기능적 대 명령과 관련이 없으며 선택한 데이터 구조의 문제 일뿐입니다.
따라서 실제로 벤치마킹하고, 결과를 분석하고, 방법의 성능을 고려하고,이를 최적화하는 방법을 찾는 문제에 가면 기능적 방식보다 명령 적 방식으로이를 수행하는 더 빠른 방법을 찾을 수 있습니다.
그러나이 모든 노력은 평균적인 Java 프로그래머 코드가 평균적인 Scala 프로그래머 코드보다 빠를 것이라고 말하는 것과는 매우 다릅니다. 질문이 예라면 그것은 단순히 거짓입니다. 그리고 질문을 무시하더라도 우리는 질문의 기본 전제가 사실이라는 증거를 보지 못했습니다.
편집하다
먼저, 제가 명확하지 않은 것 같기 때문에 제 요점을 다시 말씀 드리겠습니다. 내 요점은 평균적인 Java 프로그래머가 작성하는 코드가 더 효율적으로 보일 수 있지만 실제로는 그렇지 않다는 것입니다. 달리 말하면, 전통적인 Java 스타일은 성능을 얻지 못합니다. Java 또는 Scala가 되더라도 노력 만합니다.
다음으로, 제안 된 거의 모든 솔루션을 포함하여 벤치 마크와 결과도 있습니다. 그것에 대한 두 가지 흥미로운 점 :
목록 크기에 따라 개체 생성은 목록을 여러 번 순회하는 것보다 더 큰 영향을 미칠 수 있습니다. Adrian의 원래 기능 코드 는 최대 요소의 요소 를 전혀 복사하지 않음 으로써 목록이 영구적 인 데이터 구조라는 사실을 활용 합니다.
Vector대신 a 를 사용하면 왼쪽과 오른쪽이 대부분 변경되지 않아 성능이 더욱 향상 될 수 있습니다.알 수없는 사용자와 패러다임에는 유사한 재귀 솔루션이 있지만 패러다임은 훨씬 빠릅니다. 그 이유는 그가 패턴 매칭을 피하기 때문입니다. 패턴 매칭은 정말 느릴 수 있습니다.
벤치 마크 코드는 여기에 , 결과는 여기에 있습니다 .
def removeOneMax (xs: List [Int]) : List [Int] = xs match {
case x :: Nil => Nil
case a :: b :: xs => if (a < b) a :: removeOneMax (b :: xs) else b :: removeOneMax (a :: xs)
case Nil => Nil
}
다음은 한 번만 반복되는 재귀 메서드입니다. 성능이 필요하다면, 그렇지 않다면 생각해야합니다.
표준 방식으로 꼬리를 재귀 적으로 만들 수 있습니다. carry기본적으로 빈 목록 인 추가 매개 변수를 제공하고 반복하는 동안 결과를 수집합니다. 물론 조금 더 길지만 성능이 필요한 경우 비용을 지불해야합니다.
import annotation.tailrec
@tailrec
def removeOneMax (xs: List [Int], carry: List [Int] = List.empty) : List [Int] = xs match {
case a :: b :: xs => if (a < b) removeOneMax (b :: xs, a :: carry) else removeOneMax (a :: xs, b :: carry)
case x :: Nil => carry
case Nil => Nil
}
나중에 컴파일러가 느린 맵 호출을 while 루프만큼 빠르게 개선 할 가능성이 무엇인지 모르겠습니다. 그러나 고속 솔루션은 거의 필요하지 않지만 자주 필요하면 빠르게 학습 할 수 있습니다.
시스템에서 솔루션에 1 초를 사용하려면 컬렉션이 얼마나 커야하는지 알고 계십니까?
Oneliner로서 Daniel C. Sobrals 솔루션과 유사합니다.
((Nil : List[Int], xs(0)) /: xs.tail) ((p, x)=> if (p._2 > x) (x :: p._1, p._2) else ((p._2 :: p._1), x))._1
그러나 그것은 읽기 어렵고 효과적인 성능을 측정하지 않았습니다. 정상적인 패턴은 (x / : xs) ((a, b) => / * something * /)입니다. 여기서 x와 a는 List-so-far와 max-so-far의 쌍으로, 모든 것을 한 줄의 코드로 가져 오는 문제를 해결하지만 읽기는 어렵습니다. 그러나 이런 식으로 CodeGolf에서 평판을 얻을 수 있으며 누군가 성능 측정을 좋아할 수도 있습니다.
이제 놀랍게도 몇 가지 측정 값이 있습니다.
업데이트 된 타이밍 방법, 가비지 수집을 방해하고 핫스팟 컴파일러가 워밍업, 메인 및이 스레드의 여러 메서드를 명명 된 Object에 함께 포함하도록합니다.
object PerfRemMax {
def timed (name: String, xs: List [Int]) (f: List [Int] => List [Int]) = {
val a = System.currentTimeMillis
val res = f (xs)
val z = System.currentTimeMillis
val delta = z-a
println (name + ": " + (delta / 1000.0))
res
}
def main (args: Array [String]) : Unit = {
val n = args(0).toInt
val funs : List [(String, List[Int] => List[Int])] = List (
"indexOf/take-drop" -> adrian1 _,
"arraybuf" -> adrian2 _, /* out of memory */
"paradigmatic1" -> pm1 _, /**/
"paradigmatic2" -> pm2 _,
// "match" -> uu1 _, /*oom*/
"tailrec match" -> uu2 _,
"foldLeft" -> uu3 _,
"buf-=buf.max" -> soc1 _,
"for/yield" -> soc2 _,
"splitAt" -> daniel1,
"ListBuffer" -> daniel2
)
val r = util.Random
val xs = (for (x <- 1 to n) yield r.nextInt (n)).toList
// With 1 Mio. as param, it starts with 100 000, 200k, 300k, ... 1Mio. cases.
// a) warmup
// b) look, where the process gets linear to size
funs.foreach (f => {
(1 to 10) foreach (i => {
timed (f._1, xs.take (n/10 * i)) (f._2)
compat.Platform.collectGarbage
});
println ()
})
}
모든 메서드의 이름을 바꾸고 공통 메서드 선언 (List [Int] => List [Int])에 맞게 uu2를 약간 수정해야했습니다.
긴 결과에서 1M 호출에 대한 출력 만 제공합니다.
scala -Dserver PerfRemMax 2000000
indexOf/take-drop: 0.882
arraybuf: 1.681
paradigmatic1: 0.55
paradigmatic2: 1.13
tailrec match: 0.812
foldLeft: 1.054
buf-=buf.max: 1.185
for/yield: 0.725
splitAt: 1.127
ListBuffer: 0.61
숫자는 샘플 크기에 따라 완전히 안정적이지 않으며 실행마다 조금씩 다릅니다. 예를 들어 100k ~ 1M 실행의 경우 100k 단계에서 splitAt의 타이밍은 다음과 같습니다.
splitAt: 0.109
splitAt: 0.118
splitAt: 0.129
splitAt: 0.139
splitAt: 0.157
splitAt: 0.166
splitAt: 0.749
splitAt: 0.752
splitAt: 1.444
splitAt: 1.127
초기 솔루션은 이미 꽤 빠릅니다. splitAt다니엘의 수정으로 종종 더 빠르지 만 항상 그런 것은 아닙니다.
측정은 xUbuntu Linux, Scala-2.8 및 Sun-Java-1.6 (데스크탑)을 실행하는 단일 코어 2Ghz Centrino에서 수행되었습니다.
나를위한 두 가지 교훈은 다음과 같습니다.
- 항상 성능 향상을 측정하십시오. 매일하지 않으면 추정하기가 매우 어렵습니다.
- 기능적 코드를 작성하는 것은 재미있을뿐만 아니라 때로는 결과가 더 빠릅니다.
누군가 관심이 있다면 여기 내 벤치 마크 코드에 대한 링크가 있습니다.
우선, 제시 한 방법의 동작이 동일하지 않습니다. 첫 번째는 요소 순서를 유지하고 두 번째는 그렇지 않습니다.
둘째, "특이성"으로 분류 될 수있는 모든 가능한 솔루션 중에서 일부는 다른 것보다 더 효율적입니다. 예제에 매우 가깝게 유지하면 예를 들어 꼬리 재귀를 사용하여 변수를 제거하고 수동 상태 관리를 수행 할 수 있습니다.
def removeMax1( xs: List[Int] ) = {
def rec( max: Int, rest: List[Int], result: List[Int]): List[Int] = {
if( rest.isEmpty ) result
else if( rest.head > max ) rec( rest.head, rest.tail, max :: result)
else rec( max, rest.tail, rest.head :: result )
}
rec( xs.head, xs.tail, List() )
}
또는 목록을 접으십시오.
def removeMax2( xs: List[Int] ) = {
val result = xs.tail.foldLeft( xs.head -> List[Int]() ) {
(acc,x) =>
val (max,res) = acc
if( x > max ) x -> ( max :: res )
else max -> ( x :: res )
}
result._2
}
원래 게재 신청서를 유지하려면 별도의 노력없이 다음과 같이 작성할 수 있습니다 (한 번이 아닌 두 번의 패스를 사용하는 대신).
def removeMax3( xs: List[Int] ) = {
val max = xs.max
xs.filterNot( _ == max )
}
첫 번째 예보다 더 분명합니다.
프로그램을 작성할 때 가장 큰 비 효율성은 잘못된 것에 대해 걱정하는 것입니다. 이것은 일반적으로 걱정할 잘못된 것입니다. 왜?
개발자 시간은 일반적으로 CPU 시간보다 훨씬 비쌉니다. 사실 일반적으로 전자는 부족하고 후자는 과잉입니다.
대부분의 코드는 매초마다 여러 번 백만 항목 데이터 세트에서 실행되지 않으므로 매우 효율적일 필요는 없습니다.
대부분의 코드는 버그가 없어야하며 코드가 적을수록 버그를 숨길 공간이 적습니다.
당신이 준 예는 실제로 그다지 기능적이지 않습니다. 수행중인 작업은 다음과 같습니다.
// Given a list of Int
def removeMaxCool(xs: List[Int]): List[Int] = {
// Find the index of the biggest Int
val maxIndex = xs.indexOf(xs.max);
// Then take the ints before and after it, and then concatenate then
xs.take(maxIndex) ::: xs.drop(maxIndex+1)
}
알았지, 안 나쁜 ,하지만 당신이 원하는 것을 설명 할 때 기능 코드가 최상의 때 대신 당신이 원하는 방법으로, 알고있다. 사소한 비판으로, 당신이 사용하는 경우 splitAt대신 take하고 drop당신은 약간 개선 할 수있다.
이를 수행하는 또 다른 방법은 다음과 같습니다.
def removeMaxCool(xs: List[Int]): List[Int] = {
// the result is the folding of the tail over the head
// and an empty list
xs.tail.foldLeft(xs.head -> List[Int]()) {
// Where the accumulated list is increased by the
// lesser of the current element and the accumulated
// element, and the accumulated element is the maximum between them
case ((max, ys), x) =>
if (x > max) (x, max :: ys)
else (max, x :: ys)
// and of which we return only the accumulated list
}._2
}
이제 주요 문제에 대해 논의하겠습니다. 이 코드가 Java 코드보다 느립니까? 거의 확실히! Java 코드가 C에 해당하는 것보다 느립니까? JIT 또는 JIT가 아닐 수 있습니다. 어셈블러에서 직접 작성하면 더욱 빠르게 만들 수 있습니다!
그러나 그 속도의 대가는 더 많은 버그를 얻고 코드를 디버그하기 위해 코드를 이해하는 데 더 많은 시간을 소비하며 작은 코드가 수행하는 작업과 달리 전체 프로그램이 수행하는 작업에 대한 가시성이 떨어집니다. -자체 성능 문제가 발생할 수 있습니다.
그래서 제 대답은 간단합니다. 스칼라 프로그래밍의 속도 패널티가 이득을 얻을 가치가 없다고 생각한다면 어셈블러로 프로그래밍해야합니다. 내가 급진적이라고 생각한다면 익숙한 것을 "이상적인"트레이드 오프로 선택했다고 반박합니다.
성능이 중요하지 않다고 생각합니까? 전혀! Scala의 주요 장점 중 하나는 정적으로 입력 된 언어의 성능과 함께 동적으로 입력 된 언어에서 종종 발견되는 이점을 활용하는 것입니다! 성능이 중요하고 알고리즘 복잡성이 중요하며 지속적인 비용도 중요합니다.
그러나 성능과 가독성 및 유지 보수성 중에서 선택 이있을 때마다 후자가 선호됩니다. 물론 성능 을 개선 해야 한다면 선택의 여지가 없습니다. 무언가를 희생해야합니다. 그리고 Scala와 동적으로 입력되는 언어와 같이 가독성 / 유지 보수성에 손실이 없다면 성능을 추구하십시오.
마지막으로, 함수형 프로그래밍에서 성능을 얻으려면 함수형 알고리즘과 데이터 구조를 알아야합니다. 물론, 5-10 년의 경험을 가진 자바 프로그래머의 99 %는 6 개월의 경험을 가진 스칼라 프로그래머의 99 %를 능가 할 것입니다. 20 년 전 명령형 프로그래밍과 객체 지향 프로그래밍의 경우도 마찬가지였으며 역사는 그것이 중요하지 않았 음을 보여줍니다.
편집하다
참고로 "빠른"알고리즘에는 심각한 문제가 있습니다 ArrayBuffer.. 해당 컬렉션에는 일정한 시간 추가가 없으며 선형 시간이 toList있습니다. ListBuffer대신 사용 하면 일정한 시간이 추가 되고 toList .
참고로 Scala 표준 라이브러리의 TraversableLike 에 splitAt정의 된 방법 은 다음 과 같습니다.
def splitAt(n: Int): (Repr, Repr) = {
val l, r = newBuilder
l.sizeHintBounded(n, this)
if (n >= 0) r.sizeHint(this, -n)
var i = 0
for (x <- this) {
(if (i < n) l else r) += x
i += 1
}
(l.result, r.result)
}
Java 프로그래머가 생각 해낼 수있는 예제 코드와 다르지 않습니다.
성능이 중요한 곳에서는 가변성이 합리적인 방법이기 때문에 저는 Scala를 좋아합니다. 컬렉션 라이브러리가 좋은 예입니다. 특히 기능적 인터페이스 뒤에이 가변성을 숨기는 방법.
일부 애플리케이션 코드와 같이 성능이 중요하지 않은 경우 Scala 라이브러리의 고차 함수는 뛰어난 표현력과 프로그래머 효율성을 허용합니다.
호기심에서 나는 Scala 컴파일러 ( scala.tools.nsc.typechecker.Typers.scala ) 에서 임의의 큰 파일을 선택하고 37 for 루프, 11 while 루프, 6 연결 ( ++) 및 1 폴드와 같은 것을 계산 했습니다. 될 수 있습니다 foldRight).
이건 어때?
def removeMax(xs: List[Int]) = {
val buf = xs.toBuffer
buf -= (buf.max)
}
좀 더 못 생겼지 만 더 빠릅니다.
def removeMax(xs: List[Int]) = {
var max = xs.head
for ( x <- xs.tail )
yield {
if (x > max) { val result = max; max = x; result}
else x
}
}
이 시도:
(myList.foldLeft((List[Int](), None: Option[Int]))) {
case ((_, None), x) => (List(), Some(x))
case ((Nil, Some(m), x) => (List(Math.min(x, m)), Some(Math.max(x, m))
case ((l, Some(m), x) => (Math.min(x, m) :: l, Some(Math.max(x, m))
})._1
Idiomatic, functional, traverses only once. Maybe somewhat cryptic if you are not used to functional-programming idioms.
Let's try to explain what is happening here. I will try to make it as simple as possible, lacking some rigor.
A fold is an operation on a List[A] (that is, a list that contains elements of type A) that will take an initial state s0: S (that is, an instance of a type S) and a function f: (S, A) => S (that is, a function that takes the current state and an element from the list, and gives the next state, ie, it updates the state according to the next element).
The operation will then iterate over the elements of the list, using each one to update the state according to the given function. In Java, it would be something like:
interface Function<T, R> { R apply(T t); }
class Pair<A, B> { ... }
<State> State fold(List<A> list, State s0, Function<Pair<A, State>, State> f) {
State s = s0;
for (A a: list) {
s = f.apply(new Pair<A, State>(a, s));
}
return s;
}
For example, if you want to add all the elements of a List[Int], the state would be the partial sum, that would have to be initialized to 0, and the new state produced by a function would simply add the current state to the current element being processed:
myList.fold(0)((partialSum, element) => partialSum + element)
Try to write a fold to multiply the elements of a list, then another one to find extreme values (max, min).
Now, the fold presented above is a bit more complex, since the state is composed of the new list being created along with the maximum element found so far. The function that updates the state is more or less straightforward once you grasp these concepts. It simply puts into the new list the minimum between the current maximum and the current element, while the other value goes to the current maximum of the updated state.
What is a bit more complex than to understand this (if you have no FP background) is to come up with this solution. However, this is only to show you that it exists, can be done. It's just a completely different mindset.
EDIT: As you see, the first and second case in the solution I proposed are used to setup the fold. It is equivalent to what you see in other answers when they do xs.tail.fold((xs.head, ...)) {...}. Note that the solutions proposed until now using xs.tail/xs.head don't cover the case in which xs is List(), and will throw an exception. The solution above will return List() instead. Since you didn't specify the behavior of the function on empty lists, both are valid.
Another contender. This uses a ListBuffer, like Daniel's second offering, but shares the post-max tail of the original list, avoiding copying it.
def shareTail(xs: List[Int]): List[Int] = {
var res = ListBuffer[Int]()
var maxTail = xs
var first = true;
var x = xs
while ( x != Nil ) {
if (x.head > maxTail.head) {
while (!(maxTail.head == x.head)) {
res += maxTail.head
maxTail = maxTail.tail
}
}
x = x.tail
}
res.prependToList(maxTail.tail)
}
Another option would be:
package code.array
object SliceArrays {
def main(args: Array[String]): Unit = {
println(removeMaxCool(Vector(1,2,3,100,12,23,44)))
}
def removeMaxCool(xs: Vector[Int]) = xs.filter(_ < xs.max)
}
Using Vector instead of List, the reason is that Vector is more versatile and has a better general performance and time complexity if compared to List.
Consider the following collections operations: head, tail, apply, update, prepend, append
Vector takes an amortized constant time for all operations, as per Scala docs: "The operation takes effectively constant time, but this might depend on some assumptions such as maximum length of a vector or distribution of hash keys"
While List takes constant time only for head, tail and prepend operations.
Using
scalac -print
generates:
package code.array {
object SliceArrays extends Object {
def main(args: Array[String]): Unit = scala.Predef.println(SliceArrays.this.removeMaxCool(scala.`package`.Vector().apply(scala.Predef.wrapIntArray(Array[Int]{1, 2, 3, 100, 12, 23, 44})).$asInstanceOf[scala.collection.immutable.Vector]()));
def removeMaxCool(xs: scala.collection.immutable.Vector): scala.collection.immutable.Vector = xs.filter({
((x$1: Int) => SliceArrays.this.$anonfun$removeMaxCool$1(xs, x$1))
}).$asInstanceOf[scala.collection.immutable.Vector]();
final <artifact> private[this] def $anonfun$removeMaxCool$1(xs$1: scala.collection.immutable.Vector, x$1: Int): Boolean = x$1.<(scala.Int.unbox(xs$1.max(scala.math.Ordering$Int)));
def <init>(): code.array.SliceArrays.type = {
SliceArrays.super.<init>();
()
}
}
}
ReferenceURL : https://stackoverflow.com/questions/7084212/is-scala-idiomatic-coding-style-just-a-cool-trap-for-writing-inefficient-code
'code' 카테고리의 다른 글
| 라텍스 다중 줄 바꿈 (0) | 2021.01.09 |
|---|---|
| 백분율 계산 (0) | 2021.01.09 |
| django 튜토리얼 테스트 실행 실패-polls.tests라는 모듈이 없습니다. (0) | 2021.01.09 |
| 그렇다면 Windows에서 경로 슬래시 (/ 또는 \)의 올바른 방향은 무엇입니까? (0) | 2021.01.09 |
| SystemInformation.ComputerName, Environment.MachineName 및 Net.Dns.GetHostName의 차이점 (0) | 2021.01.08 |