Fancy DSA Fancy DSA
数据结构
算法
LeetCode
  • 关于
  • 导航 (opens new window)
  • 分类
  • 标签
  • 归档
设计模式 (opens new window)
博客 (opens new window)
GitHub (opens new window)

Jonsam NG

想的更多,也要想的更远
数据结构
算法
LeetCode
  • 关于
  • 导航 (opens new window)
  • 分类
  • 标签
  • 归档
设计模式 (opens new window)
博客 (opens new window)
GitHub (opens new window)
  • 开始上手
  • Plan 计划
  • Roadmap 路线
  • 算法简介
  • Sort 排序

  • Search 搜索

  • Recursive 递归

  • Graph 图

  • Tree 树

  • Math 数学

  • Hash 哈希

  • String 字符串

  • BitManipulation 位操纵

  • Backtracking 回溯

  • DynamicProgramming 动态规划

  • Cache 缓存

    • LFUCache [最近最少使用缓存]
    • LRUCache [最近最久未使用缓存]
    • Memoize [缓存函数]
      • 介绍
      • 高阶函数
      • 实现
      • 扩展
      • 参考
  • Array 数组

  • Ciphers 密码学

  • Conversions 转换

  • ProjectEuler 欧拉计划

  • 其他

  • 算法
  • Cache 缓存
jonsam
2022-09-26
目录

Memoize [缓存函数]

# 介绍

记忆化(英语:memoization,缓存化)是一种提高计算机程序执行速度的优化技术。通过储存大计算量函数的返回值,当这个结果再次被需要时将其从缓存提取,而不用再次计算来节省计算时间。

记忆化是一种典型的在计算时间与电脑记忆体空间之中取得平衡的方案。

缓存函数可以通过高阶函数实现。

# 高阶函数

在数学和计算机科学中,高阶函数是至少满足下列一个条件的函数:

  • 接受一个或多个函数作为输入
  • 输出一个函数

在数学中它们也叫做算子(运算符)或泛函。微积分中的导数就是常见的例子,因为它映射一个函数到另一个函数。在函数式编程中,返回另一个函数的高阶函数被称为 Curry 化的函数。如排序函数,接受一个比较函数作为参数、filter 函数、fold 函数、apply(英语:apply)函数、函数复合(英语:Function composition (computer science))、积分、回调函数等。

对其他函数进行操作的函数,无论是把它们作为参数还是返回值,都被称为高阶函数(higher-order functions)。高阶函数允许我们对动作进行抽象,而不仅仅是数值。它们有几种形式。例如,我们可以有创建新函数的函数。

参考:

  • Higher-Order Functions :: Eloquent JavaScript (opens new window)
  • 高阶函数 - Wikiwand (opens new window)
  • Higher Order Functions and Currying - GeeksforGeeks (opens new window)

# 实现

# JavaScript

/**
 * @function memoize
 * @description ->
 * From [Wikipedia](https://en.wikipedia.org/wiki/Memoization),
 * memoization is an optimization technique used primarily to speed up computer programs,
 * by storing the results of expensive function calls and returning the cached result when the same inputs occur again
 * This function is a first class objects, which lets us use it as [Higher-Order Function](https://eloquentjavascript.net/05_higher_order.html) and return another function
 * @param {Function} func Original function
 * @param {Map} cache - it's receive any cache DS which have get, set & has method
 * @returns {Function} Memoized function
 */
const memoize = (func, cache = new Map()) => {
  const jsonReplacer = (_, value) => {
    // if the value is Set it's converted to Array cause JSON.stringify can't convert Set
    if (value instanceof Set) return [...value]
    // if the value is Map it's converted to Object cause JSON.stringify can't convert Map
    if (value instanceof Map) return Object.fromEntries(value)
    return value
  }

  return (...args) => {
    /**
     * Arguments converted to JSON string for use as a key of Map - it's easy to detect collections like -> Object and Array
     * If the args input is -> [new Set([1, 2, 3, 4]), {name: 'myName', age: 23}]
     * Then the agrsKey generate to -> '[[1,2,3,4],{"name":"myName","age":23}]' which is JSON mean string
     * Now it's ready to be a perfect key for Map
     */
    const argsKey = JSON.stringify(args, jsonReplacer)

    /** Checks if the argument is already present in the cache, then return the associated value / result */
    if (cache.has(argsKey)) return cache.get(argsKey)

    /** If the argument is not yet present in the cache, execute original function and save its value / result in cache, finally return it */
    const result = func(...args) // spread all args
    cache.set(argsKey, result)

    return result
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
  • JSON.stringify() 方法将一个 JavaScript 对象或值转换为 JSON 字符串,如果指定了一个 replacer 函数,则可以选择性地替换值,或者指定的 replacer 是数组,则可选择性地仅包含数组指定的属性。参见:JSON.stringify() | MDN (opens new window)
    • JSON.stringify(value[, replacer [, space]]) 。
    • replacer:如果该参数是一个函数,则在序列化过程中,被序列化的值的每个属性都会经过该函数的转换和处理;如果该参数是一个数组,则只有包含在这个数组中的属性名才会被序列化到最终的 JSON 字符串中;如果该参数为 null 或者未提供,则对象所有的属性都会被序列化。
    • space:指定缩进用的空白字符串,用于美化输出(pretty-print);如果参数是个数字,它代表有多少的空格;上限为 10。该值若小于 1,则意味着没有空格;如果该参数为字符串(当字符串长度超过 10 个字母,取其前 10 个字母),该字符串将被作为空格;如果该参数没有提供(或者为 null),将没有空格。

# 扩展

# 高阶组件

高阶组件(HOC,higher-order component)是 React 中重用组件逻辑的一种高级技术。HOC 本身不是 React API 的一部分。它们是一种从 React 的组合(compositional)性质中出现的模式。参见:Higher-Order Components – React (opens new window)。

# 参考

  • Memoization - Wikiwand (opens new window)
  • 记忆化 - Wikiwand (opens new window)
编辑 (opens new window)
上次更新: 2022/10/28, 10:40:37
LRUCache [最近最久未使用缓存]
LocalMaxPoint [局部最值]

← LRUCache [最近最久未使用缓存] LocalMaxPoint [局部最值]→

最近更新
01
0-20题解
10-31
02
本章导读
10-31
03
算法与转换:Part1
10-28
更多文章>
Theme by Vdoing | Copyright © 2022-2022 Fancy DSA | Made by Jonsam by ❤
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式