将Scala数组转换为唯一排序列表的有效方法

Question

任何人都可以在Scala中优化以下语句:

// maybe large
val someArray = Array(9, 1, 6, 2, 1, 9, 4, 5, 1, 6, 5, 0, 6) 

// output a sorted list which contains unique element from the array without 0
val newList=(someArray filter (_>0)).toList.distinct.sort((e1, e2) => (e1 > e2))

由于性能至关重要,有更好的方法吗？

谢谢.

Answer 1

这条简单的线是迄今为止最快的代码之一:

someArray.toList.filter (_ > 0).sortWith (_ > _).distinct

但到目前为止,明显的赢家是 - 由于我的测量 - 杰德韦斯利 - 史密斯.也许如果Rex的代码是固定的,它看起来会有所不同.

典型免责声明1 + 2:

1. 我修改了代码以接受一个数组并返回一个List.
2. 典型基准考虑:
   • 这是随机数据,均匀分布.对于100万个元素,我在0到1百万之间创建了一个100万英寸的数组.因此,或多或少的零,以及或多或少的重复,它可能会有所不同.
   • 它可能取决于机器等.我使用单核CPU,Intel-Linux-32bit,jdk-1.6,scala 2.9.0.1

以下是底层涂层代码和生成图形的具体代码(gnuplot).Y轴:以秒为单位的时间.X轴:阵列中的100 000到1 000 000个元素.

更新:

在发现Rex代码的问题之后,他的代码和Jed的代码一样快,但最后一个操作是将他的Array转换为List(以填满我的基准界面).使用a var result = List [Int],并result = someArray (i) :: result加速他的代码,使其速度大约是Jed-Code的两倍.

另一个可能有趣的发现是:如果我按照filter/sort/distinct(fsd)=>(dsf,dfs,fsd,...)的顺序重新排列我的代码,则所有6种可能性都没有显着差异.

Answer 2

我没有测量过,但是我和Duncan在一起,排序到位然后使用类似的东西:

util.Sorting.quickSort(array)
array.foldRight(List.empty[Int]){ 
  case (a, b) => 
    if (!b.isEmpty && b(0) == a) 
      b 
    else 
      a :: b 
}

从理论上讲,这应该是非常有效的.