최근 스터디에서 scala를 주제로 학습하고 있다. 단순히 scala 책만 보려니 재미 없어서 생각하는 프로그래밍 책을 읽으면서 알고리즘 공부도 좀 하면서 scala 언어도 배워가고 있다.

요구사항은 다음과 같다.

최대 40억 개의 32비트 정수가 랜덤한 순서로 들어있는 순차적 파일이 주어졌다. 이 때 이 파일에 포함되지 않은 임의의 32비트 정수 하나를 찾아라. (적어도 하나는 없을 것임이 분명하다. - 이유는?) 메모리는 수백 바이트 밖에 없고, 너댓 개의 외부 임시 파일을 사용할 수 있는 상황이라면 어떻게 해결할 수 있을까?

뭐 혼자 문제를 풀기는 힘들어 책의 힌트에서 아이디어를 얻어 scala로 구현을 시작했다. 일단 시작 단계는 동작하도록 구현하는데 집중한 코드는 다음과 같이 완전 지저분하다.

package pearls.essay2

import scala.io.Source
import pearls.support.Utils
import java.io.File
import java.io.FileWriter
import java.io.PrintWriter
import java.nio.file.Files

object MissFinder {
  private val prefix = "resources/pearls/essay2/"
  val lowerFileName = prefix + "lower.txt"
  val higherFileName = prefix + "higher.txt"
  private val tempFileName = prefix + "tempdata.txt"
    
  def getCenter(start: Int, end: Int) = {
    (start + end)/2
  }
  
  def getValue(fileName: String): Int = {
  	val lines = Source.fromFile(fileName).getLines()
  	if (lines.isEmpty) 
  		0
  	else 
  		lines.next().toInt
  }
  
  def getMissedValue(): Int = {
  	getMissedValue(getValue(lowerFileName), getValue(higherFileName))
  }
  
  def getMissedValue(lowerValue: Int, higherValue: Int): Int = {
  	if (higherValue > 0) {
  		higherValue - 1
  	} else {
  		lowerValue + 1
  	}
  }
  
  def findNo(fileName: String): Int = {
    def findMissedSector(start: Int, end: Int, missedFileName: String): Int = {
      println("start : " + start + " end : " + end)
      
      if (end - start == 1 || end - start == 0) {
        return getMissedValue()
      }
        
      val center = getCenter(start, end)
      var lower = 0
      var higher = 0
      
      Files.copy(new File(missedFileName).toPath(), new File(tempFileName).toPath())
      
      val lowerPW = new PrintWriter(new File(lowerFileName))
      val higherPW = new PrintWriter(new File(higherFileName))
      val linesSource = Source.fromFile(tempFileName)
      val lines = linesSource.getLines
      lines.foreach(line => {
        if (line.toInt > center) {
          higher += 1
          higherPW.println(line)
        } else {
          lower += 1
          lowerPW.println(line)
        }
      })

      lowerPW.close
      higherPW.close
      linesSource.close
      Files.delete(new File(tempFileName).toPath())

      println("center : " + center + " higher : " + higher + " lower : " + lower)
      if (end - center == higher)
        findMissedSector(start, center, lowerFileName)
      else
        findMissedSector(center, end, higherFileName)
    }
    
    findMissedSector(0, 1000, prefix + fileName)
  }

  def main(args: Array[String]): Unit = {
    println(findNo("missfiledata.txt"))
  }
}

위와 같이 구현한 후 지금까지 내가 알고 있는 scala 지식 범위 내에서 리팩토링 시작해 다음 단계까지 진행했다.

object Utils {
  def withPrintWriter(fileName: String)(op: PrintWriter => Unit) {
    withPrintWriter(new File(fileName))(op)
  }
  
  def withPrintWriter(f: File)(op: PrintWriter => Unit) {
    val p = new PrintWriter(f)
    try { op(p) } finally { p.close() }
  }

  def withPrintWriter2(fileName1: String, fileName2: String)(op: (PrintWriter, PrintWriter) => Unit) {
    withPrintWriter2(new File(fileName1), new File(fileName2))(op)
  }  
  
  def withPrintWriter2(f1: File, f2: File)(op: (PrintWriter, PrintWriter) => Unit) {
    val p1 = new PrintWriter(f1)
    val p2 = new PrintWriter(f2)
    try { op(p1, p2) } finally { p1.close; p2.close }
  }
  
  def withFileWriter(f: File)(op: FileWriter => Unit) {
    val fw = new FileWriter(f, true)
    try { op(fw) } finally { fw.close() }
  }
  
  def withFileLines(fileName: String)(op: Iterator[String] => Unit) {
    val source = Source.fromFile(fileName)
    try { op(source.getLines()) } finally { source.close }
  }
}

package pearls.essay2

import scala.io.Source
import pearls.support.Utils._

import java.io.File
import java.io.FileWriter
import java.io.PrintWriter
import java.nio.file.Files

object MissFinder {
  private val prefix = "resources/pearls/essay2/"
  private val tempFileName = prefix + "tempdata.txt"
  val lowerFileName = prefix + "lower.txt"
  val higherFileName = prefix + "higher.txt"

  def getCenter(start: Int, end: Int) = {
    (start + end) / 2
  }

  def getValue(fileName: String): Int = {
    val lines = Source.fromFile(fileName).getLines()
    if (lines.isEmpty)
      return 0
    lines.next().toInt
  }

  def getMissedValue(): Int = {
    getMissedValue(getValue(lowerFileName), getValue(higherFileName))
  }

  def getMissedValue(lowerValue: Int, higherValue: Int): Int = {
    if (higherValue > 0)
      return higherValue - 1
    lowerValue + 1
  }
  
  def findNo(fileName: String): Int = {
    def copyToWorkingFromOriginal(originalFileName: String) {
      if (new File(tempFileName).exists)
        Files.delete(new File(tempFileName).toPath())
      Files.copy(new File(originalFileName).toPath(), new File(tempFileName).toPath())
    }
    
    def divideHighAndLow(center: Int): Tuple2[Int, Int] = {
      var lower, higher = 0
      
      def plusOneAndPrint(lowerFile: PrintWriter, higherFile: PrintWriter, line: String) {
        if (line.toInt > center) { higher += 1; higherFile.println(line) } 
        else {lower += 1; lowerFile.println(line)} 
      }
      
      withFileLines(tempFileName) {
        lines => {
          withPrintWriter2(lowerFileName, higherFileName) {
            (lowerFile, higherFile) => { lines.foreach { line => plusOneAndPrint(lowerFile, higherFile, line) }}
          }          
        }
      }

      println(" lower : " + lower + ", center : " + center + ", higher : " + higher)
      (lower, higher)
    }
    
    def findMissedSector(start: Int, end: Int, originalFileName: String): Int = {
      if (end - start == 1 || end - start == 0) {
        return getMissedValue()
      }

      copyToWorkingFromOriginal(originalFileName)
      
      val center = getCenter(start, end)
      val lowAndHigh = divideHighAndLow(center)
      
      if (end - center == lowAndHigh._2)
        findMissedSector(start, center, lowerFileName)
      else
        findMissedSector(center, end, higherFileName)
    }

    findMissedSector(0, 1000, prefix + fileName)
  }

  def main(args: Array[String]): Unit = {
    println(findNo("missfiledata.txt"))
  }
}

물론 아직도 부족한 부분이 많아 보이고 복잡하다. 내가 집중한 부분은 파일에서 데이터를 읽어 두 개의 파일로 나누는 부분에 대한 리팩토링 작업을 연습해 봤다. 그 코드만 살펴보면 다음과 같다.

    def divideHighAndLow(center: Int): Tuple2[Int, Int] = {
      var lower, higher = 0
      
      def plusOneAndPrint(lowerFile: PrintWriter, higherFile: PrintWriter, line: String) {
        if (line.toInt > center) { higher += 1; higherFile.println(line) } 
        else {lower += 1; lowerFile.println(line)} 
      }
      
      withFileLines(tempFileName) {
        lines => {
          withPrintWriter2(lowerFileName, higherFileName) {
            (lowerFile, higherFile) => { lines.foreach { line => plusOneAndPrint(lowerFile, higherFile, line) }}
          }          
        }
      }

      println(" lower : " + lower + ", center : " + center + ", higher : " + higher)
      (lower, higher)
    }

위 소스 코드에서 lower와 higher에 +1하는 방식으로 구현하고 있는데 val을 쓰면서 처리할 수 있는 방법은 없을까? lower와 higher 값을 가지는 객체를 만들까도 생각해 봤다.

scala 나름 연습해 볼 수록 재미있는 언어라는 생각이 든다. 근데 너무 자유도가 높아서 슬슬 짜증이 나려고도 한다.