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
