Posts

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方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。 ...

LRU缓存 用缓存来存放之前读取过的数据，这样，再次读取的时候，可以直接在缓存里面取，而不用再重新查找一遍，这样系统的反应能力会有很大提高。但是，当我们读取的个数特别大的时候，我们不可能把所有已经读取的数据都放在缓存里，毕竟内存大小是一定的，所以一般把最近常读取的放在缓存里。 LRU(Least Recently Used)缓存利用了这样的一种思想, 把最新读取的数据放在最前面，缓存中存储的是读取最频繁的数据，以能够提高系统的性能。 LinkedHashMap实现LRU LinkedHashMap支持按照访问顺序的存储，也就是说，最近读取的会放在最前面，最不常读取的会放在最后。其次，LinkedHashMap 有一个方法用于判断是否需要移除最不常读取的数，原始方法默认不需要移除，所以，LRU 需要 override 这个方法，使得当缓存里存放的数据个数超过规定个数后，就把最不常用的移除掉。 import java.util.LinkedHashMap; import java.util.Collection; import java.util.Map; import java.util.ArrayList; /** * An LRU cache, based on <code>LinkedHashMap</code>. * * <p> * This cache has a fixed maximum number of elements (<code>cacheSize</code>). * If the cache is full and another entry is added, the LRU (least recently * used) entry is dropped. * * <p> * This class is thread-safe. All methods of this class are synchronized. * * <p> * Author: Christian d'Heureuse, Inventec Informatik AG, Zurich, Switzerland<br> * Multi-licensed: EPL / LGPL / GPL / AL / BSD. */ public class LRUCache<K, V> { private static final float hashTableLoadFactor = 0.75f; private LinkedHashMap<K, V> map; private int cacheSize; /** * Creates a new LRU cache. 在该方法中，new LinkedHashMap<K,V>(hashTableCapacity, * hashTableLoadFactor, true)中，true代表使用访问顺序 * * @param cacheSize * the maximum number of entries that will be kept in this cache. */ public LRUCache(int cacheSize) { this.cacheSize = cacheSize; int hashTableCapacity = (int) Math .ceil(cacheSize / hashTableLoadFactor) + 1; map = new LinkedHashMap<K, V>(hashTableCapacity, hashTableLoadFactor, true) { // (an anonymous inner class) private static final long serialVersionUID = 1; @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > LRUCache.this.cacheSize; } }; } /** * Retrieves an entry from the cache.<br> * The retrieved entry becomes the MRU (most recently used) entry. * * @param key * the key whose associated value is to be returned. * @return the value associated to this key, or null if no value with this * key exists in the cache. */ public synchronized V get(K key) { return map.get(key); } /** * Adds an entry to this cache. The new entry becomes the MRU (most recently * used) entry. If an entry with the specified key already exists in the * cache, it is replaced by the new entry. If the cache is full, the LRU * (least recently used) entry is removed from the cache. * * @param key * the key with which the specified value is to be associated. * @param value * a value to be associated with the specified key. */ public synchronized void put(K key, V value) { map.put(key, value); } /** * Clears the cache. */ public synchronized void clear() { map.clear(); } /** * Returns the number of used entries in the cache. * * @return the number of entries currently in the cache. */ public synchronized int usedEntries() { return map.size(); } /** * Returns a <code>Collection</code> that contains a copy of all cache * entries. * * @return a <code>Collection</code> with a copy of the cache content. */ public synchronized Collection<Map.Entry<K, V>> getAll() { return new ArrayList<Map.Entry<K, V>>(map.entrySet()); } // Test routine for the LRUCache class. public static void main(String[] args) { LRUCache<String, String> c = new LRUCache<String, String>(3); c.put("1", "one"); // 1 c.put("2", "two"); // 2 1 c.put("3", "three"); // 3 2 1 c.put("4", "four"); // 4 3 2 if (c.get("2") == null) throw new Error(); // 2 4 3 c.put("5", "five"); // 5 2 4 c.put("4", "second four"); // 4 5 2 // Verify cache content. if (c.usedEntries() != 3) throw new Error(); if (!c.get("4").equals("second four")) throw new Error(); if (!c.get("5").equals("five")) throw new Error(); if (!c.get("2").equals("two")) throw new Error(); // List cache content. for (Map.Entry<String, String> e : c.getAll()) System.out.println(e.getKey() + " : " + e.getValue()); } }

在Java中，JVM负责内存动态分配和垃圾回收的问题。Java的对象必须要有引用才能被使用，也就是说如果要操作对象，必须通过引用来进行。如果一个对象唯一的引用变量死了（随着堆栈块一起解散），对象就会被认定为可被垃圾回收（Garbage Collection）的。没有被引用的对象，是没有存在意义的，因为没有人知道它的地址，无法调用它，它的存在只会浪费空间。 目前内存的动态分配和内存回收技术已经相当成熟，但还是需要了解GC和内存分配，这样当需要排查各种内存溢出、内存泄漏问题时，当GC成为系统达到更高并发量的瓶颈时，需要对这些自动化的技术实施必要的监控和调节。 判断对象是否可回收 最简单的方法是通过引用计数（reference counting）来判断一个对象是否可以被回收。不失一般性，如果一个对象没有任何引用与之关联，那么这个对象就被判定为可被回收的对象了。这种方式实现简单，而且效率较高，但是它无法解决对象间循环引用的问题，因此在Java中并没有采用这种方式（Python采用的是引用计数法）。 主流的商用程序语言（Java，C#，Lisp）的主流实现中，使用可达性分析（reachability analysis）来判定对象是否存活。 使用一些列GC Root对象作为起始点，从这些节点开始往下沿着引用链搜索，如果GC Root到某个对象无法通过任何引用链项链，则该对象会被标记一次, 并且进行一次筛选, 筛选的条件是此对象是否有必要执行finalize()方法. 当对象没有覆盖finalize()方法, 或者该方法已经被JVM调用过, JVM都会视之为没有必要执行finalize()。 如果该对象被判定为有必要执行finalize()方法, 那么这个对象会被放置在F-Queue队列中, 并在稍后由一个由JVM自动建立的, 低优先级的Finalizer线程去执行. 执行只是触发该方法, 但不会等待它结束, 因为可能会有执行缓慢或者死循环等特殊情况 稍后GC会动F-Queue里的对象进行第二次标记, 如果对象要在finalize()中避免被消灭, 只需要重新与引用链上的任何一个对象建立关联即可(finalize()的优先级较低), 这样第二次标记时它将不会被考虑. 否则就只能被回收. 要注意, 任何一个对象的finalize()只会被系统自动调用一次, 下次再GC时不会再执行, 也就是只有一次自救机会. 在Java中，可作为GC Roots的对象包括： 虚拟机栈（栈帧中的本地变量表）中引用的对象。 方法区中类静态属性引用的对象 方法区中常量引用的对象 本地方法栈中native方法引用的对象 引用 引用分为强引用，软引用，弱引用，虚引用。根据不同引用，有不同的GC回收策略。 强引用：类似Object obj = new Object();这种, 垃圾回收器永远不会回收他们 软引用：非必须引用，内存溢出之前进行回收. 如果这次回收后内存还不足,才会抛出内存溢出异常 Object obj = new Object(); SoftReference<Object> sf = new SoftReference<Object>(obj); obj = null; sf.get();//有时候会返回null 软引用主要用户实现类似缓存的功能，在内存足够的情况下直接通过软引用取值，无需从繁忙的真实来源查询数据，提升速度；当内存不足时，自动删除这部分缓存数据，从真正的来源查询这些数据。 弱引用：非必须引用, 强度比软引用更弱. 当GC工作时, 无论当前内存是否足够, 都会回收掉只有弱引用关联的对象. ...

Exception-handling 假如调用了一个不是自己写的方法, 该方法执行某些有风险的任务(当然,自己写的也可能会有风险),可能会在运行期间出状况,那么就必须认识到该方法是有风险的, 要写出可以在发生状况时做出应对的代码. 当程序出现错误时，假如继续运行下去已经没有意义（或者根本不可能继续），那么我们就想要中断正常的控制流程 - throws an exception。 Throwing Exceptions 比如当想从某ArrayMap中提取某个不存在的键值时, java自动抛出一个implicit exception $ java ExceptionDemo Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at ArrayMap.get(ArrayMap.java:38) at ExceptionDemo.main(ExceptionDemo.java:6) 如果想让自己的程序抛出更详细的信息, 可以在程序中加入explicit exception public V get(K key) { intlocation = findKey(key); if(location < 0) { throw newIllegalArgumentException("Key " + key + " does not exist in map."\); } return values[findKey(key)]; } $java ExceptionDemo Exception in thread "main" java.lang.IllegalArgumentException: Key yolp does not exist in map. at ArrayMap.get(ArrayMap.java:40) at ExceptionDemo.main(ExceptionDemo.java:6) Catch Exceptions 单纯 throw exception 会导致代码崩溃。但是通过 try - catch “捕捉”异常(RuntimeException 是 Java object), 可以防止程序崩溃。 ...