Jul 8

ooxx的const 不指定

felix021 @ 2009-7-8 00:13 [IT » 程序设计] 评论(3) , 引用(0) , 阅读(4696) | Via 本站原创
咱们来对比一下这5个东西:
char ** a;
const char ** b;
char * const * c;
const char * const * d;
const char * const * const e;

——天哪,这都是什么东西?用5个小程序来解释一下。。或许你可以看得懂?
如果你急着和mm去约会,直接跳到文末,有比较简洁的说明。

#include <iostream>
#include <cstring>
using namespace std;

void test1(){
    char **s; //s是数组的指针;
    s = NULL;
    s = new char*[4];
    for (int i = 0; i < 4; ++i){
        s[i] = new char[10];
        strcpy(s[i], "test");
    }
    for (int i = 0; i < 4; ++i){
        printf("%s\n", s[i]);
    }
    for (int i = 0; i < 4; ++i){
        delete[] s[i];
    }
    delete[] s;
}

void test2(){
    const char **s; //s是指向字符串常量的指针
    s = NULL;
    char b[4][10] = {"a","b","c","d"};
    s = new const char*[4];
    for (int i = 0; i < 4; ++i){
        s[i] = b[i]; // OK
        //s[i][0] = 'd'; //这句要报错,因为s[i]指向的是字符串常量
                    //即使b[i]字符串本不是常量(编译期间添加的属性)
    }
    for (int i = 0; i < 4; ++i){
        printf("%s\n", s[i]);
    }
    delete[] s;
}

void test3(){
    char * const * s; //s指向常量数组,数组的每一个元素是字符指针常量。
                //数组的元素不可改,但数组元素指向的字符串可修改    
    s = NULL;// s不是常量
    char a[4][10] = {"aa", "bb", "cc", "dd"};
    char * const(b[4]) = {a[0], a[1], a[2], a[3]};
    s = b;
    for (int i = 0; i < 4; ++i){
        s[i][1] = 'd'; //OK
        //s[i] = NULL; //报错,因为s[i]是常量
        printf("%s\n", s[i]);
    }
}

void test4(){
    const char * const * s; //s指向一个常量指针数组
    //数组的每一个元素是字符指针常量,指向字符串常量(绕口令阿这是。。。)
    s = NULL;// s不是常量
    char a[4][10] = {"aa", "bb", "cc", "dd"};
    char * const(b[4]) = {a[0], a[1], a[2], a[3]};
    s = b;
    for (int i = 0; i < 4; ++i){
        //s[i][1] = 'd'; //报错,因为s[i][j]是常量
        //s[i] = NULL; //报错,因为s[i]是常量
        printf("%s\n", s[i]);
    }
}

void test5(){
    char a[4][10] = {"aa", "bb", "cc", "dd"};
    const char * const(b[4]) = {a[0], a[1], a[2], a[3]};
    const char * const * const s = b;
    //s是一个常量指针,指向一个常量指针数组
    //数组的每一个元素是字符指针常量,指向字符串常量(这才是绕口令!)
    //s = NULL; //Error, s是常量
    for (int i = 0; i < 4; ++i){
        //s[i][1] = 'd'; //报错,因为s[i][j]是常量
        //s[i] = NULL; //报错,因为s[i]是常量
        printf("%s\n", s[i]);
    }
}

int main(){
    test5();
    return 0;
}


OK,其实有一种很简单的阅读方法:从右向左读定义,结果就是——
char ** s;
s是一个指针1,指向一个指针2, 指针2指向char

const char ** s;
s是一个指针1,指向一个指针2,指针2指向char,char是常数

char * const * s;
s是一个指针1,指向一个常量1,常量1是个指针2,指针2指向char

const char * const * s;
s是一个指针1,指向一个常量1,常量1是个指针2,指针2指向char,char是常数

const char * const * const s;
s是一个常量1,常量1是一个指针1,指针1指向一个常量2,常量2是个指针2,指针2指向char,char是常数
Jun 23
坦白说,我不确定这个东西是不是叫做败者树,因为我觉得它就是以前写过n遍的线段树的一个简单变种。
在线段树的每个节点存储v, i,分别表示该区间内最小值和最小值所在单元的索引。
建立好线段树以后,每次取出整个区间的最小值,然后将该值来源的那一路的下一个数字填充进去
如果那一路已经没有下一个数字了,就填一个max进去,然后递归地更新其所有祖先节点。
这个过程有点像heap的sift_up。

代码如下:
Jun 23

采用堆的多路归并 不指定

felix021 @ 2009-6-23 00:38 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(3285) | Via 本站原创
一般数据结构上用败者树来实现,这东西我没写过,所以暂时忽略之。
改用相对比较熟悉的heap来处理,写了一个class heap。
为了方便采用一个 5 x 5 的数组来存储需要归并的数据;很容易可以扩展到不定长的不同数据组。
明天再试着写一下败者树。

代码如下:
Jun 16

scanf: 你不知道的 不指定

felix021 @ 2009-6-16 13:28 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(3607) | Via 本站原创
zz from http://c-faq-chn.sourceforge.net/ccfaq/node206.html#q:12.17

13.15 当我用 "%d\n" 调用 scanf 从键盘读取数字的时候, 好像要多输入一行函数才返回。
可能令人吃惊, \n 在 scanf 格式串中不表示等待换行符, 而是读取并放弃所有的空白字符

@2oo911o8
前些天试了一下,其实所谓\n代表所有空白字符,倒不如说scanf将所有空白字符等同视之:
在这里你用scanf(" "); scanf("\t");效果都是一样的。
Jun 14
nth element, 也就是要找出一个数列中排名第n的那个数。

很直观地,把所有的数排序以后,就可以得出这nth element了。
快排测试:4.5s,1千万个int。

仔细想一下,这似乎有点浪费:其实只要找出最大的n个就行了。
如果n比较小,我们可以直接用选择排序。
这个程序太简单了,懒得测试。

然后再仔细想一下,发现还是有点浪费,其实前n个数不需要排序。
于是可以用最小堆来实现。
测试结果:3.02s,1千万个int,n = 500。

然后你可能会发现,STL里面有个函数,叫做nth_element,就是用来做这个的
测试一下:3.4s,1千万个int, n = 500。

如果想要深入了解,那么实际上这个nth_element使用的算法是快速划分。
它其实就是不完全的快速排序,只要递归地排序需要排序的部分就可以了。
自写代码测试:3.4s,1千万个int, n = 500。

------

从上面可以看出,在k=500(N = 10,000,000)时,最小堆是最快的,其次是快速划分,快排当然最慢。

最小堆的时间复杂度是 O( N * log(k) )
快速划分虽然平均时间复杂度是O(C*N)(但是C比较大),但是最坏时间复杂度是O(N^2)(所以随机化很重要!可以避免RPWT!)
快排就不用说了,撑死 O(N * log(N) ),最坏时间复杂度也可能是O(N^2)。

似乎最小堆是最快的,快速划分慢些,但是它们各有自己的适用范围:

当 k 接近 N / 2时,最小堆的时间复杂度其实就相当于一个堆排,事实上还不如快排。
所以最小堆的适用范围是k << N时的情况,或者当k 很接近N, 可以转化成 N-k << N的情况。

而快速划分的算法本身决定了其复杂度和 k 的大小无关,所以当 k 接近 N/2 时,快速划分显然更优。

可是还有另一种情况,也是大公司面试的时候很可能会问到的题目:

给你200亿个整数,找出TOP500000。

第一次遇到这个问题,估计大多数人直接口突白沫了吧。

200亿,对一般PC而言,内存显然存不下,需要保存在辅存中,而辅存的IO速度。。。

所以你应该尽可能少地扫描。

于是这时候最小堆就是最优解决方案:只扫描一遍,就可以得出结果。

------

代码如下:
Jun 14
回忆一下tx的二面,有一道题是这样的:

假设有1kw个身份证号,以及他们对应的数据。身份证号可能重复,要求找出出现次数最多的身份证号。
一个很显然的做法是,hash之,O(n)搞定。这前提是内存中可以存下。
如果是中国的13亿人口,内存中存不下呢?借用磁盘,多次扫描?磁盘IO的速度慢得能让你疯掉。
这时候你终于感受到,中国人口真TMD多阿。。。

--

然后再看看今天的astar复赛第一题:
Jun 14

map/set的效率 不指定

felix021 @ 2009-6-14 15:28 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(7077) | Via 本站原创
算是续上篇文章吧。

上篇文章最后我有一个不是太好的总结(当然,在上一篇应该成立):
引用
结论:在大多数情况下,我们可以迷信STL之父对效率的迷信。

我们知道vector和数组在基本操作上都是同一数量级的,而且事实上它们的常数也没有多少差别
所以我们可以放心地用vector来替换数组,不仅如此,他们在存储效率上,几乎也没有差别
一个简单的测试程序表明,存储1kw个整数,使用vector,整个程序消耗38.4MB空间,使用array,消耗38.2MB空间。

所以在这里我们可以放纵我们的迷信。

但是迷信也有限度的,就像上帝可以创造万物,但是不能创造自己。

然后进入本篇的主题:map/set的效率。

众所皆知,map/set底层数据结构是RB Tree,虽然不是真正的平衡树

但是其查找效率在统计上是比AVL等平衡树效率更高的,都能达到O(logN)的水平。Excellent。

于是我就迷信了,导致了自己对map的滥用,导致了很挫的结果。

究其原因,我忽略了那个确实很容易被忽略的东西,因为在提及复杂度的时候一般都不讲它。

——它就是传说中的那个常数。(我是不是很挫? =.=)

废话少说,数据说话:

map/set + 1,000,000个int的插入:
real  0m2.153s
user  0m1.812s
sys  0m0.056s

vector + 1,000,000个int的插入 + sort():
real  0m0.581s
user  0m0.436s
sys  0m0.016s
改成堆排sort_heap():
real  0m0.628s
user  0m0.492s
sys  0m0.016s

差别已经很明显了。

-----

然后再看看内存占用:

map: 19.4MB
vector: 4.1MB

so, hash + map用来构建hash table是我至今为止干过的最挫的事情之一了。——还不如用个vector。
Jun 14

关于vector的效率 不指定

felix021 @ 2009-6-14 03:22 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(6933) | Via 本站原创
看过《STL之父访谈录》,了解了STL之父对效率的极度迷信,因而我对STL容器的效率也是很迷信的。

但是某一次和feli聊到vector的效率问题,他说,有时候在比赛的时候用vector会TLE,换成自己写的单链表就AC了。

可惜当时是在永和门口争论的,无法验证,后来某天想到这个问题,于是验证之:

1. vector和数组的效率对比:

对一个含有100,000,000个元素的int数组进行循环10遍的写入,测试结果(使用linux下的time命令统计)为:

Array:
real  0m3.801s
user  0m3.136s
sys  0m0.568s

Vector:
real  0m4.210s
user  0m3.548s
sys  0m0.520s

可以看出,vector和Array相比,至少在acm程序中,效率损失几乎是可以忽略的。
还需要声明一点,这里的vector是在运行时动态申请的空间,而array则是预分配的。

测试程序后附。


2. 单链表的效率和STL的list效率对比:

添加10,000,000个元素,测试结果为:

单链表:
real  0m0.836s
user  0m0.620s
sys  0m0.204s

list<int>:
real  0m1.202s
user  0m1.024s
sys  0m0.168s

可以看出来,完全没必要和vector对比的,接近两个数量级的差距阿。

单链表比STL的list快并不是因为STL效率损失,而是因为STL的list是一个双向链表,可能还有更多的底层细节(具体我就不了解了)。


---------------------

所以很显然的,vector比手写的单链表快。快很多。非常多。至于原因,我觉得主要有2:

1。链表是基于指针访问的,不仅需要更多的访存,而且cache命中率会比较低。
而vector的存储空间是连续的,在连续访问的情况下,命中率会高很多。

2。链表的内存是动态申请的,每一次都使用new/malloc从系统维护的堆中进行申请,效率很低。
当然,STL的list使用了优秀的allocator,但是效率仍然和vector无法比拟,所以说明第一条才是关键。

结论:在大多数情况下,我们可以迷信STL之父对效率的迷信。


--------------------

下附测试代码:
分页: 10/21 第一页 上页 5 6 7 8 9 10 11 12 13 14 下页 最后页 [ 显示模式: 摘要 | 列表 ]