Scala中Array和List的区别说明
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.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
以上为个人经验,希望能给大家一个参考,也希望大家多多支持猪先飞。
相关文章
Java8 实现stream将对象集合list中抽取属性集合转化为map或list
这篇文章主要介绍了Java8 实现stream将对象集合list中抽取属性集合转化为map或list的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-05- 这篇文章主要介绍了java8如何用Stream查List对象某属性是否有重复的操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-09-11
- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了C#中list用法,结合实例形式分析了C#中list排序、运算、转换等常见操作技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了Java8处理List的双层循环问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-19
- 这篇文章主要介绍了C# List 排序各种用法与比较的相关资料,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了使用list stream:任意对象List拼接字符串操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-09-09
- 这篇文章主要介绍了C# List介绍及具体用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
- 这篇文章主要介绍了R语言-将list转换为向量的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-06
- 这篇文章主要介绍了Python 列表(List)的底层实现原理分析,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-09
C#中数组、ArrayList、List、Dictionary的用法与区别浅析(存取数据)
在工作中经常遇到C#数组、ArrayList、List、Dictionary存取数据,但是该选择哪种类型进行存储数据呢?很迷茫,今天小编抽空给大家整理下这方面的内容,需要的朋友参考下吧...2020-06-25- 这篇文章主要介绍了jQuery中inArray方法注意事项,结合实例形式分析了jQuery中inArray方法变量判断的相关注意事项,需要的朋友可以参考下...2016-01-26
- 这篇文章主要介绍了C#中List和数组之间转换的方法,涉及比较简单的转换技巧,需要的朋友可以参考下...2020-06-25
- 这篇文章主要是介绍了.net C# 实现任意List的全组合算法实现代码,需要的朋友可以参考下...2020-06-25
解决vue props传Array/Object类型值,子组件报错的情况
这篇文章主要介绍了解决vue props传Array/Object类型值,子组件报错的情况,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-11-07JSON字符串转换JSONObject和JSONArray的方法
这篇文章主要介绍了JSON字符串转换JSONObject和JSONArray的方法的相关资料,需要的朋友可以参考下...2016-06-12- 今天小编就为大家分享一篇python Tensor和Array对比分析,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-27
idea 无法创建Scala class 选项的原因分析及解决办法汇总
这篇文章主要介绍了idea 无法创建Scala class 选项的解决办法汇总,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2020-09-02- 今天小编就为大家分享一篇关于C#中List和SortedList的简介,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧...2020-06-25