open-courses
  • 公开课笔记
  • CMU 15-445/645 Database Systems
    • Relational Data Model
    • Advanced SQL
    • Database Storage
    • Buffer Pools
    • Hash Tables
    • Tree Indexes
    • Index Concurrency Control
    • Query Processing
    • Sorting&Aggregations
    • Join Algorithms
    • Query Optimization
    • Parallel Execution
    • Embedded Database Logic
    • Concurrency Control Theory
    • Two Phase Locking
    • Timestamp Ordering Concurrency Control
    • Multi-Version Concurrency Control
    • Logging Schemes
    • Database Recovery
    • Introduction to Distributed Databases
    • Distributed OLTP Databases
    • Distributed OLAP Databases
  • UCB - CS162
    • OS intro
    • Introduction to the Process
    • Processes, Fork, I/O, Files
    • I/O Continued, Sockets, Networking
    • Concurrency: Processes & Threads
    • Cooperating Threads, Synchronization
    • Semaphores, Condition Variables, Readers/Writers
    • Scheduling
    • Resource Contention & Deadlock
    • Address Translation, Caching
    • File System (18,19,20)
    • Distributed Systems, Networking, TCP/IP, RPC (21,22)
    • Distributed Storage, Key-Value Stores, Security (23)
    • Security & Cloud Computing (24)
    • Topic: Ensuring Data Reaches Disk
  • MIT - 6.006
    • Sequence and Set Interface
    • Data Structure for Dynamic Sequence Interface
    • Computation Complexity
    • Algorithms and Computation
    • Structure Of Computation
    • Graph & Search
    • Tree & Search
    • Weighted Shortest Paths
    • String Matching, Karp-Rabin
    • Priority Queue Interface & Implementation
    • Dictionary Problem & Implementation
    • Sorting
    • Dynamic Programming
    • Backtracking
    • Self-Balancing Tree
  • MIT - 6.824
    • 2PC & 3PC
    • Introduction and MapReduce
    • RPC and Threads
    • Primary/Backup Replication
    • Lab: Primary/Backup Key/Value Service
    • Google File System (GFS)
    • Raft
    • Lab: Raft - Leader Election
    • Lab: Raft - Log Replication
  • Stanford-CS107
    • 原始数据类型及相互转化
    • 指鹿为马
    • 泛型函数
    • 泛型栈
    • 运行时内存结构
    • 从 C 到汇编
    • 函数的活动记录
    • C 与 C++ 代码生成
    • 编译的预处理过程
    • 编译的链接过程
    • 函数的活动记录续、并发
    • 从顺序到并发和并行
    • 信号量与多线程 1
    • 信号量与多线程 2
    • 复杂多线程问题
    • 函数式编程 - Scheme 1
    • 函数式编程 - Scheme 2
    • 函数式编程 - Scheme 3
    • 函数式编程 - Scheme 4
    • 函数式编程 - Scheme 5
    • Python 基础
  • MIT - 6.001 - SICP
    • 什么是程序
    • 程序抽象
    • 替代模型
    • 时间/空间复杂度
    • 数据抽象
    • 高阶函数
    • Symbol
    • 数据驱动编程与防御式编程
    • 数据抽象中的效率与可读性
    • 数据修改
    • 环境模型
    • 面向对象-消息传递
    • 面向对象 - Scheme 实现
    • 构建 Scheme 解释器
    • Eval-Apply Loop
    • Normal Order (Lazy) Evaluation
    • 通用机
    • 寄存器机器
    • 子程序、栈与递归
    • 在寄存器机器中执行
    • 内存管理
  • MIT - 6.046
    • Randomized Algorithms
    • Skip Lists
  • System Design
    • Twitter
    • Cache Consistency & Coherence
  • DDIA 笔记
    • Replication
    • Transactions
    • The Trouble with Distributed Systems
    • Consistency & Consensus
  • Papers We Love
    • Consistent Hashing and Random Trees (1997)
    • Dynamic Hash Tables (1988)
    • LFU Implementation With O(1) Complexity (2010)
    • Time, Clocks, and the Ordering of Events in a Distributed System (1978)
    • Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)
    • Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015)
  • Release It 笔记
    • Anti-patterns & Patterns in Microservice Architecture
  • Database Design
    • Log Structured Merge (LSM) Tree & Usages in KV Stores
    • Prometheus
Powered by GitBook
On this page
  1. MIT - 6.001 - SICP

数据抽象中的效率与可读性

十一课

Previous数据驱动编程与防御式编程Next数据修改

Last updated 6 years ago

概要

本课将深入讨论数据抽象,体会设计数据结构时的权衡 (trade-off) — 高效率与可读性。

抽象数据类型 — 表 (table)

抽象数据类型表所规定的协议包含以下协议:

  1. make — 创建新的表

  2. put! key value — 往表中插入键值对,若有重复键则覆盖值

  3. get key — 从表里检索该键对应的值

这便是一个表的抽象数据类型,它对具体的实现没有任何规定,只规定了接口行为。

实现1:Association List — List of Lists

如果要存储下面这张简单的表:

x

15

y

20

在 scheme 中我们可以用 list of lists 来表示:

> (list (list 'x 15) (list 'y 20))
((x 15) (y 20))

其内部结构如下图所示:

为了实现上文规定的协议,我们需要一些辅助操作 (operations)

; 以健查值
(define (find-assoc key alist)
  (cond
   ((null? alist) #f)
   ((equal? key (caar alist)) (cadar alist))
   (else (find-assoc key (cdr alist)))))
; 插入键值对
(define (add-assoc key val alist)
  (cons (list key val) alist))

定义了以上两个操作我们就实现了表的基本功能,接着我们需要:

  1. constructor — 表的构造器,即协议中的 make

  2. information hiding — 隐藏背后依赖的 Scheme 的抽象数据类型 list

; Data Directed Programming
; table tag
(define table1-tag 'table1)
; constructor
(define (make-table1) (cons table1-tag nil))
; get
(define (table1-get tbl key)
  (find-assoc key (cdr tbl)))
; put!
(define (table1-put! tbl key val)
  (set-cdr! tbl (add-assoc key val (cdr tbl))))

问题1:如何判断 Table1 是表抽象数据类型的实现

你可能会想到的原因:

  • 它有一个 type tag

  • 它有一个 constructor

  • 它有 mutators 和 accessors

但它们都不是根本原因。根本原因在对用户的抽象隔离,用户并不了解接口背后的实现。而 type tag、constructor、mutators 以及 accessors 是做到抽象隔离的必要组件:

  • type tag: 利用类型标签可以防止非 ADT 中的函数误操作

  • constructor: 在构造时隐藏了背后实现

  • mutators、accessors: 在操作时隐藏了背后实现

小结:

  • Association List 结构可以用来表示表的抽象数据类型

  • 数据抽象技术 (constructors、accessors、mutators、type tag) 是支撑 information hiding 的基础

  • Information hiding 是模块化的必要条件

  • 模块化是软件工程的核心

  • Opaque type names denote information hiding (理解意思但是不好翻译,暂时保留原话)

实现2:Hash Tables

利用 Association List 实现的表有很高的插入键值对效率 — O(1),但它的读取效率较差 — O(n),如果我们的使用过程有非常多的读取操作,则我们优化的方向就是换一种读取效率较高的实现。

Hash Table 的实现将基于 Scheme 的另一个抽象数据类型 — vector,它规定的接口协议如下:

  • make-vector

    • a vector with size locations; each initially contains value

    • number, A -> vector<A>

  • vector-ref

    • whatever is stored at that index of v (error if index >= size of v)

    • vector<A>, number -> A

  • vector-set!

    • stores val at that index of v (error if index >= size of v)

    • vector<A>, number, A -> undef

于是可以开始实现 Hash Table

; type tag
(define t2-tag 'table2)
; constructor
(define (make-table2 size hashfunc)
  (let ((buckets (make-vector size nil)))
    (list t2-tag size hashfunc buckets)))
; accessors
(define (size-of tbl) (cadr tbl))
(define (hashfunc-of tbl) (caddr tbl))
(define (buckets-of tbl) (cadddr tbl))
;; get
(define (table2-get tbl key)
  (let ((index
         ((hashfunc-of tbl) key (size-of tbl))))
    (find-assoc key
          (vector-ref (buckets-of tbl) index))))
; mutators
;; put!
(define (table2-put! tbl key val)
  (let ((index
         ((hashfunc-of tbl) key (size-of tbl)))
        (buckets (buckets-of tbl)))
    (vector-set! buckets index
                 (add-assoc key val
                            (vector-ref buckets index)))))

注意到,Association List 与 Hash Table 实现的 Table ADT 协议一模一样,可以无缝衔接,抽象对用户隔离。

问题:Table1 和 Table2 哪个更好?

答案:具体情况具体分析

对比一下二者的实现:

  • Table1:

    • make O(1)

    • put! O(1)

    • get O(n)

  • Table2:

    • make O(n)

    • put! O(1), 需要计算 hashfunc

    • get O(1 + k),需要计算 hashfunc (k 为 bucket 的大小)

在 get 操作极少且表规模较小的时候 Table1 更好。

在大部分时候 Table2 都更好,但前提是

  • 要准确预测所需 vector 的大小

  • 要选择合适的 hashfunc,使得 key 被均匀地分布

参考

Youtube: SICP-2004-Lecture-11
MIT6.006-SICP-2005-lecture-notes-11