Scala의 ListMap은 삽입 순서를 유지하지 않습니다.
소개
ListMap(mutable인)은 이름적으로 순서를 보관 유지한 Map를 만들어 준다고 생각해 구현하고 있었습니다만,
사실은 아니었기 때문에 공부를 위해 구현을 쫓아보기로했습니다.
※ 아직 Scala 처음으로 일주일 정도이므로 잘못되어 있으면 죄송합니다.
결론
immutable ListMap은 삽입 순서를 유지하지만 mutable ListMap은 삽입 순서를 유지하지 않는다는 것을 배웠습니다.
import scala.collection.mutable
import collection.immutable.ListMap
object Untitled {
def main(args: Array[String]) {
val iListMap = ListMap[Int, String]()
val iRes = iListMap.updated(1,"一郎").updated(2,"二郎").updated(3,"三郎").updated(4,"四郎")
println("immutable:",iRes)
val mListMap = mutable.ListMap[Int,String]()
val mRes = mListMap.updated(1,"一郎").updated(2,"二郎").updated(3,"三郎").updated(4,"四郎")
println("mutable",mRes)
}
}
// output
//(immutable:,ListMap(1 -> 一郎, 2 -> 二郎, 3 -> 三郎, 4 -> 四郎))
//(mutable,Map(4 -> 四郎, 2 -> 二郎, 3 -> 三郎, 1 -> 一郎))
구현을 쫓아보기
mutable ListMap
updated 는 내부에서는 map() += map()
를 실시하고 있습니다.
그래서 mutable.ListMap의 다음 메소드에서 해독을 시작합니다.
+=
def += (kv: (A, B)) = { elems = remove(kv._1, elems, List()); elems = kv :: elems; siz += 1; this }
kv는 순차 map을 저장하고 A는 key를, B는 Value를 저장합니다.
elems는 remove의 결과를 포함합니다. (remove의 내용에 대해서는 아래에서 설명)
마지막으로 kv를 remove 결과의 시작 부분에 저장합니다.
remove
@tailrec
private def remove(key: A, elems: List[(A, B)], acc: List[(A, B)]): List[(A, B)] = {
if (elems.isEmpty) acc
else if (elems.head._1 == key) { siz -= 1; acc ::: elems.tail }
else remove(key, elems.tail, elems.head :: acc)
}
elems 는 선두 요소를 제외한 List 를 재귀적으로 받아, acc 에는 최종적인 처리 결과를 포함하고 있습니다.
remove if
에서 elems가 비어있을 때 acc를 반환
remove의 else if
의 처리에서는, 동일한 key를 가지는 원의 map의 요소를 없애고, 새로운 요소를 선두에 추가하고 있습니다.
예: map(1 -> "hoge") += map(1 -> "fuga") 는 map(1 -> "fuga")
재귀 적으로 호출하는 else remove
의 부분에서, 처리 결과의 전에 선두 요소를 추가하고 있습니다.
※ @tailrec
실제로 디버그로 접었더니 다음과 같이 되었습니다.
remove(key, elems.tail, elems.head :: acc)
의 개소에서 처리 결과를 말미에 추가하고 있기 때문에 순서가 어긋나 있는 것 같습니다.
참고 기사
htps //w w. chs 이것. 이 m/bぉg/2015/06/15/s ぁ_무타 bぇ_ぃst마 p/
immutable ListMap
나중에 쓰다
(현재 자신의 레벨 낮아서 쫓지 않았다···w)
Reference
이 문제에 관하여(Scala의 ListMap은 삽입 순서를 유지하지 않습니다.), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/yoshinori_hisakawa/items/96f34fcb900d57159379
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
immutable ListMap은 삽입 순서를 유지하지만 mutable ListMap은 삽입 순서를 유지하지 않는다는 것을 배웠습니다.
import scala.collection.mutable
import collection.immutable.ListMap
object Untitled {
def main(args: Array[String]) {
val iListMap = ListMap[Int, String]()
val iRes = iListMap.updated(1,"一郎").updated(2,"二郎").updated(3,"三郎").updated(4,"四郎")
println("immutable:",iRes)
val mListMap = mutable.ListMap[Int,String]()
val mRes = mListMap.updated(1,"一郎").updated(2,"二郎").updated(3,"三郎").updated(4,"四郎")
println("mutable",mRes)
}
}
// output
//(immutable:,ListMap(1 -> 一郎, 2 -> 二郎, 3 -> 三郎, 4 -> 四郎))
//(mutable,Map(4 -> 四郎, 2 -> 二郎, 3 -> 三郎, 1 -> 一郎))
구현을 쫓아보기
mutable ListMap
updated 는 내부에서는 map() += map()
를 실시하고 있습니다.
그래서 mutable.ListMap의 다음 메소드에서 해독을 시작합니다.
+=
def += (kv: (A, B)) = { elems = remove(kv._1, elems, List()); elems = kv :: elems; siz += 1; this }
kv는 순차 map을 저장하고 A는 key를, B는 Value를 저장합니다.
elems는 remove의 결과를 포함합니다. (remove의 내용에 대해서는 아래에서 설명)
마지막으로 kv를 remove 결과의 시작 부분에 저장합니다.
remove
@tailrec
private def remove(key: A, elems: List[(A, B)], acc: List[(A, B)]): List[(A, B)] = {
if (elems.isEmpty) acc
else if (elems.head._1 == key) { siz -= 1; acc ::: elems.tail }
else remove(key, elems.tail, elems.head :: acc)
}
elems 는 선두 요소를 제외한 List 를 재귀적으로 받아, acc 에는 최종적인 처리 결과를 포함하고 있습니다.
remove if
에서 elems가 비어있을 때 acc를 반환
remove의 else if
의 처리에서는, 동일한 key를 가지는 원의 map의 요소를 없애고, 새로운 요소를 선두에 추가하고 있습니다.
예: map(1 -> "hoge") += map(1 -> "fuga") 는 map(1 -> "fuga")
재귀 적으로 호출하는 else remove
의 부분에서, 처리 결과의 전에 선두 요소를 추가하고 있습니다.
※ @tailrec
실제로 디버그로 접었더니 다음과 같이 되었습니다.
remove(key, elems.tail, elems.head :: acc)
의 개소에서 처리 결과를 말미에 추가하고 있기 때문에 순서가 어긋나 있는 것 같습니다.
참고 기사
htps //w w. chs 이것. 이 m/bぉg/2015/06/15/s ぁ_무타 bぇ_ぃst마 p/
immutable ListMap
나중에 쓰다
(현재 자신의 레벨 낮아서 쫓지 않았다···w)
Reference
이 문제에 관하여(Scala의 ListMap은 삽입 순서를 유지하지 않습니다.), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/yoshinori_hisakawa/items/96f34fcb900d57159379
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
def += (kv: (A, B)) = { elems = remove(kv._1, elems, List()); elems = kv :: elems; siz += 1; this }
@tailrec
private def remove(key: A, elems: List[(A, B)], acc: List[(A, B)]): List[(A, B)] = {
if (elems.isEmpty) acc
else if (elems.head._1 == key) { siz -= 1; acc ::: elems.tail }
else remove(key, elems.tail, elems.head :: acc)
}
Reference
이 문제에 관하여(Scala의 ListMap은 삽입 순서를 유지하지 않습니다.), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/yoshinori_hisakawa/items/96f34fcb900d57159379텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)