Scala中Array和List的區別有哪些區別

這篇文章主要講解了“Scala中Array和List的區別有哪些區別”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Scala中Array和List的區別有哪些區別”吧！

目錄

• Scala Array和List的區別

• Scala快排List和Array數組效率實測

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.

所以，除非你需要快速隨機訪問或需要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 : 28808

Sorting.quickSort
-2147483293,-2147483096,-2147481318,-2147480959,-2147479572,-2147479284,-2147478285,-2147477579,-2147476191,-2147475936,
use time : 773

qSortArray1
-2147483293,-2147483096,-2147481318,-2147480959,-2147479572,-2147479284,-2147478285,-2147477579,-2147476191,-2147475936,
use time : 1335

qSortArray2
-2147483293,-2147483096,-2147481318,-2147480959,-2147479572,-2147479284,-2147478285,-2147477579,-2147476191,-2147475936,
use time : 629

qSortArray3
508128328,554399267,876118465,968407914,1274954088,1550124974,296879812,2125832312,1874291320,965362519,
use time : 10617

qSortArray4
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的區別有哪些區別這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！