这篇文章主要讲解了“Scala中Array和List的区别有哪些区别”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“Scala中Array和List的区别有哪些区别”吧!
Scala Array和List的区别
Scala快排List和Array数组效率实测
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,否则,列表比数组更好。
代码
package com.tingfeng.scala.test import scala.annotation.tailrec import 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的区别有哪些区别这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。