Scala中Array和List的区别有哪些区别
这篇文章主要讲解了"Scala中Array和List的区别有哪些区别"，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习"Scala中Array和List的区别有哪些区别"吧！
目录
Scala Array和List的区别
Scala快排List和Array数组效率实测
Scala Array和List的区别
Difference between Array and List in scala
Q：什么时候用Array（Buffer）和List（Buffer）?
A：Scala中的List是不可变的递归数据（immutable recursive data），是Scala中的一种基础结构，你应该多用List而不是Array（Array实际上是mutable，不可变（immutable）的Array是IndexedSeq）
Mutable Structures
ListBuffer提供一个常数时间的转换到List。
一个Scala的Array应该是由Java array生成的，因此一个Array[Int]也许比List[Int]更有效率。
但是，我认为Scala中数组尽量少用，因为它感觉是你真的需要知道底层发生了什么，来决定是否Array将所需的基本数据类型进行备份，或者可能boxed as a wrapper type.
| Performance differences | Array | List |
|---|---|---|
| Access the ith element | O(1) | O(i) |
| Discard the ith element | O(n) | O(i) |
| Insert an element at i | O(n) | O(i) |
| Reverse | O(n) | O(n) |
| Concatenate (length m,n) | O(n+m) | O(n) |
| Calculate the length | O(1) | O(n) |
| memory differences | Array | List |
|---|---|---|
| Get the first i elements | O(i) | O(i) |
| Drop the first i elements | O(n-i) | O(1) |
| Insert an element at i | O(n) | O(i) |
| Reverse | O(n) | O(n) |
| Concatenate (length m,n) | O(n+m) | O(n) |
所以，除非你需要快速随机访问或需要count batches of elements,否则，列表比数组更好。
Scala快排List和Array数组效率实测
代码
package com.tingfeng.scala.testimport scala.annotation.tailrecimport scala.util.{Random, Sorting}/** * 快速排序测试 */object SortTest { /** * 初始化一个数组，产生随机数字填充 * @param size * @return */ def initRandomList(size :Int):List[Int]={ val random = new Random() def initList(size :Int,random: Random):List[Int] = size match { case 0 => Nil case 1 => List(random.nextInt()) case s:Int => val value = s / 2 if( s % 2 == 0) { initList(value,random) ++ initList(value,random) }else{ initList(value,random) ++ initList(value + 1,random) } } initList(size,random) } /** * 打印出使用的时间 * @param call */ def printTime(call : => Unit,tag: String = ""){ val startTime = System.currentTimeMillis() println(tag) call println println(s"use time : ${System.currentTimeMillis() - startTime}\n") } /** * 交换数组中两个位置的值，经过测试这种按位与的方式比普通建立变量交换的效率更高 * @param array * @param x * @param y */ def swap(array: Array[Int],x:Int,y:Int):Unit ={ val t = array(x) ^ array(y) array(x) = t ^ array(x) array(y) = t ^ array(y) } /** * 将传入的值直接返回,并且执行逻辑 * @param call * @param any * @tparam A */ def doThing[A<:Any](any: A,call: A => Unit):A = { call(any) any } /** * 打印列表 */ def printList[A<%Seq[Any]](seq:A,size :Int = 10):Unit={ seq.splitAt(size)._1.foreach(it => print(s"$it,")) } def shuffleIntSeq(seq: Array[Int],size: Int):Unit={ val random = new Random() val maxSize = size/2 for(i <- 0 to maxSize){ swap(seq,i,maxSize + random.nextInt(maxSize)) } } def main(args: Array[String]): Unit = { val size = 5000000 val printSize = 10 val list = initRandomList(size) //打印出钱100个，和List快速排序的时间花费 printTime(printList[List[Int]](qSortList(list),Math.min(10,size)),"qSortList") val array = list.toArray printTime(printList[Array[Int]](doThing[Array[Int]](array,Sorting.quickSort),Math.min(printSize,size)),"Sorting.quickSort") shuffleIntSeq(array,size) printTime(printList[Array[Int]](doThing[Array[Int]](array,qSortArray1),Math.min(printSize,size)),"qSortArray1") shuffleIntSeq(array,size) printTime(printList[Array[Int]](doThing[Array[Int]](array,qSortArray2),Math.min(printSize,size)),"qSortArray2") shuffleIntSeq(array,size) printTime(printList[Array[Int]](doThing[Array[Int]](array,qSortArray3),Math.min(printSize,size)),"qSortArray3") shuffleIntSeq(array,size) printTime(printList[Array[Int]](doThing[Array[Int]](array,qSortArray4),Math.min(printSize,size)),"qSortArray4") } /** * 对List快速排序 * @param list * @return */ def qSortList(list: List[Int]):List[Int] = list match { case Nil => Nil case head :: other => val (left, right) = other.partition(_ < head) (qSortList(left) :+ head) ++ qSortList(right) } /** * 通过每次比较数组'head'值与其余值的方式直接实现 * 比'head'小的值移动到其前，比'head'大的移动到其之后 * @param array */ def qSortArray1(array: Array[Int]):Unit = { def sort(ay : Array[Int],start: Int,end: Int):Unit={ if(start >= end) { return } val head = ay(start) var spliteIndex = start for (i <- start + 1 to end){ if(ay(i) < head){ swap(array,spliteIndex,i) spliteIndex += 1 } } if(start != spliteIndex){ sort(ay, start, spliteIndex) } if(start == spliteIndex){ spliteIndex += 1 } if(spliteIndex != end){ sort(ay, spliteIndex, end) } } sort(array,0,array.size - 1) } /** * 将数据以中线拆分左右两部分，交换值，使得右边值比左边大， * 再以左或者右边交换的界限分为两部分做递归 * @param array */ def qSortArray2(array: Array[Int]) { def sort(l: Int, r: Int) { val pivot = array((l + r) / 2) var lv = l; var rv = r while (lv <= rv) { while (array(lv) < pivot) lv += 1 while (array(rv) > pivot) rv -= 1 if (lv <= rv) { swap(array,lv, rv) lv += 1 rv -= 1 } } if (l < rv) sort(l, rv) if (rv < r) sort(lv, r) } sort(0, array.length - 1) } /** * 系统自带的过滤函数,无法排序成功，因为filter返回的是引用 * @param xs * @return */ def qSortArray3(xs: Array[Int]): Array[Int] ={ if (xs.length <= 1){ xs }else { val pivot = xs(xs.length / 2) val left = xs filter (pivot > _) val cu = xs filter (pivot == _ ) val right = xs filter (pivot < _ ) Array.concat( qSortArray3(left),cu,qSortArray3(right)) } } /** * 系统自带的分割函数,无法排序成功，因为partition返回的是引用，数据量大的时候会栈溢出失败 * @param xs * @return */ def qSortArray4(array: Array[Int]): Array[Int] ={ if (array.length <= 1){ array }else { val head = array(0) val (left,right) = array.tail partition (_ < head ) Array.concat(qSortArray4(left),Array(head),qSortArray4(right)) } }}测试结果
qSortList
-2147483293,-2147483096,-2147481318,-2147480959,-2147479572,-2147479284,-2147478285,-2147477579,-2147476191,-2147475936,
use time : 28808Sorting.quickSort
-2147483293,-2147483096,-2147481318,-2147480959,-2147479572,-2147479284,-2147478285,-2147477579,-2147476191,-2147475936,
use time : 773qSortArray1
-2147483293,-2147483096,-2147481318,-2147480959,-2147479572,-2147479284,-2147478285,-2147477579,-2147476191,-2147475936,
use time : 1335qSortArray2
-2147483293,-2147483096,-2147481318,-2147480959,-2147479572,-2147479284,-2147478285,-2147477579,-2147476191,-2147475936,
use time : 629qSortArray3
508128328,554399267,876118465,968407914,1274954088,1550124974,296879812,2125832312,1874291320,965362519,
use time : 10617qSortArray4
865409973,-645195021,-735017922,-1893119148,1838343395,1038029591,-560471115,-182627393,-228613831,220531987,
use time : 6904
Process finished with exit code 0
环境：版本Scala2.12.6 ， win10 ，ryzen5 1600 ， 8G
感谢各位的阅读，以上就是"Scala中Array和List的区别有哪些区别"的内容了，经过本文的学习后，相信大家对Scala中Array和List的区别有哪些区别这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是，小编将为大家推送更多相关知识点的文章，欢迎关注！
