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数组效率实测
代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
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
以上为个人经验，希望能给大家一个参考，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/power0405hf/article/details/50235541
