甲乙小朋友的房子

甲乙小朋友很笨,但甲乙小朋友不会放弃

0%

这里主要是我自己学习笔记。主要有以下几类:

算法与数据结构

为了方便,在本站统称为算法(事实上还是很有必要搞清算法和数据结构的关系)。算法分类传送门:主要围绕Leetcode中的各种题型整理的。

二刷目录:算法-题目集锦

每篇文章之下都是相关概念及相关题。总结起来有以下专题:

数组与数模块

动态规划

链表模块

  • 算法-链表 。链表的基本原理和操作非常重要,比如增、删、反转、合并、找中点等等。涉及到的技巧不多,大概就是dummy Node和快慢指针,个人觉得其终极原则就是链表这个数据结构的形式,以及这个形式造成了哪些优缺点。
  • 算法-栈 。一般来说栈可以用数组和链表实现。但链表实现的栈更容易扩充一些。本文记录了一些栈的常见题型。

树模块

  • 算法-二叉树与分治 。树上面的很多东西与链表很相似,它们都不能访问它前一个节点(父节点)。而树的前中后遍历体现了DFS的思想,层序遍历体现了BFS的思想,这两个都是树的搜索问题。当然在二叉树里,还有一个分治的思想,将大问题分解为不相干的子问题,这一点非常重要。
  • 算法-堆 。堆,也就是优先队列,我的理解,它是树个结构,始终维护树顶为极值。
  • 算法-Trie树 。 用树状结构表示很多个单词,以此加速单词的搜索。我想采用此结构的原因在于单词中的字母只有26个,数分支较少。如果是中文的话恐怕情况就不那么乐观了。(但这仅仅是个人猜测,待验证)
  • 算法-线段树 。介绍了线段树的概念和一道经典题目
  • 算法-B树 简单介绍了B树的原理
  • 算法-红黑树 简单介绍了红黑树的原理

图模块

  • 算法-DFS 。深度优先遍历看似简单,但事实上写起程序来还是有点棘手的。因为每道题的边界条件不同,细节之处就不同了。
  • 算法-回溯法 。 回溯法是一种选优搜索法,一般与DFS联合使用。经典的八皇后问题非常好地诠释了回溯法。
  • 算法-并查集 。 并查集非常适用于解决动态连通性的问题。如果图是静态的,其实DFS更快一些。
  • 算法-图 。树其实是一种有强约束的图。而图里算法非常多,截止现在这篇文章涉及到的只有拓扑排序。
  • 算法-单源最短路径问题 。早期的文章。
  • 算法-最小生成树算法 。这篇文章写得比较早了。简单地描述了最小生成树算法。

散列表

系统设计

系统设计这里坑比较大。

搜索引擎设计

系统设计课程

语言

网络

分布式存储

机器学习、深度学习

机器学习基础

基础的模型主要了解了两个方面,一个是线性模型,一个是树模型。而树模型又阐述了Bagging和Boosting两种思想。

线性模型

集成学习

竞赛

O2O优惠券预测

腾讯社交广告CVR转化率预估

其它实践相关

===========================================================

路漫漫其悠远兮,吾将上下而求索。

===========================================================

阅读全文 »

是视频马士兵 多线程与高并发的学习笔记。

计算机架构

从CPU到: - 寄存器,<1ns - L1 Cache, 1ns - L2 Cache, 3ns - L3 Cache, 15ns - main memory, 80ns

flowchart TB
  subgraph CPU
    subgraph CPU1
        Register寄存器
        ArithmeticLogicUnit运算逻辑单元
        L1Cache
        L2Cache
    end
    subgraph CPU2
    end
 end


  subgraph 内存
    subgraph ProgramA
        subgraph Thread1
        Data
        指令集
        end
        subgraph Thread2
        Data2
        指令集2
        end
    end
  end

  指令集 --> Register寄存器
  Data --> ArithmeticLogicUnit运算逻辑单元

多线程相关基础知识

CAS Compare And Swap (Compare And Exchange)

  • AtomicInteger的incrementAndGet(), 使用的是CAS-unsafe的方法-lock cmpxchg
  • linux底层实现:lock cmpxchg
  • lock: 操作系统&硬件层面 lock 当前内存 - 保证原子性
  • cmpxchg : compare and exchange - 非原子性

Java对象布局

  • Object o = new Object()
  • 24字节: markword(8个字节)、class pointer(4个字节,用了UseCompressedClassPointers)、padding(4个字节,为了保证是8字节的倍数)
  • 可以使用JOL(Java Object Layout)来显示打印对象的信息
  • markword包括 (UseCompressedOops enabled by default)
    • GC信息【分代年龄:4个bit表示,普通的15,CMS是6】
    • hashCode(调用后才会有)
    • markword里包含this object的锁状态!当用asynchronous(o) 给对象o加锁时,对象o的锁状态会产生如下锁升级的变化。

锁升级

    • 锁升级:无锁态->偏向锁->轻量级锁->重量级锁
    • 偏向锁(适合一个线程很短时间使用后释放,且反复使用):包含JavaThread当前线程指针
    • 轻量级锁:一旦有线程竞争,就升级为自旋锁。自旋锁:包含线程栈中Lock Record的指针。好处:用户态,所以效率高;坏处:占用CPU资源
    • 重量级锁(竞争激烈,自旋超过10次或者等待线程超过CPU核数一半、或者自适应自旋,向操作系统申请锁):指向互斥量(重量级锁)的指针。好处:锁有队列,当线程没有拥有锁时不消耗CPU资源在wait(也就是自旋线程会阻塞,进入阻塞队列进行等待)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|--------------------------------------------------------------------------------------------------------------|--------------------|
| Object Header (96 bits) | State |
|--------------------------------------------------------------------------------|-----------------------------|--------------------|
| Mark Word (64 bits) | Class Word (32 bits) | |
|--------------------------------------------------------------------------------|-----------------------------|--------------------|
| unused:25 | identity_hashcode:31 | cms_free:1 | age:4 | biased_lock:1 | lock:2 | OOP to metadata object | 无锁态 |
|--------------------------------------------------------------------------------|-----------------------------|--------------------|
| thread:54 | epoch:2 | cms_free:1 | age:4 | biased_lock:1 | lock:2 | OOP to metadata object | 偏向锁 |
|--------------------------------------------------------------------------------|-----------------------------|--------------------|
| ptr_to_lock_record | lock:2 | OOP to metadata object | Lightweight Locked |
|--------------------------------------------------------------------------------|-----------------------------|--------------------|
| ptr_to_heavyweight_monitor | lock:2 | OOP to metadata object | Heavyweight Locked |
|--------------------------------------------------------------------------------|-----------------------------|--------------------|
| | lock:2 | OOP to metadata object | Marked for GC |
|--------------------------------------------------------------------------------|-----------------------------|--------------------|

锁降级

只发生在GC。忽略。

锁消除

1
2
3
4
void Add(String s1, String s2){
StringBuffer sb = new StringBuffer();
sb.append(s1).append(s2); // StringBuffer 的append是线程安全的,StringBuilder的append是线程不安全的
}

StringBuffer 是用synchronized修饰的线程安全的。jdk如果检测到sb不可能有线程竞争,那jvm自动消除StringBuffer对象内部的锁。

锁粗化

1
2
3
4
5
6
7
void Test(String s){
StringBuffer sb = new StringBuffer();
while (i < 100){
sb.append(s);
++i;
}
}

JVM检测到sb的锁可以拿出到while外面

synchronized 的底层实现

用了个什么插件可以看到,用synchronized修饰的锁,底层实现就调用了lock cmpxchg

实际的各个层级 - java代码:synchronized - 字节码实现:monitorenter、moniterexit。也就是在执行过程中自动升级(无锁-偏向锁-自旋锁-重量级锁) - 更底层实现:lock cmpxchg:通过自旋改变一个值

volatile

volatile的两个含义: - 线程可见性 (下面code解释了) - 禁止指令重排序(禁止乱序):指的是对这个obj的读写的指令不能乱序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* volatile 关键字,使一个变量在多个线程间可见
* A B线程都用到一个变量,java默认是A线程中保留一份copy,这样如果B线程修改了该变量,则A线程未必知道
* 使用volatile关键字,会让所有线程都会读到变量的修改值
*
* 在下面的代码中,running是存在于堆内存的t对象中
* 当线程t1开始运行的时候,会把running值从内存中读到t1线程的工作区,在运行过程中直接使用这个copy,并不会每次都去
* 读取堆内存,这样,当主线程修改running的值之后,t1线程感知不到,所以不会停止运行
*
* 使用volatile,将会强制所有线程都去堆内存中读取running的值
*
* 可以阅读这篇文章进行更深入的理解
* http://www.cnblogs.com/nexiyi/p/java_memory_model_and_thread.html
*
* volatile并不能保证多个线程共同修改running变量时所带来的不一致问题,也就是说volatile不能替代synchronized
* @author mashibing
*/

public class T01_HelloVolatile {
/*volatile*/ boolean running = true; //对比一下有无volatile的情况下,整个程序运行结果的区别
void m() {
System.out.println("m start");
while(running) {
}
System.out.println("m end!");
}

public static void main(String[] args) {
T01_HelloVolatile t = new T01_HelloVolatile();

new Thread(t::m, "t1").start();

try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}

t.running = false;
}

}

volatile在JVM里怎么实现的?

结论:JVM内存屏障。 先看下面的一些概念,然后就懂了。

超线程

一个CPU有两个寄存器,一个计算单元。这样就可以两个thread“几乎同时”跑(很少有上下文切换)。所谓的四核八线程也即这个原因

缓存一致性协议 --> 保证线程可见性

  • L1,L2是单个cpu内部的。就是线程本地内存!
  • L3是多个cpu共享的
  • CPU数据的来源从近及远依次是L1 Cache, L2 Cache, L3 Cache(多个核或者多个CPU公用)以及main memory,也就是先从近的读取,如果没有再逐渐向外读取。
  • cache line 缓存行:由于程序局部性原理,会把数据按块读取。一个块就叫一个缓存行,64 bytes
  • CPU层级的数据一致性volatile,是以cache line为单位的。
  • 也就是一旦修改cache line里的任意data,别的L1/L2里的此cacheLine就失效了,要重读!也就是MESI Cache缓存一致性协议。x86 intel CPU的协议,表示modified、exclusive(独占整个缓存行)、shared、invalid(一个cpu修改了另一个的就是失效的)
  • 缓存行对齐:对于有些特别敏感的数字,会存在线程高竞争的访问,为了保证不发生伪共享(两个数字在同一个缓存行,但长期被两个不同的线程使用),可以使用缓存行对齐的编程方式;可以补齐到64字节,避免volatile可见性带来的效率低下问题。disruptor(环形队列)
jpg

内存屏障 --> 禁止指令重排序

  • 代码层面 volatile i
  • 字节码层面 ACC_VOLATILE 加标志
  • JVM层面是通过内存屏障来实现
    • JVM定义了四种接口,LoadLoad, StoreStore, LoadStore,StoreLoad,也是四种内存屏障
    • 对volatile 变量 的读写操作加:
      • StoreStore, Volatile Write, StoreLoad --> 也就是write->VolatileWrite->Read 这样的指令不可以重排序
      • LoadLoad, Volatile Read, LoadStore --> 也就是Read->VolatileRead->Write 这样的指令不可以重排序 (sfence mfence lfence等系统原语)。写操作前后ss和sl,读操作前后ll和ls
  • 系统层面 x86:

比较volatile和synchronized

  • volatile 关键字用途:
    • 保证变量的可见性:当一个变量被声明为 volatile 时,它确保了变量的修改对其他线程是可见的。也就是说,如果一个线程修改了 volatile 变量的值,其他线程会立即看到这个修改。这对于标志位或状态标识非常有用。
    • 禁止指令重排序:volatile 变量的读写操作不会被重排序,这意味着 volatile 变量的写入操作不会被移到后面执行,确保了写入操作的原子性。
    • 因此它不能保证线程安全!
  • synchronized 关键字用途:
    • 实现互斥锁:synchronized 用于实现互斥锁,可以确保同一时间只有一个线程可以访问被 synchronized 修饰的代码块或方法。这可以用于保护共享资源,防止多线程同时修改它们而导致的数据竞争和不一致性。
    • 实现条件同步:synchronized 还可以与 wait() 和 notify()/notifyAll() 方法一起使用,实现线程之间的条件同步。这对于线程等待某个条件满足后再执行特定操作非常有用。

所以,根据需求和具体情况,你可以选择使用 volatile 或 synchronized: - 如果你只需要确保变量的可见性并禁止指令重排序,而不需要互斥锁或条件同步,可以使用 volatile。 - 如果你需要互斥访问共享资源或实现复杂的条件同步,应该使用 synchronized。

是视频搜索广告的业务逻辑和技术分享的学习笔记。

关键词

广告主: - 创建广告方案capaign,和capaign下的多条ads。 - 每个capaign和ads有budget上限。 - 每个ads有key words

Impression(展示):有ML/SideBar/Bottom....

Workflow

Query Understand --> Select Ads (From Ads Store) --> Filter Ads --> Rank Ads --> Select Top K Ads --> Pricing --> Allocate Ads

阅读全文 »

本文总结做过的题,和关键思路。

二分查找

题号 题目 描述 关键思路
数组
34 Search for a range 给int[] {5,7,7,8,8,10],找到target=8出现的范围[3,4]。没找到返回[-1,-1] 二分
35 Search Insert Position 有序无重数组[1,3,5,6],把target=5插入,问插入的位置=2 二分
74 Search a 2D Matrix 严格行、列、换行递增的二维数组,找target 二分
240 Search a 2D Matrix II 行、列递增的二维数组,但换行不一定递增。找target 每行二分,或从左下开始寻找
278 First Bad Version 版本号是从 1 到 n 的整数。某一天,有人提交了错误版本的代码,因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号 二分,巧妙下标赋值
162 Find Peak Element 给一个数组。找峰值。相邻两个数都不一样。如果有多个峰值,就随便输出一个 二分
1901 Find a Peak Element II 二维数组。找四周峰值。相邻两个数都不一样。如果有多个峰值,就随便输出一个 二分
153 Find Minimum in rotated sorted array 找有序、无重、旋转数组(首位相接)中的最小值 二分
154 Find Minimum in rotated sorted array II 找有序、有重、旋转数组(首位相接)中的最小值 二分+精妙边界处理
33 Search in Rotated Sorted Array 从有序、无重、旋转数组(首位相接)中找target 二分+精妙边界处理
81 Search in Rotated Sorted Array II 从有序、有重、旋转数组(首位相接)中找target 二分+精妙边界处理
4 Median of two Sorted Arrays 找到两个有序数组的中位数 二分。太难了,没搞定。思路在《二分查找》里面
木材加工 把一些木头切成长度相同的小段木头,需要得到的小段的数目至少为 k。计算能够得到的小段木头的最大长度 将“最大长度”二分查找
374 Guess Number Higher or Lower A出一个1~n之间的数字,B猜为k。每次调用guess(k)时,返回:-1=猜大了,1=猜小了,0=猜对了。实现一个函数,模拟B猜测数字的过程,最终输出A心里的数字 二分

数组与数

题号 题目 描述 关键思路
数组
88 Merge Sorted Array 给两个排序数组,A,B,将B合并进A 从尾开始
349 Intersection of Two Arrays 求两个数组的交集 先排序
稀疏数组点乘 跳过0/建索引
第K大 堆、快速选择

二叉树与分治法

题号 题目 描述 关键思路
104 Maximum Depth of Binary Tree 求二叉树的最大深度 分治
110 Balanced Binary Tree 判断一个树是不是平衡二叉树 分治
236 ※ Lowest Common Ancestor 求两个节点的最近公共祖先 分治
124 Binary Tree Maximum Path Sum 给一个二叉树,找到从any node 到 any node最大路径和。路径可以在任何地方被结束掉 分治
226 Invert Binary Tree 将二叉树镜像反转(左右替换) 分治
98 Validate Binary Search Tree 验证一个二叉树是不是搜索二叉树 分治
173 Binary search Tree Iterator 中序、依次输出搜索二叉树 中序遍历
108 Convert Sorted Array to Binary Search Tree 将有序数组转化为平衡二叉树 分治
109 Convert Sorted List to Binary Search Tree 将有序链表转化为平衡二叉树 中序遍历,骚操作
还有几道题。等之后二刷
102 Binary Tree Level Order Traversal 二叉树层序遍历 队列
107 Binary Tree Level Order Traversal II 二叉树层序遍历,从最下层开始 队列
103 Binary Tree Zigzag Level Order Traversal 输出二叉树的锯齿形、层序遍历 队列
199 Binary Tree Right Side Viewl 给一个二叉树。从最右边看去,能看到的数字都是几 队列
还有几道题。等之后二刷
144 Binary Tree Preorder Traversal 二叉树的前序遍历
114 ※ Flatten Binary Tree to Linked List 将二叉树按照前序遍历的顺序变为只包含node.right的单链表 栈,巧妙只push right,还有两种骚操作
331 ※ Verify Preorder Serialization of a Binary Tree 验证一个序列是否是二叉树的前序遍历 分治法
145 ※ Binary Tree Postorder Traversal 二叉树的后序遍历 栈+hashset,还有一种栈+linkedList的骚操作
572 Subtree of Another Tree 给两个二叉树s和t。判断t是否是s的子树 两个二叉树同时遍历
106 Construct Binary Tree from Inorder and Postorder Traversal 用中序+后序恢复二叉树 分治

动态规划

题号 题目 描述 关键思路
64 Minimum Path Sum 从左上走到右下。只能向右向下走。求最小路径 dp
62 Unique Paths 从左上走到右下。只能向右向下走。求方案个数 dp
63 Unique Paths II 路上有障碍的上一题 dp
688 Knight Probability in Chessboard 给一个n*n的棋盘,每次可以走八个方向,如图所示。求从[r,c] 出发走K步之后它还停留在棋盘上的概率 dp
576 Out of Boundary paths 给一个m*n 的棋盘,每次可以走向上下左右四个方向。可以走回头路。求问在N步限制下,有多少种走出棋盘的方法 dp
70 Climbing Stairs 有一个楼梯,一步只能跨1/2步。问从0走到n层有多少层方案 dp
55 Jump Game 给一个数组A,A[i]表示在这里时最多可以跳A[i]步。只能向前跳。从数组A的第0位置出发,能不能跳到末尾。 dp/贪心
45 Jump Game II 给一个数组A,A[i]表示在这里时最多可以跳A[i]步。只能向前跳。从数组A的第0位置出发跳槽最后一个位置(假设一定能跳到),问最少的跳的次数 dp/贪心
300 ※ Longest Increasing Subsequence 求最长严格递增的子序列(子序列:可以跳着选 dp
354 ※ Russian Doll Envelopes 俄罗斯套娃信封。给一堆信封pair - [w,h] 。要求如果信封A的宽高都小于B的话,那么A就可以放入B。求这堆信封最多能套多少层 dp
673 Number of Longest Increasing Subsequence 求一个数组的最长递增子序列的个数 dp

题号 题目 描述 关键思路
295 Find Median from Data Stream 求动态数组的实时中位数 两个堆,一个比中位数大,一个都比中位数小
347 给一个int[],输出频率最高的k个数字 hashmap+堆

从定义说起,这个名字很长,一步步解释。

  1. 哈希函数 任意函数h(x)都可以说哈希函数,一般来说,一个良好的哈希函数可以尽量避免重复。x的集合是参数域,h(x)的集合是值域。
  2. 完美哈希函数 完美哈希函数,就是完全不会冲突的哈希函数,这要求函数的值域至少比参数域要大
  3. 最小完美哈希函数 最小完美哈希函数,就是指函数的值域和参数域的大小完全相等,一个也不多
  4. 保序最小完美哈希函数 保序的意思就是指这个哈希之后顺序是不变的,同时还能满足其他两个条件。

这个函数的优点就是形式上很完美,就像给一个排好序的文档编上的序号一般紧凑可靠。但是这个函数有两个缺点,一是必须事前必须知道原数据集,二是需要花一定的CPU来生成这个函数。我认为,对于数据仓库类的线下搜索应用,这个算法是有用武之地的。但对于强调实时的数据业务,这个算法是不适合的。

阅读全文 »

总结了cpp const关键字。常见的就不列举了,这里只记录我不会的。

一些我不会的

阅读全文 »

TODO.

浏览器输入 URL 之后发生了什么

  1. 浏览器解析 URL 生成 HTTP 请求报文:浏览器对 URL 进行解析,解析出服务器名,端口号,文件路径等信息之后,用于构造 HTTP 请求,并对URL 中的中文或保留字符进行编码。
  2. 应用层DNS解析:因为发送 HTTP 请求报文需要依赖下层 TCP 协议,TCP 建立连接并通信是需要 IP 地址 + 端口号 这一对二元组的,端口号可以直接从 URL 中获得,但是 IP 地址需要由 DNS 解析域名来获得。DNS 服务主要功能就是将 URL 中的域名,解析为 IP 地址
  3. ARP 地址解析ARP 协议是将 IP 地址映射为 MAC 地址。IP 地址和 MAC 地址是什么关系呢?这里就体现了计算机网络的分层的设计哲学。IP 地址是网络层的概念,而 MAC 地址是数据链路层的概念。假如有 N 个主机,通过一个交换机连接起来,那么这就是一个局域网,而局域网之间通过发送 MAC 帧进行通信,互相识别的都是 MAC 地址。而 N 个局域网通过路由器连接在一起就形成了一个互联网,这时候主要假如主机之间跨局域网,通过互联网来通信,就需要 IP 地址来发挥作用了。
  4. TCP 三次握手
  5. IP路由
阅读全文 »