Как работает эта частичная функция Scala? - PullRequest
Новая
       6

Как работает эта частичная функция Scala?

0 голосов
/ 29 апреля 2019 
// First using normal dictionary lookup
def findElement(e: String, dict: Map[String, Any]): Option[Any] = dict.get(e)
;

// Second using Partial function
def findElement(e: String, dict: Map[String, Any]): Option[Any] = dict.find { case (k, v) => k == e } map (_._2)


Они оба дают один и тот же ответ, но как работает вторая функция?

Что такое BigO для частичной функции, которая использует ключевое слово case? Перебирает ли он все элементы карты, чтобы найти правильный ключ?

Ответы [ 3 ]

4 голосов
/ 30 апреля 2019

dict.get(e) = O (1) или до O (N) зависит от того, как Map обрабатывает коллизии или как распределяются хэш-коды dict.find { case (k, v) => k == e } map (_._2) = O (N) из-за реализации .find.Если мы углубимся в реализацию метода find, то увидим: 

override /*TraversableLike*/ def find(p: A => Boolean): Option[A] =
    iterator.find(p)

, затем глубже: 

  def find(p: A => Boolean): Option[A] = {
    while (hasNext) {
      val a = next()
      if (p(a)) return Some(a)
    }
    None
  }

, и здесь мы можем видеть, как цикл повторяется по всем элементам в Iterator, пока не будет передана функция p: A => Boolean возвращает истину.Таким образом, у нас есть максимум N итераций здесь.

Я не был таким ленивым и написал тест, используя sbt-jmh : 

import java.util.concurrent.TimeUnit
import org.openjdk.jmh.annotations.{Benchmark, OutputTimeUnit, Scope, State}

@State(Scope.Benchmark)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
class FindElementBenchmark {

  val dict: Map[String, Any] =
    (0 to 100).foldLeft(Map.empty[String, Any])((m, i) => m + (s"key$i" ->s"value$i"))

  val e: String = "key99"

  // First using normal dictionary lookup
  @Benchmark
  def findElementDict: Option[Any] =
    dict.get(e)

  // Second using Partial function
  @Benchmark
  def findElementPF: Option[Any] =
    dict
      .find { case (k, v) => k == e }
      .map(_._2)
}

, запустил его: 

$ sbt
$ sbt:benchmarks> jmh:run -i 20 -wi 10 -f1 -t1

и получилРезультаты: 

[info] Running (fork) org.openjdk.jmh.Main -i 20 -wi 10 -f1 -t1
[info] # JMH version: 1.21
[info] # VM version: JDK 1.8.0_161, Java HotSpot(TM) 64-Bit Server VM, 25.161-b12
[info] # VM invoker: /Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/bin/java
[info] # VM options: <none>
[info] # Warmup: 10 iterations, 10 s each
[info] # Measurement: 20 iterations, 10 s each
[info] # Timeout: 10 min per iteration
[info] # Threads: 1 thread, will synchronize iterations
[info] # Benchmark mode: Throughput, ops/time
[info] # Benchmark: bmks.FindElementBenchmark.findElementDict
[info] # Run progress: 0.00% complete, ETA 00:10:00
[info] # Fork: 1 of 1
[info] # Warmup Iteration   1: 48223.037 ops/ms
[info] # Warmup Iteration   2: 48570.873 ops/ms
[info] # Warmup Iteration   3: 48730.899 ops/ms
[info] # Warmup Iteration   4: 45050.838 ops/ms
[info] # Warmup Iteration   5: 48191.539 ops/ms
[info] # Warmup Iteration   6: 48464.603 ops/ms
[info] # Warmup Iteration   7: 48690.140 ops/ms
[info] # Warmup Iteration   8: 46432.571 ops/ms
[info] # Warmup Iteration   9: 46772.835 ops/ms
[info] # Warmup Iteration  10: 47214.496 ops/ms
[info] Iteration   1: 49149.297 ops/ms
[info] Iteration   2: 48476.424 ops/ms
[info] Iteration   3: 48590.436 ops/ms
[info] Iteration   4: 48214.015 ops/ms
[info] Iteration   5: 48698.636 ops/ms
[info] Iteration   6: 48686.357 ops/ms
[info] Iteration   7: 48948.054 ops/ms
[info] Iteration   8: 48917.577 ops/ms
[info] Iteration   9: 48872.980 ops/ms
[info] Iteration  10: 48970.421 ops/ms
[info] Iteration  11: 46269.031 ops/ms
[info] Iteration  12: 44934.335 ops/ms
[info] Iteration  13: 46279.314 ops/ms
[info] Iteration  14: 47721.223 ops/ms
[info] Iteration  15: 46238.490 ops/ms
[info] Iteration  16: 47453.282 ops/ms
[info] Iteration  17: 47886.762 ops/ms
[info] Iteration  18: 48032.580 ops/ms
[info] Iteration  19: 48142.064 ops/ms
[info] Iteration  20: 48460.665 ops/ms
[info] Result "bmks.FindElementBenchmark.findElementDict":
[info]   47947.097 ±(99.9%) 1003.440 ops/ms [Average]
[info]   (min, avg, max) = (44934.335, 47947.097, 49149.297), stdev = 1155.563
[info]   CI (99.9%): [46943.657, 48950.537] (assumes normal distribution)
[info] # JMH version: 1.21
[info] # VM version: JDK 1.8.0_161, Java HotSpot(TM) 64-Bit Server VM, 25.161-b12
[info] # VM invoker: /Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/bin/java
[info] # VM options: <none>
[info] # Warmup: 10 iterations, 10 s each
[info] # Measurement: 20 iterations, 10 s each
[info] # Timeout: 10 min per iteration
[info] # Threads: 1 thread, will synchronize iterations
[info] # Benchmark mode: Throughput, ops/time
[info] # Benchmark: bmks.FindElementBenchmark.findElementPF
[info] # Run progress: 50.00% complete, ETA 00:05:00
[info] # Fork: 1 of 1
[info] # Warmup Iteration   1: 7261.136 ops/ms
[info] # Warmup Iteration   2: 7548.525 ops/ms
[info] # Warmup Iteration   3: 7517.692 ops/ms
[info] # Warmup Iteration   4: 7126.543 ops/ms
[info] # Warmup Iteration   5: 7732.285 ops/ms
[info] # Warmup Iteration   6: 7525.456 ops/ms
[info] # Warmup Iteration   7: 7739.055 ops/ms
[info] # Warmup Iteration   8: 7555.671 ops/ms
[info] # Warmup Iteration   9: 7624.464 ops/ms
[info] # Warmup Iteration  10: 7527.114 ops/ms
[info] Iteration   1: 7631.426 ops/ms
[info] Iteration   2: 7607.643 ops/ms
[info] Iteration   3: 7636.029 ops/ms
[info] Iteration   4: 7413.881 ops/ms
[info] Iteration   5: 7726.417 ops/ms
[info] Iteration   6: 7410.291 ops/ms
[info] Iteration   7: 7452.339 ops/ms
[info] Iteration   8: 7825.050 ops/ms
[info] Iteration   9: 7801.677 ops/ms
[info] Iteration  10: 7783.978 ops/ms
[info] Iteration  11: 7788.909 ops/ms
[info] Iteration  12: 7778.982 ops/ms
[info] Iteration  13: 7784.158 ops/ms
[info] Iteration  14: 7771.173 ops/ms
[info] Iteration  15: 7750.280 ops/ms
[info] Iteration  16: 7813.570 ops/ms
[info] Iteration  17: 7845.550 ops/ms
[info] Iteration  18: 7841.003 ops/ms
[info] Iteration  19: 7808.576 ops/ms
[info] Iteration  20: 7847.100 ops/ms
[info] Result "bmks.FindElementBenchmark.findElementPF":
[info]   7715.902 ±(99.9%) 124.303 ops/ms [Average]
[info]   (min, avg, max) = (7410.291, 7715.902, 7847.100), stdev = 143.148
[info]   CI (99.9%): [7591.598, 7840.205] (assumes normal distribution)
[info] # Run complete. Total time: 00:10:01
[info] REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on
[info] why the numbers are the way they are. Use profilers (see -prof, -lprof), design factorial
[info] experiments, perform baseline and negative tests that provide experimental control, make sure
[info] the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from the domain experts.
[info] Do not assume the numbers tell you what you want them to tell.
[info] Benchmark                              Mode  Cnt      Score      Error   Units
[info] FindElementBenchmark.findElementDict  thrpt   20  47947.097 ± 1003.440  ops/ms
[info] FindElementBenchmark.findElementPF    thrpt   20   7715.902 ±  124.303  ops/ms
[success] Total time: 603 s, completed Apr 30, 2019 7:33:10 PM

Как мы видим, findElementPF имеет в 7 раз худший результат.Я только что доказал теоретически алгоритм оценки сложности алгоритма.

4 голосов
/ 29 апреля 2019

Несколько вещей, которые вам нужно знать:

  • Map[A, B] также является PartialFunction[A, B]
  • частичной функцией с lift методом с превращением ее в A => Option[B]- get становится в основном apply.lift _
  • Map также может рассматриваться как последовательность пар (Seq[(A, B)]) - вы можете увидеть это, когда вы map, flatMap, collect,find и т. Д.
  • find - это функция, которая возвращает первый элемент коллекции (в случае Map это пара) - если в коллекции такого элемента нет, то обрабатывает Noneчто
  • { case (k,v) => } использует сопоставление с образцом для извлечения значений из кортежа и помещения его в значения k и v,
  • _._2 - это метод кортежа (возвращает 2-е значение).

Имея это в виду: 

dict.get(e)


... вполне очевидно - возвращаемое значение для ключа e, если оно существует, обернуть его в Some в противном случае,return None (apply выдаст пропущенное значение). 

dict.find { case (k, v) => k == e } map (_._2)


попытается найти первый элемент, где k == e, вернет Option[(String, Any)] и затем использует map для преобразования значениявOption (если существует), повернув целый кортеж только до его второго значения.

3 голосов
/ 29 апреля 2019

РЕДАКТИРОВАТЬ: OP отредактировал свой вопрос, чтобы удалить ссылки на «Частично примененные функции», чтобы разделы больше не были релевантными. Я оставляю их здесь, хотя, так как это может быть полезно для кого-то, кто их смешивает.

Это не частично примененная функция, а скорее PartialFunction (https://www.scala -lang.org / api / current / scala / PartialFunction.html ).

Частично примененная функция - это функция с несколькими параметрами, для которой вы указали только часть, и вы можете передать эту частично примененную функцию кому-то другому для предоставления остальных.

Частичная функция определяется в документах как:

Частичная функция типа PartialFunction [A, B] - это унарная функция, в которой домен необязательно включает в себя все значения типа A. Функция isDefinedAt позволяет динамически проверять, находится ли значение в домене функции.

Предоставленное вами дело должно охватывать все дела, поскольку ваш домен - это все Tuple2 s, поскольку вы не защищаете от определенных значений, но вы не обязаны покрывать все дела в PartialFunction.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...