Posts

在很多语言中，字符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....

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

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

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

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

在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工作时, 无论当前内存是否足够, 都会回收掉只有弱引用关联的对象. Object obj = new Object(); WeakReference<Object> wf = new WeakReference<Object>(obj); obj = null; wf....