字符串匹配的后缀算法

字符串匹配问题是算法领域的经典问题,C/C++中常用的 strstr函数就是这个问题的定义:

const char* strstr( const char* str, const char* target );
char* strstr( char* str, const char* target );

Finds the first occurrence of the byte string target in the byte string pointed to by str. The terminating null characters are not compared.

在目标字符串 str中寻找是否存在子串 target,字符串 str的长度为\(n\), target的长度为\(m\)。这个问题最为人所熟知的算法应该是KMP(Knuth-Morris-Pratt)算法,其时间复杂度为\(O(n)\),想法非常酷。

但是,Can we do better?

继续阅读:

Strict Aliasing,神坑?

先来看一段代码:

你觉得程序的输出是什么样的呢?

继续阅读:

探索C++虚函数在g++中的实现

本文是我在追查一个诡异core问题的过程中收获的一点心得,把公司项目相关的背景和特定条件去掉后,仅取其中通用的C++虚函数实现部分知识记录于此。

在开始之前,原谅我先借用一张图黑一下C++:

“无敌”的C++

“无敌”的C++

如果你也在写C++,请一定小心…至少,你要先有所了解:当你在写虚函数的时候,g++在写什么?

继续阅读:

TCP Maximum Segment Size (MSS)

这篇是一个小小的查缺补漏,还记得大三网络实验最后助教检查实验问过这个问题:“MSS是干什么的?”,当时背了个定义蒙混过去了,没有仔细理解,现在又遇到了,补上~

MSS是什么?

下图中看到的是TCP连接发送和接收的过程示意图,最大报文段长度(MSS)的作用是限制在TCP层产生的报文段的最大长度(当然要在滑动窗口允许的前提下)。

TCP发送接收过程图

TCP发送接收过程图

比如如果MSS为1000个字节,每个TCP报文的最大长度为1020字节(附加20字节TCP头部),之后传递到IP层加装20字节IP头部封装成为IP报文利用链路层发送。

继续阅读:

关于Linux环境C/C++网络框架的一点思考

最近又看了一个网络框架的源码,和之前看过的比起来,应该说是各有特色,互有所长。在这个全民写框架的时代,可能是因为框架(Framework)听起来逼格比较高,所以大家都乐于去写一个自己的“框架”,那么,一个合格的网络框架究竟应该是什么样的?我们又该从何下手?

什么是网络框架

网络框架,顾名思义,是给网络应用程序使用的框架,本文中指代在Linux环境下使用C/C++编写的网络服务器框架。用户在使用框架时应该能够做到在对底层网络完全不了解或者所知很少的情况下,轻松实现自己所需要的后台网络服务应用。

原材料

听上去似乎很神奇,但实际上网络框架所要完成的只有一件事情——封装。网络框架所做的事情就是将Linux提供的底层网络API进行封装,向用户提供一套没有网络细节的接口。

继续阅读:

Hello, SciPy!

“学而时习之,不亦乐乎”,利用放假几天时间,简单复习了一下之前学习的Machine Learning课程,并且用刚上手没两天的SciPy重新完成了大部分Ng的课后作业,SciPy真的非常好用~

SciPy

SciPy

上图是SciPy官方网站对SciPy的介绍,SciPy并不是单个开源项目,而是一组开源项目共同构成的Python科学计算生态系统,一个非常值得一看的系列Tutorial在这里

下面是重写后的课后练习的notebooks:

  1. Linear regression
  2. Logistic Regression
  3. Multi-class Classification
  4. Learning curve(Bias v.s. Variance)
  5. SVM
  6. K-Means & PCA

神经网络相关的实验还没有重写,sklearn没有提供监督学习的神经网络组件,需要用pylearn2来做,有时间补上。

OpenStack网络迷宫:Neutron以及LBaaS

"一团糟" - 我对OpenStack网络实现的第一感觉

“一团糟” – 我对OpenStack网络实现的第一感觉

OpenStack的网络模块相信不会有人否认是整个OpenStack中最复杂的部分,即使是OpenStack社区的成员也常常被网络模块的复杂性搞的焦头烂额。因为研究负载均衡的关系,我不得不对网络模块进行一点粗浅的了解,这里按照个人的理解把这些东西总结起来写下来。

本文算不上是的OpenStack网络分析(没有实力写),但求可以以自己的一些粗浅理解,为想要一窥OpenStack网络实现的同学提供哪怕一点点帮助。

PS:本文中所描述的所有概念和实现均基于OpenStack当前版本(neutron git version : 2921d3c686b5f5cd68d51f906766983f975b1cf2),在此也强烈建议任何想要了解OpenStack网络的同学一定要实际搭建一个可用的环境来对其中网络的每一个环节进行推敲。

继续阅读:

SRM657 DIV1 Problem Sets

原题链接:Problem Sets

Cat Snuke came up with some problems. He wants to construct as many problem sets as possible using those problems. Each problem set must contain exactly three problems: one for the Easy slot, one for the Medium slot, and one for the Hard slot. Each problem can only be assigned to a single slot in a single problem set. He came up with E + EM + M + MH + H problems in total. The distribution of the problems is as follows:

  • E problems can only be used in the Easy slot.
  • EM problems can be used either in the Easy slot or the Medium slot.
  • M problems can only be used in the Medium slot.
  • MH problems can be used either in the Medium slot or the Hard slot.
  • H problems can only be used in the Hard slot.

Return the maximal number of problem sets he can construct.

继续阅读:

SRM656 DIV1 Random Pancake Stack

被虐了……这个题目其实不难,但是从一开始想法有个漏洞没有发现…一直没有转过弯来…还是需要训练训练…

原题链接:Random Pancake Stack

Charlie has N pancakes. He wants to serve some of them for breakfast. We will number the pancakes 0 through N-1. For each i, pancake i has width i+1 and deliciousness d[i].

Charlie chooses the pancakes he is going to serve using the following randomized process: He starts by choosing the first pancake uniformly at random from all the pancakes he has. He places the chosen pancake onto a plate. This pancake now forms the bottom of a future stack of pancakes. Then, Charlie repeats the following procedure:

  1. If there are no more pancakes remaining, terminate.
  2. Choose a pancake uniformly at random from the pancakes that have not been chosen yet.
  3. If the width of this pancake is greater than the width of the pancake on top of the stack, terminate without taking it.
  4. Place the chosen pancake on top of the stack and go back to step 1.

You are given the vector d with N elements. The total deliciousness of a serving of pancakes is the sum of the deliciousness of all pancakes used in the serving. Compute and return the expected value of the total deliciousness of the pancakes chosen by Charlie.

继续阅读: