hihocoder 1197 Give My Text Back (模拟)

#1197 : Give My Text Back

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

To prepare for the English exam Little Ho collected many digital reading materials. Unfortunately the materials are messed up by a malware.

It is known that the original text contains only English letters (a-zA-Z), spaces, commas, periods and newlines, conforming to the following format:

1. Each sentence contains at least one word, begins with a letter and ends with a period.

2. In a sentence the only capitalized letter is the first letter.

3. In a sentence the words are separated by a single space or a comma and a space.

4. The sentences are separated by a single space or a single newline.

It is also known the malware changes the text in the following ways:

1. Changing the cases of letters.

2. Adding spaces between words and punctuations.

Given the messed text, can you help Little Ho restore the original text?

输入

A string containing no more than 8192 English letters (a-zA-Z), spaces, commas, periods and newlines which is the messed text.

输出

The original text.

样例输入
样例输出

比较容易忽视的几个细节是:
连续的空格或者换行符只能有一个;

一个句子是某一行最后一个句子的时候,’.’后没有空格

比较难处理的是,’.’或者’,’前面的空格.

我的做法是,先不处理,最后倒序处理.

 

今日头条2017秋招笔试_1

头条校招(今日头条2017秋招真题)

头条的2017校招开始了!为了这次校招,我们组织了一个规模宏大的出题团队。每个出题人都出了一些有趣的题目,而我们现在想把这些题目组合成若干场考试出来。在选题之前,我们对题目进行了盲审,并定出了每道题的难度系数。一场考试包含3道开放性题目,假设他们的难度从小到大分别为a, b, c,我们希望这3道题能满足下列条件:

a<= b<= c
b – a<= 10
c – b<= 10

所有出题人一共出了n道开放性题目。现在我们想把这n道题分布到若干场考试中(1场或多场,每道题都必须使用且只能用一次),然而由于上述条件的限制,可能有一些考试没法凑够3道题,因此出题人就需要多出一些适当难度的题目来让每场考试都达到要求。然而我们出题已经出得很累了,你能计算出我们最少还需要再出几道题吗?

输入输入的第一行包含一个整数n,表示目前已经出好的题目数量。

第二行给出每道题目的难度系数 d1, d2, …, dn。

样例输入4

20 35 23 40

输出输出只包括一行,即所求的答案。

样例输出2

时间限制C/C++语言:1000MS其它语言:3000MS
内存限制C/C++语言:65536KB其它语言:589824K

 

div2 A的难度…直接贪就好,不给数据范围的都是耍流氓…

 

 

今日头条笔试题_或与加(打表,构造)

给定 x, k ,求满足 x + y = x | y 的第 k 小的正整数 y 。 | 是二进制的或(or)运算,例如 3 | 5 = 7。

比如当 x=5,k=1时返回 2,因为5+1=6 不等于 5|1=5,而 5+2=7 等于 5 | 2 = 7。

 

输入描述:

每组测试用例仅包含一组数据,每组数据为两个正整数 x , k。 满足 0 < x , k ≤ 2,000,000,000。

 

输出描述:

输出一个数y。

 

输入例子:

 

输出例子:

一看就是数学题…?
打表观察…

 

发现如果x的二进制表示中,如果某位为1,那么对应的y的位置上一定为0.

如果某位为0,那么对应的y的位置上可以为0也可以为1…

就是说…x的二进制表示中,为1的的那些位置是能改变的.

影响当前第几大的就是那些为0的位置…

所以我们可以把k转化成二进制表示,按顺序填充到x中为0的那些位置(主要可以填充到x最大权值的1之后的0的位置),然后得到的数就是x+y的答案,最后再减去x即可

因为数组开小了..第一次只过了90%….

果然是个废k了呜呜呜,数组开小这种错误我也是服了…

 

今日头条笔试题-木棒拼图(数学)

有一个由很多木棒构成的集合,每个木棒有对应的长度,请问能否用集合中的这些木棒以某个顺序首尾相连构成一个面积大于 0 的简单多边形且所有木棒都要用上,简单多边形即不会自交的多边形。

初始集合是空的,有两种操作,要么给集合添加一个长度为 L 的木棒,要么删去集合中已经有的某个木棒。每次操作结束后你都需要告知是否能用集合中的这些木棒构成一个简单多边形。

 

输入描述:

每组测试用例仅包含一组数据,每组数据第一行为一个正整数 n 表示操作的数量(1 ≤ n ≤ 50000) , 接下来有n行,每行第一个整数为操作类型 i (i ∈ {1,2}),第二个整数为一个长度 L(1 ≤ L ≤ 1,000,000,000)。如果 i=1 代表在集合内插入一个长度为 L 的木棒,如果 i=2 代表删去在集合内的一根长度为 L 的木棒。输入数据保证删除时集合中必定存在长度为 L 的木棒,且任意操作后集合都是非空的。

 

输出描述:

对于每一次操作结束有一次输出,如果集合内的木棒可以构成简单多边形,输出 “Yes” ,否则输出 “No”。

 

输入例子:

 

输出例子:

能组成n边形的条件可以由三角形推广而来..(虽然只是猜想…
也就是n-1条较小边的和大于最大边…事实证明这结论是对的orz..
然后就是multiset就好…

 

今日头条笔试题-最大映射(贪心)

一开始看漏了首位不能映射到0的条件…直接贪了..结果发现不太对…

哦贪心的方法就是算每个字母的权值和…用pair 搞一下…

处理的办法是如果10个字母都出现,那么先把没有在首位出现过的字母中权重最小的那个映射到0,再搞剩下的…

一个trick是…map映射到0..和某个key没有被映射过..产生了二义性….

窝的做法就是整体+1,最后再减回来..

然后因为某处手残卡了1个小时…???.

哎我果然是个废k了…..傻逼贪心都写不对QAQ

 

murmurhash源码分析

分析levelDB源码的时候遇到的…发现是一个广泛应用的hash算法,而且是纯c写的,于是找来了源码看。

MurmurHash 是一种非加密哈希函数,适用于一般的哈希检索操作。[1][2][3]由Austin Appleby在2008年发明,[4][5] 并出现了多个变种,[6] 都已经发布到了公有领域(public domain)。与其它流行的哈希函数相比,对于规律性较强的key,MurmurHash的随机分布特征表现更良好。[7]

最初的实现是C++的,但是被移植到了其他的流行语言上,包括 Python,[11]C,[12]C#,[9][13]Perl,[14]Ruby,[15]PHP,[16]Haskell,[17]Scala[18]Java[19][20]JavaScript[21][22]等。

这个算法已经被若干开源计划所采纳,最重要的有libstdc++ (4.6版)、Perl[23]nginx (不早于1.0.1版)[24]Rubinius[25]、 libmemcached (MemcachedC语言客户端驱动)[26]、maatkit[27]Hadoop[1]、Kyoto Cabinet[28]以及RaptorDB[29]

虽然说破天就是一个hash函数。。似乎没什么好分析的?

不过由于是第一次分析有现实意义的代码,所以简单一点也不是罪过吧orz

以及这次分析代码的重点不在hash算法本身…而是算法之外的其他东西…

大概感受下有现实意义的工程代码的布局之类orz

hash函数本身没有分析…这个没什么好分析的吧…应该是类似一种构造,看懂每一步很容易,但是你还是想不出来啊?而且一堆”magic number”

代码很短,也就200行,分析见注释。

 

 

 

内存屏障(Memory Barriers)

起因是最近在看levelDB源码,其中port里的atomic_pointer.h文件用到了内存屏障。。

于是来学习一下。。

粗略得说下我自己的理解。

代码的顺序并不和执行的顺序完全对应,出于对效率的追求,cpu和编译器会对一些顺序指令重排,以期得到最大的执行效率。

比如下面这段代码:

v的值是没有改变的,那么编译器可能会认为 _store = v; v = _store; 是多余的,就直接把这一段给“优化”掉了。这段代码在单线程中确实是多余的,但是在多线程环境下,可能在 somefunc()被调用的时候,另一个线程把v的值给改变了,而这种情况是编译器无法发现的。因此,为了避免这种情况。。。内存屏障登场!

摘自维基百科:

内存屏障,也称内存栅栏内存栅障屏障指令等,是一类同步屏障指令,是CPU或编译器在对内存随机访问的操作中的一个同步点,使得此点之前的所有读写操作都执行后才可以开始执行此点之后的操作。

大多数现代计算机为了提高性能而采取乱序执行,这使得内存屏障成为必须。

语义上,内存屏障之前的所有写操作都要写入内存;内存屏障之后的读操作都可以获得同步屏障之前的写操作的结果。因此,对于敏感的程序块,写操作之后、读操作之前可以插入内存屏障。

在多线程环境里需要使用某种技术来使程序结果尽快可见。。请先假定一个事实:一旦内存数据被推送到缓存,就会有消息协议来确保所有的缓存会对所有的共享数据同步并保持一致。这个使内存数据对CPU核可见的技术被称为内存屏障或内存栅栏

 

再看一个例子

这段代码,是想知道for循环空转100000次的耗时,这里就需要加入一个MemoryBarrier,如果不加,那么编译器可能就会直接把这个无意义的for循环直接优化掉了。

除了编译器,cpu由于指令流水线或者超流水线等计数,也可能导致出现乱序执行的情况。

内存屏障提供了两个功能。首先,它们通过确保从另一个CPU来看屏障的两边的所有指令都是正确的程序顺序,而保持程序顺序的外部可见性;其次它们可以实现内存数据可见性,确保内存数据会同步到CPU缓存子系统。

不过内存平展由于阻碍了cpu和编译器的部分优化。。。因此对性能的影响是不忽略的。

为了达到最佳性能,最好是把要解决的问题模块化,这样处理器可以按单元执行任务,然后在任务单元的边界放上所有需要的内存屏障。采用这个方法可以让处理器不受限的执行一个任务单元。合理的内存屏障组合还有一个好处是:缓冲区在第一次被刷后开销会减少,因为再填充改缓冲区不需要额外工作了。

内存屏障的实现不同平台差别很大。。。因为我们可以看到atomic_pointer.h文件中 一堆和平台相关的条件编译…

 

参考资料:

内存屏障_维基百科

内存屏障_并发编程网

LINUX内核之内存屏障

Lock-free vs wait-free concurrency

参考资料

看leveldb源码中遇到的,关于lock-free 和 wait-free..感觉这个讲得不错,我试着翻译一下?

There are two types of non-blocking thread synchronization algorithms – lock-free, and wait-free. Their meaning is often confused. In lock-free systems, while any particular computation may be blocked for some period of time, all CPUs are able to continue performing other computations. To put it differently, while a given thread might be blocked by other threads in a lock-free system, all CPUs can continue doing other useful work without stalls. Lock-free algorithms increase the overall throughput of a system by occassionally increasing the latency of a particular transaction. Most high- end database systems are based on lock-free algorithms, to varying degrees.

有两种 无阻塞线程同步算法,一种是lock-free,一种是wait-free,它们的含义经常被搞混。在一个lock-free系统中,尽管某个特定的计算会被阻碍一段时间,所有的cpu还是能够继续其他计算。换一种说法,尽管在一个lock-free的系统里,一个线程可能被其他线程阻碍,所有的cpu仍然可以继续做其他工作而不做停顿。lock-free算法通过偶然增加一个特定事物的延迟,增加了系统总体的吞吐率。大多数高端数据库系统都在某种程度上基于lock-free 算法。

 

By contrast, wait-free algorithms ensure that in addition to all CPUs continuing to do useful work, no computation can ever be blocked by another computation. Wait-free algorithms have stronger guarantees than lock-free algorithms, and ensure a high thorughput without sacrificing latency of a particular transaction. They’re also much harder to implement, test, and debug. The lockless page cachepatches to the Linux kernel are an example of a wait-free system.

与此相反,wait-free算法除了保证所有cpu继续做其他工作以外,还保证不会有任何计算被另一个计算阻止。wait-free算法比lock-free算法有更强的保证,确保了在不牺牲某一事物的延迟的基础上,拥有更高的吞吐率.wait-free算法因此也更加难以实现,测试,调试。linux内核的无锁页面缓存(?)就是一个wait-free系统的例子。

 

In a situation where a system handles dozens of concurrent transactions and has soft latency requirements, lock-free systems are a good compromise between development complexity and high concurrency requirements. A database server for a website is a good candidate for a lock-free design. While any given transaction might block, there are always more transactions to process in the meantime, so the CPUs will never stay idle. The challenge is to build a transaction scheduler that maintains a good mean latency, and a well bounded standard deviation.

在一个系统处理几十个并发事务并且对延迟要求不高的情况下,lock-free系统是开发复杂性和高并发性要求之间的良好折衷。一个网站的数据库服务器是lock-free系统的很好的体现。尽管某个特定的事物可能被阻塞,但同时也有更多的事务要处理,所以CPU永远不会空闲。面临的挑战是建立一个好的事物调度表,以此来获得尽可能低的平均延迟和一个有界的标准偏差。

In a scenario where a system has roughly as many concurrent transactions as CPU cores, or has hard real-time requirements, the developers need to spend the extra time to build wait-free systems. In these cases blocking a single transaction isn’t acceptable – either because there are no other transactions for the CPUs to handle, minimizing the throughput, or a given transaction needs to complete with a well defined non-probabilistic time period. Nuclear reactor control software is a good candidate for wait-free systems.

在一个场景中,系统与CPU内核大致相同数量的并发事务,或者有硬实时要求,开发人员需要花费额外的时间来构建wait-free系统。在这种情况下,阻塞单个事务是不可接受的,要么是因为CPU没有其他事务要处理从而减少了吞吐量,要么是给定的事务需要用一个定义良好的非概率时间段来完成(相对比较确定的时间的意思?)。核反应堆控制软件是wait-free系统的一个很好的体现。

 

AWK 初探

参考资料:

awk_维基百科

awk简明教程

awk是一门比较古老但是很好用的文本处理工具(语言?)

语法还是很好懂的。。。转载了一篇文章。。。算是简明手册? 不过台词有点糟糕orz

有一些网友看了前两天的《Linux下应该知道的技巧》希望我能教教他们用awk和sed,所以,出现了这篇文章。我估计这些80后的年轻朋友可能对awk/sed这类上古神器有点陌生了,所以需要我这个老家伙来炒炒冷饭。况且,AWK是贝尔实验室1977年搞出来的文本出现神器,今年是蛇年,是AWK的本命年,而且年纪和我相仿,所以非常有必要为他写篇文章

之所以叫AWK是因为其取了三位创始人 Alfred AhoPeter Weinberger, 和 Brian Kernighan 的Family Name的首字符。要学AWK,就得提一提AWK的一本相当经典的书《The AWK Programming Language》,它在豆瓣上的评分是9.4分!在亚马逊上居然卖1022.30元

我在这里的教程并不想面面俱到,本文和我之前的Go语言简介一样,全是示例,基本无废话。

我只想达到两个目的:

1)你可以在乘坐公交地铁上下班,或是在坐马桶拉大便时读完(保证是一泡大便的工夫)。

2)我只想让这篇博文像一个火辣的脱衣舞女挑起你的兴趣,然后还要你自己去下工夫去撸。

废话少说,我们开始脱吧(注:这里只是topless)。

起步上台

我从netstat命令中提取了如下信息作为用例:

下面是最简单最常用的awk示例,其输出第1列和第4例,

  • 其中单引号中的被大括号括着的就是awk的语句,注意,其只能被单引号包含。
  • 其中的$1..$n表示第几例。注:$0表示整个行。

脱掉外套

过滤记录

我们再来看看如何过滤记录(下面过滤条件为:第三列的值为0 && 第6列的值为LISTEN)

其中的“==”为比较运算符。其他比较运算符:!=, >, <, >=, <=

我们来看看各种过滤记录的方式:

如果我们需要表头的话,我们可以引入内建变量NR:

再加上格式化输出:

内建变量

说到了内建变量,我们可以来看看awk的一些内建变量:

$0 当前记录(这个变量中存放着整个行的内容)
$1~$n 当前记录的第n个字段,字段间由FS分隔
FS 输入字段分隔符 默认是空格或Tab
NF 当前记录中的字段个数,就是有多少列
NR 已经读出的记录数,就是行号,从1开始,如果有多个文件话,这个值也是不断累加中。
FNR 当前记录数,与NR不同的是,这个值会是各个文件自己的行号
RS 输入的记录分隔符, 默认为换行符
OFS 输出字段分隔符, 默认也是空格
ORS 输出的记录分隔符,默认为换行符
FILENAME 当前输入文件的名字

怎么使用呢,比如:我们如果要输出行号:

指定分隔符

上面的命令也等价于:(-F的意思就是指定分隔符)

注:如果你要指定多个分隔符,你可以这样来:

 

再来看一个以\t作为分隔符输出的例子(下面使用了/etc/passwd文件,这个文件是以:分隔的):

脱掉衬衫

字符串匹配

我们再来看几个字符串匹配的示例:

上面的第一个示例匹配FIN状态, 第二个示例匹配WAIT字样的状态。其实 ~ 表示模式开始。/ /中是模式。这就是一个正则表达式的匹配。

其实awk可以像grep一样的去匹配第一行,就像这样:

我们可以使用 “/FIN|TIME/” 来匹配 FIN 或者 TIME :

再来看看模式取反的例子:


折分文件

awk拆分文件很简单,使用重定向就好了。下面这个例子,是按第6例分隔文件,相当的简单(其中的NR!=1表示不处理表头)。

你也可以把指定的列输出到文件:

统计

下面的命令计算所有的C文件,CPP文件和H文件的文件大小总和。

我们再来看一个统计各个connection状态的用法:(我们可以看到一些编程的影子了,大家都是程序员我就不解释了。注意其中的数组的用法)

再来看看统计每个用户的进程的占了多少内存(注:sum的RSS那一列)

脱掉内衣

awk脚本

在上面我们可以看到一个END关键字。END的意思是“处理完所有的行的标识”,即然说到了END就有必要介绍一下BEGIN,这两个关键字意味着执行前和执行后的意思,语法如下:

  • BEGIN{ 这里面放的是执行前的语句 }
  • END {这里面放的是处理完所有的行后要执行的语句 }
  • {这里面放的是处理每一行时要执行的语句}

为了说清楚这个事,我们来看看下面的示例:

假设有这么一个文件(学生成绩表):

我们的awk脚本如下(我没有写有命令行上是因为命令行上不易读,另外也在介绍另一种用法):

我们来看一下执行结果:(也可以这样运行 ./cal.awk score.txt)

环境变量

即然说到了脚本,我们来看看怎么和环境变量交互:(使用-v参数和ENVIRON,使用ENVIRON的环境变量需要export)


 

sad

C++ const 用法总结(转载)

基本全文照搬了:关于C++ const 的全面总结

总结全面还是要一点时间的orz..感谢原作者,暂时没发现有什么错误(?

其中对我而言比较陌生的是“const修饰成员函数”的用法。。已经加粗。

    C++中的const关键字的用法非常灵活,而使用const将大大改善程序的健壮性,本人根据各方面查到的资料进行总结如下,期望对朋友们有所帮助。

Const 是C++中常用的类型修饰符,常类型是指使用类型修饰符const说明的类型,常类型的变量或对象的值是不能被更新的。

 

一、Const作用

   如下表所示:

No. 作用 说明 参考代码
1 可以定义const常量 const int Max = 100;
2 便于进行类型检查 const常量有数据类型,而宏常量没有数据类型。编译器可以对前者进行类型安全检查,而对后者只进行字符替换,没有类型安全检查,并且在字符替换时可能会产生意料不到的错误 void f(const int i) { ………}
//对传入的参数进行类型检查,不匹配进行提示
3 可以保护被修饰的东西 防止意外的修改,增强程序的健壮性。 void f(const int i) { i=10;//error! }
//如果在函数体内修改了i,编译器就会报错
4 可以很方便地进行参数的调整和修改 同宏定义一样,可以做到不变则已,一变都变
5 为函数重载提供了一个参考 class A
{
……
void f(int i)       {……} //一个函数
void f(int i) const {……} //上一个函数的重载
……
};
6 可以节省空间,避免不必要的内存分配 const定义常量从汇编的角度来看,只是给出了对应的内存地址,而不是象#define一样给出的是立即数,所以,const定义的常量在程序运行过程中只有一份拷贝,而#define定义的常量在内存中有若干个拷贝 #define PI 3.14159         //常量宏
const doulbe  Pi=3.14159;  //此时并未将Pi放入ROM中
……
double i=Pi;   //此时为Pi分配内存,以后不再分配!
double I=PI;  //编译期间进行宏替换,分配内存
double j=Pi;  //没有内存分配
double J=PI;  //再进行宏替换,又一次分配内存!
7  提高了效率 编译器通常不为普通const常量分配存储空间,而是将它们保存在符号表中,这使得它成为一个编译期间的常量,没有了存储与读内存的操作,使得它的效率也很高

 

二、Const的使用

1、定义常量
(1)const修饰变量,以下两种定义形式在本质上是一样的。它的含义是:const修饰的类型为TYPE的变量value是不可变的。

TYPE const ValueName = value;
const TYPE ValueName = value;
(2)将const改为外部连接,作用于扩大至全局,编译时会分配内存,并且可以不进行初始化,仅仅作为声明,编译器认为在程序其他地方进行了定义.

extend const int ValueName = value;

2、指针使用CONST
(1)指针本身是常量不可变
char* const pContent;

(2)指针所指向的内容是常量不可变
const char *pContent;

(3)两者都不可变
const char* const pContent;

(4)还有其中区别方法,沿着*号划一条线:
如果const位于*的左侧,则const就是用来修饰指针所指向的变量,即指针指向为常量;
如果const位于*的右侧,const就是修饰指针本身,即指针本身是常量。

 

3、函数中使用CONST

(1)const修饰函数参数
a.传递过来的参数在函数内不可以改变(无意义,因为Var本身就是形参)

void function(const int Var);

b.参数指针所指内容为常量不可变

void function(const char* Var);

c.参数指针本身为常量不可变(也无意义,因为char* Var也是形参)

void function(char* const Var);

d.参数为引用,为了增加效率同时防止修改。修饰引用参数时:

void function(const Class& Var); //引用参数在函数内不可以改变

void function(const TYPE& Var); //引用参数在函数内为常量不可变

这样的一个const引用传递和最普通的函数按值传递的效果是一模一样的,他禁止对引用的对象的一切修改,唯一不同的是按值传递会先建立一个类对象的副本, 然后传递过去,而它直接传递地址,所以这种传递比按值传递更有效.另外只有引用的const传递可以传递一个临时对象,因为临时对象都是const属性, 且是不可见的,他短时间存在一个局部域中,所以不能使用指针,只有引用的const传递能够捕捉到这个家伙.
(2)const 修饰函数返回值
const修饰函数返回值其实用的并不是很多,它的含义和const修饰普通变量以及指针的含义基本相同。
a.const int fun1() //这个其实无意义,因为参数返回本身就是赋值。
b. const int * fun2() //调用时 const int *pValue = fun2();
//我们可以把fun2()看作成一个变量,即指针内容不可变。
c.int* const fun3()   //调用时 int * const pValue = fun2();
//我们可以把fun2()看作成一个变量,即指针本身不可变。

一般情况下,函数的返回值为某个对象时,如果将其声明为const时,多用于操作符的重载。通常,不建议用const修饰函数的返回值类型为某个对象或对某个对象引用的情况。原因如下:如果返回值为某个对象为const(const A test = A 实例)或某个对象的引用为const(const A& test = A实例) ,则返回值具有const属性,则返回实例只能访问类A中的公有(保护)数据成员和const成员函数,并且不允许对其进行赋值操作,这在一般情况下很少用到。
4、类相关CONST

(1)const修饰成员变量
const修饰类的成员函数,表示成员常量,不能被修改,同时它只能在初始化列表中赋值。
class A
{

const int nValue;         //成员常量不能被修改

A(int x): nValue(x) { } ; //只能在初始化列表中赋值
}

(2)const修饰成员函数
const修饰类的成员函数,则该成员函数不能修改类中成员变量,也不能调用类中任何非const成员函数。一般写在函数的最后来修饰。
class A
{

void function()const; //常成员函数, 它不改变对象的成员变量.

//也不能调用类中任何非const成员函数。
}

对于const类对象/指针/引用,只能调用类的const成员函数,因此,const修饰成员函数的最重要作用就是限制对于const对象的使用。

  1. const成员函数不被允许修改它所在对象的任何一个数据成员。
  2. const成员函数能够访问对象的const成员,而其他成员函数不可以。

 

任何不会修改数据成员(即函数中的变量)的函数都应该声明为const 类型。如果在编写const 成员函数时,不慎修改了数据成员,或者调用了其它非const 成员函数,编译器将指出错误,这无疑会提高程序的健壮性。以下程序中,类stack 的成员函数GetCount 仅用于计数,从逻辑上讲GetCount 应当为const 函数。编译器将指出GetCount 函数中的错误。

 

(3)const修饰类对象/对象指针/对象引用

  • const修饰类对象表示该对象为常量对象,其中的任何成员都不能被修改。对于对象指针和对象引用也是一样。
  • const修饰的对象,该对象的任何非const成员函数都不能被调用,因为任何非const成员函数会有修改成员变量的企图。
    例如:
    class AAA
    {
    void func1();
    void func2() const;
    }
    const AAA aObj;
    aObj.func1(); ×
    aObj.func2(); 正确const AAA* aObj = new AAA();
    aObj-> func1(); ×
    aObj-> func2(); 正确

 

三、将Const类型转化为非Const类型的方法

 

采用const_cast 进行转换。
用法:const_cast <type_id>  (expression)
该运算符用来修改类型的const或volatile属性。除了const 或volatile修饰之外, type_id和expression的类型是一样的。

  • 常量指针被转化成非常量指针,并且仍然指向原来的对象;
  • 常量引用被转换成非常量引用,并且仍然指向原来的对象;
  • 常量对象被转换成非常量对象。

 

四、使用const的一些建议

  • 要大胆的使用const,这将给你带来无尽的益处,但前提是你必须搞清楚原委;
  • 要避免最一般的赋值操作错误,如将const变量赋值,具体可见思考题;
  • 在参数中使用const应该使用引用或指针,而不是一般的对象实例,原因同上;
  • const在成员函数中的三种用法(参数、返回值、函数)要很好的使用;
  • 不要轻易的将函数的返回值类型定为const;
  • 除了重载操作符外一般不要将返回值类型定为对某个对象的const引用;
  • 任何不会修改数据成员的函数都应该声明为const 类型。

 

五、补充重要说明

 

  • 类内部的常量限制:使用这种类内部的初始化语法的时候,常量必须是被一个常量表达式

初始化的整型或枚举类型,而且必须是static和const形式。

  • 如何初始化类内部的常量:一种方法就是static 和 const 并用,在外部初始化,例如:

class A { public: A() {} private: static const int i; file://注意必须是静态的! };

const int A::i=3;另一个很常见的方法就是初始化列表: class A { public: A(int

i=0):test(i) {} private: const int i; }; 还有一种方式就是在外部初始化,

  • 如果在非const成员函数中,this指针只是一个类类型的;如果在const成员函数中,

this指针是一个const类类型的;如果在volatile成员函数中,this指针就是一个

volatile类类型的。

  • new返回的指针必须是const类型的。

京东实习面试总结

印象中是并没有看到jd,只是要求熟悉算法和数据结构+C艹…于是当时扔了份简历过去。

然后立刻就接到了一个电话,大概问了下一些基本情况。。以及。。你为什么不考研。。。

然后说之后会安排面试。。就杳无音信了。。然后突然有一天周末晚上11点接到短信说要安排面试orz…

【一面】

一面先是手写代码…都是面试套路题,就不说了…

哦其中一道题给出了优于面试官手中正解复杂度(nlgn)的复杂度的做法…

因为我说完我的做法给出了一点正确性的证明以后听他说了句“哦这题原来可以O(n)啊”

然后问了一点cpp基础。。。不记得问什么了。。反正也都很简单?

之后问了两个智力题吧。。。其中一个是7g+9g砝码称140g中的50g的问题…当时的确想了一下。。

再之后。。。开始问机器学习。。。。

这个时候我才意识到。。。这大概是算法岗啊。。。orz

然后我就全程装死。。。直言说不会orz…

然后面试官说,那我问问你微积分和概率论吧。。。。

我继续装死…

然后就结束了…结束的时候问了面试官有什么建议

他说。。建议我。。去读研。。。。。。去读研。。。。

心想一定gg了。。。于是就忘了这事。。。

 

【二面】

然后10天以后。。竟然接到电话。。自称是二面面试官。。。

还说看到一面面试官对我评价很高。。。

我:喵喵喵喵喵?

然后我当时直接就问了一句:但是我机器学习基本不会,怎么会评价高呢。。。。

面试官说:放心我不会问你这些。。。

之后约了面试,还是手写代码…

先是考了个尺取。。忘记题目了。。反正是那种被考烂的题。。。

然后第二个问题是手写快排。。。问了下快排相关的问题。。。

第三个问题是让我设计一个高效算法。。查询区间最大值。。。。。

我问查询次数多吗。。他说很多。。。我说可以用st表的rmq来做。。。

他说对,然后让我手写一下rmq的初始化函数…

再之后,问了一个top k问题…还好之前看群里的人讨论过orz…

最后一个问题问了蓄水池抽样…orz…

之前没看过这个算法,没有回答出来。。

 

第二天有一个貌似是部门负责人的人告诉我二面通过了。。。评价很高(我:?????)

说是可能还会有个HR面。。。让我保持联系。。。

【HR面】

不知道能不能称之为HR面。。。感觉就是HR姐姐确认一些问题?

先是问我。。你一个武汉的学生。。。怎么想到北京来了呢。。。

之后问了。。。以后的打算啊。。。有没有拿到其他offer啊。。。

然后确认了下薪资问题。。。。

说是offer流程要一周左右。。。让我耐心等待。。

 

然后果然等了快一周2333

【总结】

其实接到二面通知的时候,jd是我当时面过的几家里面的最差的一家了(害怕。。。这里最差显然是说我很多没答上来的意思好么2333。。。京东很强啊orz…不要误会啊QAQ)….能接到二面也是很神奇…想了想也只可能那个复杂度O(n)的解法起了作用吧2333

 

2017年3月更新archlinux后没有声音问题的解决办法

系统信息:

表现为不管外放还是耳机。。都没有声音。。。

解决办法:

 

参考资料

 

一致性哈希初探

原始论文:一致性哈希

本来不打算放的。。被批评说太不严谨orz..

说说自己的理解好了。。

大概就是。。。hash的时候。。一开始有n个桶。。你设计的函数是y=x%n…看起来美滋滋。。。

然后这时候突然一个桶不见了。。。如果按照之前设计的hash函数。。就变成了x%(n-1)…

这可能会造成大量的数据改变自己之前所在的桶。。。这是不可接受的。。。

或者是。。。当前的桶不够用了。。要增加一个桶。。。变成了x%(n+1)。。。也会出现类似情况。。。

我们的目的就是设计一种算法。。。使得当减少一个桶或者增加一个桶的时候。。。。变化尽可能小。。。

并且希望以后新放入的数据尽可能到新的桶中(?

桶是简化的模型。。。实际应用上。。。一致性哈希主要用在分布式系统中。。。每个桶就相当于一台服务器(?or something…不是很懂分布式的术语)

 

一致性哈希算法

tencent2012笔试题附加题

问题描述: 例如手机朋友网有n个服务器,为了方便用户的访问会在服务器上缓存数据,因此用户每次访问的时候最好能保持同一台服务器。

已有的做法是根据ServerIPIndex[QQNUM%n]得到请求的服务器,这种方法很方便将用户分到不同的服务器上去。但是如果一台服务器死掉了,那么n就变为了n-1,那么ServerIPIndex[QQNUM%n]与ServerIPIndex[QQNUM%(n-1)]基本上都不一样了,所以大多数用户的请求都会转到其他服务器,这样会发生大量访问错误。

问: 如何改进或者换一种方法,使得:

(1) 一台服务器死掉后,不会造成大面积的访问错误,

(2)原有的访问基本还是停留在同一台服务器上;

(3)尽量考虑负载均衡。(思路:往分布式一致哈希算法方面考虑。)

  1. 最土的办法还是用模余方法:做法很简单,假设有N台服务器,现在完好的是M(M<=N),先用N求模,如果不落在完好的机器上,然后再用N-1求模,直到M.这种方式对于坏的机器不多的情况下,具有更好的稳定性。
  2. 一致性哈希算法。

下面,本文剩下部分重点来讲讲这个一致性哈希算法。

应用场景

在做服务器负载均衡时候可供选择的负载均衡的算法有很多,包括: 轮循算法(Round Robin)、哈希算法(HASH)、最少连接算法(Least Connection)、响应速度算法(Response Time)、加权法(Weighted )等。其中哈希算法是最为常用的算法.

典型的应用场景是: 有N台服务器提供缓存服务,需要对服务器进行负载均衡,将请求平均分发到每台服务器上,每台机器负责1/N的服务。

常用的算法是对hash结果取余数 (hash() mod N):对机器编号从0到N-1,按照自定义的hash()算法,对每个请求的hash()值按N取模,得到余数i,然后将请求分发到编号为i的机器。但这样的算法方法存在致命问题,如果某一台机器宕机,那么应该落在该机器的请求就无法得到正确的处理,这时需要将当掉的服务器从算法从去除,此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算;如果新增一台机器,会有N /(N+1)的服务器的缓存数据需要进行重新计算。对于系统而言,这通常是不可接受的颠簸(因为这意味着大量缓存的失效或者数据需要转移)。那么,如何设计一个负载均衡策略,使得受到影响的请求尽可能的少呢?

在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了Consistent Hashing算法,可以说Consistent Hashing 是分布式系统负载均衡的首选算法。

Consistent Hashing算法描述

下面以Memcached中的Consisten Hashing算法为例说明。

consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出,目前在 cache 系统中应用越来越广泛;

基本场景

比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache ;

hash(object)%N

一切都运行正常,再考虑如下的两种情况;

  1. 一个 cache 服务器 m down 掉了(在实际应用中必须要考虑这种情况),这样所有映射到 cache m 的对象都会失效,怎么办,需要把 cache m 从 cache 中移除,这时候 cache 是 N-1 台,映射公式变成了 hash(object)%(N-1) ;
  2. 由于访问加重,需要添加 cache ,这时候 cache 是 N+1 台,映射公式变成了 hash(object)%(N+1) ;

1 和 2 意味着什么?这意味着突然之间几乎所有的 cache 都失效了。对于服务器而言,这是一场灾难,洪水般的访问都会直接冲向后台服务器;再来考虑第三个问题,由于硬件能力越来越强,你可能想让后面添加的节点多做点活,显然上面的 hash 算法也做不到。

有什么方法可以改变这个状况呢,这就是consistent hashing。

hash 算法和单调性

Hash 算法的一个衡量指标是单调性( Monotonicity ),定义如下:

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。

容易看到,上面的简单 hash 算法 hash(object)%N 难以满足单调性要求。

consistent hashing 算法的原理

consistent hashing 是一种 hash 算法,简单的说,在移除 / 添加一个 cache 时,它能够尽可能小的改变已存在 key 映射关系,尽可能的满足单调性的要求。

下面就来按照 5 个步骤简单讲讲 consistent hashing 算法的基本原理。

环形hash 空间

考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值,也即是 0~2^32-1 次方的数值空间;我们可以将这个空间想象成一个首( 0 )尾( 2^32-1 )相接的圆环,如下面图 1 所示的那样。

图 1 环形 hash 空间

把对象映射到hash 空间

接下来考虑 4 个对象 object1~object4 ,通过 hash 函数计算出的 hash 值 key 在环上的分布如图 2 所示。

hash(object1) = key1;

… …

hash(object4) = key4;

图 2 4 个对象的 key 值分布

把cache 映射到hash 空间

Consistent hashing 的基本思想就是将对象和 cache 都映射到同一个 hash 数值空间中,并且使用相同的hash 算法。

假设当前有 A,B 和 C 共 3 台 cache ,那么其映射结果将如图 3 所示,他们在 hash 空间中,以对应的 hash值排列。

hash(cache A) = key A;

… …

hash(cache C) = key C;

图 3 cache 和对象的 key 值分布

说到这里,顺便提一下 cache 的 hash 计算,一般的方法可以使用 cache 机器的 IP 地址或者机器名作为hash 输入。

把对象映射到cache

现在 cache 和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了,接下来要考虑的就是如何将对象映射到 cache 上面了。

在这个环形空间中,如果沿着顺时针方向从对象的 key 值出发,直到遇见一个 cache ,那么就将该对象存储在这个 cache 上,因为对象和 cache 的 hash 值是固定的,因此这个 cache 必然是唯一和确定的。这样不就找到了对象和 cache 的映射方法了吗?!

依然继续上面的例子(参见图 3 ),那么根据上面的方法,对象 object1 将被存储到 cache A 上; object2和 object3 对应到 cache C ; object4 对应到 cache B ;

考察cache 的变动

前面讲过,通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性,当 cache 有所变动时,cache 会失效,进而对后台服务器造成巨大的冲击,现在就来分析分析 consistent hashing 算法。

移除 cache

考虑假设 cache B 挂掉了,根据上面讲到的映射方法,这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache ( cache C )之间的对象,也即是本来映射到 cache B 上的那些对象。

因此这里仅需要变动对象 object4 ,将其重新映射到 cache C 上即可;参见图 4 。

图 4 Cache B 被移除后的 cache 映射

添加 cache

再考虑添加一台新的 cache D 的情况,假设在这个环形 hash 空间中, cache D 被映射在对象 object2 和object3 之间。这时受影响的将仅是那些沿 cache D 逆时针遍历直到下一个 cache ( cache B )之间的对象(它们是也本来映射到 cache C 上对象的一部分),将这些对象重新映射到 cache D 上即可。

因此这里仅需要变动对象 object2 ,将其重新映射到 cache D 上;参见图 5 。

图 5 添加 cache D 后的映射关系

虚拟节点

考量 Hash 算法的另一个指标是平衡性 (Balance) ,定义如下:

平衡性

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。

hash 算法并不是保证绝对的平衡,如果 cache 较少的话,对象并不能被均匀的映射到 cache 上,比如在上面的例子中,仅部署 cache A 和 cache C 的情况下,在 4 个对象中, cache A 仅存储了 object1 ,而 cache C 则存储了 object2 、 object3 和 object4 ;分布是很不均衡的。

为了解决这种情况, consistent hashing 引入了“虚拟节点”的概念,它可以如下定义:

“虚拟节点”( virtual node )是实际节点在 hash 空间的复制品( replica ),一实际个节点对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以 hash 值排列。

仍以仅部署 cache A 和 cache C 的情况为例,在图 4 中我们已经看到, cache 分布并不均匀。现在我们引入虚拟节点,并设置“复制个数”为 2 ,这就意味着一共会存在 4 个“虚拟节点”, cache A1, cache A2 代表了 cache A ; cache C1, cache C2 代表了 cache C ;假设一种比较理想的情况,参见图 6 。

图 6 引入“虚拟节点”后的映射关系

此时,对象到“虚拟节点”的映射关系为:

objec1->cache A2 ; objec2->cache A1 ; objec3->cache C1 ; objec4->cache C2 ;

因此对象 object1 和 object2 都被映射到了 cache A 上,而 object3 和 object4 映射到了 cache C 上;平衡性有了很大提高。

引入“虚拟节点”后,映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache时的映射关系如图 7 所示。

图 7 查询对象所在 cache

“虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。例如假设 cache A 的 IP 地址为202.168.14.241 。

引入“虚拟节点”前,计算 cache A 的 hash 值:

Hash(“202.168.14.241”);

引入“虚拟节点”后,计算“虚拟节”点 cache A1 和 cache A2 的 hash 值:

Hash(“202.168.14.241#1”); // cache A1

Hash(“202.168.14.241#2”); // cache A2

 

 

Linux 下各个目录的作用及内容

参考:wiki_FHS

其实这东西。。。虽然有一个统一的标准。。。但是不同发行版。。。或者同一个发行版的不同版本。。。差异貌似都蛮大的。。。所以只是理论上各个目录的作用。。。可能和具体的发行版不符。。。

Linux 目录

在 Linux 下,我们看到的是文件夹(目录): img 在早期的 UNIX 系统中,各个厂家各自定义了自己的 UNIX 系统文件目录,比较混乱。Linux 面世不久后,对文件目录进行了标准化,于1994年对根文件目录做了统一的规范,推出 FHS ( Filesystem Hierarchy Standard ) 的 Linux 文件系统层次结构标准。FHS 标准规定了 Linux 根目录各文件夹的名称及作用,统一了Linux界命名混乱的局面。

无论何种版本的 Linux 发行版,桌面、应用是 Linux 的外衣,文件组织、目录结构才是Linux的内心。

FHS(英文: Filesystem Hierarchy Standard 中文:文件系统层次结构标准),多数 Linux 版本采用这种文件组织形式,FHS 定义了系统中每个区域的用途、所需要的最小构成的文件和目录同时还给出了例外处理与矛盾处理。 FHS 定义了两层规范,第一层是, / 下面的各个目录应该要放什么文件数据,例如 /etc应该要放置设置文件, /bin/sbin 则应该要放置可执行文件等等。

第二层则是针对 /usr/var 这两个目录的子目录来定义。例如 /var/log 放置系统登录文件、 /usr/share 放置共享数据等等。

FHS 是根据以往无数 Linux 用户和开发者的经验总结出来的,并且会维持更新,FHS 依据文件系统使用的频繁与否以及是否允许用户随意改动(注意,不是不能,学习过程中,不要怕这些),将目录定义为四种交互作用的形态,如下表所示:

img

/:根目录,一般根目录下只存放目录,不要存放件,/etc、/bin、/dev、/lib、/sbin应该和根目录放置在一个分区中

img

/bin: /usr/bin: 可执行二进制文件的目录,如常用的命令ls、tar、mv、cat等。

/boot:放置linux系统启动时用到的一些文件。/boot/vmlinuz 为 linux 的内核文件,以及 /boot/gurb。建议单独分区,分区大小100M即可

/dev:存放linux系统下的设备文件,访问该目录下某个文件,相当于访问某个设备,常用的是挂载光驱 mount /dev/cdrom /mnt。

/etc:系统配置文件存放的目录,不建议在此目录下存放可执行文件,重要的配置文件有 /etc/inittab、/etc/fstab、/etc/init.d、/etc/X11、/etc/sysconfig、/etc/xinetd.d修改配置文件之前记得备份。

注:/etc/X11 存放与 x windows 有关的设置。

/home:系统默认的用户家目录,新增用户账号时,用户的家目录都存放在此目录下,~表示当前用户的家目录,~edu 表示用户 edu 的家目录。建议单独分区,并设置较大的磁盘空间,方便用户存放数据

/lib: /usr/lib: /usr/local/lib:系统使用的函数库的目录,程序在执行过程中,需要调用一些额外的参数时需要函数库的协助,比较重要的目录为 /lib/modules。

/lost+fount:系统异常产生错误时,会将一些遗失的片段放置于此目录下,通常这个目录会自动出现在装置目录下。如加载硬盘于 /disk 中,此目录下就会自动产生目录 /disk/lost+found

/mnt: /media:光盘默认挂载点,通常光盘挂载于 /mnt/cdrom 下,也不一定,可以选择任意位置进行挂载。

/opt:给主机额外安装软件所摆放的目录。如:FC4使用的Fedora 社群开发软件,如果想要自行安装新的 KDE 桌面软件,可以将该软件安装在该目录下。以前的 Linux 系统中,习惯放置在 /usr/local 目录下

/proc:此目录的数据都在内存中,如系统核心,外部设备,网络状态,由于数据都存放于内存中,所以不占用磁盘空间,比较重要的目录有 /proc/cpuinfo、/proc/interrupts、/proc/dma、/proc/ioports、/proc/net/* 等。

/root:系统管理员root的家目录,系统第一个启动的分区为 /,所以最好将 /root和 /放置在一个分区下。

/sbin: /usr/sbin: /usr/local/sbin:放置系统管理员使用的可执行命令,如fdisk、shutdown、mount 等。与 /bin 不同的是,这几个目录是给系统管理员 root使用的命令,一般用户只能”查看”而不能设置和使用。

/tmp:一般用户或正在执行的程序临时存放文件的目录,任何人都可以访问,重要数据不可放置在此目录下

/srv:服务启动之后需要访问的数据目录,如 www 服务需要访问的网页数据存放在 /srv/www 内。

/usr:应用程序存放目录,/usr/bin 存放应用程序,/usr/share 存放共享数据,/usr/lib 存放不能直接运行的,却是许多程序运行所必需的一些函数库文件。/usr/local: 存放软件升级包。/usr/share/doc: 系统说明文件存放目录。/usr/share/man: 程序说明文件存放目录,使用 man ls 时会查询 /usr/share/man/man1/ls.1.gz 的内容建议单独分区,设置较大的磁盘空间

/var:放置系统执行过程中经常变化的文件,如随时更改的日志文件 /var/log,/var/log/message:所有的登录文件存放目录,/var/spool/mail:邮件存放的目录,/var/run:程序或服务启动后,其PID存放在该目录下。建议单独分区,设置较大的磁盘空间

一切皆文件

Linux 对数据文件(.mp3、.bmp),程序文件(.c、.h、*.o),设备文件(LCD、触摸屏、鼠标),网络文件( socket ) 等的管理都抽象为文件,使用统一的方式方法管理。

文件分类:

1)普通文件( 数据文件 )

普通文件是用于存放数据、程序等信息的文件,一般都长期地存放在外存储器(磁盘)中。普通文件又分为文本文件和二进制文件。

2)目录文件

目录文件是文件系统中一个目录所包含的目录项所组成的文件。

3)设备文件

设备文件是用于为操作系统与设备提供连接的一种文件。在Linux系统中将设备作为文件来处理,操作设备就像是操作普通文件一样。每一个设备对应一个设备文件,存放在 /dev 目录中。

5)链接文件

似于 windows 下的快捷方式,链接又可以分为软链接(符号链接)和硬链接。

6)管道文件

管道文件主要用于在进程间传递数据的一种特殊文件。

7)套接口文件

主要用于不同计算机间网络通信的一种特殊文件。

img img