Scala：構建外部合併排序的文件讀取

我想在Scala中實現外部合併排序。它用於排序整個主內存中不適合的大文件。Scala：構建外部合併排序的文件讀取

詳細信息可以在這裏找到： - How external merge sort algorithm works?

現在，我需要閱讀的文件塊，排序，並將其寫入到磁盤等等等等

什麼是閱讀的最地道的/功能性的方式/寫一個大文件的部分？

如果我使用'Source.fromFile（filename）.getLines'方法，我知道我得到一個遍歷文件的迭代器，並且可以分段讀取它。但是當我得到一個迭代器時，在主內存中讀取了多少文件？是否有可能從中讀取固定數量的字節？
關於如何實現這個的任何其他建議？可能有一些指向fs2（scalaz-stream）/ Akka Stream/Monix實現的地方，我可以將該文件視爲Stream並以塊讀取？

來源

2017-09-04 Aarsh Shah

分塊排序/寫作

假設你想保留N個數在內存中的時間和進一步假設你被賦予其寫入N個分割的數字到一個文件中的函數：

val N : Int = ??? 

val writeToFile : Seq[Int] => Unit = ???

正如你的問題表明，一個Iterator可以用來在RAM中只保留N個數在一個時間對它們進行排序，並將其寫入中間文件：

val sourceFileName : String = ??? 

val sortAndWrite : Seq[Int] => Unit = 
    (_.sorted) andThen writeToFile 

Source 
    .fromFile(sourceFileName) 
    .getLines 
    .map(_.toInt) 
    .grouped(N) 
    .foreach(sortAndWrite)

現在你在不同的文件中有每組N個數字。剩下的唯一事情就是將這些文件合併在一起。

合併

由於從各個子文件返回迭代一些閱讀功能：

val subFiles : Iterable[Iterator[String]] = ???

我們可以寫，將返回一個新的迭代，從得到的值的函數每個文件和排序他們：

val mergeSort : Iterable[Iterator[String]] => Iterator[Int] = 
    (fileIterators) => { 

    val nonEmptyFiles = fileIterators filter (_.hasNext) 

    nonEmptyFiles 
     .map(_.next) 
     .map(_.toInt) 
     .sorted 
     .toIterator ++ mergeSort(nonEmptyFiles) 
    }

注：上述功能將保持單一Integer在每個文件的內存中，因此RAM使用率取決於writeToFile創建的文件數量。

現在只值寫入文件：

val destinationFileName : String = ??? 

val writer : Writer = new FileWriter(destinationFileName) 

mergeSort(subFiles) foreach (i => writer write i.toString)

不完善排序

有一點需要注意：如果N是小和源文件是不夠的隨機則該解決方案將不產生完美的排序。例如：假設N = 2和初始列表是[10,11,0,1]，那麼算法在一次通過後將產生[0,10,1,11]作爲結果。

來源

2017-09-04 17:09:38

老兄，我正在考慮做這個爲期一個月的項目。但看起來你在15分鐘內完成了大部分工作。你的男人的帽子！輝煌＆鼓舞人心的東西:) –

你認爲我們可以通過做k-way合併，而不是每次排序列表，讓這更高效嗎？（在合併階段） –

@AarshShah我不知道你的意思是「k-way merge」。 mergeSort每次迭代都會從每個非空子文件中讀取一個Integer，並在再次從磁盤讀取數據之前對這些ints進行排序。那是你在找什麼？ –

Scala：構建外部合併排序的文件讀取

回答

相關問題