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.

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 : 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

以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • Scala解析Json字符串的实例详解

    Scala解析Json字符串的实例详解 1. 添加相应依赖 Json解析工具使用的 json-smart,曾经对比过Java的fastjson.gson.Scala的json4s.lift-json.其中 json-smart 解析速度是最快的. <dependency> <groupId>net.minidev</groupId> <artifactId>json-smart</artifactId> <version>2.3<

  • Scala入门之List使用详解

    Scala中使用List Scala是函数式风格与面向对象共存的编程语言,方法不应该有副作用是函数风格编程的一个重要的理念.方法唯一的效果应该是计算并返回值,用这种方式工作的好处就是方法之间很少纠缠在一起,因此就更加可靠和可重用.另一个好处(静态类型语言)是传入传出方法的所有东西都被类型检查器检查,因此逻辑错误会更有可能把自己表现为类型错误.把这个函数式编程的哲学应用到对象世界里以为着使对象不可变. 前面一章介绍的Array数组是一个所有对象都共享相同类型的可变序列.比方说Array[Strin

  • Java泛型模拟scala实现自定义ArrayList方式

    目录 泛型模拟scala实现自定义ArrayList 自定义实现ArrayList代码 泛型模拟scala实现自定义ArrayList 泛型就是将类型由原来的具体的类型参数化,类似于方法中的变量参数,此时类型也定义成参数形式(可以称之为类型形参), 然后在使用/调用时传入具体的类型 操作的数据类型被指定为一个参数,这种参数类型可以用在类.接口和方法中,分别被称为泛型类.泛型接口.泛型方法. 以下实例通过泛型,灵活的实现了类似scala中集合的map,reduce方法,并可以链式编程 Functi

  • 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,不可变(im

  • 对numpy中array和asarray的区别详解

    array和asarray都可以将结构数据转化为ndarray,但是主要区别就是当数据源是ndarray时,array仍然会copy出一个副本,占用新的内存,但asarray不会. 举例说明: import numpy as np #example 1: data1=[[1,1,1],[1,1,1],[1,1,1]] arr2=np.array(data1) arr3=np.asarray(data1) data1[1][1]=2 print 'data1:\n',data1 print 'ar

  • 浅析scala中map与flatMap的区别

    在函数式语言中,函数作为一等公民,可以在任何地方定义,在函数内或函数外,可以作为函数的参数和返回值,可以对函数进行组合.由于命令式编程语言也可以通过类似函数指针的方式来实现高阶函数,函数式的最主要的好处主要是不可变性带来的.没有可变的状态,函数就是引用透明(Referential transparency)的和没有副作用(No Side Effect). 任何一种函数式语言中,都有map函数与faltMap这两个函数,比如python虽然不是纯函数式语言,也有这两个函数.再比如在jdk1.8之后

  • C# 中 Array和 ArrayList详解及区别

    C# 中 Array和 ArrayList详解及区别 一.Array 的用法 type[] typename=new type[size]; 或者 type[] typename=new type[]{ }; Array类型的变量在声明的同时必须进行实例化(如果初始化至少得初始化数组的大小) 平常我们int[],string[]...事实上就是声明一个array数组了 如: string [] srt=new string[]{"a","b"}; int[] a=n

  • 详解c#中Array,ArrayList与List<T>的区别、共性与相互转换

    目录 Array,ArrayList and List<T> Array 一维数组 定义 初始化赋值 多维数组 定义 初始化赋值 元素赋值和获取元素 交错数组 定义 初始化赋值 获取元素和单个赋值 方法和属性 改 查 获取长度 Array.ConvertAll() 数据类型转换 切片 获取单个元素和赋值 Array.ForEach 循环 ArrayList 定义 初始化赋值 循环 方法和属性 List<T> 定义 初始化 循环 方法和属性 属性 长度 属性 取值 增 查 删 改 切

  • scala中常用特殊符号详解

    =>(匿名函数)  => 匿名函数,在Spark中函数也是一个对象可以赋值给一个变量. Spark的匿名函数定义格式: (形参列表) => {函数体} 所以,=>的作用就是创建一个匿名函数实例. 比如:(x:Int) => x +1 ,就等同于下面的Java方法: public int function(int x) { return x+1; } 示例: class Symbol { var add = (x: Int) => x + 1 } object test2

  • 浅析Java和Scala中的Future

    随着CPU的核数的增加,异步编程模型在并发领域中的得到了越来越多的应用,由于Scala是一门函数式语言,天然的支持异步编程模型,今天主要来看一下Java和Scala中的Futrue,带你走入异步编程的大门. Future 很多同学可能会有疑问,Futrue跟异步编程有什么关系?从Future的表面意思是未来,一个Future对象可以看出一个将来得到的结果,这就和异步执行的概念很像,你只管自己去执行,只要将最终的结果传达给我就行,线程不必一直暂停等待结果,可以在具体异步任务执行的时候去执行其他操作

  • PHP中isset与array_key_exists的区别实例分析

    本文实例讲述了PHP中isset与array_key_exists的区别.分享给大家供大家参考.具体分析如下: 1.对于数组值的判断不同,对于值为null或''或false,isset返回false,array_key_exists返回true: 2. 执行效率不同,isset是内建运算符,array_key_exists是php内置函数,isset要快一些.请参考:PHP 函数实现原理及性能分析 3.当用isset访问一个不存在索引数组值时,不会引起一个E_NOTICE的php错误消息: 4.

  • 浅谈Java中Collection和Collections的区别

    1.java.util.Collection 是一个集合接口.它提供了对集合对象进行基本操作的通用接口方法.Collection接口在Java 类库中有很多具体的实现.Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式. Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set 2.java.util.Collections 是一个包装类.它包含有各种有关集合操作的静态多态方法.此类不能实例化,就像一

  • iOS中setValue和setObject的区别详解

    网上关于setValue和setObject的区别的文章很多,说的并不准确,首先我们得知道: setObject:ForKey: 是NSMutableDictionary特有的:setValue:ForKey:是KVC的主要方法 话不多说,上代码: - (void)viewDidLoad { [super viewDidLoad]; //setObject和setvalue的区别 NSMutableDictionary *dic = [NSMutableDictionary dictionary

随机推荐