Медленный ввод-вывод с большими данными

Question

Я пытаюсь найти лучший способ сделать это, так как это может занять годы!Мне нужно вычислить карту, которая слишком велика, чтобы поместиться в памяти, поэтому я пытаюсь использовать IO следующим образом.

У меня есть файл, который содержит список Ints, около 1 миллионаих.У меня есть другой файл, который содержит данные о моей (500 000) коллекции документов.Мне нужно вычислить функцию подсчета, для каждого Int в первом файле, сколько документов (строк во втором) он появляется. Позвольте мне привести пример:

File1:

-1
1
2
etc...

file2:

E01JY3-615,  CR93E-177 , [-1 -> 2,1 -> 1,2 -> 2,3 -> 2,4 -> 2,8 -> 2,... // truncated for brevity] 
E01JY3-615,  CR93E-177 , [1 -> 2,2 -> 2,4 -> 2,5 -> 2,8 -> 2,... // truncated for brevity]
etc...

Вот то, что я пробовал до сих пор

def printToFile(f: java.io.File)(op: java.io.PrintWriter => Unit) {
    val p = new java.io.PrintWriter(new BufferedWriter((new FileWriter(f))))
    try {
      op(p)
    } finally {
      p.close()
    }
  }

  def binarySearch(array: Array[String], word: Int):Boolean = array match {
    case Array() => false
    case xs      => if (array(array.size/2).split("->")(0).trim().toInt == word) {
      return true
    } else if (array(array.size/2).split("->")(0).trim().toInt > word){
      return binarySearch(array.take(array.size/2), word)
    } else {
      return binarySearch(array.drop(array.size/2 + 1), word)
    }
  }

  var v = Source.fromFile("vocabulary.csv").getLines()

  printToFile(new File("idf.csv"))(out => {
    v.foreach(word =>{
      var docCount: Int = 0
      val s = Source.fromFile("documents.csv").getLines()
      s.foreach(line => {
        val split = line.split("\\[")
        val fpStr = split(1).init
        docCount = if (binarySearch(fpStr.split(","), word.trim().toInt)) docCount + 1 else docCount
      })
      val output = word + ", " + math.log10(500448 / (docCount + 1))
      out.println(output)
      println(output)
    })
  })

Должен быть более быстрый способ сделать это, кто-нибудь может придумать способ?

Answer 1

Исходя из того, что я понимаю в вашем коде, вы пытаетесь найти каждое слово в словаре в списке документов. Следовательно, вы делаете N * M сравнений, где N - количество слов (в словаре с целыми числами), а M - количество документов в списке документов. Используя ваши значения, вы пытаетесь вычислить 10 ^ 6 * 5 * 10 ^ 5 сравнений, что составляет 5 * 10 ^ 11. Неосуществимым.

Почему бы не создать изменяемую карту со всеми целыми числами в словаре в качестве ключей (1000000 дюймов в памяти - примерно 3,8 млн. От моих измерений) и пройти список документов только один раз, где для каждого документа вы извлекаете целые числа и увеличиваете их соответствующие значения на карте (для которых целое число является ключевым).

Примерно так:

import collection.mutable.Map
import scala.util.Random._

val maxValue = 1000000

val documents = collection.mutable.Map[String,List[(Int,Int)]]()

// util function just to insert fake input; disregard
def provideRandom(key:String) ={ (1 to nextInt(4)).foreach(_ => documents.put(key,(nextInt(maxValue),nextInt(maxValue)) :: documents.getOrElse(key,Nil)))}

// inserting fake documents into our fake Document map 
(1 to 500000).foreach(_ => {val key = nextString(5); provideRandom(key)})

// word count map
val wCount = collection.mutable.Map[Int,Int]()

// Counting the numbers and incrementing them in the map
documents.foreach(doc => doc._2.foreach(k => wCount.put(k._1, (wCount.getOrElse(k._1,0)+1))))

scala> wCount
res5: scala.collection.mutable.Map[Int,Int] = Map(188858 -> 1, 178569 -> 2, 437576 -> 2, 660074 -> 2, 271888 -> 2, 721076 -> 1, 577416 -> 1, 77760 -> 2, 67471 -> 1, 804106 -> 2, 185283 -> 1, 41623 -> 1, 943946 -> 1, 778258 -> 2...

в результате получается карта, ключами которой являются число в dict, а значением - количество раз, которое она появляется в списке документов

Это упрощено с

• Я не проверяю, существует ли число в словаре, хотя вам нужно только инициировать карту со значениями, а затем увеличивать значение в окончательной карте, если у него есть этот ключ;
• Я не делаю IO, что ускоряет все это

Таким образом, вы проходите документы только один раз, что делает задачу снова выполнимой.