2016-09-19 385 views
4

我有一個21.6GB的文件,我想從頭到尾讀取它,而不是像從前一樣,從頭到尾閱讀。爲什麼ReversedLinesFileReader這麼慢?

如果我使用下面的代碼從頭到尾讀取文件的每一行,則需要1分12秒。

val startTime = System.currentTimeMillis() 
File("very-large-file.xml").forEachLine { 
    val i = 0 
} 
val diff = System.currentTimeMillis() - startTime 
println(diff.timeFormat()) 

現在,我已閱讀,在反向讀取文件,然後我應該使用ReversedLinesFileReader從Apache的百科全書。我創建了下面的擴展功能來做到這本:

fun File.forEachLineFromTheEndOfFile(action: (line: String) -> Unit) { 
    val reader = ReversedLinesFileReader(this, Charset.defaultCharset()) 
    var line = reader.readLine() 
    while (line != null) { 
     action.invoke(line) 
     line = reader.readLine() 
    } 

    reader.close() 
} 

然後調用它以下面的方式,這是同前路只有到forEachLineFromTheEndOfFile函數的調用:

val startTime = System.currentTimeMillis() 
File("very-large-file.xml").forEachLineFromTheEndOfFile { 
    val i = 0 
} 
val diff = System.currentTimeMillis() - startTime 
println(diff.timeFormat()) 

這跑了17分50秒跑!

  • 我正在以正確的方式使用ReversedLinesFileReader嗎?
  • 我在SSD上運行帶有Ext4文件系統的Linux Mint。這可能與它有什麼關係?
  • 是不是應該從頭到尾閱讀文件?
+0

你知道什麼是數據的模樣?這條生產線有多統一? –

+0

@BrianKent,我不確定你的意思是如何統一換行符,但有問題的數據是來自OpenStreetMap項目的XML文件。 – Arthur

+0

您確定需要按相反順序處理文件嗎?我懷疑你會更好地閱讀自然順序中的行,並將大塊數據保存到臨時文件和/或數據庫,然後以這種中間格式處理數據,如果數據塊分成較小的文件和/或數據庫可以然後輕鬆地按相反順序處理。 – mfulton26

回答

1

您正在尋求非常昂貴的操作。您不僅在塊中使用隨機訪問來讀取文件並向後退出(因此,如果文件系統正在讀取,它正在讀取錯誤的方向),您還正在讀取一個UTF-8 XML編碼文件比固定字節編碼慢。

然後最重要的是,你使用的算法效率不高。它在大小不便的時候讀取塊(是否可以識別磁盤塊大小?是否將塊大小設置爲與文件系統匹配?),同時處理編碼並使部分字節數組複製(不必要),然後轉動它變成一個字符串(你需要一個字符串解析?)。它可以創建沒有副本的字符串,並且真正創建該字符串可能會被延遲,並且如果需要(例如,XML解析器也可以從ByteArrays或緩衝區運行),則直接從緩衝區解碼。還有其他的陣列副本不需要,但對代碼更方便。

它也可能有一個錯誤,它會檢查換行符,而不考慮如果實際上是多字節序列的一部分字符可能意味着不同的東西。它將不得不回顧一些額外的字符來檢查這個可變長度編碼,我沒有看到它這樣做。

因此,不是一個很好的向前緩衝文件的順序讀取,這是文件系統上可以做的最快的事情,而是一次隨機讀取1個塊。它至少應該讀取多個磁盤塊,以便能夠使用前向動量(將塊大小設置爲磁盤塊大小的一些倍數將有所幫助),並且還可以避免在緩衝區邊界處製作的「剩餘」副本的數量。

有可能是更快的方法。但它不會像按照順序讀取文件一樣快。

UPDATE:

好了,我試過的實驗包含通過讀取維基數據JSON轉儲前10萬行和扭轉這些線路圍繞數據的27G處理一個相當愚蠢的版本。

我的2015 Mac Book Pro計時器(我的所有開發工具和許多chrome窗口一直開着進食內存和一些CPU,大約5G的內存都是免費的,虛擬機大小是默認設置,根本沒有設置參數,不在調試器中運行):

reading in reverse order: 244,648 ms = 244 secs = 4 min 4 secs 
reading in forward order: 77,564 ms = 77 secs = 1 min 17 secs 

temp file count: 201 
approx char count: 29,483,478,770 (line content not including line endings) 
total line count: 10,050,000 

該算法是讀出由線緩衝原始文件在時間50000線,寫以相反的順序線到編號臨時文件。然後在所有文件被寫入後,它們將以相反的數字順序逐行讀出。基本上將它們分成原始的反向排序順序片段。它可以進行優化,因爲這是該算法最天真的版本,無需任何調整。但是它確實能夠完成文件系統最好的功能,連續讀取和具有良好大小緩衝區的順序寫入。

所以這比你使用的快很多,它可以從這裏調整,以提高效率。你可以交換CPU的磁盤I/O大小,並嘗試使用gzip文件,也可能是一個雙線程模型,在處理前一個文件時有下一個緩衝區。更少的字符串分配,檢查每個文件函數以確保沒有額外的事情發生,確保沒有雙緩衝,等等。

醜陋,但功能代碼:

package com.stackoverflow.reversefile 

import java.io.File 
import java.util.* 

fun main(args: Array<String>) { 
    val maxBufferSize = 50000 
    val lineBuffer = ArrayList<String>(maxBufferSize) 
    val tempFiles = ArrayList<File>() 
    val originalFile = File("/data/wikidata/20150629.json") 
    val tempFilePrefix = "/data/wikidata/temp/temp" 
    val maxLines = 10000000 

    var approxCharCount: Long = 0 
    var tempFileCount = 0 
    var lineCount = 0 

    val startTime = System.currentTimeMillis() 

    println("Writing reversed partial files...") 

    try { 
     fun flush() { 
      val bufferSize = lineBuffer.size 
      if (bufferSize > 0) { 
       lineCount += bufferSize 
       tempFileCount++ 
       File("$tempFilePrefix-$tempFileCount").apply { 
        bufferedWriter().use { writer -> 
         ((bufferSize - 1) downTo 0).forEach { idx -> 
          writer.write(lineBuffer[idx]) 
          writer.newLine() 
         } 
        } 
        tempFiles.add(this) 
       } 
       lineBuffer.clear() 
      } 

      println(" flushed at $lineCount lines") 
     } 

     // read and break into backword sorted chunks 
     originalFile.bufferedReader(bufferSize = 4096 * 32) 
       .lineSequence() 
       .takeWhile { lineCount <= maxLines }.forEach { line -> 
        lineBuffer.add(line) 
        if (lineBuffer.size >= maxBufferSize) flush() 
       } 
     flush() 

     // read backword sorted chunks backwards 
     println("Reading reversed lines ...") 
     tempFiles.reversed().forEach { tempFile -> 
      tempFile.bufferedReader(bufferSize = 4096 * 32).lineSequence() 
       .forEach { line -> 
        approxCharCount += line.length 
        // a line has been read here 
       } 
      println(" file $tempFile current char total $approxCharCount") 
     } 
    } finally { 
     tempFiles.forEach { it.delete() } 
    } 

    val elapsed = System.currentTimeMillis() - startTime 

    println("temp file count: $tempFileCount") 
    println("approx char count: $approxCharCount") 
    println("total line count: $lineCount") 
    println() 
    println("Elapsed: ${elapsed}ms ${elapsed/1000}secs ${elapsed/1000/60}min ") 

    println("reading original file again:") 
    val againStartTime = System.currentTimeMillis() 
    var againLineCount = 0 
    originalFile.bufferedReader(bufferSize = 4096 * 32) 
      .lineSequence() 
      .takeWhile { againLineCount <= maxLines } 
      .forEach { againLineCount++ } 
    val againElapsed = System.currentTimeMillis() - againStartTime 
    println("Elapsed: ${againElapsed}ms ${againElapsed/1000}secs ${againElapsed/1000/60}min ") 
} 
2

探討這個問題的正確方法應該是:

  1. 純Java編寫一個版本的測試。
  2. 基準測試,以確保性能問題仍然存在。
  3. 將其分析以找出性能瓶頸所在。

問:我在正確的方式使用ReversedLinesFileReader?

是的。 (假設使用線閱讀器是一件合適的事情,這取決於你真正想要做什麼,例如,如果你只是想向後數線,那麼你應該閱讀1個字符時間和計算新行序列。)

問:我正在SSD上運行帶有Ext4文件系統的Linux Mint。這可能與它有什麼關係?

可能。反向讀取文件意味着操作系統爲提供快速I/O而使用的預讀策略可能不起作用。它可能會與SSD的特性相互作用。

問:是不是應該從頭到尾讀取文件?

可能。往上看。


另一件你沒有考慮的事情是你的文件實際上可能包含一些非常長的行。瓶頸可能是將字符組合成(長)行。

看看source code,看起來線路很長時,有可能存在O(N^2)行爲。關鍵部分是(我認爲)「翻轉」由FilePart處理。請注意複製「剩餘」數據的方式。