Explanation of the difference between Array and List in Scala
- 2021-11-24 01:21:49
- OfStack
Differences between Scala, Array and List
Difference between Array and List in scala
Q: When will Array (Buffer) and List (Buffer) be used?
A: List in Scala is immutable recursive data (immutable recursive data), which is a kind of infrastructure in Scala. You should use List instead of Array (Array is actually mutable, Array immutable (immutable) is IndexedSeq)
Mutable Structures
ListBuffer provides a constant time conversion to List.
An Array of an Scala should be generated by an Java array, so an Array [Int] may be more efficient than an List [Int].
However, I think arrays are used as little as possible in Scala, because it feels like you really need to know what's going on at the bottom to decide whether Array will back up the required basic data type, or maybe 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) |
So unless you need quick random access or count batches of elements, lists are better than arrays.
Efficiency measurement of List and Array arrays in Scala fast row
Code
package com.tingfeng.scala.test
import scala.annotation.tailrec
import scala.util.{Random, Sorting}
/**
* Quick sort test
*/
object SortTest {
/**
* Initialization 1 An array of random numbers to fill
* @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)
}
/**
* Print out the time used
* @param call
*/
def printTime(call : => Unit,tag: String = ""){
val startTime = System.currentTimeMillis()
println(tag)
call
println
println(s"use time : ${System.currentTimeMillis() - startTime}\n")
}
/**
* Swap the values of two positions in the array. After testing, this bitwise AND method is more efficient than ordinary variable exchange
* @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)
}
/**
* Returns the passed-in value directly , And execute the logic
* @param call
* @param any
* @tparam A
*/
def doThing[A<:Any](any: A,call: A => Unit):A = {
call(any)
any
}
/**
* Print list
*/
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)
// Print out the money 100 A, and List Time spent on quick sorting
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")
}
/**
* Right List Quick sort
* @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)
}
/**
* By comparing arrays every time ' head' Value and the rest of the values
* Than ' head' A smaller value moves to its front than ' head' The big one moves behind it
* @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)
}
/**
* Split the left and right parts of the data with the center line, and exchange the values so that the value on the right side is larger than that on the left side.
* Then divide the boundary of left or right exchange into two parts for recursion
* @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 function of the system , Unable to sort successfully because filter Returns a reference
* @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))
}
}
/**
* Segmentation function of the system , Unable to sort successfully because partition It returns a reference, and when the amount of data is large, the stack overflows and fails
* @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))
}
}
}
Test results
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
Environment: Versions Scala2.12. 6, win10, ryzen51600, 8G