重複搜索Scala迭代器的最有效方法

Question

我有一個很大的文本文件，它由從Gigaword構建的Word2Vec向量組成（它的大小超過3GB），每行都是一個單詞及其相應的向量。它按頻率排序，以便列表中的高頻詞比低頻詞更高。

對於給定的單詞列表，我需要構建一個包含單詞和它的word2vec向量的Scala地圖。下面是我的做法：

---

1. 每個字，打開該文件作爲一個迭代器：

   val it = scala.io.Source.fromFile(filePath).getLines()

2. 使用find找到匹配的單詞，用默認值，如果未找到：

   val match = it.find(_.split(" ").head == word).getOrElse("zzz" 0d)

---

這裏是我的全部方法：

def buildArray2b: (Double, Array[(String, breeze.linalg.DenseVector[Double])]) = { 
val startAll = System.currentTimeMillis().toDouble 
val stream = (for (word <- this.vocabulary.map(each => each.toLowerCase)) yield { 
    println("starting " + word) 
    val start = System.currentTimeMillis().toDouble 
    println("building iterator") 
    val iterator = Source.fromInputStream(this.inputStream).getLines() 
    println("finding") 
    val line = iterator.find(it => it.split(" ").head == word).getOrElse("zzz 0.0") 
    println("found") 
    val splitLine = line.split(" ")                  //split string into elements 
    val tail = splitLine.tail.map(_.toDouble)                //build w2v vector 
    val vectorizedLine = splitLine.head -> breeze.linalg.DenseVector(tail)        //build map entry 
    val stop = System.currentTimeMillis().toDouble 
    println(word + ":" + (stop - start)/1000d) 
    vectorizedLine 
}).toArray 
val stopAll = System.currentTimeMillis().toDouble 
val elapsed = (stopAll - startAll)/1000d 
(elapsed, stream) 

}

這裏是與時俱進的輸出，找到下面的話 「一」， 「阿Q精神」 和 「」：

scala> w2v.buildArray2 
a:0.001 
quixotic:0.795 
the:25.6 

我不知道爲什麼它沒有時間找到「quixotic」（與「a」和「the」相比，它應該是「遠」），b永遠找到「the」這個詞。我對數據結構的經驗很少，所以我很感激（1）對這個問題的深入瞭解，以及（2）關於如何使這個過程更高效的任何建議。

爲此，我已經試過如下：

1. 加載整個文件轉換成地圖。這需要很長時間才能首先轉換爲序列，然後轉換爲地圖。
2. 將.txt文件轉換爲.json文件，然後使用包（在本例中爲json4s）將該.json文件直接打開到地圖中。我遇到了內存錯誤（我已經有14g的內存分配給這個項目）。

在此先感謝您的任何意見/見解！

Answer 1

斯卡拉的Iterator是有狀態的，不打算共享或重用。任何可能的共享或重用都完全取決於迭代的基礎資源。即您可以安全地迭代文件多次，但在下載流中重複使用迭代器沒有任何意義。

您可以通過將vocabulary轉換爲Map或Set來實現線性時間&恆定空間。在高層次上，你需要遍歷各行內word2vec文件，並檢查單詞是否在你的vocabulary，那麼如果是&重量添加文字到地圖是這樣的：

val vocab = this.vocabulary.toSet 
val it = Source.fromInputStream(inputStream).getLines 
val result: Map[String, DenseVector] = foldLeft(Map.empty[String, DenseVector]){(acc, line) => 
    val Array(word, weight) = line.split(" ") 
    if(vocab.contains(word)) 
     acc + (word -> breeze.linalg.DenseVector(weight.toDouble)) 
    else 
     acc 
} 

foldLeft迭代從迭代器的左側（即頭部）遍歷整個文件。在每一行，它檢查單詞是否是詞彙單詞，如果是，則將其添加到映射（acc），然後在處理了所有迭代器後返回。

Answer 2

使用地圖

只要你有使用Map[String,Vector[String]]將開始一個不錯的選擇，沒有記憶問題。 一次讀取文件並將數據放入一個Map中。您幾乎已經在那裏了，因爲幾乎所有Seq[Tuple2]都可以使用toMap輕鬆轉換爲地圖。 你將得到每個密鑰constant time access。

轉換爲json

這會增加額外的間接步驟。它只會讓需要分析和處理的數據增長，並使進程變得更慢。

迭代和重複使用

援引官方文件斯卡拉：http://www.scala-lang.org/api/current/index.html#scala.collection.IteratorThey have a hasNext method for checking if there is a next element available, and a next method which returns the next element and discards it from the iterator.因此，通過定義一個Iterator是不能重複使用。