小齐本齐

小齐本齐 查看完整档案

海外编辑武汉大学  |  金融工程 编辑亚马逊  |  Full Stack 编辑 github.com/xiaoqi6666/NYCSDE 编辑
编辑

公众号:码农田小齐
回复【666】查看往期文章分类。
回复【进群】有技术交流群/自习打卡群/好文分享群。
回复【01-05】可以获取计算机精选书籍、个人刷题笔记、大厂面经、面试资料等资源~

愿我们一起成为更好的人,期待与你相遇️️

个人动态

小齐本齐 发布了文章 · 11月26日

感恩节新花样~瞄一眼小齐的暖心福利你能领多少?

大家早呀~今天是感恩节,趁着这个节日,想和大家说点心里话。


2020年初,我十分想写点什么。

我经历过迷茫和彷徨,也有破茧成蝶的蜕变,有些太多想和你分享。

于是,我在公众号上我借助文字来发现自己、观察内心,整理和升华知识体系。

但是,在互联网上,跟陌生人表达我的成长经历或是技术理解,我有些忐忑。

很幸运的是,有很多人喜欢我的文字,但也有一些不友善的评论。

我的内心也随着这些反馈,跌宕起伏。

每一篇文章,每一个视频,发完之后的第二天我都会早早醒来,赶紧去看评论。

有时兴奋,有时沮丧。

但自始至终,我都保持着初心:分享有用的信息。

在这个特殊的节日,我想真诚的对你说一句,谢谢你!

感谢你们

或许大家不清楚坚持原创文章是一种多么大的挑战,哪怕只是一周一篇。

始于热情,陷于好评。

<,, , >

谢谢你们的喜欢和支持,让我有源源不断的动力写下去。

写作这件事让我认识到,正向反馈真的很重要,我只是一个普通人,再爱的事情,没有了正向反馈,人都会放弃。

  • 就像追女孩子,别说半年,追 3 个月她不理你,或者忽冷忽热,你还会继续吗?
  • 就像上班,老板不给升职加薪,我们工作动力还会这么足吗?

坚持一件事本身就是逆人性的过程,而让这个过程可持续的动力,就是得到正向反馈。

这里的正向反馈可以是物质上的,可以是情绪上的。

比如我们坚持学习,是因为知道学习能够提高自己,将来带来财富或者社会地位的提高就是正向反馈。

比如我们坚持工作,是因为知道家人需要我们,上有老下有小全指望着我们,家人的笑脸就是我们的正向反馈。

比如我坚持写作,你们的鼓励就是我的正向反馈。

所以真心的感谢你们,感谢你们的陪伴和支持,你们的每句留言都是对我最大的鼓励!

感谢他们

同时,我还想感谢另外一群人。

因为他们,让我的声音传播给更多的人;因为他们,我才更能耐住寂寞,笔耕不缀;因为他们,我会更快的提高文章质量。

写作路上,我认识了很多作者。这个月大家可以看到我有推荐一些公众号,有些人会觉得是商业互吹,但其实他们都是我在写作路上的伙伴,他们每个人都有自己擅长的领域,相信会对你有所帮助。


在这里,还想感谢金主的认可。

我每周都会收到很多付费投放,但只发过一次。

我恰饭的原则很简单:

  • 一是要对大多数读者有用,这是我做公众号的初心呐;
  • 二是我自己认可,判断标准是不给我💰我是否愿意推广

只有满足了这两个条件,才是三赢的局面,否则任何一方的损伤都是我不愿意看到的。


感谢你们陪伴了这么久,也感谢你读到这里。

在这个特殊的节日,除了优质的文章,还有两个专属的宠粉活动,来回馈我的真爱粉!

回馈读者

活动一

这一年里,有很多读者问过我问题,但由于时间关系我没办法一一回复~

其实,我是有付费咨询的,但从没公开说过,毕竟我的时间非常有限。

大公司面试经验不足?想刷题不知如何下手?没有职场经验?想去大厂工作苦于没有好的老师指导?

趁着年末的假期,我想和你们建立更深层次的链接。

15分钟、价值 ¥249 元的交流,开放 10 个免费送给你! 今年年底之前用完哦!选择你合适的时间,和我聊聊天,可以是技术相关的,也可以是其他你想了解的话题。

获取方式非常简单!

仅需在公主号里评论过 3 次以上,或者在我的任意一个群里有过高质量的发言。

只要你满足任意一点,就可以来找我和我约时间,先到先得。

活动二

感谢华章书院的大力支持赞助,给大家送出 20 本价值 ¥92 元的 Effective Java 中文版!

很久之前我在视频里就推荐过 Effective C++ 和 Java,我自己都拜读过不止一遍,可以说是帮我拿下了半个 offer!

书中的每一章都包含几个“条目”,对于 Java 平台精妙之处有独到见解,并给出了优秀的代码范例。

每个条目的综合描述和解释都阐明了应该怎么做,不应该怎么做,以及为什么。

还采用了双色印刷,更便于读者阅读,在技术书里,非常罕见,足以证明这本书的地位之高!

它是针对如何编写高效、设计优良的程序提出了最实用、最权威的指导方针!

抽奖方式是:

一、视频号里我留了 10 个名额

点击👇这个视频:

二、公众号里有 10 个名额,其中 3 本送给我的读者群里的热心读者:

  1. 国内群的??没有昵称。。

谁让你们都这么谦虚。。

咳咳,其实还因为人家回答过妹子的一个问题,嗯,多帮妹子肯定要奖励的!

哦对了,读者群快满了,满了之后不打算建新群,所以没进群的抓紧吧,经常会有活动福利哦~

  1. 好文群的 NARCISSUS

没啥好说的,我就是如此肤浅。

  1. 自习室打卡第一名🥇 好好学习

  1. 海外群的宝宝们,因为没办法包邮海外。。就不选了。。

另外 7 位将在本文的留言中选:

大家转发+留言这篇文章,选留言点赞前 3 名 + 我最喜欢最走心的 4 个留言,直接送书,谢谢一路的支持!

查看原文

赞 1 收藏 0 评论 1

小齐本齐 发布了文章 · 11月23日

10 张图聊聊线程的生命周期和常用 APIs

上一篇文章我们聊了多线程的基础内容,比如为什么要使用多线程,线程和进程之间的不同,以及创建线程的 4 种方式。本文已收录至我的 Github: https://github.com/xiaoqi6666...

今天我们来说一下线程的生命周期和常用 APIs:我们需要非常清楚的知道线程的各种状态,比如排查程序运行慢的原因时,就需要看下是不是哪里被阻塞了;另外它也是面试时非常喜欢问的,如果基础内容都答不好,恐怕直接就挂了。

本文分为两大部分,

  1. 线程的 6 大状态;
  2. 多线程常用的 APIs:

    1. join()
    2. wait()
    3. notify()
    4. yield()
    5. sleep()
    6. currentThread()
    7. getName()
    8. getId()
    9. getPriority()
    10. setPriority()
    11. stop()

线程状态

关于线程的状态,网上各种说法都有,比较流行的是 5 种或者 6 种。关于 5 种状态的那个版本我没有找到理论依据,如果有小伙伴清楚的也欢迎留言指出。

我这里所写的是根据 java.lang.Thread 的源码,线程有以下 6 大状态:

public enum State {
  NEW,
  RUNNABLE,
  BLOCKED,
  WAITTING,
  TIMED_WAITTING,
  TERMINATED;
}

先上图,我们再依次来看。

1. New

A thread that has not yet started is in this state.

就是指线程刚创建,还没启动的时候,比如刚 new 了一个 thread

MyThread myThread = new MyThread();

2. Runnable

A thread is executing in the Java virtual machine but it may be waiting for other resources from the operating system such as processor.

那么接下来,自然就是要启动线程了,也就是调用 threadstart() 方法。

myThread.start();

启动之后,线程就进入了 Runnable 状态。

此时所有的线程都会添加到一个等待队列里,等待“CPU 调度”。

如果抢占到 CPU 的资源,那就执行;如果没抢到,就等着呗,等当前正在执行的线程完成它能执行的时间片之后,再次抢占。

要注意这里在等待的一般是系统资源,而不是锁或者其他阻塞。

3. Blocked

Thread state for a thread blocked waiting for a monitor lock.
A thread in the blocked state is waiting for a monitor lock to enter a synchronized block/method or reenter a synchronized block/method after calling wait() Object.

这里给出了非常明确的 use case,就是被锁在外面的才叫阻塞。所以这里必须要有至少 2 个线程。

4. Waiting

A thread in the waiting state is waiting for another thread to perform a particular action.

那具体有哪些原因呢?

A thread is in the waiting state due to calling one of the following methods:

  • Object.wait with no timeout
  • Thread.join with no timeout
  • LockSupport.park

所以说,当调用了

  • wait()
  • join()
  • park()
    方法之后,线程进入等待状态。

这里的等待状态是没有时间限制的,可以无限的等下去... 所以需要有人来唤醒

  1. 如果是通过 wait() 进入等待状态的,需要有 notify() 或者 notifyAll() 方法来唤醒;
  2. 如果是通过 join() 进入等待状态的,需要等待目标线程运行结束。

比如在生产者消费者模型里,当没有商品的时候,消费者就需要等待,等待生产者生产好了商品发 notify()。下一篇文章我们会细讲。

5. Timed_waiting

导致这个状态的原因如下:

  • Thread.sleep
  • Object.wait with timeout
  • Thread.join with timeout
  • LockSupport.parkNanos
  • LockSupport.parkUntil

其实就是在上一种状态的基础上,给了具体的时间限制

那么当时间结束后,线程就解放了。

6. Terminated

A thread that has exited is in this state.

这里有 3 种情况会终止线程:

  • 执行完所有代码,正常结束;
  • 强制被结束,比如调用了 stop() 方法,现在已经被弃用;
  • 抛出了未捕获的异常。

线程一旦死亡就不能复生。

如果在一个死去的线程上调用 start() 方法,那么程序会抛出 java.lang.IllegalThreadStateException

接下来我们说说多线程中常用的 11 个 APIs。

APIs

1. join()

join() 方法会强制让该线程执行,并且一直会让它执行完。

比如上一篇文章的例子是两个线程交替执行的,那么我们这里该下,改成调用小齐线程.join(),那么效果就是先输出 小齐666

public class MyRunnable implements Runnable {
    @Override
    public void run() {
        for(int i = 0; i < 100; i++) {
            System.out.println("小齐666:" + i);
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Thread t = new Thread(new MyRunnable());
        t.start();
        t.join();

        for(int i = 0; i < 100; i++) {
            System.out.println("主线程" + i + ":齐姐666");
        }
    }
}

图2

所以 join() 能够保证某个线程优先执行,而且会一直让它执行完,再回归到公平竞争状态。

join() 方法其实是用 wait() 来实现的,我们来看下这个方法。

2. wait() and notify()

wait() 其实并不是 Thread 类的方法,而是 Object 里面的方法。

该方法就是让当前对象等待,直到另一个对象调用 notify() 或者 notifyAll()

当然了,我们也可以设定一个等待时长,到时间之后对象将会自动苏醒。

4. yield()

yield 本身的中文意思是屈服,用在这里倒也合适。

yield() 表示当前线程主动让出 CPU 资源一下,然后我们再一起去抢。

注意这里让一下真的只是一下,从“执行中”回到“等待 CPU 分配资源”,然后所有线程再一起抢占资源。

5. sleep()

顾名思义,这个方法就是让当前线程睡一会,比如说,

myThread.sleep(1000); // 睡眠 1 秒钟

它会抛出一个 InterruptedException 异常,所以还要 try catch 一下。

6. currentThread()

Returns a reference to the currently executing thread object.

该方法是获取当前线程对象。

注意它是一个 static 方法,所以直接通过 Thread 类调用。

比如打印当前线程

System.out.println(Thread.currentThread());

前文的例子中,它会输出:

Thread[Thread-0,5,main]
Thread[main,5,main]

没错,它的返回值也是 Thread 类型。

7. getName()

该方法可以获取当前线程名称。

这个名称可以自己设置,比如:

Thread t = new Thread(new MyRunnable(), "壹齐学");

8. getId()

该方法是获取线程的 Id.

9. getPriority()

线程也有优先级的哦~

虽然优先级高的线程并不能百分百保证一定会先执行,但它是有更大的概率被先执行的。

优先级的范围是 1-10,我们来看源码:

    /**
     * The minimum priority that a thread can have.
     */
    public final static int MIN_PRIORITY = 1;

   /**
     * The default priority that is assigned to a thread.
     */
    public final static int NORM_PRIORITY = 5;

    /**
     * The maximum priority that a thread can have.
     */
    public final static int MAX_PRIORITY = 10;

如果不在这个范围,JDK 抛出 IllegalArgumentException() 的异常。

10. setPriority()

当然啦,我们也是可以自己设置某个线程的优先级的。

设置的优先级也需要在规定的 1-10 的范围内哦,如果不在这个范围也会抛异常。

11. stop()

最后我们来说下 stop() 方法,也是前文提到过的强制停止线程的一种方式,但现在已被弃用,因为会引起一些线程安全方面的问题。

好了,以上就是有关线程状态和常用 API 的介绍了。相信大家看完之后对线程的整个流程应该有了清晰的认识,其实里面还有很多细节我没有展开,毕竟这是多线程的第 2 讲,更深入的内容我们慢慢来。

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...**

查看原文

赞 3 收藏 3 评论 0

小齐本齐 发布了文章 · 11月20日

不想做科技第一的金融公司,不是好的养老去处

<span style="display:block;text-align:center;">这里是《齐姐聊大厂》系列的第 15 篇

<span style="display:block;text-align:center;">每周五早上 8 点,与你唠唠大厂的那些事

小齐说:

大家周五好~今天是《齐姐聊大厂》系列的最后一篇了。

可能大家并不清楚这一篇文章的制作成本和来源,今天先和大家叨叨两句。

大家有没有想过这些文章是怎么来的?

我本身不是 CS 科班出身,身边的朋友在互联网公司的很少,而这半年来疫情宅家也没有社交活动,接触的人也很少。

为了这个系列,我更多的是要去联系一些陌生人,比如去 Linkedin 上加人,然后问人家是否愿意参与,答应之后我还需要和他聊天,引导的问些问题,最后再整理编辑排版出来,比我自己写文章还要费时间费精力费钱

就像当年找工作一样,我一共给上百个人发了消息,回复我的大概有 10%,最终能够拿到的只有这 15 篇文章。。当然了,也是有其他好处的,比如链接到了这些人。

随着这个系列阅读量的逐渐走低,我决定不再更新了,让自己休息一下,也需要维护已有的这些关系。

如果你喜欢这个系列,还请转发支持一下,谢谢大家~


今天这家公司有点特别,可能不了解金融行业的同学不清楚,先做个小介绍。

Bloomberg 这家公司只做一件事:提供 Bloomberg 这个软件(文中的 terminal),是一个集金融信息、数据、社交为一体的软件,几乎所有金融公司都需要的,价格也非常昂贵,可以说已经垄断了整个行业。

国内对应的软件是 Wind,当年在券商实习时都是要天天用的,当然国内也会用 Bloomberg,毕竟需要获取国外的数据,但是因为太贵,所以只会在某些部门里才有。

Bloomberg 是标准的 Fintech 公司,私人企业,创始人Mike Bloomberg 曾是纽约市市长,目前公司年收入 100 亿美金左右,最近还传言要“借壳上市”,就是一种 SPAC 的方式,这个就不多展开了,来看作者的工作感受吧。


Bloomberg 大半年,感受不少:

不同职业的人眼里,这家公司的定义是完全不同的。

  • 纯码农眼里,这是一家金融公司
  • 金融人眼里,这是一家软件公司
  • 老百姓眼里,这是一家电视台(以至于我父母一直认为我在电视台工作);
  • 我个人眼里,这是一家fintech 公司,terminal 给华尔街提供数据和咨询服务(infrastructure),而 IB 是金融从业者的 facebook(ecosystem)。

公司文化

我觉得感受最深的, 或者说 BBG 最大的优点还是Culture 非常赞!感觉大家都挺开心 + 挺 nice, 千金难买爷开心呀!

有几点:

a. wlb 很好

可能是产品和商业上很成熟, 所以技术角度我们没有那么大的压力。总之我目前只算使出 50%的心力,就算 performance 不错 + 自己开心。

b. Tech 员工扁平化

组里有 tech lead (就是直接管我们的 manager),上面有 manager(相当于其他公司的 senior manager)。

Tech lead 同时要规划项目,管理人员,自己也依然要写代码;所以跟直属 manager 交流没任何问题。当然了, 对于能力超长的技术大牛,扁平化反而不是好事。

c. 把员工当做 asset, 尊重员工

对于 SDE 新人提供三个月的 training(貌似过去培训大半年);这也反应出公司的心态,就是期待员工会很长久的呆在这里。考 CFA 会报销,修 part-time degree 也会报销一部分。还有一个细节,有 HR 或者 journalist 这种纯文科员工,只要会 coding 居然也能内部转成码农,真是新奇。

d. 貌似从来不开除码农

这是 good culture 的重要原因。因为大家不愁生计, 不用担心亚马逊那种 PIP,这种环境下大家自然更加友善,愿意相互帮助。只要你愿意,可以做到退休。

2008 年金融危机以及现在的疫情疫情期间,Bloomberg 都是在招人的,正好网罗从其他公司被迫失业的人才。

e. 人才来源

首先, 可以看到很多气质完全不同的金融人才,挺有意思。

其次码农这边的话主力是两类,一类是优秀新人,另一类是多年经验 + 忠诚的老员工(10 年+)。

新人里牛人挺多的比如不少 H Y P S M 这类顶级学校的;同时貌似越来越倾向于招美本的,所以大家英文都不错的样子。老员工的话,因为好些组历史久远或者需要特定的 finance knowledge,所以老员工的宝贵经验很重要,不过也可能就一辈子在这个组干了。而薄弱环节貌似是中间部分比如做了 3-5 年的 senior,要么跳槽要么很尴尬,据说工资不够 competitive。

技术

Bloomberg 是 Fintech 公司, 总体来说纯技术水平当然落后西海岸巨头的(FLAG 这种)。

很多原因,比如我们可能比科技公司更加 business driven,维持华尔街稳定比技术创新更重要;比如公司历史太久有很多 legacy code;再比如只服务于几十万用户所以 scalability 不可能跟 billion 用户级别的 F/G/A 比;然后基于金融业对 security 的高要求必然有很多 in-house tech stack,等等等等。

一些具体的缺点,如内部 tech infrastructure 很弱,没有 unit test, integration test, 没有 coding style, document 更加是没有,都是靠老员工"心口相传" (yes, verbal document, lol)。

然后老掉牙的 20 年前的 fortran code 外面套上好几层 wrapper,等等。

以上问题尤其是直接面向用户的 finance service 的组更加严重,纯 software 的组可能会好很多。

所以, 如果你是技术大牛,或者只对纯 software 纯 Internet 有兴趣,那么不要来这家,坦白说不要来华尔街

其实因为 Bloomberg 的直接盈利产品是软件,所以我们是华尔街上很少的码农是 first-class citizen 的公司了。08 年危机后街上的银行貌似更加不行;一般的 fund 没名气待遇也没太好;那几家 top hedge fund 自然是超级好,但很难进去。

但是,公司也在非常迅猛的甚至壮士断腕般努力的全公司范围内 update infrastructure,大量的组都在 migrate to Linux,去除过于 legacy 的东西,很多组也都在用 open-source technology。

当然我从来不认为 in-house tech 是一件坏事,大公司都是如此,对码农的训练也差不多。只不过 FG 这种技术水平极高同时面向大众的公司可以把 internal tool 做成真实产品推广;而 BBG 的目的是服务于金融业,完全没这个商业需求。另外 AI 组也发展迅猛,因为商业上涉及很多 news,所以对 NLP 有非常多需求。总之,技术角度总是可以找到喜欢的组的。

当然, 如果你喜欢金融/fintech, Bloomberg 当然是一家很棒的 dream company 了。这也是我来这儿的原因,至少一定可以学到金融和投资常识,还可以探索全新的职业出路。可能还是我自己 SDE 半路出家,对 pure tech 热情不高,而喜欢 tech + domain knowledge。另外可以多见见不同行业的人,感受一下华尔街,都会是人生宝贵经验。

Business

最后想强调一下很多码农都未必关注的商业方面

我个人觉得, 我们 tech 员工能有不错的 wlb 很大原因就是公司商业上的成功我们只是通过 tech 的手段来达到商业目的罢了

Michael Bloomberg 是深谙华尔街之道但也懂计算机的,很知道华尔街的 painpoint(其实 Jeff Bezos 也是, 如果你看他的背景)。

说几点个人看法:

a. 占到先机

1980 年代就看到了需求,抢占了金融咨询数字化的先机,跟微软抢 software 先机,Google 抢互联网先机一样,变成 monopoly 就很难被击败了(除非自己作死)。IB chat 已经成了华尔街的 facebook,你不用就脱离了圈子。

b. 只租不卖, 一口价

每台 terminal 年租金高达 2.5 万刀,其实大部分人怕是 1%的 function 都用不到,或者你只是冲着用 IB,但你要买就必须全部买下来。

当然现在 sales 上一个新卖点就是 enterprise data,而不是出售整台 terminal。这么霸道的背后是因为没有其他取代产品;同时对于手握 hundred million 资产的 portfolio manager,这点小钱算个啥?很多时候也只是身份的象征吧。这也是金融跟我们 tech 不同的思维。

c. 很了解金融需求

只要你能想到的任何 financial service 需求,任何 security,恐怕都可以在 terminal 里找到。

Sales 非常强大, 恐怕每一家 client(比如每一家 BOA branch)都会有一个 contact person 做售后服务。所以这让我充分认识到,首先这是一门 business,其次才是 tech;尤其是金融业水这么深的行业,怎么可能光靠 pure tech 就取胜的?Google 技术再强大,google finance 也取代不了 Bloomberg 的业务,毕竟一个是免费,一个是 2.4 万美金的服务。华尔街怎么会有白吃的午餐呢。

d. Media.

老百姓眼里的 Bloomberg News 电视台,其实只是 terminal 的一个广告罢了。哪怕 Bloomberg News 这笔生意是直接亏损的,但换来的民间的广告效益是无价的,我觉得这是公司决策者非常高明的一项战略投资。

e. Private company.

私有公司,不需要股民投资,所以不受股市影响;影响着华尔街,却尽量避免华尔街的冲击,是不是有点小 😈,lol. 这或许也是公司比较稳定安全的原因之一吧。

其他

很多人说公司办公环境很高大上, 我觉得一般吧;鱼缸倒是挺 fancy 也挺少见的算是一个特色。

各种福利不说了。我觉得, 如果你对金融市场有兴趣,那么最赞的福利应该是人手一台的每年 2.4 万刀的 terminal 吧。

NYC 的几栋楼地理位置优越,都紧靠交通枢纽/地铁站,不知道是不是公司故意这么设计的。但是纽约地铁实在臭不可闻,哪天我离开这里一定是因为纽约地铁。

没有 free lunch,只有汤。晚上 8 点后有晚餐。无论午汤还是晚餐,个人觉得都 barely eatable(难以下咽)。

公司没股票,所以给的 base 会高点,然后给 bonus in cash。貌似这是华尔街的规矩。

dei,无论是投行还是 fund,都是这样。

如果你不想在彭博永远待下去(you can if you want),很多做 2-3 年就跳去比如 Google NYC 或者其他 trading company/fund 啥的。

总之, 除了技术不如西海岸巨头,我个人觉得这是一家很赞的公司。另外,现在是艰难时期,但疫情导致金融市场不稳定,反而极大增加了用户对 terminal 的依赖;另外我个人推测 wfh 不能 share account 很多公司也被迫订更多 terminal;所以导致彭博其实在扩招,跟 2008 年的套路一模一样,历史惊人重演。所以这次危机中不幸失去工作的小伙伴,值得投一投彭博。

查看原文

赞 0 收藏 0 评论 0

小齐本齐 发布了文章 · 11月19日

新手一看就懂的线程池!

经过前几篇文章的学习,大家对多线程应该有些了解了吧,这里附上前三篇文章的链接,还没有看过的小伙伴快去复习吧~~

多线程基础篇入门

线程的生命周期和常用 APIs

生产者消费者问题

那相信大家也能感受到,其实用多线程是很麻烦的,包括线程的创建、销毁和调度等等,而且我们平时工作时好像也并没有这样来 new 一个线程,其实是因为很多框架的底层都用到了线程池。

线程池是帮助我们管理线程的工具,它维护了多个线程,可以降低资源的消耗,提高系统的性能。

并且通过使用线程池,我们开发人员可以更好的把精力放在任务代码上,而不去管线程是如何执行的,实现任务提交和执行的解藕。

本文将从是何、为何、如何的角度来讲解线程池:

  1. 线程池是什么
  2. 为什么要用线程池
  3. 怎么用线程池

线程池 Thread Pool

线程池是一种池化的技术,类似的还有数据库连接池、HTTP 连接池等等。

池化的思想主要是为了减少每次获取和结束资源的消耗,提高对资源的利用率。

比如在一些偏远地区打水不方便的,大家会每段时间把水打过来存在池子里,这样平时用的时候就直接来取就好了。

线程池同理,正是因为每次创建、销毁线程需要占用太多系统资源,所以我们建这么一个池子来统一管理线程。用的时候从池子里拿,不用了就放回来,也不用你销毁,是不是方便了很多?

Java 中的线程池是由 jucjava.util.concurrent 包来实现的,最主要的就是 ThreadPoolExecutor 这个类。具体怎么用我们下文再说。

线程池的好处

在多线程的第一篇文章中我们说过,进程会申请资源,拿来给线程用,所以线程是很占用系统资源的,那么我们用线程池来统一管理线程就能够很好的解决这种资源管理问题

比如因为不需要创建、销毁线程,每次需要用的时候我就去拿,用完了之后再放回去,所以节省了很多资源开销,可以提高系统的运行速度。

而统一的管理和调度,可以合理分配内部资源,根据系统的当前情况调整线程的数量。

那总结来说有以下 3 个好处:

  1. 降低资源消耗:通过重复利用现有的线程来执行任务,避免多次创建和销毁线程。
  2. 提高相应速度:因为省去了创建线程这个步骤,所以在拿到任务时,可以立刻开始执行。
  3. 提供附加功能:线程池的可拓展性使得我们可以自己加入新的功能,比如说定时、延时来执行某些线程。

说了这么多,终于到了今天的重点,我们来看下究竟怎么用线程池吧~

线程池的实现

Java 给我们提供了 Executor 接口来使用线程池。

Executor

我们常用的线程池有这两大类:

  • ThreadPoolExecutor
  • ScheduledThreadPoolExecutor

它俩的区别呢,就是第一个是普通的,第二个是可以定时执行的。

当然还有其他线程池,比如 JDK 1.7 才出现的 ForkJoinPool ,可以把大任务分割成小任务来执行,最后再大一统。

那么任务提交到一个线程池之后,它会经历一个怎样的过程呢?

执行过程

线程池在内部实际上采用了生产者消费者模型(还不清楚这个模型的在文章开头有改文章的链接)将线程和任务解藕,从而使线程池同时管理任务和线程。

当任务提交到线程池里之后,需要经过以下流程:

执行过程

  1. 首先它检查核心线程池是否已满。这个核心线程池,就是不管用户量多少线程池始终维护的线程的池子。比如说线程池的总容量最多能装 100 个线程,核心线程池我们设置为 50,那么就无论用户量有多少,都保持 50 个线程活着。这个数字当然是根据具体的业务需求来决定的。
  2. 阻塞队列,就是 BlockingQueue ,在生产者消费者这节里提到过。
  3. 最后判断线程池是否已满,就是判断是不是已经有 100 个线程了,而不是 50 个。
  4. 如果已经满了,所以不能继续创建线程了,就需要按照饱和策略或者叫做拒绝策略来处理。这个饱和策略我们下文再讲。

ThreadPoolExecutor

我们主要说下 ThreadPoolExecutor ,它是最常用的线程池。

ThreadPoolExecutor Structure

这里我们可以看到,这个类里有 4 个构造方法,点进去仔细看,其实前三个都 call 了最后一个,所以我们只需要看最后一个就好。

public ThreadPoolExecutor(int corePoolSize,
                          int maximumPoolSize,
                          long keepAliveTime,
                          TimeUnit unit,
                          BlockingQueue<Runnable> workQueue,
                          ThreadFactory threadFactory,
                          RejectedExecutionHandler handler) {
    ...
}

这里我们来仔细看下这几个参数:

  1. corePoolSize:这个就是上文提到过的核心线程池的大小,在核心里的线程是永远不会失业的。
corePoolSize the number of threads to keep in the pool, even if they are idle, unless {\@codeallowCoreThreadTimeOut} is set
  1. maximumPoolSize:线程池的最大容量。
maximumPoolSizethe maximum number of threads to allow in the pool
  1. keepAliveTime:存活时间。这个时间指的是,当线程池中的线程数量大于核心线程数,这些线程闲着之后,多久销毁它们。
keepAliveTimewhen the number of threads is greater than the core, this is the maximum time that excess idle threads will wait for new tasks before terminating.
  1. unit:对应上面存活时间的时间单位。
unit the time unit for the {\@codekeepAliveTime} argument
  1. workQueue:这是一个阻塞队列,其实线程池也是生产者消费者模型的一种,任务 - 相当于生产者,线程 - 相当于消费者,所以这个阻塞队列是用来协调生产和消费的进度的。
workQueuethe queue to use for holding tasks before they are executed.
  1. threadFactory:这里用到了工程模式,用来创建线程的。
threadFactorythe factory to use when the executor creates a new thread
  1. handler:这个就是拒绝策略。
handlerthe handler to use when execution is blocked because the thread bounds and queue capacities are reached

所以我们可以通过自己传入这 7 个参数构造线程池,当然了,贴心的 Java 也给我们包装好了几类线程池可以很方便的拿来使用。

  • newCachedThreadPool
  • newFixedThreadPool
  • newSingleThreadExecutor

我们具体来看每个的含义和用法。

newCachedThreadPool

public static ExecutorService newCachedThreadPool() {
    return new ThreadPoolExecutor(0, Integer.MAX_VALUE,
                                  60L, TimeUnit.SECONDS,
                                  new SynchronousQueue<Runnable>());
}

这里我们可以看到,

  • 核心线程池数量为 0,也就是它不会永久保留任何线程;
  • 最大容量是 Integer.MAX_VALUE
  • 每个线程的存活时间是 60 秒,也就是如果 1 分钟没有用这个线程就被回收了;
  • 最后用到了同步队列。

它的适用场景在源码里有说:

These pools will typically improve the performance of programs that execute many short-lived asynchronous tasks.

来看怎么用:

public class newCacheThreadPool {

    public static void main(String[] args) {
        // 创建一个线程池
        ExecutorService executorService = Executors.newCachedThreadPool();
        // 向线程池提交任务
        for (int i = 0; i < 50; i++) {
            executorService.execute(new Task());//线程池执行任务
        }
        executorService.shutdown();
    }
}

执行结果:

newCached 结果

可以很清楚的看到,线程 1、2、3、5、6 都很快重用了。

newFixedThreadPool

public static ExecutorService newFixedThreadPool(int nThreads) {
    return new ThreadPoolExecutor(nThreads, nThreads,
                                  0L, TimeUnit.MILLISECONDS,
                                  new LinkedBlockingQueue<Runnable>());
}

这个线程池的特点是:

  1. 线程池中的线程数量是固定的,也是我们创建线程池时需要穿入的参数;
  2. 超出这个数量的线程就需要在队列中等待。

它的适用场景是:

Creates a thread pool that reuses a fixed number of threads operating off a shared unbounded queue.
public class FixedThreadPool {
    public static void main(String[] args) {
        ExecutorService executorService = Executors.newFixedThreadPool(10);
        for (int i = 0; i < 200; i++) {
            executorService.execute(new Task());
        }
        executorService.shutdown();
    }
}

newFixed 结果

这里我限制了线程池里最多有 10 个线程,哪怕有 200 个任务需要执行,也只有 1-10 这 10 个线程可以运行。

newSingleThreadExecutor

public static ExecutorService newSingleThreadExecutor() {
    return new FinalizableDelegatedExecutorService
        (new ThreadPoolExecutor(1, 1,
                                0L, TimeUnit.MILLISECONDS,
                                new LinkedBlockingQueue<Runnable>()));
}

这个线程池顾名思义,里面只有 1 个线程。

适用场景是:

Creates an Executor that uses a single worker thread operating off an unbounded queue.

我们来看下效果。

public class SingleThreadPool {
    public static void main(String[] args) {
        ExecutorService executorService = Executors.newSingleThreadExecutor();
        for (int i = 0; i < 100; i++) {
            executorService.execute(new Task());
        }
        executorService.shutdown();
    }
}

newSingle 结果

这里在出结果的时候我能够明显的感觉到有些卡顿,这在前两个例子里是没有的,毕竟这里只有一个线程在运行嘛。

小结

所以在使用线程池时,其实都是调用的 ThreadPoolExecutor 这个类,只不过传递的不同参数。

这里要特别注意两个参数:

  • 一是 workQueue 的选择,这个就是阻塞队列的选择,如果要说还得这么一大篇文章,之后有机会再写吧。
  • 二是 handler 的设置。

那我们发现,在上面的 3 个具体线程池里,其实都没有设定 handler,这是因为它们都使用了 defaultHandler

/**
 * The default rejected execution handler
 */
private static final RejectedExecutionHandler defaultHandler =
    new AbortPolicy();

ThreadPoolExecutor 里有 4 种拒绝策略,这 4 种策略都是 implementsRejectedExecutionHandler

  1. AbortPolicy 表示拒绝任务并抛出一个异常 RejectedExecutionException。这个我称之为“正式拒绝”,比如你面完了最后一轮面试,最终接到 HR 的拒信。
  2. DiscardPolicy 拒绝任务但不吭声。这个就是“默拒”,比如大部分公司拒简历的时候都是默拒。
  3. DiscardOldestPolicy 顾名思义,就是把老的任务丢掉,执行新任务。
  4. CallerRunsPolicy 直接调用线程处理该任务,就是 VIP 嘛。

所以这 3 种线程池都使用的默认策略也就是第一种,光明正大的拒绝。

好了以上就是本文的所有内容了。当然线程池还有很多知识点,比如 execute()submit() 方法,线程池的生命周期等等。

但随着阅读量的逐渐走低,齐姐意识到了这似乎有什么误会,所以这篇文章是多线程系列的最后一篇了。

本文已收录至我的 Github 上:https://github.com/xiaoqi6666/NYCSDE,点击阅读原文直达,这个 Github 汇总了我所有的文章和资料,之后也会一直更新和维护,还希望大家帮忙点个 Star,你们的支持和认可,就是我创作的最大动力!

我是小齐,终生学习者,每天晚上 9 点,云自习室里不见不散!

查看原文

赞 7 收藏 4 评论 1

小齐本齐 发布了文章 · 11月17日

一文带你玩转设计模式之「责任链」

微信搜索🔍「码农田小齐」,关注这个在纽约的程序媛,回复「01-05」可以获取计算机精选书籍、个人刷题笔记、大厂面经、面试资料等资源,么么哒~

前言

对于已经工作了的小伙伴,你应该是见过"责任链"这种面向对象的设计模式的,还在上学的小伙伴也不用着急,你迟早会接触到的。本文旨在让小白同学和不太熟悉责任链的朋友能够迅速对这一设计模式有一个大致的了解。

在我们的工农业生产中,经常有这样的场景:一个任务、事务、流程等都需要很多不同的步骤,来完成不同的计算或者收集不同的数据。

为了维护一个比较复杂,有时甚至是对顺序敏感的任务流程,我们经常在代码的编写和设计上采用"责任链"设计模式。

究竟什么是"责任链"呢?咱们看下面这个例子。

例子

假设你也"穿越"到了清朝,是会写代码的和珅和中堂,皇上马上要南巡。请你用代码封装并模拟:"乾隆下江南" 这件事。

你要怎么安排万岁爷的行程?要知道这可是个大工程,中间可不能有差错,一旦出了什么岔子可是要掉脑袋的 😂

但皇上又是性情中人,行程可能经常更改,甚至半路就微服私访。

所以我们在伺候皇上下江南的时候,既得让皇上的行程有序进行,又要尽量适应圣上由于一时兴起而可能做出的变化。

怎么设计呢?如果把皇上的行程都写在一起执行,有两个不好的地方:

  1. 行程太多,而且全都事关重大,这么远的路,全都要你一个人打理,哪里一不注意出了乱子,脑袋就要搬家;
  2. 行程多,所以增改起来太麻烦,一旦有改动圣上的行程表容易乱。毕竟行程写在一起,好似
    一堆乱麻,条理不清。

所以问题来啦,和大人您可怎么排圣上的行程呢?

和大人莫急,看看地图我们就知道,乾隆从北京到杭州要顺序经过直隶、山东、江苏、浙江四省(基本就是现在京沪高铁的路子):

这样和大人就可以按省把任务大致划分为四个部分,责成四省的官员们分担这一个大工程,把他们应尽的的责任连成一个有序的链条,然后依次让他们执行伺候皇上的任务。

这样一来解决了行程过于丰富,和大人一个人安排不过来的问题,二来保证了各个步骤的灵活安排(后面的例子讲),三来哪一步出了问题还便于问责(甩锅,否则全是自己的错)。

好了,说了这么多,现在切入技术层面。

设计

Step1:

首先总结一下我们所研究的问题中的名词,来确定大概需要哪些类:

  1. 皇帝(乾隆)
  2. 行程的管理者(和中堂)
  3. 各省官员(具体干活的公仆们)

Step2:

再来确定各个类之间的关系:

  • 最容易看出来的是各省官员是同僚关系,他们都要接待乾隆,只是在皇上南巡的过程中出场顺序和做的具体接待行为不一样,比如:

    • 直隶总督会带乾隆去避暑山庄,
    • 山东巡抚会张罗着皇上祭拜孔庙,
    • 苏州织造让皇上游览园林,
    • 而杭州知州就带着皇上去西湖苏堤。
  • 这里告诉大家 OOD 中一个优化设计的小口诀:变化的抽接口,相同的建模版

所以我们在这里面对官员们不同的行为,最好把他们抽象成接口或者抽象类,这里我们采用官员(Official)
这个抽象类。

而和大人作为总管,他既要掌握皇帝的动向,又要辖制各省官员,所以在类的层面上和大人(PrimeMinister)这个类就得有指向皇帝(Emperor)和官员列表的引用。

下面上 UML 图。

UML 图

各省同僚:

而你和大人,作为乾隆面前的红人,得统筹安排皇帝的行程,既要挟持皇帝,又要掌管各省官员,让他们有序地执行任务:


责任链一般都至少有一个被处理的对象,作为参数传入各个步骤,这里的乾隆就是这个被处理(伺候)的对象。

代码

作为官员这个抽象类,我们考虑到实际情况,他要安排一个地方并陪同皇帝参观、游览,其实就是一句话:伺候皇上。

所以他有一个抽象方法 serve,接受皇帝(Emperor)这个对象

@Data
public abstract class Official {
    protected String title;

    protected abstract void serve(Emperor emperor);

    @Override
    public String toString() {
        return title;
    }
}

这里为了区别不同的官员,我们还给了官员(Official)类一个成员变量 title。

Official 下面有具体实现的类,代表各省官员,他们自己有自己具体的方式去服务吾皇,比如直隶总督,他是这么干的:

public class HebeiOfficial extends Official {

    public HebeiOfficial() {
        this.title = "直隶总督";
    }

    @Override
    protected void serve(Emperor emperor) {
        emperor.play(this, "避暑山庄");
    }
}

这里在 serve 里面完全让参数"皇帝"自己决定怎么玩,(顺便说句题外话,这种让参数这个"外来的和尚"念经的方式,在各种设计模式里很常见。如果把这里的 Emperor 换成 Comparator,相信很多小伙伴就感觉有点像策略模式了。而且"直隶总督"也可以在皇帝 play 之前或者之后分别做一些事情,这像不像用 JDK 的代理的时候中那个 InvocationHandler 对待 Method 的方式?或者 Spring 中对于 Aspect 的处理?另外在 Visitor 等设计模式中你也能看到这种写法的身影)

其他官员的写法类似,只是换个地方供皇帝游览而已,参见后面的输出结果,这里略。

而作为皇帝,乾隆只管着玩就好,当然了,你和中堂可以安排当地的官员陪同,所以
皇帝类只有一个 play 方法,这里用一个字符串简单表示去游览的地方。

为了防止乾隆南下期间有人在北京"另立新君"(执行 new Emperor()),这个"皇帝"对象的创建过程采用了单例模式,保证整个 JVM 里面就只有这么一个皇上,而且名字叫"乾隆":

public class Emperor {
    private static final Emperor INSTANCE = new Emperor("乾隆");
    private final String name;

    private Emperor(String name) {
        this.name = name;
    }

    public static Emperor getInstance() {
        return INSTANCE;
    }

    public void play(Official official, String place){
        System.out.println(official.getTitle() + " 安排 " + name + "皇帝游览了: " + place);
    }
}

而你,和珅和大人,只需要按各省顺序,合理安排好下面的官员,然后请出皇上并昭告天下:圣上下江南了,沿途各省小心伺候就好:

public class PrimeMinister {
    private static List<Official> list = new ArrayList<>();

    public static void main(String[] args) {
        // 下令沿途各省官员准备好
        list.add(new HebeiOfficial());
        list.add(new ShandongOfficial());
        list.add(new JiangsuOfficial());
        list.add(new ZhejiangOfficial());
        // 请出皇上
        Emperor emperor = Emperor.getInstance();
        // 昭告天下:万岁爷起驾下江南!沿途各省依次伺候圣上
        System.out.println("乾隆下江南!");
        start(list, emperor);
    }

    private static void start(List<Official> officials, Emperor emperor) {
        for (Official o : officials) {
            o.serve(emperor);
        }
    }
}

看看,你的任务是不是简明多了,只需要维护好这个沿途各省官员的花名册即可。

更重要的是,你不用亲自负责了,下面的人谁办事不力,就要谁的脑袋!

只要自己的这个"花名册"或者"行程表"没写错,咱的脑袋就算保住啦。

而且各个官员的任务也比较单一,他们自己也更不容易出错。下面是整个行程模拟的执行情况:

乾隆下江南!
直隶总督 安排 乾隆皇帝游览了: 避暑山庄
山东巡抚 安排 乾隆皇帝游览了: 曲阜孔庙
苏州织造 安排 乾隆皇帝游览了: 苏州园林
杭州知州 安排 乾隆皇帝游览了: 西湖苏堤

嗯,一切看上去似乎还不错,各省官员按照顺序,依次完成了任务,把万岁爷伺候的还不错,没有什么异常状况发生,总算松了口气。

但是,现在来了个突发情况:皇上突然要求,在路过山东的时候加一个环节——大明湖畔三日游!

为啥要特意去那里?咱也不敢问呐!只管准备就好。

幸好我们的行程又已经有了大致框架,赶紧查,大明湖那里归谁管,哦,济南知府,就是他了!

现在只需把他也加到"花名册":责令济南知府安排皇上在大明湖畔三天的行程,不得有误,否则拿你试问!下面是和大人这边要做的改动:

    ...以上略...
    list.add(new HeibeiOfficial());
    // 加入济南知府,让他干活,他知道在大明湖畔该怎么玩
    list.add(new JinanOfficial());
    list.add(new ShandongOfficial());
    list.add(new JiangsuOfficial());
    list.add(new ZhejiangOfficial());
    ...以下略...

而另一边济南知府这里,他也是属于官僚体制了(Official 的子类),所以也要极尽所能,让圣上在大明湖畔玩得开心:

public class JinanOfficial extends Official{
    public JinanOfficial() {
        title = "济南知府";
    }

    @Override
    protected void serve(Emperor emperor) {
        emperor.play(this, "大明湖畔");
    }
}

再次执行程序,模拟圣上的行程,结果输出如下:

乾隆下江南!
直隶总督 安排 乾隆皇帝游览了: 避暑山庄
济南知府 安排 乾隆皇帝游览了: 大明湖畔
山东巡抚 安排 乾隆皇帝游览了: 曲阜孔庙
苏州织造 安排 乾隆皇帝游览了: 苏州园林
杭州知州 安排 乾隆皇帝游览了: 西湖苏堤

嗯,这下总算又迎合了圣意,以后皇上再来什么其他的行程也不怕了(只要他不微服私访,微服私访您找纪晓岚去啊,单一责任原则,专门的类干专门的事儿不是?)。

只要找到当地具体的官员,一纸命令:你给我极尽所能招待皇上,具体怎么招待,你看着办,伺候不好万岁爷,我要你脑袋!

当然了,皇帝也可能临时删掉南巡中的某个环节,我们直接把它从行程列表中删除就好,而且什么时候想再重新加进来还可以随时添加,做到了可以"灵活插拔",把代码的改动减到了最小,有新的业务逻辑加进来的时候,只是做添加,这样既不容易出错,也确保了代码的弹性扩展,而且当前责任链中的步骤,如果没有状态相关的信息的话,也可以被组装到其他的责任链中。

而且如果是我们的真实项目,我们甚至可以把工作步骤的列表配置在 Spring Boot 的配置文件里,开启流程的这个类,只要读取配置,然后把各个步骤依次执行。

这样如果有修改只要改动配置文件即可,在 Java 代码里无需任何改动。

总结与拓展

以上其实只是一个责任链模式最简单的应用,它是一个有序列表里面装了各个任务的步骤,然后依次运行到最后。

我们可以把它写在自己的程序里,也可以把它抽象出来做成产品,让其他人自由扩展与配置,尽量减少重复制造轮子。

有很多工作流引擎便是这样,比如 ActivitiNetflixConductor 等。不光这些,就连你
最常用的 SpringMVC 甚至是 Tomcat 都用到了责任链模式,只不过他们的责任链是双向的,分别处理请求和响应,而且他们的处理顺序是刚好相反的,本质上是用类似递归的方法正序倒序各便历了一次(Filter 或 Interceptor 的)数组。

另外在一些持续集成和持续部署的框架中,如 Jenkins,会有管道(Pipeline)的概念,当你在做出 git push 提交代码之后,会触发整个流程开始一步步地运作:拉取代码(Checkout code)、构建(Build)、测试(Test)等,直到部署(Deploy)完成并运行脚本关闭旧版本的服务并启动最新部署的服务。这个"流水线"(Pipeline)其实也是一个可以让你用代码脚本来配置的责任链。

没有责任链模式的应用,你甚至都无法运行任何一个 Java 程序。因为类加载一般遵循"双亲委派"机制,实际上是用类似递归的方法正序和倒序各便历了一次 Classloader 类所构成的链表(题外话,想把一个链表翻转过来,可以参见齐姐之前写过的:),只不过其中的逻辑比较复杂,而且还应用了"模板方法"这一设计模式。由于本文只是做一个责任链模式的简单入门,这些不做过多展开了。

综上,充分理解和应用责任链设计模式,对我们的日常工作和阅读源码都很有帮助,能让我们有效提高代码的扩展性和可读性,希望对你也有所帮助。


好了,以上就是本文的全部内容,如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 10 收藏 5 评论 2

小齐本齐 发布了文章 · 11月16日

看了齐姐这篇文章,再也不怕面试问树了

微信搜索🔍「码农田小齐」,关注这个在纽约的程序媛,回复「01-05」可以获取计算机精选书籍、个人刷题笔记、大厂面经、面试资料等资源,么么哒~

在写完了所有线性数据结构之后,今天开启非线性数据结构系列。

我们今天先来看,什么是“树”。

树是由顶点和边组成的且不存在环的数据结构。作为一个应用非常广的数据结构,不仅在工作中常用,在面试中也非常常考。

一是因为树的结构天然决定了它和递归联系紧密,很多树相关的算法题都非常适合用递归来解;

二是因为它的难度介于链表和图之间,非常适合在 45 分钟的面试里进行考察,所以一场面试中遇到两三轮问树都是再正常不过的了。

本文先来讲树的基础内容,分为以下小节,每个小节开头都会有思维导图和对应的 Leetcode 算法题哟~

  1. 简介
  2. 金融里的二叉树
  3. 树的所有概念
    a. 树的三大特点
    b. 树的五大品种
    c. 高度和深度
  4. 看树的角度
    a. 三种 DFS 遍历方式
    b. 两种 BFS 遍历方式
    c. 四种视图

鉴于树相关的内容太多,而且又是面试重点内容,之后会有文章再专门来讲树有关的解题思路以及最常用的二叉搜索树,大家敬请期待~

简介

其实数据结构里的“树”和我们现实世界里的树挺像的,只不过倒过来了嘛,根朝上。

比如:

在这片森林里,最常用的还是「二叉树」。

二叉树,是由很多个 TreeNode 构成的这种树形的数据结构,

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
}

就像链表中的 ListNode

二叉树并不一定非得是“二叉”的,而是说每个节点最多有两个孩子,叫 leftright,但也可以没有。

当每个节点都只有一个孩子的时候,就退化成了链表。

所以链表就是一棵特殊的树,而树是一个特殊的图。

金融里的二叉树

大家知道我是金融背景的,所以我最开始了解二叉树是在金融工程课程中给衍生品定价,这里也简单梳理下,不感兴趣的小伙伴可以跳过这一段。

在金融工程里,二叉树是用来在风险中性世界里给期权定价使用的模型。

比如这是一个股价二叉树,其实就是我们把二叉树放倒了看嘛。

有些小伙伴会发现,这里的节点好像少了很多,没错,因为我们让股价每次上涨和下跌的幅度保持不变,所以到第 n 层最多有 n 个节点,而不会像普通的二叉树一样按照等比序列增长。

上图是两期的二叉树,那么最简单的一期的二叉树定价模型表示为:

我们假设当前股票的价格为 S,那我们想知道未来某个时刻比如 t 时刻的价格,股价有可能上涨也有可能下跌,还可能不变呢。

在该模型里我们就抽象成两种可能性,一种是上涨,一种是下跌,所以可以用二叉树来表示。

假设股票价格会有 p 的概率上涨至 uS,
1-p 的概率下跌至 dS.

这里的 p 并不是在真实世界里股票上涨的概率,而是一个在风险中性世界里的上涨概率,所以

股票现在的价格就是未来某时刻的无风险收益的折现

即:

$$S = e^{-rt}[pS_u + (1-p) S_d] $$

这就是最简单的二叉树定价模型。

那我们言归正传。

树的所有概念

1. 三大特点

树的三大特点是:

  1. 如果把树看成一个无向图,那么它是一个连通图connected graph.
  2. 树是一个无环图
  3. 树的节点个数和边的个数之间的关系是固定的。如果树上有 nnode,那么它有 n-1 条边。因为除了根节点,其他的节点都会有一条边指向它。

2. 树的品种

2.1 平衡二叉树Balanced Binary Tree

  • 定义:对于这棵树里的每个节点,它的左子树和右子树的高度差不大于 1。

这里要注意,是对于每个节点,而不只是对于根结点。

比如左边这棵树就不是平衡二叉树,右边的才是。

那么大名鼎鼎的 AVL-Tree 就是平衡二叉树,准确说是自平衡二叉查找树。

那什么是二叉查找树呢?

2.2 二叉查找树Binary Search Tree

  • 定义:对于这棵树里的每个节点,

    • 它左子树里的每个节点的值都小于它的值;
    • 它右子树里的每个节点的值都大于它的值。

对二叉查找树,最重要的性质就是:

在做中序遍历时,这个序列是一个升序序列。

当你在做二叉查找树的算法题没有思路时,可以想想这个性质,很多题目都会迎刃而解。

2.3 完全二叉树Complete Binary Tree

  • 定义:除了最后一层,其他层都是满的,那么最后一层的节点要靠左排列且中间不允许有气泡。

比如左边不是完全二叉树,右边的是。

比如堆就是一个完全二叉树,还不了解堆的基本操作的,公众号内回复「堆」获取文章复习哟~

那么完全二叉树的最大的好处就是因为它排列紧密没有气泡,所以可以用数组来存储,这样就大大节省了内存空间。

2.4 完美二叉树Perfect Binary Tree

  • 定义:所有层的所有节点都必须是满的。

完美二叉树比完全二叉树的定义更加严格,包括最后一层,每一层的节点都要是满的,毕竟是追求完美的嘛。

所以我们如果知道了层数,就知道了它有多少个节点,也就是一个等比数列求和。

2.5 完满二叉树Full Tree

  • 定义:对于这棵树的每个节点而言,要么有 0 个孩子,要么有 2 个孩子。

大家不要轻视这些概念哦,很多算法题都会直接考察,在本节的思维导图里也附带了 Leetcode 对应的题目,电面时很喜欢考哦~

3. 高度和深度

树的高度 height 和深度 depth 是两个非常重要的概念,比如 Leetcode 104 和 111 就是专门求树的高度的。

而这两个概念是相反方向的,大体上呢,

  • 高度是从当前节点到叶子 🍃 节点的;
  • 深度是从当前节点到根 🌲 节点的。

高度Height

  • 定义:从该节点,到以该节点为根节点的这棵树的最远的叶子结点的最长距离。

核心是,从该节点到最远叶子节点,有几条边。

这个概念在分析时空复杂度时非常常用,比如在树上做一个递归复杂度是 O(height)。

为什么呢?

因为这个距离决定了在 call stack 上有多少层。

深度Depth

  • 定义:从这个节点到根节点的距离。

这个概念用的比较少,是和高度方向相反的概念。

看树的角度

俗话说,横看成岭侧成峰,这句话用在这里太合适不过了。

对于树的几种遍历方式想必大家都不陌生,这就是我所说的「岭」;

而还有一种面试常考题是问 left/right/vertical/border view,也就是求树的左视图、右视图、俯视图、border view 这我没找到中文翻译。。这就是我所说的「峰」。

先来总图:

最基本的三种遍历就是

  • 前序 pre order
  • 中序 in order
  • 后序 post order

其实这三种遍历方式本质都是一样的,只是输出/打印节点的顺序不同罢了。

来看伪代码吧:

public void traverse(TreeNode node) {
  if (root == null) {
    return;
  }
  //preOrder
  print(root.value);

  traverse(root.left); //真正的遍历

  //inOrder
  print(root.value);

  traverse(root.right); //真正的遍历

  //postOrder
  print(root.value);
}

真正的遍历就这两句话,无论是那种遍历顺序都是不变的,变的只是打印的顺序罢了。

这三种遍历都是深度优先遍历 DFS,而层序遍历是广度优先遍历 BFS

DFSBFS 都是图的基本遍历方式,我之后也会专门写一篇。

那我们来看层序遍历 level order traversal

输出 5 7 3 1 4.

参考 Leetcode 102 题。

也就是每一层按照从左到右的顺序遍历。

那么还有一种 Zigzag 的遍历方式,就是一行从左到右,下一行从右到左这样子。

输出的就是 5 3 7 1 4.

参考 Leetcode 103 题。

left/right/vertical/border view,也就是求树的左视图、右视图、俯视图,是非常爱考的一类题,它们是什么意思呢?

比如对于这棵树,

左视图left view

  • 就是从左边看的每层的第一个节点。
  • [5, 7, 9]

右视图right view

  • 就是从右边看的每层的第一个节点。
  • [5, 3, 8]

这两个应该比较简单,在层序遍历的时候保留我们需要的值就可以了。

当然还有其他方法,比如前序遍历可以做左视图,但不是那么的直观,因为你还要判断这个元素是否是当前层的第一个。大家有想法的可以在群里交流哟。(提示:可以再加一个变量

俯视图

这个视图比前两个稍微难一点,在北美面试中是很爱考的。

首先这个图中有一个变量叫 column,根节点为 0,左孩子 - 1,右孩子 + 1。

俯视图指的是,从上往下看这棵树,把 column 相同的这些节点放在一个 list 里,从上往下放,然后按照 column 从小到大的顺序排出来。

所以对于这棵树,它的俯视图是:

[[7], [5, 9], [3], [8]]

这题就作为本文的思考题啦,不是很难,大家可以在评论区或者群里交流~

Border View

在讲完前三种视图之后,这个 border view 想必大家都能猜出来意思了。

就是求这棵树的“轮廓”。

比如还是这棵树,它的 border view 就是:

5, 7, 9, 8, 3

这题的大体思路不难,但是细节很多,而且很多条件可能就像我给的这样并没有定义清楚,所以你需要和面试官不断的 clarify 很多细节。

普通的思路可以用

左视图 + 叶子结点 + 反着的右视图

来做,表面上来看需要做三遍遍历,但是其实一遍遍历就够了,因为我刚才说过,DFS 遍历时,哪种遍历方式都是一样的,只是在不同时间打印不同节点罢了。


好了,以上就是本文的全部内容,如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 4 收藏 3 评论 1

小齐本齐 发布了文章 · 11月13日

Facebook 的神仙组长什么样?

<span style="display:block;text-align:center;">这里是《齐姐聊大厂》系列的第 14 篇

<span style="display:block;text-align:center;">每周五早上 8 点,与你唠唠大厂的那些事

号外号外!前 12 篇已出 PDF:公粽号后台回复「大厂」即可获得!

小齐说:

这篇文章是来自阿米粥的分享,他今年暑假在 Facebook 实习,跟大家完整的分享从申请面试到实习结束的整个过程,让我们一起来感受下吧~

时间线

我是 2019 年 9 月底找朋友内推的 facebook software engineer summer internship 岗位,fb 的 hr 工作效率很高,3 个工作日之内就有了邮件回复,说在看简历。

10 月初的时候某个周四收到短信,说下周三有面试官来学校宣讲会,问我有没有兴趣直接参加面试,白板作答。

第一轮通过后,第二轮是电面。之后收到邮件约了 10 月 30 日早上的第三次加面(也是电面),在当天下午就拿到了 offer(再次感叹工作效率)。

实习

我是 2020 年 6 月开始的 summer internship,做的是 ios 类的开发工作。

因为今年是在家工作,也有了不一样的工作体验,开始是一些设置,有很详细教学,跟着一步一步来很快就能上路。

我的 mentor 是一个国人小哥,我们早在今年 4 月份左右就有了邮件联系,主要是问他有没有什么推荐的书籍可以提前阅读熟悉工作语言(我是第一次做 ios,没有经验,略紧张)。

没想到小哥长篇大论写了 500 字的小作文回复我,大概意思就是他也是实习生转正的,可以理解我的心情,但是不用太过紧张,工作起来啥都会了。但是也推荐了两本基础的书,让我有时间可以学习学习(事实证明真的很有用,因为读了这两本书我看 code 非常熟悉,不用去查询 syntax 这些内容,直接就能理解到)。

小齐问:哪些书呢?

"Objective-C Programming: The Big Nerd Ranch Guide" pretty good for beginners, and "Effective Objective-C 2.0" for more advanced topics and tricks.

除此之外,我也自己找了一些 tutorial,例如 Stanford 的 ios 课来学习,这些前期的准备工作真的为我后面无比顺利的实习打下了坚实的基础。

在收到分组信息知道自己的 mentor 的邮箱后,去打个招呼,简短介绍一下自己,了解一下这个组是干嘛的,开发 app 的话是开发哪个功能,提前熟悉一下准没错;如果不熟悉工作语言,也可以像我一样问问 mentor 有没有推荐的学习材料。

6 月份开始实习后,我发现自己进到了一个神仙组。

mentor 在第一周每天都和我视频电话,手把手带我熟悉各种工具,发消息必秒回,无法文字解释清楚的直接共享屏幕教我,并且跟我说,你不要觉得现在问题多不好意思或者怎么样,也不要自己钻一样东西钻几个小时不问,不仅浪费时间我也没办法知道你的问题和进度。

因为前期的问题都能得到很快的解决,我在第一周就做完了第二周要做的活。

此外,每周的组会上,老板也会问我对工作有什么想法和意见,进度怎么样了,觉得难了简单了等等。

我的两个 mentor 中有一个是工作狂,就是随时随地晚上 11 点找他他都在的那种,所以我写的东西基本是全天候都有人 review,效率极高。

组内的人都非常友好,我的 mentor 帮我和 design 的人拉了一个群,我有一些 design 方面要求不清楚的都能直接和 designer 沟通。

实习期中 review 的时候我已经把整个 project 做完了,manager 知道后也很开心,专门开了一个会问我你对什么方面感兴趣,接下来的五周你就可以做你感兴趣的活。

为了拿 return offer 其实我有点功利,我就说现在组里有什么比较紧急的活要做吗,我做这些就好了。

manager 就派了一些组内 priority 较高的活给我,所以后半段的时间我基本都在帮组里解决一些 priority 较高,且我能 handle 的事情。

hr 组织的活动也挺有意思的,每周都有和本学校的 intern 的 tea time。大家互相了解一下,增进校友感情。每周我们有组内 intern happy hour(intern 和 mentor 一起),每两周有 team happy hour。气氛轻松活跃,每周的 happy hour 就是最好的放松时间。

在 fb 实习的这段经历让我觉得我时刻都是被人关注着的。mentor 随 call 随到,manager 每周都来过问感受,hr 也问过三次情况。感觉公司很注重实习生的体验,也想要对自己的不足有所改进。

最后离职的时候组里每个 member 都发了一段话给我,非常感动,希望今后也有机会继续合作。

建议

最后说一些自己的建议和感想吧:

  • 前期不懂就问,不要自己想两三个小时浪费时间。
  • 中后期自己多查文件,找网上的例子或者类似的代码,尝试自己解决实在不行再问,不要浪费 mentor 时间。
    重复的问题最好不要犯第二遍。一些比较复杂的 setting 或者操作要有个记录,避免下次又去问 mentor 耽搁大家的时间,他也可能会怀疑你的学习能力。我也知道一些 intern 说自己的 mentor 不负责或者不好,如果觉得自己不被平等待遇了,一定要尽早反馈给 manager 或 intern director,尽早让他们知道你的处境,不然后期根本没办法翻盘。
  • 中期 review 如果是 no trend to offer,也不要自暴自弃,大批的人后期逆风翻盘的。主要是要看 mentor 和 peer mentor 给的意见,有哪些要改进的,他们都会就 axes 说的很清楚。
  • 要善于和勇于 mentor 沟通,不要害怕。可以问 mentor,你觉得我现在哪里还能改进的,大部分 mentor 都是乐于解答的。这样自己也能尽快知道自己的不足,加以改进。

总的来说,在 fb 的实习经历体验非常好,也顺利拿到了 return offer,明年 2 月份就入职了。我知道今年工作不好找,希望大家不要气馁,祝大家都能拿到 offer!

查看原文

赞 0 收藏 0 评论 1

小齐本齐 发布了文章 · 11月12日

哈希冲突详解

微信搜索🔍「码农田小齐」,关注这个在纽约的程序媛,回复「01-05」可以获取计算机精选书籍、个人刷题笔记、大厂面经、面试资料等资源,么么哒~

哈希冲突详解

一般来说哈希冲突有两大类解决方式

  1. Separate chaining
  2. Open addressing

Java 中采用的是第一种 Separate chaining,即在发生碰撞的那个桶后面再加一条“链”来存储,那么这个“链”使用的具体是什么数据结构,不同的版本稍有不同:

在 JDK1.6 和 1.7 中,是用链表存储的,这样如果碰撞很多的话,就变成了在链表上的查找,worst case 就是 O(n);

在 JDK 1.8 进行了优化,当链表长度较大时(超过 8),会采用红黑树来存储,这样大大提高了查找效率。

(话说,这个还真的喜欢考,已经在多次面试中被问过了,还有面试官问为什么是超过“8”才用红黑树🤔)

第二种方法 open addressing 也是非常重要的思想,因为在真实的分布式系统里,有很多地方会用到 hash 的思想但又不适合用 seprate chaining

这种方法是顺序查找,如果这个桶里已经被占了,那就按照“某种方式”继续找下一个没有被占的桶,直到找到第一个空的。

如图所示,John Smith 和 Sandra Dee 发生了哈希冲突,都被计算到 152 号桶,于是 Sandra 就去了下一个空位 - 153 号桶,当然也会对之后的 key 发生影响:Ted Baker 计算结果本应是放在 153 号的,但鉴于已经被 Sandra 占了,就只能再去下一个空位了,所以到了 154 号。

这种方式叫做 Linear probing 线性探查,就像上图所示,一个个的顺着找下一个空位。当然还有其他的方式,比如去找平方数,或者 Double hashing.


如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 2 收藏 1 评论 0

小齐本齐 关注了专栏 · 11月12日

技术风暴

关注公众号「关山不难越」学习更多前端进阶知识。 Classical is something not fade,but grow more precious with time pass by,so is dream id dream.

关注 2392

小齐本齐 发布了文章 · 11月11日

为什么重写 equals() 方法,一定要重写 hashCode() 呢?| HashMap

微信搜索🔍「码农田小齐」,关注这个在纽约的程序媛,回复「01-05」可以获取计算机精选书籍、个人刷题笔记、大厂面经、面试资料等资源,么么哒~

首先我们有一个假设:任何两个 object 的 hashCode 都是不同的。

那么在这个条件下,有两个 object 是相等的,那如果不重写 hashCode(),算出来的哈希值都不一样,就会去到不同的 buckets 了,就迷失在茫茫人海中了,再也无法相认,就和 equals() 条件矛盾了,证毕。

撒花~~🎉🎉🎉

接下来我们再对这两个方法一探究竟:

其实 hashCode() 和 equals() 方法都是在 Object class 这个老祖宗里定义的,Object 是所有 Java 中的 class 的鼻祖,默认都是有的,甩不掉的。

那既然是白给的,我们先来看看大礼包里有什么,谷歌 Object 的 Oracle 文档:

所以这些方法都是可以直接拿来用的呢~

回到 hashCode() 和 equals(),那么如果这个新的 class 里没有重写 (override) 这两个方法,就是默认继承 Object class 里的定义了。

那我们点进去来看看 equals() 是怎么定义的:

记笔记:

equals() 方法就是比较这两个 references 是否指向了同一个 object.

嗯???你在逗我吗??那岂不是和 == 一样了??

补充:
我们常用的比较大小的符号之 ==
如果是 primitive type,那么 == 就是比较数值的大小;
如果是 reference type,那么就比较的是这两个 reference 是否指向了同一个 object。

再补充:
Java 的数据类型可以分为两种:
Primitive type 有且仅有8种:byte, short, int, long, float, double, char, boolean.
其他都是 Reference type.
所以虽然 Java 声称 “Everything is object”,但是还是有非 object 数据类型的存在的。

我不信,我要去源码里看看它是怎么实现的。

哈,还真是的,绕了这么半天,equals() 就是用 == 来实现的!

那为什么还弄出来这么个方法呢?

答:为了让你 override~

比如一般来说我们比较字符串就是想比较这两个字符串的内容的,那么:

str1 = “tianxiaoqi”;
str2 =  new String(“tianxiaoqi”);

str1 == str2; // return false
str1.equals(str2); // return true 

因为 String 里是重写了 equals() 方法的:

老祖宗留给你就是让你自己用的,如果你不用,那人家也提供了默认的方法,也是够意思了。

好了,我们再去看 hashCode() 的介绍:

那至于 hashCode() 返回的究竟是什么,和本文关联不太大,有兴趣的同学可以看参考这篇文章参考文章"),结论就是:

返回的并不一定是对象的(虚拟)内存地址,具体取决于运行时库和JVM的具体实现。

但无论是怎么实现的,都需要遵循文档上的约定,也就是对不同的 object 会返回唯一的哈希值

所以说,

hashCode() 决定了 key 放在这个桶里的编号,也就是在数组里的 index;

equals() 是用来比较两个 object 是否相同的。

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 2 收藏 1 评论 0

认证与成就

  • 获得 402 次点赞
  • 获得 4 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 4 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 4月7日
个人主页被 11.1k 人浏览