DouKaku? 1740 yuin: 素直に付き合わせるとどうなるのかな？と思...(モノクロ画像の類似検索)

Comment detail

素直に付き合わせるとどうなるのかな？と思ったので素直につき合わせ。

このお題の趣旨は検索処理の実行速度、とあるので本物の画像ではなく、配列を生成して画像に見立てました。

Ahtlon64 3000で32秒くらいです。遅いですねえ・・・実用的な速度がどの程度をさすのかわかりませんが、まぁ使えないことはないですよね。

object Similar {
  type CMap = Array[Array[int]]
  def similarityScore(c1:CMap, c2:CMap) = {
    (0 to c1(0).length-1).foldLeft(0){(r,y) => {
      r + (0 to c1.length-1).foldLeft(0){(r,x) => {
        r + (c1(x)(y)^c2(x)(y)^1)
      }}
    }}
  }

  def select(c1:CMap, clist:Array[CMap]) = {
    var r:CMap = null
    var topScore = 0
    clist.foreach(c => {
      val s = similarityScore(c1, c)
      if(s > topScore) {
        r = c
        topScore = s
      }
    })
    (topScore, r)
  }

  def makeRandomCMap(width:int, height:int):CMap = {
    new Array[int](height).map(y => {
      new Array[int](width).map(x => Math.random.hashCode & 0x1)
    })
  }
}

val width = 1024
val height = 768
val c1 = Similar.makeRandomCMap(width, height)
val clist = List.range(0, 100).map(x => Similar.makeRandomCMap(width, height)).toArray
println("start")
val start = System.currentTimeMillis
val (score, c) = Similar.select(c1, clist)
println("top score:"+score)
println("time:"+(System.currentTimeMillis-start) + " milli seconds.")

これじゃScalaが完全にダメな子になるので
続いてパフォーマンス重視版。

同じ環境で一気に1.2秒程度になりました。
foldLeftやforeachの関数呼び出しに時間が
かかるので、そこをwhileループにしてやると
速くなります。

ので呼び出し回数が多いsimilarityScoreをwhileに変更。

http://www.scala-lang.org/docu/faq.html#id2243538

らへんを参照。速度的にはwhile,for,mapなどIterableのメソッド、の順です。

import java.util.Random
object Similar {
  type CMap = Array[Array[int]]
  def similarityScore(c1:CMap, c2:CMap) = {
    var score = 0
    var i = 0
    var height = c1.length
    var width  = c1(0).length
    while(i < height) {
      var score2 = 0
      var j = 0
      while(j < width) {
        score2 = score2 + (c1(i)(j)^c2(i)(j)^1)
        j = j+1
      }
      score = score + score2
      i = i+1
    }
    score
  }

  def select(c1:CMap, clist:Array[CMap]) = {
    var r:CMap = null
    var topScore = 0
    clist.foreach(c => {
      val s = similarityScore(c1, c)
      if(s > topScore) {
        r = c
        topScore = s
      }
    })
    (topScore, r)
  }

  def makeRandomCMap(width:int, height:int):CMap = {
    val rand = new Random
    new Array[int](height).map(y => {
      new Array[int](width).map(x => rand.nextInt(2))
    })
  }

  def main(args: Array[String]) = {
    val width = 1024
    val height = 768
    val c1 = Similar.makeRandomCMap(width, height)
    val clist = List.range(0, 100).map(x => Similar.makeRandomCMap(width, height)).toArray
    println("start")
    val start = System.currentTimeMillis
    val (score, c) = Similar.select(c1, clist)
    println("top score:"+score)
    println("time:"+(System.currentTimeMillis-start) + " milli seconds.")
  }
}

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq