approximate retrieval(相似搜索)这个问题之前实习的时候就经常遇到: 如何快速在大量数据中如何找出相近的数据.

## step2. 编辑fstab

\$ sudo blkid
/dev/sda1: LABEL="FILES" UUID="ddefc0a7-30a1-42fb-a71a-0aebb55cb0b3" TYPE="ext2 ...

## assumptions in Bayes viewpoint

(btw, 对一个随机变量建模, 一般来说, 连续随机变量就用高斯 ...

python科学计算包的基础是numpy, 里面的array类型经常遇到. 一开始可能把这个array和python内建的列表(list)混淆, 这里简单总结一下列表(list), 多维数组(np.ndarray)和矩阵(np.matrix)的区别.

## list列表

list和java里的数组不同之处在于, python的list可以包含任意类型的对象, 一个list里可以包含int, string或者其他任何对象, 另外list是可变长度的(list有append, extendpop等方法).

## ndarray多维数组

ndarray是numpy的基石, 其实它更像一个java里面的标准数组: 所有元素有一个相同数据类型(dtype), 不过大小不是固定的.

ndarray对于大计算量的性能非常好, 所以list要做运算的时候一定要先转为array(np.array(_a_list_ ...

Can we do better than BST if we do not need ordered operations ?

(No compare methods, use equals method)

Idea: save items in an array.
Hash function: method for calclulating the array index of a key.

Issues:

• computing hash function
• equality tests
• collision resolution

# 1. 1d Range Search

Goal: intersections of geometric objects.

Solution: BST

operations required:

• insert
• search
• delete
• range search: all keys between k1 and k2
• range count: how many keys are between k1 and k2

→ find points on an interval

## implementation by BST

range count
using the rank ...

goal: lgN for insert/search/delete operations (not necessarily binary trees..)
3 algo: 2-3 tree, (left leaning) red-black tree, B-tree

# 1. 2-3 Search Trees

def. 2-3 tree

• allow 1 or 2 keys per node, & 2 or 3 children per node:
• 2-node: one key, 2 children (ordinary BST node)
• 3-node: 2 ...

(BST是锻炼递归代码的好题目)

# 1. Binary Search Trees

def. BST
A binary tree where each node has a key:
for every node, the key is larger than all nodes in left subtree, smaller than all nodes in right subtree.

Fields: key, val, left, right

## Implementation

An inner class of BST nodes:

private class ...

# 1. Symbol Table API

key-value pair abstraction

• insert a value with a key
• given a key, search for its value

## Association array abstraction

Associate a value to a key — generalized array: a[key]=val.

public class ST<Key, Value>{
void put(Key k, Value v);//remove key if value=null ...

# 1. API and elementary implementations

Collection: data struct for inserting and deleting items (ex. stack and queue).
Priority queue: a special kind of collection — remove largest/smallest element.

API:

public class Max<Kye implements Comparable<Key>>{
public MaxPQ();
public void insert(Key k);
public Key delMax();
public boolean isEmpty();
public ...