왜 리스트 뒤에 추가하지 않고 앞에 추가할까요?

[낭만검객]

<Programming in Scala> 역서 88쪽에 보면 해당 사항에 대한 설명이 나옵니다.

"리스트 뒤에 원소를 추가하는 연산은 리스트의 길이에 비례한 시간이 걸리기 때문이다. 반면 ::를 사용해 맨 앞에 추가하는 것은 상수 시간이 걸린다. 리스트 뒤에 추가하면서 효율적인 리스트를 만들어내려면, 뒤집은 리스트 앞에 원소를 추가한 다음에 다시 뒤집거나, ListBuffer를..."

이 문장을 읽으면서 몇 가지 생각과 질문이 생겼습니다.

"List니 뒤에 추가하려면 목록을 따라 끝까지 간 다음에 추가하니 당연히 List 길이에 비례하겠구나." 이건 당연한거죠.

그런데 위에 보면 효율적인 리스트를 만들어내려면 리스트를 뒤집는다고 했습니다. 저는 이 부분이 이해가 안갑니다. 뒤집고 추가하고 뒤집고. 왜 이렇게 하죠? 어떤 점에서 효율적일까요?

사실 저는 앞에 추가하는 것이 리스트 공유에 적합하기 때문이라고 생각했습니다.

val a = List(1, 2, 3)

val b = 0 :: a

이런 코드에서 맨 처음 만든 a는 b에서 공유를 할 수 있는데,

만일 새로운 목록에서 a의 뒤에 덧붙이면 기존 a가 1, 2, 3에서 끝나야 하는데 그 덧붙인 것 때문에 공유를 못하고 copy가 발생합니다.

저는 이런 견지에서 앞에 추가하는 전략이 좋겠다고 생각했습니다. 그런데 책의 박스에는 그런 이야기가 없네요...

의견 부탁드립니다.

[blueiur]

간단하게 생각해서 길이 10 리스트 뒤에 3개원소를 붙인다면 비용이 33이 되지만, 뒤집고 붙이고 뒤집는다면 비용이 23이 되겠죠. 전자는 페인트공 알고리즘이 되기 때문에 리스트가 길면 길수록 비효율적이 됩니다.

2015년 5월 22일 (금) 오전 9:09, 낭만검객 <cyb...@gmail.com>님이 작성:

--
이 메일은 Google 그룹스 '라 스칼라 코딩단' 그룹에 가입한 분들에게 전송되는 메시지입니다.
이 그룹에서 탈퇴하고 더 이상 이메일을 받지 않으려면 scala-korea...@googlegroups.com에 이메일을 보내세요.
이 그룹에 게시하려면 scala...@googlegroups.com에 이메일을 보내세요.
웹에서 이 토론을 보려면 https://groups.google.com/d/msgid/scala-korea/c9e12496-e815-4602-907e-bcfdce4f86dd%40googlegroups.com을(를) 방문하세요.
더 많은 옵션을 보려면 https://groups.google.com/d/optout을(를) 방문하세요.

[낭만검객]

구현의 차이였군요.

저는 last를 가리키는 변수 하나를 두고 (이때는 길이에 비례한 시간이 걸리겠죠)

그 변수를 움직이며 추가한다고 생각했습니다.

궁금한 것 중 하나는 풀렸네요 ^^ 고맙습니다.

[낭만검객]

적고 보니 제가 말한 내용이 책에서 언급한 ListBuffer였네요 ^^

[Hyunsok Oh]

그래서 요즘 추세는 벡터를 쓰는겁니다.

그냥 재귀 연습용으로 생각하고 리스트를 사용하세요.

물론 입구에서만 깨작깨작하면 되는 알고리즘은 리스트가 최강일 수도 있습니다.

> https://groups.google.com/d/msgid/scala-korea/08bb8dfe-5e22-4e57-af35-f6957d212292%40googlegroups.com을(를)

[Joseph Yang]

컬렉션 퍼포먼스 관련해서 스칼라 문서에 잘 정리가 되어있더라구요. 

http://docs.scala-lang.org/overviews/collections/performance-characteristics.html

head	tail	apply	update	prepend	append	insert
immutable
List	C	C	L	L	C	L	-
Stream	C	C	L	L	C	L	-
Vector	eC	eC	eC	eC	eC	eC	-
Stack	C	C	L	L	C	C	L
Queue	aC	aC	L	L	L	C	-
Range	C	C	C	-	-	-	-
String	C	L	C	L	L	L	-
mutable
ArrayBuffer	C	L	C	C	L	aC	L
ListBuffer	C	L	L	L	C	C	L
StringBuilder	C	L	C	C	L	aC	L
MutableList	C	L	L	L	C	C	L
Queue	C	L	L	L	C	C	L
ArraySeq	C	L	C	C	-	-	-
Stack	C	L	L	L	C	L	L
ArrayStack	C	L	C	C	aC	L	L
Array	C	L	C	C	-	-	-

C	The operation takes (fast) constant time.
eC	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.
aC	The operation takes amortized constant time. Some invocations of the operation might take longer, but if many operations are performed on average only constant time per operation is taken.
Log	The operation takes time proportional to the logarithm of the collection size.
L	The operation is linear, that is it takes time proportional to the collection size.
-	The operation is not supported.

2015년 5월 22일 오전 11:04, Hyunsok Oh <ensh...@gmail.com>님이 작성:

--
Google 그룹스 '라 스칼라 코딩단' 그룹에 가입했으므로 본 메일이 전송되었습니다.

이 그룹에서 탈퇴하고 더 이상 이메일을 받지 않으려면 scala-korea...@googlegroups.com에 이메일을 보내세요.

이 그룹에 게시하려면 scala...@googlegroups.com(으)로 이메일을 보내세요.
웹에서 이 토론을 보려면 https://groups.google.com/d/msgid/scala-korea/CAMzzDrw7KYk7tehXCaRXJ%3DyE_U4Oj_0eOFCB5tBASJ8WnHqENQ%40mail.gmail.com 을(를) 방문하세요.

더 많은 옵션을 보려면 https://groups.google.com/d/optout을(를) 방문하세요.

--

/*******************************************/
/* Get busy living, Get busy dying      */
/*******************************************/

[성큼이]

스칼라의 List는 기본적으로 immutable이기 때문에 내부에 변수를 두지 않습니다.

물론 실제 구현상 효율 때문에 디테일은 다릅니다만 사용자 입장에서는 불변객체라고 보는 게 좋죠.

On Friday, May 22, 2015 at 10:01:42 AM UTC+9, 낭만검객 wrote:

[Seoh]

http://en.m.wikipedia.org/wiki/Cons

Cons라는 자료구조에 대해 이해하시면 왜 그렇게 작동하는지와 메소드들의 복잡도에 대해 이해하는데 도움이 될껍니다 :)

Cons 구현하는 것도 책에 있었는데 PiS에 있는지 FPiS에 있었는지 가물가물하네요