diff options
author | Rocky Madden <git@rockymadden.com> | 2014-01-03 21:19:35 -0700 |
---|---|---|
committer | Rocky Madden <git@rockymadden.com> | 2014-01-03 21:19:35 -0700 |
commit | 9004f973bff2b3b86d1d36c65fa9f0ac55b56fce (patch) | |
tree | 339927cfb6bc319778a559badff15d82b4b1b850 | |
parent | 092307ce380aa57f7a0583856fa69a07304e0c30 (diff) | |
download | stringmetric-9004f973bff2b3b86d1d36c65fa9f0ac55b56fce.tar.gz stringmetric-9004f973bff2b3b86d1d36c65fa9f0ac55b56fce.tar.bz2 stringmetric-9004f973bff2b3b86d1d36c65fa9f0ac55b56fce.zip |
Created memoization decoration.
5 files changed, 64 insertions, 8 deletions
diff --git a/core/src/main/scala/com/rockymadden/stringmetric/Algorithm.scala b/core/src/main/scala/com/rockymadden/stringmetric/Algorithm.scala index 96cf142..1200926 100755 --- a/core/src/main/scala/com/rockymadden/stringmetric/Algorithm.scala +++ b/core/src/main/scala/com/rockymadden/stringmetric/Algorithm.scala @@ -1,6 +1,7 @@ package com.rockymadden.stringmetric object Algorithm { + import scala.collection.immutable.Map import Transform.StringTransform @@ -34,13 +35,28 @@ object Algorithm { final class StringAlgorithmDecorator(val sa: StringAlgorithm) { + val withMemoization: StringAlgorithm = new StringAlgorithm { + private val base: StringAlgorithm = sa + private var memo: Map[String, Option[String]] = Map() + + override def compute(a: Array[Char]): Option[Array[Char]] = + compute(a.toString).map(_.toCharArray) + + override def compute(a: String): Option[String] = + if (memo.contains(a)) memo(a) + else { + memo = memo + (a -> base.compute(a)) + memo(a) + } + } + val withTransform: (StringTransform => StringAlgorithm) = (st) => new StringAlgorithm { private val base: StringAlgorithm = sa private val transform: StringTransform = st override def compute(a: Array[Char]): Option[Array[Char]] = base.compute(transform(a)) - override def compute(a: String): Option[String] = base.compute(transform(a.toCharArray)).map(_.mkString) + override def compute(a: String): Option[String] = compute(a.toCharArray).map(_.mkString) } } } diff --git a/core/src/main/scala/com/rockymadden/stringmetric/Metric.scala b/core/src/main/scala/com/rockymadden/stringmetric/Metric.scala index 03a0425..f217f52 100755 --- a/core/src/main/scala/com/rockymadden/stringmetric/Metric.scala +++ b/core/src/main/scala/com/rockymadden/stringmetric/Metric.scala @@ -63,15 +63,30 @@ object Metric { } final class StringMetricDecorator[A](val sm: StringMetric[A]) { + val withMemoization: StringMetric[A] = new StringMetric[A] { + private val base: StringMetric[A] = sm + private var memo: Map[(String, String), Option[A]] = Map() + + override def compare(a: Array[Char], b: Array[Char]): Option[A] = compare(a.toString, b.toString) + + override def compare(a: String, b: String): Option[A] = { + val t = (a, b) + + if (memo.contains(t)) memo(t) + else { + memo = memo + (t -> base.compare(a, b)) + memo(t) + } + } + } + val withTransform: (StringTransform => StringMetric[A]) = (st) => new StringMetric[A] { private val base: StringMetric[A] = sm private val transform: StringTransform = st - override def compare(a: Array[Char], b: Array[Char]): Option[A] = - base.compare(transform(a), transform(b)) + override def compare(a: Array[Char], b: Array[Char]): Option[A] = base.compare(transform(a), transform(b)) - override def compare(a: String, b: String): Option[A] = - base.compare(transform(a.toCharArray), transform(b.toCharArray)) + override def compare(a: String, b: String): Option[A] = compare(a.toCharArray, b.toCharArray) } } } diff --git a/core/src/test/scala/com/rockymadden/stringmetric/AlgorithmSpec.scala b/core/src/test/scala/com/rockymadden/stringmetric/AlgorithmSpec.scala index d727145..b95046d 100644 --- a/core/src/test/scala/com/rockymadden/stringmetric/AlgorithmSpec.scala +++ b/core/src/test/scala/com/rockymadden/stringmetric/AlgorithmSpec.scala @@ -7,7 +7,7 @@ import org.scalatest.junit.JUnitRunner final class AlgorithmSpec extends ScalaTest { import phonetic._ import Algorithm._ - import Transform.StringTransform + import Transform._ "StringAlgorithm" should provide { "compute method and companion object pass through" in { @@ -25,6 +25,15 @@ final class AlgorithmSpec extends ScalaTest { } "StringAlgorithmDecorator" should provide { + "withMemoization()" in { + val memo = MetaphoneAlgorithm withMemoization + + (0 until 1000000) foreach { i => + memo.compute("abc123") + memo.compute("abc456") + } + } + "withTransform()" in { (MetaphoneAlgorithm withTransform StringTransform.filterAlpha).compute("abc123").get should equal (MetaphoneAlgorithm.compute("abc").get) diff --git a/core/src/test/scala/com/rockymadden/stringmetric/MetricSpec.scala b/core/src/test/scala/com/rockymadden/stringmetric/MetricSpec.scala index 3b9021d..538976d 100644 --- a/core/src/test/scala/com/rockymadden/stringmetric/MetricSpec.scala +++ b/core/src/test/scala/com/rockymadden/stringmetric/MetricSpec.scala @@ -44,6 +44,15 @@ final class MetricSpec extends ScalaTest { } "StringMetricDecorator" should provide { + "withMemoization()" in { + val memo = MetaphoneMetric withMemoization + + (0 until 1000000) foreach { i => + memo.compare("abc123", "abc456") + memo.compare("abc456", "abc123") + } + } + "withTransform()" in { (MetaphoneMetric withTransform StringTransform.filterAlpha).compare("abc123", "abc456").get should equal (true) @@ -244,11 +244,11 @@ SoundexAlgorithm.compute("lukasiewicz") // l222 --- ## Decorating -It is possible to decorate algorithms and metrics with additional functionality, this is provided by rich wrapping via implicits. Decorations include: +It is possible to decorate algorithms and metrics with additional functionality, this is provided by rich wrapping via implicits. Decorations include (you can mix and match): * __withTransform:__ Transform arguments prior to computation/comparison. A handful of pre-built transforms are located in the [transform module](https://github.com/rockymadden/stringmetric/blob/master/core/src/main/scala/com/rockymadden/stringmetric/Transform.scala). -* __withMemoization:__ Queued. +* __[withMemoization](https://en.wikipedia.org/wiki/Memoization):__ All computations/comparisons are cached. Any further calls made with identical arguments will be looked up, rather than computed/compared. --- @@ -260,6 +260,13 @@ MetaphoneMetric.compare("abc123", "abc456") --- +Memoized: +```scala +(MetaphoneAlgorithm withMemoization).compute("abc123") +``` + +--- + Single filter, so that we only examine alphabetical characters: ```scala (MetaphoneAlgorithm withTransform StringTransform.filterAlpha).compute("abc123") |