Inte Media SDK 内存优化（转）
Inte Media SDK 内存优化（转）
编辑日期： 字体：
Media SDK 是一个软件开发库，包含解码、视频处理和编码三大模块。利用 Intel 平台的硬件加速能力， Media SDK 为低端用户提供了优秀的高清视频质量，极大的降低了播放高清视频的硬件门槛。此外，强大的视频 APIs 也减轻了程序开发者的工作负担，使他们能够集中精力去处理程序的逻辑模块，而不必关心于 Media SDK 内部的复杂编解码逻辑及其如何提高效率。
本篇文章将着重讲述如何利用 Media SDK 提高程序的效率，面对的读者主要是视音频程序开发人员。
本文以下内容为：
– 初始化设置之优化
– 内存选择之优化
– 多线程之优化
– 异步方式之优化
初始化设置之优化
在讨论优化之前，首先要了解一下 Media SDK 是如何初始化编解码器的。
1. 创建和初始化一个编解码 Session。Media SDK 提供了 mfxStatus MFXInit(mfxIMPL impl,mfxVersion *ver, mfxSession *session)函数来完成这个创建和初始化工作。
2. 使 用 已 创 建 的 Session 来 创 建 它 的 解 码 器 。 Media SDK 提 供 了 mfxStatus MFXVideoDECODE_Init(mfxSession session, mfxVideoParam *par)来完成解码器的创建和初始化工作。
3. 使 用 已 创 建 的 Session 来 创 建 它 的 编 码 器 。 Media SDK 提 供 了 mfxStatus MFXVideoENCODE_Init(mfxSession session, mfxVideoParam *par)来完成编码器的创建和初始化工作。
在创建和初始化编解码 Session 时，我们需要制定编解码的实现方式：硬件方式还是软件方式。最简单的方法是强制使用硬件方式。这会带来一个问题，在非 Intel 显卡支持的平台，应用程序将无法正常工作。当然，如果强制使用软件方式，虽然应用程序能够工作于其他平台，但是在 Intel 显卡平台，硬件加速特性将荡然无存！虽然应用程序可以外加代码检测平台硬件来决定如何选择，但是程序的复杂度和效率将受到影响。Media SDK 内部提供了自动选择功能，它会根据当前运行系统来选择何种方式。这样就能够兼顾不同平台及其性能。
在 MFXInit 函数中，枚举类型 mfxIMPL 定义 AUTO 功能：
typedef enum {
MFX_IMPL_AUTO=0, /* Auto Selection/In or Not Supported/Out */
MFX_IMPL_SOFTWARE, /* Pure Software Implementation */
MFX_IMPL_HARDWARE, /* Hardware Accelerated Implementation */
MFX_IMPL_UNSUPPORTED=0 /* One of the MFXQueryIMPL returns */
} mfxIMPL;
typedef enum {MFX_IMPL_AUTO=0, /* Auto Selection/In or Not Supported/Out */MFX_IMPL_SOFTWARE, /* Pure Software Implementation */MFX_IMPL_HARDWARE, /* Hardware Accelerated Implementation */MFX_IMPL_UNSUPPORTED=0 /* One of the MFXQueryIMPL returns */} mfxIMPL;
相应的简单实用方式如下：
mfxVersion version = {MFX_VERSION_MINOR, MFX_VERSION_MAJOR};
sts = m_mfxSession.Init(MFX_IMPL_AUTO, &version);
mfxVersion version = {MFX_VERSION_MINOR, MFX_VERSION_MAJOR};sts = m_mfxSession.Init(MFX_IMPL_AUTO, &version);
通过 MFX_IMPL_AUTO 的设置，问题迎刃而解。
那么如何获知当前的编解码实用方法呢？Media SDK 已经考虑到了这种需求，它提供了mfxStatus MFXQueryIMPL(mfxSession session, mfxIMPL *impl)来查询当前采用的方法。
此外，在优化编码器初始化时，程序必须注意 mfxInfoMFX 结构中 TargetUsage 变量的选择，它的定义如下：
typedef struct {
mfxU32 reserved[8];
mfxFrameInfo FrameI
mfxU32 CodecId;
mfxU16 CodecP
mfxU16 CodecL
mfxU16 NumT
/* ENCODE */
mfxU16 TargetU
mfxU16 GopPicS
mfxU16 GopRefD
mfxU16 GopOptF
mfxU16 IdrI
mfxU16 RateControlM
mfxU16 InitialDelayInKB;
mfxU16 BufferSizeInKB;
mfxU16 TargetK
mfxU16 MaxK
mfxU16 NumS
mfxU16 NumRefF
mfxU16 EncodedO
struct { /* DECODE */
mfxU16 DecodedO
mfxU16 reserved2[12];
} mfxInfoMFX;
/* TargetUsages: 1~7; */
MFX_TARGETUSAGE_UNKNOWN =0,
MFX_TARGETUSAGE_BEST_QUALITY =1,
MFX_TARGETUSAGE_BALANCED =4,
MFX_TARGETUSAGE_BEST_SPEED =7
12345678910111213141516171819202122232425262728293031323334353637
typedef struct {mfxU32 reserved[8];mfxFrameInfo FrameInfo;mfxU32 CodecId;mfxU16 CodecProfile;mfxU16 CodecLevel;mfxU16 NumThread;union {/* ENCODE */struct {mfxU16 TargetUsage;mfxU16 GopPicSize;mfxU16 GopRefDist;mfxU16 GopOptFlag;mfxU16 IdrInterval;mfxU16 RateControlMethod;mfxU16 InitialDelayInKB;mfxU16 BufferSizeInKB;mfxU16 TargetKbps;mfxU16 MaxKbps;mfxU16 NumSlice;mfxU16 NumRefFrame;mfxU16 EncodedOrder;};struct { /* DECODE */mfxU16 DecodedOrder;mfxU16 reserved2[12];};};} mfxInfoMFX;/* TargetUsages: 1~7; */enum {MFX_TARGETUSAGE_UNKNOWN =0,MFX_TARGETUSAGE_BEST_QUALITY =1,MFX_TARGETUSAGE_BALANCED =4,MFX_TARGETUSAGE_BEST_SPEED =7};
TargetUsage 值的选择决定了编码的性能和图像质量，它的值从 0~7，值越高效率越好，但图像质量会有所下降。最佳值应该和用户选择需求挂钩，原则上是略比最小用户需求高 1 级。
本节小结：
1. 初始化 Session 时，要使用 MFX_IMPL_AUTO。它有利于跨越硬件平台，并提高编解码效率。
2. TargetUsage 的选择应该和用户需求相结合。为了提高性能，选择略高于用户最小需求的值为佳。
内存选择之优化
Media SDK 使用内存缓冲来输入/输出视频数据，内存缓冲的不同种类将会直接影响编解码的效率。内存缓冲可以是一块在系统内存中的连续块（通过 malloc 或者 new 来分配），也可以是显卡内存的连续块（通过 Microsoft Direct3D9 Surface 函数来分配）。那么内存缓冲的
种类由谁来决定呢？本节就是以此为基础，讨论在不同情况下程序如何选择内存缓冲种类的问题。
在讨论内存缓冲对编解码影响之前，先讨论下面三种情况下的内存数据传送问题。
– 系统内存间数据如何传送？
对于程序员而言，这个是最为简单的日常编程事项。一般的使用方式是 memcpy，在一些数据较大情况下（超过 L3 的 cache 尺寸时候，用 movntqa 等指令）。不管何种方式，都是CPU-BASED 的代码，在 SIMD 下效率很高。
– 显存间数据是如何传送的？
它类似于系统内存之间的数据传送，并且显存的带宽和速率都很高，传送速度更快。
– 显存和系统内存间数据是如何传送的？
通过 DMA 方式传送内存数据，速度依赖于 DMA 的带宽和速率（普通 DMA 的传送速率在33.3MB/s，而 Ultra DMA 最高也不过 100MB/s）。相比与上述两种情况，它的传送速度明显慢。
从上面的三种情况可以看出，程序一定要尽量避免出现系统内存和显存之间的数据传送，那么 Media SDK 在什么配置下会出现此类尴尬状态呢？
初始化设置之优化小节中，程序通过 MFX_IMPL_AUTO 参数根据当前平台来自动选择硬件或软件编解码，并能通过 mfxStatus MFXQueryIMPL(mfxSession session, mfxIMPL *impl)函数来获取当前平台的编解码方式，在此将获取的编码方式分别讨论。
a）使用硬件编解码方式
硬件编解码方式主要是通过显卡的硬件加速达到高效编解码的作用，也就是说它的核心是显卡。如果我们使用系统内存为其提供缓存，会出现什么情况呢？显然，在数据输出/输出时，程序必将会有显存和系统内存之间的数据传送作用，效能将受到严重影响。在此情况下，程序的最好选择就是显存，否则必将受到性能惩罚！
b）使用软件编解码方式
很显然，软件编解码的核心是 CPU。如果我们使用显存作为其缓冲，那么必将导致显存和系统内存之间的数据交互，也就会导致速度低下的程序出现，故此，系统内存是它的不二选择！
本节小结：
Media SDK 中内存类型的选择分两步走：
1. 使用 MFXQueryIMPL 函数来查询当前的编解码方式。
2. 根据编解码方式（MFX_IMPL_SOFTWARE 为软件；MFX_IMPL_HARDWARE 为硬件）来决定内存选用类型。为了便于日后方便查询，笔者建立了一个小表格，如表 1 所示，以供参考。
此外，笔者对 Media SDK 的两种不同内存类型在解码器下做了一个简单的比较。在软件解码方式下，显存选取要比内存选取慢了近 1 倍，这个是相当可观的数字！切忌，正确选取内存是高效程序的基本点！
多线程之优化
初始化设置之优化小节和内存选择之优化小节中，已经对 Media SDK 的两个重要配置部分进行了分析和总结。本节，我们将着重讨论如何使用多线程技术提高视频 Converter 的效能（一种视频的常用应用）。
在运用 Media SDK 进行格式转换时，一般要涉及三大模块，他们是 Decoder，VPP 和 Encoder，数据输入输出如图 1 所示。
从图 1 可以看出，每经过一个模块，都要对数据进行同步操作。在此期间，其他两个模块是处于空闲状态，是一个典型的串行处理过程。对于英特尔的多核技术，它的多核利用率是最低的，相应的效率也较差。
那么如何对现有流程进行多线程化呢？
本节提供了一种最简单的方法，即对每个模块线程化。请参考图 2 所示。
图 2 将 Decoder，VPP 和 Encoder 三个模块分别线程化，在彼此之间以队列（queue）为数据交换。
简单的工作模式如下：
– 若队列为空，后级模块等待数据。
– 若队列被填充，前级模块通知后级模块。
– 若无输入数据，前级模块通知后级模块结束工作，后自行了断。
虽然这种线程化的工作增加的程序的复杂性，但是对于赢得的性能而言是值得的。在理想状态下，我们看到三个模块的并行工作，转化时间的长短取决于最为耗时模块。
本节小结：
1. Media SDK 仅仅提供硬件加速能力，线程化工作展开于具体应用。
2. 三个模块线程化是一种常用的实现，但是如何充分利用英特尔的多核技术，应该建立在具体分析的基础之上。英特尔提供了丰富的性能检测和优化工具，他们能够帮助程序员找出关键问题所在。
3. VPP 模块是可选的，如果应用没有采用，就将 Decoder 后的队列直接连接到 Encoder 之前。
异步方式之优化
多线程之优化小节中已经讲述了如何使用多线程提高编解码的效能问题。因为增加了队列（Queue）的创建和维护等附加工作，使程序的复杂性有所增加，那么还有没有其他优化方法呢？本节主要从异步角度出发，讨论如何采用合适的异步方法来提高编解码器的效能问题。
在多线程方案中，我们使用队列（Queue）的同步机制来保证三个模块的协同工作，如图 3所示。
从图 3 中，有两个基本的开销点：
– 需要 3 次同步帧（SyncFrame）来完成一次编解码动作。
– 模块间的 2 个共享 Queue 都需要做同步操作。
这两个开销点对于多线程效率和竞争是不利的，那么有什么方法可以剔除或减小这种开销呢？
Media SDK 提供了异步机制，它提供了三个函数支持相应的三个模块：
– MFXVideoDECODE_DecodeFrameAsync
– MFXVideoVPP_RunFrameVPPAsync
– MFXVideoENCODE_EncodeFrameAsync
模块异步工作原理如图 4 所示。
相比于多线程模式，它有几个优点：
– 只需要一次帧同步，而其他两次的异步操作基本上不耗时间，节省了时间。
– 不需要队列的同步操作，提高了效率。
– 不需要多线程，一个线程搞定三个模块，实现复杂度低。
本节小结：
1. 异步模式对于硬件编解码比较适合。它的效能高，软件复杂度低。在软件编解码中，它的效能和简单串行模式无太多优势，所以可考虑采用多线程模式来实现。
2. 多线程模式和异步模式仅仅是提高效率的两种方法，它们之间没有冲突，应用可以根据自身的需求灵活采用，也可以混合运用，提高效率。
虽然使用 Media SDK 提供的 APIs 非常的方便，但是它也有一定的使用技术。正确的使用这些 APIs 能够极大的提高程序的运行效率、移植性和可维护性。本文着重讲述了四个重要的 Media SDK 编程技术，通过分析和揭露 Media SDK 的工作机制，能够让程序员充分认识到Media SDK 的内在工作方式，为视音频软件开发的性能提高起到积极作用。
本文固定链接:
转载请注明:
作者：Jianchihu
管理员——低调做事，低调做人
您可能还会对这些文章感兴趣！2014华科某大牛的找工作总结
2014华科某大牛的找工作总结
编辑日期： 字体：
其实我的求职过程在十一之前就已经结束了，总体讲比较顺利。参加面试的几家公司基本都拿到了offer，分别是阿里巴巴、美团网、创新工场涂鸦移动以及华为。当时也参加了其他公司的面试，比如人人，一面过后收到了二面通知，拒了。创新工场豌豆荚一面结束后等消息。十一过后的公司基本都是酱油而过。去哪儿面试拒了。腾讯一面后收到了二面的通知，也拒了。主要是因为自己已经拿到了理想公司的offer。看来人还是需要一点压力，这样才能发挥出自己的潜能。也本着攒RP的原则吧，感觉没必要刷那么多offer，而且我也知道自己的水平，对阿里的offer已经很满意了。剩下的时间还不如先预习一下入职要用到的东西。其实好早就想着写总结的，一直拖到现在，我想要是我再不写总结，估计很多东西就记不起来了。
一、自我介绍-往事不堪回首
首先自我介绍，某985院校计算机学院普通硕士。无ACM、挑战杯或者是各种编程大赛获奖经历，无牛逼哄哄的项目经历，无名企实习经历。总之一句话，一个再普通不过的CS硕士。本科期间成绩平平，课外也没有学太多东西，基础很一般。常常后悔白白浪费了本科期间阅读那些经典书籍的大好时机。对于硕士期间自己的实验室，不好意思吐槽太多。项目很扯，没有感觉学到了什么东西。方向是什么图形图像，面试到现在没一个面试官感兴趣。代码也没有写多少行。所以起初一直很担心自己在面试中怎么来介绍自己的项目。因此，为了准备秋季校园招聘，我提前做了很多准备，在现在看来，我当初的选择是完全正确的。下面详细介绍自己所做的准备吧。
二、实习生应聘-备受打击
我正式开始准备找工作是从4月份开始。在此之前，除了在实验室做所谓的项目，然后就是学习一些基础的东西，主要包括C++、STL、Linux、算法。这几项其实都学的比较浅。看过的书有：《C++Primer》、《C++标准程序库》、《STL源码剖析》、《深度探索C++对象模型》、《EffectiveC++》、《鸟哥的Linux私房菜》。到了4月份，参加了腾讯是实习生招聘，结果是挂了。我报的是后台开发。由于没有Linux项目经验，面试官狂问数据结构和算法。一面还好，顶住了。问到的题目有：非递归二叉树遍历-纸上写代码、shell排序、基数排序、找出一堆数中出现次数大于总数一半的数，还有一道算法题是：给出一天内的很多条QQ号的登入及登出记录，每条包括时间、QQ号、标记是登入还是登出的标记符。要求求出一天中最大在线人数。（精确到秒）。基本都答出来了，顺利进入二面。二面面试官瞅了一下我的简历，就开始问算法。四道算法题，具体题目可以看这里http://blog.csdn.net/xiajun/article/details/8882981。四道题答出来两道，一回宿舍，用微信查了下，就进入人才库了。好吧，被鄙视了。其他的一些公司也投了，比如阿里、大摩、百度等等，不是简历筛选没通过，就是笔试没通过。反正木有获得面试机会。不过，我很庆幸自己参加了实习招聘，知道了自己的短板，知道了自己以后想做后台开发需要准备些什么，也了解了面试中面试官的常用套路，这对我接下来着手开始准备看书准备找工作有很大作用。
在这里需要说明的一点是，根据我的了解，实习是一把双刃剑。如果能去好的公司实习，能够获得实习offer，这样能够给自己的简历锦上添花，再去面试别的公司也是一个筹码。但是如果不能获得实习offer，就失去了复习打牢基础的时间，在笔试面试中会很吃亏。所以，大家一定要考虑清楚。
三、为找工作做准备-养兵千日
在此之后，我便开始了我的读书计划，目标是后台开发职位。重点放在C++、数据结构和算法、Linux、网络、Nginx。我之所以要学习Nginx，主要原因有，一，这是一个优秀的开源web服务器，研究开源代码，非常有意义。这也是腾讯面试官给我以及另外同学的建议。二，拓展下我的视野，弥补自己项目经历不足的问题。下面展开介绍这几个方面的准备。
下图是我的部分书籍。其中一些也没有去细看。
1、数据结构和算法
在之前已经阅读了一遍《算法导论》，感觉学的不够深入，很多都忘记得差不多了。因此重新阅读了重点部分，而且用C++编程实现。比如：链表、二叉树、AVL树、红黑树等等。图的算法就看了搜索算法：BFS以及DFS。然后另外在网上找了A*搜索算法的资料看了下。一提到搜索，A*算法肯定是少不了的。之后又看了《编程之美》、《剑指Offer》。不仅仅要看书，还要总结。尤其是笔试面试中出现频率很高的链表以及二叉树的操作，我将各种操作进行了总结，并且练习白纸写代码。白纸写代码是一项重要的基本功，包括边界条件考虑、书写风格等等，会直接决定面试官对你的印象，因此我着重进行了系统训练。《STL源码剖析》看完之后，我已自己动手实现了一些容器：stack、quene、priority_quene、heap等。另外，我也阅读了网上一些大牛强力推荐的博客资料，比如July的编程艺术等。将前面几本书中不曾出现的一些数据结构和算法看了一下，比如：并查集、K-d树、R树、约瑟夫环问题、数据库存储的倒排索引等等。整体讲，这部分准备的还是很充分的，面试中出现的大部分数据接结构和算法题都解决出来了。
2、Linux和网络
linux和网络是我最薄弱的部分，也是最担心的部分。因为木有这方面的项目经历，一直担心如果在简历上写上这一项，会不会被问倒。在这里要特别感谢我的基友LM，给了我很大的指导，在这段时间里，一起学习，一起进步。linux首推经典书籍《Unix环境高级编程》和《Unix网络编程》，网络基础知识首推《TCP/IP协议详解-卷一》。APUE读了两遍，UNP挑了部分看了。感觉只看书根本不够，于是在LM同学的提议下动手写一些demo程序，比如聊天程序、基于线程池的生产者消费者程序等，加深了对基础知识的理解。
3、C++与STL
重温面向对象经典书籍《深度探索C++对象模型》。这本书介绍面向对象机制讲的非常不错，这也是笔试面试中经常出现的考点。重温《Effective C++》。关于STL，我想学的更深一点，作为自己的一项可以在面试中发挥的亮点，因此又重新看了STL内存管理、迭代器、traits编程技法、典型容器的原理。这也在后面的面试中多次被问到。
其实Nginx只学习了两个月。我购买了两本书籍：陶辉的《深入理解Nginx-模块开发与架构解析》以及《深入剖析Nginx》。首先阅读陶辉的书，从总体上对Nginx有个初步的了解，了解了Nginx模块开发流程以及整体架构。并尝试搭建了Nginx环境，实现了书本上的几个模块例子。接下来开始着重看重要的模块：进程模型、负载均衡、epoll模块。阅读了重要的源码，并尝试用gdb跟踪（其实做的比较少了，没太多时间！）。在面试中经常被问到我觉得Nginx的优越性在哪？我就提提进程模型、epoll了，再和Apache简单做了下比较，基本可以蒙混过关。
笔试题面试题
至于笔试题面试题，也看了不少。大多数在网上搜索的。在这里给大家推荐一些比较好的学习资源吧：
Coolshell：/
Matrix67大牛的博客：/blog/。
July的CSDN博客：http://blog.csdn.net/v_JULY_v。
何海涛博客：http://zhedahht./。
笔试面试的经典：Cracking the coding interview–问题与解答：/posts/ctci-solutions-contents.html
LeetCode：/
这里有不少笔试题集锦：http://blog.csdn.net/hackbuteer1
除了上面的基础知识，也系统梳理了一下自己的项目。虽然项目经历很扯，但是，也需要仔细梳理下思路，不能让面试官感觉读研期间没有做什么事情。把项目流程、关键点、难点、解决方案等等重新回想了下。以便面试官问到这些问题能够很流利地答出来。
四、校园招聘-用兵一日
接下来介绍我参加的几个公司的面试情况：阿里巴巴、美团、人人、华为、创新工场涂鸦移动、创新工场豌豆荚。
1、阿里巴巴-拿到offer
阿里巴巴笔试比较难，题目属于互联网公司中比较难的了。笔试题中有较多的概率题之类的数学题。而且选择题选错了会扣分，想得高分真是有难度啊。22日晚上笔试完之后就感觉很差，当时感觉可能就没戏了。没想到第二天中午午睡的时候就收到阿里巴巴的面试通知，居然是当天下午四点。起初还以为是第二天。不得不说阿里巴巴的效率真高，传说三天全部搞完。猛然间想起来已经和创新工场涂鸦移动HR约好了二面，也是最后一面了，恰好也是在下午四点。这可怎么办？连忙打了一个电话给HR，结果发现是个总机，需要拨分机号，无奈只能作罢，先去阿里吧。
三点从学校出发，坐公交来到君宜王朝大酒店。发现等待的场地很小，等待的人也不是很多。等到4点，阿里面试还没开始，结果涂鸦移动那边打电话来了。情急之下说现在有点事情，能不能十分钟之后打过来。然后我去和阿里的工作人员说能不能推迟四十分钟，我想四十分钟应该能够结束涂鸦移动的面试。工作人员说没问题，然后连忙去找安静的地方、光线充足的地方准备电面。结果发现酒店里面到处都很暗，比较亮的地方只有走廊了。算了，蹲在走廊上面吧。整个面试过程大概四十分钟，感觉面的还可以。结束后马上去找阿里的工作人员，等候阿里的面试。
等了没一会就通知去一面。进去后，发现很大的一个屋子里面摆着很多桌子，一个桌子是一个面试官和一个面试者单面。我的面试官很年轻，也很和蔼。一开始就和我聊一些轻松的话题。他首先是看我简历，看到我的兴趣爱好的时候，还问我：“你还会交谊舞？”我笑了一下，回答：“是啊”。他又笑哈哈的说：“就是为了把妹呗。。。”囧。。。我忍不住笑了（PS：居然这也被你看穿了）。然后问我家是哪里的，等等。之后就是开始一个自我介绍，然后是对着简历问技术。C++、算法与数据结构、Linux、GDB、网络、操作系统等等只要我写了的都问了一个遍。因为我在简历上写了博客地址，于是在电脑上敲进去打开看了下。我博客写的文章还挺多的，不过都是些基础的总结的东西。没想到面试官很仔细的看了，觉得还不错。又对着博客问了很多东西。他看我课外研究了Nginx，还写了一些博文，也问了nginx上的一些东西。还好前两天看了一下前面的笔记，答的还凑合。后来居然从我博文里面抽一些东西来问我，我回答之后才告诉我说：“我是在用你的博客来当面试问题哈”囧…总共面试了一个半小时左右，比一般人的四十分钟多好多。总体感觉一面面试官人很好，很和蔼，健谈，这样的面试很开心。
由于一面面完之后就七点多了，工作人员告诉我，由于今天太晚了，就让我明天早晨9:30再去参加二面。第二天一大早，天下着大雨，早起吃个早饭便匆忙赶到酒店。等了会就参加二面了。二面是一个技术面试官和一个HR同时面。首先依然是自我介绍，和一面的自我介绍差不多。项目也许是不感兴趣吧，便开始出算法题，都要求写代码。总共问了两道算法题，不算难。第一道题是两个字符串A、B。从A中剔除存在于B中的字符。比如A=“hello world”,B=”er”，那么剔除之后A变为”hllowold”。空间复杂度要求是O(1)，时间复杂度越优越好。我又问了下字符串中字符是不是仅限于小写字母，它说可以这么认为。那么判断A中字符是不是在B中的话就可以用hash了。这道题不难，直接设置一个count变量，记录A中存在于B中的字符数量。然后设置一个指针遍历字符串A，遇到不是B中的字符往前移动到正确的位置即可。第二道题是求打靶十次，获得80环的概率。我是用类似于八皇后来做的，遍历加回溯。只不过代码没写太全。先想写一个非递归的回溯的，但是楞是憋不出来，于是想着用递归吧，要简单一点。反正写的不全，还是TM代码写少了啊。水啊~~技术方面其他的就是问的课余时间都学些什么。我课余也就学习了Nginx和Linux。首先就聊了下Nginx，什么进程模型，优点等等。然后问了select、poll和epoll的区别。这个很熟悉，很快答上来。之后又问了Linux是如何减少内存碎片的问题的。我就说了下slab，貌似主要应该是伙伴算法。这个问题回答的不好。然后HR问了一些问题，什么家乡啊，职业规划啊，最感兴趣的三家互联网公司什么的。结束了我问什么时候可以出通知，说一周之后。囧！这是不是挂的节奏啊！！！
话说等通知真是纠结的很。终于在25日晚10点左右收到了阿里的HR电话，说通过了面试，第二天去参加意向会议。阿里是目前为止我最满意的互联网公司了，这段时间的努力总算没有白费。
2、创新工场-涂鸦移动（拿到offer）以及豌豆荚（仍在面试中）
笔试题答的不错，总分25分，得了22分。错了一个选择题，编程题求根号2的我采用的是二分法，实际上更好的方法是牛顿迭代法。还有错了一道数据库的选择题，数据库真的是不会啊，o(╯□╰)o。
大约9点多笔试完，当天晚上十一点就收到了面试通知，开始说是早晨八点多，但是因为上午有华为面试，就重新约在了下午一点。上午从华为面试完急匆匆赶回学校吃了午饭，回寝室坐了一会就和同学一起出发去启明学院参加创新工场的面试。到达地点的时候大概还有二十多分钟，于是我和同学掏出手机，又温习了Onenote上的笔记，把堆排序、归并排序等等基本算法又琢磨了一遍。话说onenote真心很好用，比有道笔记要好用很多。啊哈哈~算是给微软免费打一个广告吧~
很快就一点了，一位面试官把我叫了进去。猛然间发现这位面试官怎么这么眼熟，后来知道了他的名字后才发现是我在人人网上的一个好友，ACM大牛。面试官人很随和，让我做了一个自我介绍，仅限于技术上的，一看就是技术宅，哈哈~然后对着简历看了下，开始问问题。因为我的实验室项目都是图形图像方面的，面试官一点都不感兴趣，于是都是对着我的技能那一栏写的进行提问。先是问了Vim我平时都使用过哪些插件。GDB调试命令：查看栈帧backtrace等等。fork函数的返回值，以及执行过程。linux方面的东西问完之后就开始算法。总共写了三个算法题，都要求白纸写代码。因为我平时这方面练习比较多，因此都不是问题，很快就写出来了。第一道题是有一个int型数组，每两个相邻的数之间的差值不是1就是-1.现在给定一个数，要求查找这个数在数组中的位置。我先说了下最基础的方法，那就是顺序遍历，还没说完面试官就打断问有没有更好的方法。我就说可以在遍历的时候进行一些跳跃，提高查找效率。然后他说，嗯，写代码吧。第二道题记不得了。第三道题是一个字符数组，里面的字符可能是a-z、A-Z、0-9.现在要求对数组进行排序，要求所有小写字符放在最前面，所有大写字符放在中间，所有数字放在最后。而且各部分内部分别有序。我一开始没想到这个数组可能会很大，于是用比较笨的方法来写代码，他过了一会就问我是不是要先分别排序再合并，我说是的。他就问如果数组很大呢？我立马回答出了桶排序。因此大家在开始答题的之前一定要和面试官多沟通，把题目意思搞明白。
然后面试官就说没啥问题了，问我又没啥问题。我就随便问了下总共有几面就出来了。出来才发现总时长才二十分钟。囧！这是不是挂的节奏啊！还好很快就收到了双选会的通知。
双选会在中秋前一天下午举行。主要是到场的6家创新工场旗下的公司做介绍，然后大家填了一个意向表。每个人可以选择三家意向公司，而且三家公司都有面试机会。我填的是豌豆荚、涂鸦移动和墨迹天气。会上还说涂鸦移动的面试会在当天晚上就开始，因此中秋期间也要准备随时面试。
二面-涂鸦移动
果然当天下午5点就收到了涂鸦移动的二面通知，还是晚上十点的。我去，这是第一次这么晚去面试。本来是十点，结果开始得比较晚，十一点半才面试完，回宿舍都关门了。感觉面试官特别注重考查思维能力。他问我会哪些数据结构和算法，我先说可链表、数组、栈、AVL树等等还没说完就被打断了，他补充说，偏重算法。我挑了我熟悉的几个说了下：BFS、DFS、KMP、A*算法。然后就出了四个算法题。下面说说两个较难的算法题
（1）一个矩阵，指定其中两个元素，将这两个元素用折线连接起来，折线只能朝右或者朝下，要求：折线组成的路径上的数的乘积末尾的0最多。
（2）连连看游戏。判断两个点能否连接起来消去，而且要求出最短路径。可以用哪些搜索算法？BFS，DFS，A*？A*如何剪枝？
典型解法：BFS。
其他同学的面试题：
由‘0’-‘9’组成的字符串，求一个最大子串。该子串不能满足条件：该子串的任意两个子串对应数字的乘积字符串对应的数字不能是这个子串的子串。
本来以为涂鸦二面面的很差，结果还是收到了Offer。今年好像招的人不少。
二面：豌豆荚：
豌豆荚的代码超级好，氛围也很不错。我们学院一个大牛在4月份就拿到了正式offer，听他说，里面全部是大牛，给力的工资以及各种福利等等，让人艳羡不已。豌豆荚招人非常严格，一般有6-7轮技术面试，难度可想而知。我本着打酱油的心情参加了面试。
面试时间：,5:00
总时间大概1小时。
先是一个女工程师面试，主要是问简历，聊了Linux shell命令，统计出一个文件夹下大小大于7MB的文件夹，这个没答上来。还有的记不得了。接下来又安排了一个面试官专门问我C++的，主要是问STL，内存管理、Vector容器等等。之后就是线上编程环节。那边可以看见我的一举一动，第一次这样面试，压力还是有点大的。题目就是将一个四位整数比如4298转化为大写：四千二百九十八。我漏掉了一个情况：就是十的时候，前面不需要一！PS：不得不说，中文博大精深啊！然后就结束了，我问了下之后还有几面，HR说还有至少两到三面。好吧。不得不说豌豆荚的招聘真心严格。
本来以为豌豆荚挂了，结果时隔十多天于10月16日收到了HR电话，说要进行二面。面就面吧，就当长点见识，这高富帅公司也从没想过进去。
3、美团-拿到offer
笔试是六道大题，有几道是写代码，有几道是计算题。第二天收到面试通知。美团是三面连续着面，通过一轮面试马上进入下一轮面试。面试地点在大学生活动中心。一面，面试官让我介绍了一下项目，我就blabla介绍一通，目测他也没听懂。随便聊了下就开始问C和算法题。算法题不难，纸上写代码。大约35分钟面试结束，在门外等候了一会，紧接着进去二面。二面就是几道算法题，有的写代码，有的讲思想。基本都答得差不多了。又出来等消息。由于已经5点了，hr告诉我先去吃个饭，然后回来参加三面。我特意问了一下三面是技术面还是HR面，她说是技术面，技术副总裁面。汗！压力大啊，副总裁面试！果不其然，副总裁面试就是不同，问题一个接着一个，也很有深度。比如项目中遇到了哪些问题，是怎么解决的，软件设计，Linux、Nginx等等。反正很多没答上来。面完之后就感觉要挂的样子。因为听宣讲会的时候说道美团今年全国只招200人。没想到一会就收到了HR电话，算是HR面吧。
十月初便收到了美团网的offer，薪资也还蛮给力的，氛围也很不错，只不过在北京额。
4、华为-拿到offer
华为先是机试，三道编程题，题不难，但是只做出来两道，第三道题题目理解错了，尼玛。面试分为两轮，一轮技术一轮HR。感觉华为技术面试是我面的最差的。几道题一个都没答上来。什么数据库存储原理、linux内核的东东….囧。干嘛总是问我不会的呢！
本感觉没戏了，不过后来也收到了签约池的信息。再后来就收到了HR聊意向的电话。虽然说华为今年涨薪了，但是对华为的氛围一直没有什么好的印象，没有去的欲望，不久就拒了。
5、人人-二面就没去了
人人就面了一面，因为有阿里offer二面就没去了。一面感觉还不错。面试在我们学校的一个咖啡厅。面试官主要问C++和STL。C++主要问面向对象的一些东西，基本答出来。STL我比较熟悉，也没啥问题。最后他介绍了一下自己所在部门的情况，说是做广告推荐、数据挖掘的。问我对以后职业发展有什么意向没。我说对后台开发、广告推荐很感兴趣，他就记录下来了。一面大概35分钟，这样就结束了。
后来不久就收到了二面通知，不过没有去了。
五、总结-一点小感悟
其实我从来没有料到自己的求职过程会这么顺利，因为实现没有发现自己身上有哪些过人的优点。
自我感觉我在面试中的亮点主要有三部分：
（1）基础扎实。很多公司都非常注重基础：语言、数据结构与算法、Linux、操作系统等等。手写代码能力很重要，有必要重点强化训练。
（2）课外知识。我课外花时间学习了web服务器Nginx，虽然研究得不是很深入，但是了解基本的架构和重点模块。对于服务器模型有了基本理解。
（3）技术博客。我的技术博客原创博文已经很多了，虽然没有太多高深的东西，都是一些基础知识，但是大多是自己加以总结了的。大多数面试官都打开我的博客看了，评价还不错。
其实，关于怎么样去学习，并没有固定的套路。有的同学，在研究生期间做过比较出色的项目，能够赢得面试官的青睐，比如发过论文，或者是和面试官的方向一致，或者是当下互联网比较热的方向等等，这样，可能一次面试，项目聊完就没有多少时间了，面试官也不会去问其他的东西。好的项目经验能够让面试官觉得你实践经验丰富，可以直接拿来干活，通过面试的概率也是非常之大的。如果没有好的项目经验，最好努力去打牢自己的基础，多关注互联网的前沿，充实自己，一样可以赢得面试官的赞许。总之，大家都要有自己的亮点，能让面试官眼前一亮，那么，通过面试也是不难的事情了。
不得不说，面试也看眼缘和运气，有时候问的东西刚好是自己都会的，有的时候容易遇到挫折。大家要善于把面试朝自己擅长的方向引，展现自己的优势。多数面试官都不会以问倒求职者作为目的，而是往往尝试去发现求职者身上的有优点及潜力。应聘者应尽量将面试看成一个相互交流的过程。
最后，希望我的总结能够给各位学弟学妹一点借鉴的意义，希望大家都能找到好的工作！
本文固定链接:
转载请注明:
作者：Jianchihu
管理员——低调做事，低调做人
您可能还会对这些文章感兴趣！}