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

list列表

列表属于python的三种基本集合类型之一, 其他两种是元组(tuple)和字典(dict). tuple和list区别主要在于是不是mutable的.

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

所以, python内建的所谓"列表"其实是功能很强大的数组, 类比一下可以说它对应于java里面的ArrayList<Object> .

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

Classic space-time tradeoff.

1. Hash Functions ...

1. 1d Range Search

Goal: intersections of geometric objects.

Solution: BST

1d range search

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 ...

(maybe best algorithm for sorting.)

1. Quicksort

Idea:

1. shuffle the array
2. Partition the array into two subarrays to left and right of pivot (*now pivot is *in its final position)

no larger entry to the left of pivot
no smaller entry to the right of pivot

1. sort each subarray recursively ...

Two classical sorting algorithms: mergesort, quicksort.

1. Mergesort

Divide and conquer: top 10 algorithms of the 20th century, invented by von Neumann.

Idea:

• divide array into 2 halves
• recursively sort each half
• merge two sorted halves

Implementation

Merge:
Goal: a[lo] to a[mid] and a[mid+1] to a ...

1. Introduction

rearanging array of size N into ascending order
test client code: Insertion.sort(a);

sort any datatype

callback

callback = reference to executable code
i.e. passing functions as argument to sort() method
sort() function calls object's compareTo() method

→ implement the Comparable interface:

    public class XX implements Comparable ...