Posts

我们已经看到了一些优雅的设计原则，例如分而治之，图探索和贪婪的选择，它们为各种重要的计算任务提供了确定的算法。这些工具的缺点是只能用于非常特定类型的问题。现在我们来谈谈算法工艺的两个大锤，即动态编程和线性编程，这两种适用性非常广泛的技术可以在更专门的方法失败时调用。可以预见的是，这种普遍性通常会带来效率上的损失。 很多经典的方法，如 divide-and-conquer, graph exploration, and greedy等, 为各种重要的计算任务提供了确定性的解法。但是这些算法只能用于特定类型的问题。 这里介绍两个算法大杀器: Dynamic programing 和 linear programming. 这两种适用性非常广的算法可以在黔驴技穷时考虑调用（如 the knapsack problem, sequence alignment, and optimal binary search trees）。当然，普遍性往往会带来效率上的损失。 动态规划 动态规划作为一种编程范例，可以从一个例子着手理解：求数列的 maximum-weighted independent sets (MIS, 最大非连续非相邻子集)和, 对于a = [1, 4, 5, 4], 其MIS为{a[1], a[3]} = 8. 如果使用贪心法, 每次都在可选范围内取最大值, 那么就会得到{a[2], a[0]} = 6. 如果使用分而治之法, 把数组分为两半a1 = [1, 4], a2 = [5, 4], 则分别得到MIS{a1[1]}, {a2[0]}, 合并后发现是相邻的, 与要求相悖. 要解决这个问题，关键的步骤是找到基于子问题最优解的最优解：想办法把缩小最优解备选方案的数量，在这个较小的空间中可以直接采取暴力搜索寻找最优解。 对于a = [1, 4, 5, 4], 假设其MIS为S, 假如从最右边的元素开始考虑, a[3] = 4只有属于S和不属于S两种情况 ...

一些常规的操作， 参考这个视频。 基本位操作 把某一位变为1： def set_bit(x, position): mask = 1 << position return x | mask bin(set_bit(0b110, 0b101)) 输出0b100110. 因为x = 0b110 = 6, 翻转第五位，就用position = 0b101 = 5， 得到mask = 0b00100000, 用|把第五位变为1. 清除某一位（1变0)： def clear_bit(x, position): mask = 1 << position return x & ~mask 通过XOR^和1来翻转某一位： def flip_bit(x, position): mask = 1 << position return x ^ mask 通过&1可以作为取位操作, 来判断某一位是否是1: def is_bit_set(x, position): shifted = x >> position return shifted & 1 0b1100110 >> 0b101 = 0b11, 0b11 & 0b01 = 1 根据参数state来控制修改某一位, 如果参数是1那么就是set, 如果是0那么就是clear: def modify_bit(x, position, state): mask = 1 << position return (x & ~mask) | (-state & mask) 如果state = 0b1, -state = 0b11111111 如果state = 0b0, -state = 0b0

在很多语言中，字符char类型是八位, 那么可能取值有256种(-128 ~ -1, 0 ~ 127). 但是用二进制表示为0000 0000 ~ 1111 1111, 无符号整数的全部位都表示数值，而有符号数的最高位是符号位（0表示正数，1表示负数），所以实际表达数值的只剩下n-1位。这样理论上char的取值应该是1111 1111 = -127到0111 1111 = 127. 而-128 = 1 1000 0000需要9位来表达, 所以char是如何仅仅通过八位表达-128? 首先, 因为计算机只能做加法, 所以减法操作要转化为加法, 尝试将符号位参与运算, 1-1就转化为1 + (-1), 用二进制表达为0000 0001 + 1000 0001 = -2, 很明显是错的. 如果用原码表示, 让符号位也参与计算, 显然对于减法来说, 结果是不正确的. 这也就是为何计算机内部不使用原码表示一个数. 为了避免这种错误, 引入反码(正数的反码是其本身, 负数的反码是符号位不变, 其余位取反), 用-1的原码1000 0001的反码1111 1110来表达-1, 这样1 + (-1) = [0000 0001]反 + [1111 1110]反 = [1111 1111]反, 转为原码1000 0000 = -0. 发现用反码计算减法, 结果的真值部分是正确的. ...

Memory Bit. 0 or 1. Byte. 8 bits. Megabyte (MB). 1 million or $2^{20}$ bytes. Gigabyte (GB). 1 billion or $2^{30}$ bytes. 64-bit machine. We assume a 64-bit machine with 8 byte pointers (References). ・Can address more memory. ・Pointers use more space (some JVMs “compress” ordinary object pointers to 4 bytes to avoid this cost). Typical memory usage for primitive types and arrays primitive types (bytes): boolean 1 byte 1 char 2 int 4 float 4 long 8 double 8 ...

假如有两种交税方式： 每天付 3 金币 每次付的金币呈指数级增长，但通知付款频率呈指数级下降 第1天：付 1 第2天：付 2 (累计 3) 第4天：付 4 (累积 7) 第8天：付 8 (累积 15) 哪种付的钱比较少？ 第二种比较划算，本质上等同于每天付 2，就是amortized constant。 A more rigorous examination of amortized analysis is done here, in three steps: Pick a cost model (like in regular runtime analysis) Compute the average cost of the i’th operation Show that this average (amortized) cost is bounded by a constant. 类似的应用在Array list 扩容中提到的 geometric resizing 方法(实际也是Python list 使用的方法)有体现, 所以使用一个因数来扩容数组, 可以让 ArrayList 的 add操作变为 amortized constant time. ...

Resource and Reference: CS61B Berkeley - Josh Hug Algorithms Princeton - ROBERT SEDGEWICK, KEVIN WAYNE 效率来源两个方面: 编程成本: 开发程序需要多长时间？代码是否容易阅读，修改和维护（大部分成本来自维护和可扩展性）？ 运行成本: 程序需要多长时间运行 (Time complexity)？ 需要多少内存 (Space complexity)？ Asymptotic Analysis Care about what happens for very large N (asymptotic behavior). We want to consider what types of algorithms would best handle scalability - Algorithms that scale well have better asymptotic runtime behavior. Simplification Summary Only consider the worst case. Pick a representative operation (aka: cost model) Ignore lower order terms Ignore multiplicative constants. Simplified Analysis Process ...

Stanford CS106B Programming Abstractions 和 CS106A 的学习笔记. 课程作业(cs106b spring 2017)实现代码见 https://github.com/ShootingSpace/cs106b-programming-abstraction Topics: A: Intro (by Java) B: Recursion, algorithms analysis (sort/search/hash), dynamic data structures (lists, trees, heaps), data abstraction (stacks, queues, maps), implementation strategies/tradeoffs Purposes become acquainted with the C++ programming language learn more advanced programming techniques explore classic data structures and algorithms and apply these tools to solving complex problems Reference Text Book: Data Structures & Algorithm Analysis in C++, 4th ed, by Mark A. Weiss Text Book: Programming Abstractions in C++ 1st Edition by Eric Roberts Text Book: Algorithms, 4th Edition Blog: Red Blob Games, Amit’s A* Pages Coding style Why writing clean, well-structured code ...

Hash Tables Save items in a key-indexed table. Index is a function of the key - Hash function, method for computing array index from key. 要实现哈希表, 需要解决几个问题: 如何定义/计算哈希函数。 相等判定：如何检查两个键是否相等。 冲突解决：寻找能够处理哈希到同一索引的两个密钥的算法和数据结构。 时空权衡设计问题: 如果没有空间限制, 那么可以使用非常简单的哈希函数, 极端情况就是给每一种键分配一个索引。 如果没有时间限制, 那么对于键冲突问题可以使用简单的顺序搜索。 而现实中, 哈希表就是解决同时存在空间和时间限制的问题。 哈希函数 最理想的目标, 生成均匀分布的索引, 这样计算高效. 比如电话号码, 使用前三个数字作为索引是一种比较草稿的设计, 因为前三个数字一般代表区号, 且区号都是有限的, 这样同一个区的号码都会挤在同一个索引位置. 较好的方式是使用后三位数字. 身份证号同理. 在实际设计过程中, 不同的数据类型适用不同的方法. 所有Java类都继承了int hashCode()方法. 该方法的基本要求是: If x.equals(y), then (x.hashCode() == y.hashCode()) 最好(但不是必须的)能够满足: If !x.equals(y), then (x.hashCode() != y.hashCode()) 默认的实现方式是利用内存位置. Java integers, booleans, and doubles: ...

HashMap HashMap 是基于哈希表的 Map 接口的非同步实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保证该顺序不是stable的。 HashMap 底层就是一个数组结构，数组中的每一项又是一个链表。 当新建一个 HashMap 的时候，就会初始化一个数组table = new Entry[capacity];, 每个 Entry 是一个 key-value 对，有一个指向下一个元素的引用，这就构成了链表。 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); init(); } static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; final int hash; …… } HashMap 底层数组的长度总是 2 的 n 次方，这是 HashMap 在速度上的优化, 所以有这段代码保证初始化时 HashMap 的容量总是 2 的 n 次方，即底层数组的长度总是为 2 的 n 次方。 ...

LinkedHashMap HashMap 是无序的，HashMap 在 put 的时候是根据 key 的 hashcode 进行 hash 然后放入对应的地方。所以在按照一定顺序 put 进 HashMap 中，然后遍历出 HashMap 的顺序跟 put 的顺序不同. JAVA 在 JDK1.4 以后提供了 LinkedHashMap 来实现有序的 HashMap！ LinkedHashMap 是 HashMap 的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用 LinkedHashMap。LinkedHashMap 是 Map 接口的哈希表和链表数组实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {} LinkedHashMap 采用的 hash 算法和 HashMap 相同，但是它重新定义了数组中保存的元素 Entry，该 Entry 除了保存当前对象的引用外，还保存了其上一个元素 before 和下一个元素 after 的引用，从而在哈希表的基础上又构成了双向链表。迭代顺序可以是插入顺序或者是访问顺序。 /** * The iteration ordering method for this linked hash map: <tt>true</tt> * for access-order, <tt>false</tt> for insertion-order. * 如果为true，则按照访问顺序；如果为false，则按照插入顺序。 */ private final boolean accessOrder; /** * 双向链表的表头元素。 */ private transient Entry<K,V> header; /** * LinkedHashMap的Entry元素。 * 继承HashMap的Entry元素，又保存了其上一个元素before和下一个元素after的引用。 */ private static class Entry<K,V> extends HashMap.Entry<K,V> { Entry<K,V> before, after; …… } 根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用 get 方法)的链表。默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。 ...