慎用hash_map的遍历器

On 2011/09/21, in 未分类, by qiuxiafei
1

今天同事写了这么一段代码:

1
2
3
4
5
6
7
8
//mp is a hash_map
Iterator_t it = mp.begin();
if(it == mp.end()) {
    ....
}
else {
   ....
}

发现程序跑的奇慢无比,原因就在mp.begin()上面!

hash_map这个东西,好好理解一下就明白,通过hash把key分布在一个大的空间内。空间内的key分布式相当离散的,要再上面做遍历操作肯定得遍历各个hash bucket(当然,你自己维护一个链表除外),使用遍历器的代价是十分高昂的,而这个begin()也不例外!代码里头也确实这么写的(/usr/include/c++/4.1.1/ext/hashtable.h):

1
2
3
4
5
6
7
8
      iterator
      begin()
      {
    for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
      if (_M_buckets[__n])
        return iterator(_M_buckets[__n], this);
    return end();
      }

所以,使用hash_map的时候一定要尽量避开iterator。

p.s. 原文地址:http://chunyemen.org/archives/588, 欢迎访问纯爷们的小生活

Tagged with:
 

const std::map的初始化

On 2011/02/19, in 我和小老婆之间的事, by qiuxiafei
2

其实,这是一个很弱的问题,以前我初始化一个std::map的时候是直接把初始值的pair依次insert到map里头去。可是前几天,我想使用的是一个const static map,然后就直接傻叉愣住了,直接insert肯定不行了,人家是const的。后来,google了一阵才知道答案…

map的构造函数是支持用一个区间[start, end)来初始化,我们也经常用这种方法来构造其他std容器,比如用一个数组作为区间去初始化一个vector:

1
2
int array[] = {1, 2, 3, 4};
vector<int> int_vec(array, array + 4);

那么,应该用什么类型的数组来初始化map呢?看代码吧,不说了….说起来丢人阿…

1
2
3
4
5
6
7
const map<string, int>::value_type init_value[] =
{
    map<value_type>("a", "0""),
    map<value_type>("b", "1"),
    map<value_type>("c", "2")
}
const map<string, int> mp(init_value, init_value + 3);
额,就是这样…那么value_type是什么呢?是std::pair<const _Key, _Tp>
p.s. 原文地址:http://chunyemen.org/archives/537, 欢迎访问纯爷们的小生活
p.s.s 这个html编码转换有问题阿…尖括号怎么变成&lt;和&gt;了,谁知道咋办阿?代码高亮我用的WP-CODEBOX
Tagged with:
 

废话般的引言

脚本语言的牛叉在于其将一般语言的“编辑-编译-链接-运行”的过程改变为“编辑-运行”的简单方式,使其在系统管理层面有广泛的应用,shell script便是有力的证明。此外,脚本语言都有丰富的三方库,应用场景更是更加广泛。从web server到图像处理再到电脑游戏,只要有相应的三方库,脚本语言变能发挥“胶水”的作用,将各种库“粘合”起来,极大降低了开发的代价。

Perl作为一门古老的、由语言学家发明语言,在文字处理方面Perl有着无可比拟的优势,在互联网初期,perl更是CGI的必备工具。Perl也有强大的三方库,CPan上几乎有你想要的任何东西。其实,我们也可以开发自己的perl三方库。今天这篇文章就做一个小小的尝试,抛砖引玉!

需要知道的介绍

在C/C++中,如果我们需要使用一个库的时候,一般需要一个.h头文件和动态或者静态链接库,前者定义了接口,后者封装了实现。同样,我们也可以用一个C/C++的头文件和库,封装一个perl的package。可以把这个过程看作从一个语言到另一个语言的映射,完成这个映射需要做两件事情:一是数据类型的映射,二是接口的映射。完成了这两项映射,也就基本能够在一种语言中使用另外一个语言的库了。

XS是一种用于描述接口的文件格式,当我们希望把我们的C/C++库映射成Perl的package时,需要在一个.xs文件中描述接口的映射。另外,我们还需要进行数据类型的映射,下文提到的perlobject.map可以在这里找到。

C++中的鸭子

我们将以一只鸭子作为今天的例子。我们定义一个Duck类,封装一下鸭子的名字,再给出一个swim的方法,其中我们会使用stl的数据类型作为成员变量,但是我们的接口不会包含复杂的数据类型(因为这个现成的数据类型文件只定义了基本的数据类型映射)。好吧,这只鸭子是这样的:

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
43
44
45
46
47
48
49
50
51
/*
  Duck.h ---
*/
#ifndef INCLUDED_DUCK_H
#define INCLUDED_DUCK_H 1
#include &lt;  string  &gt;
using std::string;
class Duck
{
public:
    Duck(char*);
    const char* getName();
    void swim();
    ~Duck(){}
private:
    bool swimming;
    string name;
};
#endif /* INCLUDED_DUCK_H */
 
/*
  Duck.cpp ---
*/
 
#include "Duck.h"
#include &lt;  cstdio  &gt;
 
using namespace std;
 
Duck::Duck(char* n) :
    swimming(false), name(n)
{
}
const char* Duck::getName()
{
    return name.c_str();
}
void Duck::swim()
{
    if (!swimming)
    {
        printf("%s, ok .. go swimming\n", name.c_str());
        swimming = true;
    }
    else
    {
        printf("%s is already swimming , stop\n", name.c_str());
        swimming = false;
    }
    return;
}

然后我们编译他们,得到libduck.so

g++ -g -Wall -fpic -shared -o libduck.so Duck.cpp

这样,我们就可以拿着这个libduck.so和Duck.h进入下一个流程,加工我们的Perl Package了!当然,你也可以写一个test.cpp来测试下这个.h和.so能不能用,需要注意的是,需要指定.so的路径

export LD_LIBRARY_PATH=/path/to/the/.so/:$LD_LIBRARY_PATH

游向Perl的鸭子

这里我们使用h2xs来创建这个Perl Package的初始环境。h2xs,顾名思义就是把.h转换为.xs,不过这里 我们还是手动来创建:

h2xs -A -n DuckPackage

然后,DuckPackage目录下就有了一些东西,我们需要关注的是DuckPackage.xs, Makefile.PL。DuckPackage.xs是定义接口映射的,Makefile.PL是一个Perl脚本,在里头定义编译和链接相关的选项。

接着,把之前提到的perlobject.map文件复制到当前目录中,把Duck.h和libduck.so也放进来。再创立一个文件叫typemap,内容如下:

TYPEMAP
Duck* O_OBJECT

perlobject.map定义了C/C++基础数据类型到Perl的映射,这也是为什么Duck.h中的的接口都使用基础数据类型,当然你也可以自己做string、map、set等等到Perl数据类型的映射,做好了麻烦告诉我一下~

好,我们可以开始修改DuckPackage.xs了,以下是修改完成后的样子,粗体是修改的部分

#ifdef __cplusplus
extern “C”{
#endif

#include “EXTERN.h”
#include “perl.h”
#include “XSUB.h”
#ifdef __cplusplus
}
#endif

#include “ppport.h”
#include <Duck.h>
using namespace std;

MODULE = DuckPackage            PACKAGE = DuckPackage

Duck*
Duck::new(char * name)

char*
Duck::getName()

void
swim()

void
Duck::DESTROY()

为什么要加上extern “C”呢?因为我们是C++!接下来你会看到,在编译的时候使用我们使用g++。所以,对于那些Perl提供的C Api,我们要用extern “C”把他们包围。在extern “C”之外,我们就可以把Duck.h include进来了。对于一般的成员方法,映射的写法跟.h里头没有什么区别,注意两点就好:1. 末尾没有分号;2. 参数一定要写全类型+参数名。对于构造函数和析构函数,按照上述的方法写就好了~~

接下来看Makefile.PL:

use 5.008005;
use ExtUtils::MakeMaker;

$CC = “g++”;
# See lib/ExtUtils/MakeMaker.pm for details of how to influence
# the contents of the Makefile that is written.

WriteMakefile(
NAME              => ‘DuckPackage’,
VERSION_FROM      => ‘lib/DuckPackage.pm’, # finds $VERSION
PREREQ_PM         => {}, # e.g., Module::Name => 1.1
($] >= 5.005 ?     ## Add these new keywords supported since 5.005
(ABSTRACT_FROM  => ‘lib/DuckPackage.pm’, # retrieve abstract from module
AUTHOR         => ‘A. U. Thor <xiafei@localdomain>’) : ()),
LIBS              => ['-L./ -lduck'], # e.g., ‘-lm’
DEFINE            => ”, # e.g., ‘-DHAVE_SOMETHING’
INC               => ‘-I.’, # e.g., ‘-I. -I/usr/include/other’
# Un-comment this if you add C files to link with later:
# OBJECT            => ‘$(O_FILES)’, # link all the C files too
‘CC’ => $CC,
‘LD’ => ‘$(CC)’,
‘XSOPT’ => ‘-C++’,
‘TYPEMAPS’ => ['perlobject.map' ],

);

Makefile.PL没有什么好说的,注意LIBS和INC两个地方别写错了就好。

然后,我们再写一个test.pl吧,同样放在这个目录下。

1
2
3
4
5
6
7
use DuckPackage;
 
my $duck = new DuckPackage("Dan");
my $name = $duck-&gt;getName();
$duck->swim();
$duck->swim();
print "$name\n";

好了,我们可以开始了!

perl Makefile.PL
make
make test

如果它告诉你Result: PASS,那么恭喜恭喜,可以接着make install了。如果不过,再回头看看文章吧,good luck!

p.s. 原文地址:http://chunyemen.org/archives/493, 欢迎访问纯爷们的小生活

Tagged with:
 

delete NULL

On 2010/10/19, in 我和小老婆之间的事, by qiuxiafei
0

有个传说中的好习惯,每当delete一个指针的时候,要先判断是不是NULL。比如:

1
2
if ( p != NULL)
    delete p;

心里一直很敬畏delete NULL这件事情,生怕会有什么异常或者别的。在与同事交流时,才发现自己原来2了这么久。

Primer中说,delete NULL是合法、安全但没有任何意义的。
那么,好的习惯应该是,指针未初始化的时候赋值为NULL,delete之后赋值为NULL。否则,当delete一个已经delete过的悬垂指针(dangling pointer)时,就会导致double delete,glibc会在程序崩溃的时候告诉你。

p.s原文地址:http://chunyemen.org/archives/469, 欢迎访问纯爷们的小生活

Tagged with:
 

atoi和strtol的比较

On 2010/04/23, in 我和小老婆之间的事, by qiuxiafei
0

atoi是一个常用的函数,用于将字符串转换成int。而strtol是atoi的增强版,这么牛叉的增强版,我竟然昨天才知道,真是…

两个函数声明如下:

1
2
int atoi(const char *str);
long strtol(const char *nptr, char **endptr, int base);

其中,strtol第二个参数endptr是转换停止的地址,把一个char *的指针的地址作为参数传入。最后一个参数base是转换的进制,支持2~64。endptr跟base有关,是nptr中第一个该base下非法的字符地址。

以下讨论基于Windows,vs2008。

1.越界

越界时,两者都返回INT_MAX或者INT_MIN,同时将errno置为ERANGE(34)。

2.errno

上面已经提到越界时会改变errno。同时也注意到,如果没有出错,两个函数都不会去改变errno,即errno保持之前的值。所以,在判断转换是否出错时,只用errno判断是不靠谱的,这也是atoi的缺陷。

3.输入格式

atoi的合法输入格式为:[whitespace] [{+ | -}] [digits]

strtol的输入格式为:[whitespace] [{+ | –}] [0 [{ x | X }]] [digits],格式是否合法还与base有关。比如,2进制中仅0,1合法,16进制中除了数字还包括x、a、b、c、d、e、f。

当输入格式不合法时,两个函数都会丢弃从第一个不合法字符及其之后的所有字符,保留之前字符的转换结果,即,32.34的atoi转换结果是32。而strtol函数的会将第一个非法字符的的地址保存到endptr中,从而判定整个字符串是否合法。这也是strtol比atoi更好的原因。

所以,在字符串转换为整数的时候,最好使用strtol,只有在endptr指向’\0′且errno没有指示越界时,返回的结果才是有效的。

Mingw gcc3.4.5下的atoi

没有Linux,只能用Mingw测试一下。

1.越界

越界时,不会返回INT_MAX或者INT_MIN,而是(n+2^31) %(2^32)-2^31,也就是考虑溢出的情况下,从0开始执行n次累加的结果。

2.errno

无论什么情况下,都不会改变errno。

p.s. 原文地址http://chunyemen.org/archives/357 ,欢迎访问纯爷们的小生活

Tagged with:
 

欢迎转载,转载请保留原文链接:http://chunyemen.org/blog/archives/260
==================================================
说完了找工作的历程,那么从现在开始,说说怎么准备。
求职无非是简历、笔试和面试三关,当然rp也是一个十分重要的问题,不过本文不打算详细讨论。

简历

我的观点是,简历宜简洁明了,尤其是技术类的同学,把简历做的十分花哨反而显得“没有技术含量”。
简历以技术为主,其他为辅
比如,各种项目经历、比赛经历等等。其他方面,如果不是特别突出或者有很好的点缀作用,尽量简洁。
宜巧不宜假。有些确实需要适当的修饰,这些修饰以实际作用为主,最好能有数字等有力地支撑。但是切忌编造!技术上的东西,面试官一问就知道你的底细,因为造假而被揭穿反而很不利。慎用“精通”二字。
熟悉自己简历上提到的所有东西。比如,写了“熟悉网络编程”,就要准备好面试官问你这方面的问题,不要为了充门面写很多不熟悉,甚至不懂的东西上去。
模板,模板很重要,可以让你事半功倍。我的简历是在有名的“哈佛模板”上改的,有兴趣可以去搜一下。

基础知识

有些知识是笔试面试都会考的,只是考察的方式不同而已。这里一起说一下。
C/C++基础
这部分很多很杂,主要是一些边边角角的东西,很零碎。推荐看《程序员面试宝典》,这里有pdf。这本书基本上包含了笔试面试所需要的语言基础方面常考的东西,什么sizeof啊,函数指针啊、const啊,一些比较恶心的东西都讲得挺不错。C++方面考得并不太多,重载操作符,虚函数、各种继承方式、虚析构函数比较常考。
数据结构和算法
就看看自己手中的教材吧,好好看一遍,重点是排序 、查找、各种树。如果你开始准备的时间很早,时间比较充裕,建议把常见的数据结构和算法都写一遍,包括:插入\快速\堆\希尔\归并排序,hash\二分查找,二叉树的查找增删,链表。其他的,比如AVL树、红黑树、Top-K问题,外部排序也要好好看看。如果还有富裕时间,强烈推荐《编程之美》,这里有pdf。不仅仅对于笔试面试,在开拓思路,提高分析问题能力方面,这本书都很有帮助。
其他
剩下的就取决于个人了。比如,如果你算法比较强,可以复习一下dp、kmp、图论、概率、组合方面的东西。过于复杂的面试官也不会问你。其他的类推。

Tagged with: