题目

#146 LRU Cache

运用你所掌握的数据结构，设计和实现一个LRU(最近最少使用)缓存机制。它应该支持以下操作：获取数据get和写入数据put。

获取数据get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。

写入数据put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶: 你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例：
LRUCache cache(2);

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

题目

#141 Linked List Cycle

给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

坑一：多线程

在C或Java中我们都已经熟悉了使用多线程来进行并行化计算，Python也提供了多线程的接口来实现多线程编程。但使用过了才知道，性能非但没有提高，反而有所降低！！

原因是Python中的多线程并不是真正的多线程，因为解释器全局锁（GIL）的存在，每一时刻只有一个线程在工作，性能不可能有所提高，反而会因为切换线程带来的开销降低性能！

The Python threading module uses threads instead of processes. Threads run in the same unique memory heap. Whereas Processes run in separate memory heaps. This, makes sharing information harder with processes and object instances. One problem arises because threads use the same memory heap, multiple threads can write to the same location in the memory heap which is why the global interpreter lock(GIL) in CPython was created as a mutex to prevent it from happening.

另可参见Python 最难的问题中的讨论。

因此，要想实现并行化计算请使用多进程而不是多线程！

坑二：Pickable

使用多进程的常见方法是使用进程池（Pool），demo代码如下：

OPS repo: https://github.com/sjtu-ist/OPS

启动Hadoop集群

1
2
3

# log in slave1
$ ./shell/stop-all.sh
$ ./shell/start-all.sh

slot

slot是一个逻辑概念，是Hadoop中的资源单位。

给定前一个状态的输出，将该输出的线性函数再作为输入的移位寄存器。

其应用主要是生成伪随机数、伪随机噪声序列等等。

stream

使用stream可以遍历一个collection（Array也可以），使用map(对每个元素执行操作)、filter(过滤)等操作产生一个新的collection。

流的操作：

• Intermediate: map filter distinct sorted peek limit skip parallel sequential unordered
• Terminal: forEach forEachOrdered toArray reduce collect min max count anyMatch allMatch noneMatch findFirst findAny iterator
• Short-circuiting: anyMatch allMatch nonMatch findFirst findAny limit

*** => stream

1
2
3
4
5
6
7
8
9

// 1. Individual values
Stream stream = Stream.of("a", "b", "c");
// 2. Arrays
String [] strArray = new String[] {"a", "b", "c"};
stream = Stream.of(strArray);
stream = Arrays.stream(strArray);
// 3. Collections
List<String> list = Arrays.asList(strArray);
stream = list.stream();

Thread

使用Thread的start方法启动线程才是真正实现多线程运行，而直接调用run会顺序执行。

synchronized

synchronized 关键字，代表这个方法加锁,相当于不管哪一个线程A每次运行到这个方法时,都要检查有没有其它正在用这个方法的线程B（或者C D等）,有的话要等正在使用这个方法的线程B（或者C D）运行完这个方法后再运行此线程A,没有的话,直接运行它包括两种用法：synchronized 方法和 synchronized 块。