`

memoize in Ruby

阅读更多

Common Lisp 的经典书《On Lisp》的 5.3 节叫做 Memoizing 。书中讲到了将函数调用的返回值缓存起来的一种技术。这本来是一种非常常见的技术,但是《On Lisp》让我看到了动态语言的精练之处,这样的一种技术被抽象成一个通用的函数,将任意一个函数传入 memoize ,就会得到一个经过包装的函数,并且它已经具备了缓存的能力:

1
2
3
4
5
6
7
8
(defun memoize (fn)
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args)
  (multiple-value-bind (val win) (gethash args cache)
    (if win
        val
        (setf (gethash args cache)
        (apply fn args)))))))

下面是一个例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
CL-USER> (setf (symbol-function 'memoized)
         (memoize #'(lambda (x)
          (sleep 5)
          x)))
#<CLOSURE (LAMBDA (&REST ARGS)) {B7B80F5}>
CL-USER> (time (memoized 1))
Evaluation took:
  5.0 seconds of real time
  0.004 seconds of user run time
  0.0 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  0 bytes consed.
1
CL-USER> (time (memoized 1))
Evaluation took:
  0.0 seconds of real time
  0.0 seconds of user run time
  0.0 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  0 bytes consed.
1

《On Lisp》是一本非常经典的书,如果你不明白为什么 C 语言的宏与 Lisp 的宏一个是青蛙一个是王子的话,极力建议读一读,里面讲到了许多很实用的技巧,犹如秘境寻宝般刺激!

今天在 Nextlib 的公共图书馆里面淘到这篇 Ruby Monitor-Functions ,里面讲到了 Ruby 里的 wrap_method ,我立即就想到了原来看过的 memoize 函数。

实现本身是非常简单的,因为和在 Common Lisp 里面一样,Ruby 里的哈希表用起来也是非常方便的。在 Lisp 里的 memoize 函数采用函数编程的套路,没有副作用,而是返回一个包装过的函数,而 Ruby 的语法更接近命令式,我希望能以如下方式来使用这个 memoize 函数:

class Foo
  def foo
    # do some time-consuming work
  end
  memoize :foo
end

换言之,调用 memoize 之后, 作为副作用,foo 就有了缓存的能力,而不用关心 memoize 方法的返回值。我将这个方法实现为 Module 的类方法,这样就可以在定义类的时候使用它了。

1
2
3
4
5
6
7
8
9
10
11
12
class Module
  def memoize method_name
    memo ||= { }
    orig_method = instance_method(method_name)
    define_method method_name do |*args|
      memo.fetch(args) do |key|
        val = orig_method.bind(self).call(*args)
        memo[key] = val
      end
    end
  end
end

这是一个非常简易的实现,没有用到那篇文章中实现的 wrap_method 方法。 memoize 也没有考虑有 block 的情况,因为 memoize 本身就不是万金油,不能滥用啊。另外,由于 memo 变量是为每一个方法调用的时候创建的,所以同一个类的不同的对象用同样的参数来调用的话,会取到同样的 cache ,想要区分不同的对象也简单,在存入 memo 的时候哈希表的键值(就是那个 args 数组)前面把 self 加进去就可以了,像这样

5
6
7
8
9
10
    define_method method_name do |*args|
      memo.fetch(Array.new(args).unshift(self)) do |key|
        val = orig_method.bind(self).call(*args)
        memo[key] = val
      end
    end

下面来测试一下效果:

1
2
3
4
5
6
7
8
9
10
11
require 'benchmark'
 
array = (1..100000).map { rand 100 }
computer = Computer.new
 
Benchmark.bm(20) do |x|
  x.report("normal factor:") { array.each { |i| computer.factor(i) } }
  Computer.instance_eval { memoize :factor }
  x.report("memoize installed:") { array.each { |i| computer.factor(i) } }
  x.report("all cached:") { array.each { |i| computer.factor(i) } }
end

在我的机器 (Debian GNU/Linux 2.6.22-1-686) 上跑出来的结果是:

                          user     system      total        real
normal factor:       17.060000   1.350000  18.410000 ( 18.884428)
memoize installed:    0.750000   0.120000   0.870000 (  0.895277)
all cached:           0.740000   0.120000   0.860000 (  0.904223)

可以看到 memoize 的效果非常明显,第一个和后面两个时间差距非常大。而第二个和第三个,一个是现跑现 cache ,另外一个是所有的都是从 cache 中取的,基本上就是查找哈希表的过程,不过它们之间差距并不大。

完整的代码可以从这里下载。

分享到:
评论

相关推荐

    Exercism-exercises-in-Ruby.-ruby.zip

    Exercism_exercises_in_Ruby._ruby.zip Exercism_exercises_in_Ruby._ruby.zip Exercism_exercises_in_Ruby._ruby.zip Exercism_exercises_in_Ruby._ruby.zip Exercism_exercises_in_Ruby._ruby.zip Exercism_...

    ruby面向对象设计 Practical Object-Oriented Design in Ruby

    本书《Ruby面向对象设计:Practical Object-Oriented Design in Ruby》是一本专注于Ruby编程语言中面向对象设计原则和技术的书籍。作者Sandi Metz在书中讲述了如何应用敏捷方法来设计高质量、易于维护和扩展的面向...

    Data Structures and Algorithms in Ruby mobi

    Data Structures and Algorithms in Ruby 英文mobi 本资源转载自网络,如有侵权,请联系上传者或csdn删除 查看此书详细信息请在美国亚马逊官网搜索此书

    Data Structures and Algorithms in Ruby azw3

    Data Structures and Algorithms in Ruby 英文azw3 本资源转载自网络,如有侵权,请联系上传者或csdn删除 查看此书详细信息请在美国亚马逊官网搜索此书

    Design.Patterns.in.Ruby

    Addison.Wesley.Design.Patterns.in.Ruby.Dec.2007 高清PDF英文版

    Test Driven Development in Ruby:

    Test Driven Development in Ruby: A Practical Introduction to TDD Using Problem and Solution Domain Analysis by Bala Paranj English | 5 Apr. 2017 | ISBN: 1484226372 | 288 Pages | PDF | 5.32 MB Learn ...

    Ruby In a Nutshell

    《Ruby in a Nutshell》是一本面向初学者和有经验的程序员的快速参考指南,它深入浅出地介绍了Ruby编程语言的核心概念和语法。Ruby是一种动态、面向对象的脚本语言,以其简洁、优雅的代码风格和强大的元编程能力而...

    Practical Object Oriented Design in Ruby 新版 实战ruby面向对象设计

    《Practical Object-Oriented Design in Ruby 新版 实战ruby面向对象设计》是一本非常受欢迎的编程书籍,它不仅是学习Ruby语言的重要参考资料,也是深入理解面向对象编程(OOP)技术不可或缺的宝贵资料。这本书由于...

    Programming Interview Problems and Algorithms in Ruby

    Programming Interview Problems and Algorithms in Ruby by Zachary Paul English | April 17, 2016 | ASIN: B01EGILLLS | 177 Pages The book covers a large number of the most common interview problems, as ...

    Build.Awesome.Command-Line.Applications.in.Ruby

    Build.Awesome.Command-Line.Applications.in.Ruby

    Build Awesome Command-Line Applications in Ruby

    - **标题**:“Build Awesome Command-Line Applications in Ruby”(构建卓越的Ruby命令行应用) - **含义**:本书旨在教授读者如何利用Ruby编程语言开发高效且用户友好的命令行应用程序。 - **目标受众**:面向...

    Design Patterns in Ruby Dec 2007.rar

    《Design Patterns in Ruby Dec 2007》是关于Ruby编程语言中设计模式的一份珍贵资料,这份2007年发布的PDF文档深入探讨了如何在Ruby语言中应用经典的设计模式。设计模式是软件工程中经过实践证明的有效解决方案模板...

    Programming Ruby

    Like Smalltalk, it is dynamically typed (as opposed to Java or C++), but unlike Smalltalk, Ruby features the same conveniences found in modern scripting languages such as Perl and Python. The ...

    MetaProgramming in Ruby系列教程的中译版

    MetaProgramming in Ruby系列教程的中译版。 uby是动态的、魔幻而有趣的。而元编程(Metaprogramming)技术在Ruby中的应用也让我大开眼界,虽然以前也有浅显地介绍反射机制(Reflection),但我仍然觉得才疏学浅,不...

    Data Structures and Algorithms in Ruby epub

    Data Structures and Algorithms in Ruby 英文epub 本资源转载自网络,如有侵权,请联系上传者或csdn删除 查看此书详细信息请在美国亚马逊官网搜索此书

    Design pattern in ruby

    ruby 设计模式,针对ruby语言的特点对设计模式做了很好的阐述

Global site tag (gtag.js) - Google Analytics