open-courses
Search…
公开课笔记
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
Randomized Algorithms
什么是 Randomized Algorithms
特征:
通过生成随机数来决定算法的走向
同样的输入在不同的执行中可能
运行不同的步骤 (步骤的数量、具体执行内容都可能不同)
产生不同的结果
分类:
Monte Carlo: 时间复杂度为 polynomial 以内,结果在大概率(with high probability)情况下正确
Las Vegas: 时间复杂度的期望为 polynomial 以内,结果总是正确的。
举例:
Matrix Product Checker
问题描述:
给定 n × n 矩阵 A、B、C,验证 A × B = C 是否成立
普通解法:直接计算 A × B = C
Simple Algorithm: O(n^3) multiplications
Strassen: multiply two 2 × 2 matrices in 7 multiplications: O(n^2.81)
Coppersmith-Winograd: O(n^2.376)
可以做到 O(n^2) 吗?
Frievald's Algorithm (Monte Carlo)
本算法能够做到:
如果 A × B = C,那么 Pr[output=YES] = 1
如果 A × B ≠ C,那么 Pr[output=YES] ≤ 1/2,即 False Positive Rate
这样,若 k 次运行结果都是 YES,那么 False Positive 的概率将达到 (1/2)^k,因此这是一个 Monte Carlo 算法。
过程:
任意选择一个二值向量 r,向量中的每个元素都以 1/2 的概率取值为 1,1/2 的概率取值为 0 。如果 A(Br) = Cr,输出 YES,否则输出 NO
分析:
只要证明所有的二值向量中,至多有一半能在 A × B ≠ C 的情况下,使得 output=YES,证明过程具体见
这里
。
Quicksort
Basic Quicksort
算法
始终选择 A[1] 或 A[n] 作为 pivot
def
quicksort
(
A
,
start
=
1
,
end
=
n
):
m
=
partition
(
A
)
# O(n)
quicksort
(
A
,
start
,
m
-
1
)
quicksort
(
A
,
m
+
1
,
end
)
def
partition
(
A
):
pivot
=
A
[
1
]
# ...
分析
如果输入是已经顺序或逆序,partition 会将所有元素放在 pivot 的同一边,此时:
图 1 - Basic Quicksort 的时间复杂度分析
空间复杂度在 in-place 情况下可做到 O(1)
Pivot Selection Using Median Finding
使用 Median Finding 算法可以保证在 θ(n) 时间复杂度下,获得数组的中位数,这样每次 partition 都能完美地将数组分成两部分,此时:
图 2 - Median Finding + Basic Quicksort 的时间复杂度分析
然而由于 Median Finding 较为复杂,虽然时间复杂度在 θ(n),但常数项较大,在实际运用中并不适用,通常要逊色于 mergesort。
Randomized Quicksort (Las Vegas)
使用随机选取任意元素作为 pivot 的策略,时间复杂度的期望为 O(nlgn),分析见 CLRS p.181-184。本课尝试分析该算法的一个变种:Paranoid Quicksort
"Paranoid" Quicksort (Las Vegas)
Good/Bad Pivots
图 3 - Good/Bad Pivots
可以看出选中 good pivot 的概率≥ 1/2,而 good pivot 中最差的两个分别在交界处,若选中它,问题将被分成大小分别为 (1/4)n 及 (3/4)n 的子问题。使用问题树分析:
图 4 - SubProblem Tree
本图有一定的误导性,实际上这是一个不平衡的树,树的深度从左往右逐渐递增。
由于选中 good pivot 的概率≥ 1/2,因此每次 pivot selection 执行的次数的期望:
E(#iterations) ≤ 2
所以推导公式为:
图 5 - Paranoid Quicksort Formula
从图中可以看出,树的高度最高位 log(4/3)(2cn),因此最终时间复杂度的期望 T(n) = θ(nlgn)。
参考
video
、
lecture note
MIT - 6.001 - SICP - Previous
内存管理
Next - MIT - 6.046
Skip Lists
Last modified
3yr ago
Copy link
Outline
什么是 Randomized Algorithms
特征:
分类:
举例:
Matrix Product Checker
Quicksort
参考