斯卡拉組合功能未終止

我需要生成的組合使用scalas組合方法的流/列表斯卡拉組合功能未終止

1 to 30000.toStream.combinations(2).size

此功能永遠不會完成30,000項的列表。當我在Python中嘗試相同的操作時

r = list(range(1,30000)) 
z = itertools.combinations(r, 2) 
%time sum(1 for _ in z)

該操作在26.2秒內完成。

這是怎麼回事？我如何生成scala中非常大的列表的組合？

來源

2016-11-15 user2726995

我不知道爲什麼在stdlib中的實現需要這麼長時間。然而，這種簡單的實現（專用於對和List S），相當於Python的一個：

def combinations2[A](l: List[A]): Iterator[(A, A)] = 
    l.tails.flatMap(_ match { 
    case h :: t => t.iterator.map((h, _)) 
    case Nil => Iterator.empty 
    })

然後

scala> { 
    | val t0 = System.nanoTime 
    | val res = combinations2((1 to 30000).toList).size 
    | val secs = (System.nanoTime - t0)/1000000.0 
    | s"$res (computed in $secs seconds)" 
    | } 
res11: String = 449985000 (computed in 24992.487638 seconds)

來源

2016-11-15 17:08:05

請注意，「組合」方法指定每個組合只能出現一次。所以'List（1，2，2）.combinations（2）.toList.ordered == List（List（1，2），List（2，1））''。我不知道OP是否對這個屬性感興趣，但是在你的輸出上運行'distinct'確實需要一些時間（儘管可能比stdlib的實現時間少得多）。 –

@TomasMikula提供替代方案，我很感興趣，看看爲什麼combinations是生成結果效率低下。

就讓我們來看看使用任務控制和飛行記錄揭示了問題：

的CombinationItr迭代器調用IndexedSeqOptimized.slice的next()每個迭代。 ArrayBuilder每次運行時都會創建一個新的構建器，其中包含迭代需要的元素數量，這意味着它將分配30,000個Array[Int]，每個元素包含n-1個元素，在1分鐘的示例中總共導致11.10GB。這導致大量的GC壓力，通常不是非常有效。

來源

2016-11-15 18:21:30

這是一個很好的解釋。萬分感謝。 – user2726995

斯卡拉組合功能未終止

回答

相關問題