一种将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

但到目前为止，根据我的测量，最明显的赢家是Jed Wesley-Smith。也许雷克斯的代码修好了，它看起来就不一样了。

​

​

典型的免责声明1+ 2：

1. 我修改了代码以接受数组并返回列表。
2. Typical benchmark注意事项：
   • 这是随机数据，分布均匀。对于一百万个元素，我创建了一个介于0和一百万之间的一百万个整数数组。因此，对于或多或少的零，以及或多或少的重复，它可能会不同。

   ，

   • ，这可能取决于机器，等等。我使用的是单核CPU，英特尔-Linux-32位，jdk-1.6，scala 2.9.0.1

​

下面是生成图形的底层benchcoat-code and the concrete code (gnuplot)。Y轴:以秒为单位的时间。X轴:数组中的100 000到1 000 000个元素。

更新：

在发现Rex代码的问题后，他的代码与Jed的代码一样快，但最后的操作是将他的Array转换为列表(以填充我的基准测试接口)。使用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 
}

从理论上讲，这应该是相当有效的。

Answer 3

如果没有基准测试，我不能确定，但我认为以下是相当有效的：

val list = collection.SortedSet(someArray.filter(_>0) :_*).toList

也可以尝试在您的版本中在someArray之后添加.par。不能保证它会更快，但可能会更快。您应该运行基准测试并进行实验。

sort已弃用。请改用.sortWith(_ > _)。