浏览器中的 Javascript Memoization 没有看到加速

Question

我正在尝试在 javascript 中内存一个函数，以便在客户端的浏览器中运行。用 R(我最习惯使用的语言)编写此函数。在 R 中，我看到使用记忆化的显着好处(P_n(7/10, 20, 15, 6, 1) 的运行时间从 4 分钟缩短到 0.02 秒)。当我用 javascript 重写函数时，我几乎看不到任何好处。我的 javascript 代码有什么问题(或者我完全以错误的方式解决这个问题)？

下面分别是R和javascript中的memoized函数。与朴素的递归相比，R 函数(两者中的第一个)运行得非常快，而 javascript 基本上看不出有什么区别。然而，一些记忆化正在发生，因为如果我运行完全相同的函数调用两次，即 P_memo(7/10, 20, 15, 6, 1) 然后是 P_memo(7/10, 20, 15, 6, 1 ) ，第二次调用花费 0 时间。由于在递归中重复使用中间调用，第一次调用应该会快得多。

P_n <- (function() {

  # Memoization handled through the use of cache

  cache <- NULL

  cache_reset <- function() {
    cache <<- new.env(TRUE, emptyenv())
  }

  cache_set <- function(key, value) {
    assign(key, value, envir = cache)
  }

  cache_get <- function(key) {
    get(key, envir = cache, inherits = FALSE)
  }

  cache_has_key <- function(key) {
    exists(key, envir = cache, inherits = FALSE)
  }

  # Initialize the cache
  cache_reset()


  # This is the function that gets returned by the anonymous function and
  # becomes P_n
  function(rho, n, i, k, s) {
    nc <- paste(rho, n, i, k, s)

    # Handle "vectors" by element
    if(length(n) > 1){
      return(lapply(n, function(n) sapply(n, P_n, rho = rho, i = 1:(n+k), k = k, s = s)))  
    }
    if (length(i) > 1) {
      return(sapply(i, P_n, rho = rho, n = n, k = k, s = s))
    }

    # Cached cases
    if (cache_has_key(nc)) 
      return(cache_get(nc))


    # Everything else

    #proposition 1
    if(i == (n+k)){
      #print('Proposition 1')
      if(k >= s){
        return((rho / (rho + 1))^n)
      }else if( (k+n) <= s){
        product_iter = 1
        for(j in 1:n){
          product_iter = product_iter * ( rho + (k + j - 1)/s )
        }
        out = rho^n / product_iter
        cache_set(nc, out)
        return(out)
      }else if( k < s & s < (k + n)){
        product_iter2 = 1
        for(j in 1:(s-k)){
          product_iter2 = product_iter2 * ( rho + (k + j - 1)/s )
        }
        product_denom = ((rho + 1)^(n-s+k)) * product_iter2
        out = rho^n / product_denom
        cache_set(nc, out)
        return(out)
      }
    }
    #proposition 2
    else if(k == 0 & n == i){
      #print('Proposition 2')
      if(n <= s){
        product_iter11 = 1
        for(j in 1:n){
          product_iter11 = product_iter11 * (rho + (j - 1)/s)
        }
        return(rho^n / product_iter11)
      }else if(n > s){
        product_iter12 = 1
        for(j in 1:s){
          product_iter12 = product_iter12 * ( rho + (j - 1)/s )
        }
        product_denom12 = ((rho + 1)^(n-s)) * product_iter12
        out = rho^n / product_denom12
        cache_set(nc, out)
        return(out)
      }
    }
    #if i = 1
    else if(i == 1){
      upsum = 0
      for(j in 2:(n + k)){
        upsum = upsum + P_n(rho, n, j, k, s)
      }
      out = 1 - upsum
      cache_set(nc, out)
      return(out)
    }
    #proposition 3
    else if(n == 1 & 2 <= i & i <= k){
      #print('Proposition 3')
      if(k <= s){
        begin = rho / (rho + (i - 1)/s)

        product_iter13 = 1
        for(j in 1:(k-i+1)){
          product_iter13 = product_iter13 * (1 - rho / (rho + (k - j + 1)/s) )
        }
        out = begin * product_iter13
        cache_set(nc, out)
        return(out)
      }else if(k > s & i > s){
        out = rho / (rho+1)^(k-i+2)
        cache_set(nc, out)
        return(out)
      }else if(i <= s & s <= k){

        begin2 = rho / (( rho + 1 )^(k - s + 1) * ( rho + (i - 1)/s))

        product_iter14 = 1
        for(j in 1:(s-i)){
          product_iter14 = product_iter14 * (1 - rho / (rho + (s - j)/s) )
        }
        out = begin2 * product_iter14
        cache_set(nc, out)
        return(out)
      }

    }
    #proposition 4
    else if( n >= 2 & 2 <= i & i <= (k + n - 1)){
      #print('Proposition 4')
      if(i>s){
        begin11 = rho/(rho+1)

        product_iter21 = 0
        for(j in (i-1):(k+n-1)){
          product_iter21 = product_iter21 + (1 / (rho+1))^(j-i+1) * P_n(rho, n-1, j, k, s)
        }
        out = begin11 * product_iter21
        cache_set(nc, out)
        return(out)
      }else if(i <= s){

        begin12 = rho / (rho + (i-1)/s)
        summer1 = 0
        for(j in (i-1):(s-1)){

          product_iter22 = 1
          for(h in 1:(j-i+1)){
            product_iter22 = product_iter22 * (1 - rho / (rho + (j - h + 1) / s))
          }
          summer1 = summer1 + product_iter22 * P_n(rho, n-1, j, k, s)
        }

        product_iter23 = 1
        for(h in 1:(s-i)){
          product_iter23 = product_iter23 * (1 - rho / (rho + (s-h) / s))
        }

        summer2 = 0
        for(j in s:(k+n-1)){
          summer2 = summer2 + ((1 / (rho + 1))^(j-s+1) * P_n(rho, n-1, j, k, s)) 
        }

        bottom = product_iter23 * summer2
        inner = summer1 + bottom
        out = begin12 * inner
        cache_set(nc, out)
        return(out)
      }
    }
    #check if missed all propositions
    else{
      stop("No proposition detected")
    }

  }

})()

var P_memo = (function() {
    var memo = {};
    var slice = Array.prototype.slice;

    function f(rho, n, i, k, s){
        var args = slice.call(arguments);
        var value;
        if (args in memo) {
            return(memo[args]);
        }else{
            // NOTES ON THE UNITS OF INPUTS
            //rho: ratio of lambda / tau
            // n: arrival of nth customer
            // i: are i customers in queue
            // k : number of customers at t = 0
            // s: machines in use

            //proposition 1
            if(i == (n+k)){
                //print('Proposition 1')
                if(k >= s){
                    return(Math.pow(rho / (rho + 1), n));
                }else if( (k+n) <= s){
                    var product_iter = 1;
                    for(var j=1; j<= n; j++){
                        product_iter = product_iter * ( rho + (k + j - 1)/s );
                    }
                    return(Math.pow(rho, n) / product_iter);
                }else if( k < s && s < (k + n)){
                    var product_iter2 = 1;
                    for(var j=1; j<= s-k; j++){
                        product_iter2 = product_iter2 * ( rho + (k + j - 1)/s );
                    }
                    product_denom = Math.pow((rho + 1), (n-s+k)) * product_iter2;
                    return(Math.pow(rho, n) / product_denom);
                }
            }
            //proposition 2
            else if(k == 0 && n == i){
                if(n <= s){
                    var product_iter11 = 1;
                    for(var j=1; j<= n; j++){
                        product_iter11 = product_iter11 * (rho + (j - 1)/s);
                    }
                    return(Math.pow(rho, n) / product_iter11);
                }else if(n > s){
                    var product_iter12 = 1;
                    for(var j=1; j<= s; j++){
                        product_iter12 = product_iter12 * ( rho + (j - 1)/s );
                    }
                    product_denom12 = Math.pow((rho + 1), (n-s)) * product_iter12;
                    return(Math.pow(rho, n) / product_denom12);
                }
            }
            //if i = 1
            else if(i == 1){
                var upsum = 0;
                for(var j=2; j<= (n+k); j++){
                    upsum = upsum + f(rho, n, j, k, s);
                }
                return(1 - upsum);
            }
            //proposition 3
            else if(n == 1 && 2 <= i && i <= k){
                if(k <= s){
                    begin = rho / (rho + (i - 1)/s);

                    var product_iter13 = 1;
                    for(var j=1; j<= (k-i+1); j++){
                        product_iter13 = product_iter13 * (1 - rho / (rho + (k - j + 1)/s) );
                    }
                    return(begin * product_iter13);
                }else if(k > s && i > s){
                    return(rho / Math.pow((rho+1), (k-i+2)));
                }else if(i <= s && s <= k){

                    begin2 = rho / (Math.pow( (rho + 1), (k - s + 1)) * ( rho + (i - 1)/s));

                    var product_iter14 = 1;
                    for(var j=1; j<= (s-i); j++){
                        product_iter14 = product_iter14 * (1 - rho / (rho + (s - j)/s) );
                    }
                    return(begin2 * product_iter14);
                }

            }
            //proposition 4
            else if( n >= 2 && 2 <= i && i <= (k + n - 1)){
                if(i>s){
                    begin11 = rho/(rho+1);

                    var product_iter21 = 0;
                    for(var j=(i-1); j<= (k+n-1); j++){
                        product_iter21 = product_iter21 + Math.pow((1 / (rho+1)),(j-i+1)) * f(rho, n-1, j, k, s);
                    }
                    return(begin11 * product_iter21);
                }else if(i <= s){

                    begin12 = rho / (rho + (i-1)/s);
                    var summer1 = 0;
                    for(var j=(i-1); j<= (s-1); j++){

                        var product_iter22 = 1;
                        for(var h=1; h<=(j-1+1); h++){
                            product_iter22 = product_iter22 * (1 - rho / (rho + (j - h + 1) / s));
                        }
                        summer1 = summer1 + product_iter22 * f(rho, n-1, j, k, s);
                    }

                    var product_iter23 = 1;
                    for(var h=1; h<=(s-i); h++){
                        product_iter23 = product_iter23 * (1 - rho / (rho + (s-h) / s));
                    }

                    var summer2 = 0;
                    for(var j=s; j<= (k+n-1); j++){
                        summer2 = summer2 + (Math.pow((1 / (rho + 1)), (j-s+1)) * f(rho, n-1, j, k, s)) ;
                    }

                    bottom = product_iter23 * summer2;
                    inner = summer1 + bottom;
                    return(begin12 * inner);
                }
            }
        }

    }
    //Closure of f(), self-executing anonymous function
    return f;
})();

Answer 1

你的内存有两个缺陷:

(1) 您永远不会将结果添加到 memo。

(2) args in memo 将args 转换为字符串。这适用于一组数字，但可能无法用于其他输入。

我会像这样写一个通用版本的memo:

  const memo = fn => {
    const cache = {};
    return (...args) => {
      const key = JSON.stringify(args);
      if(key in memo) return memo[key];
      return memo[key] = fn(...args);
    };
  };

  const memoizedF = memo(f);