Monthly Archives: December 2014

C++程序员的负担

C++的强大,毋庸置疑,嵌入式,操作系统,3D游戏引擎,无所不能,但是C++程序员的语言负担真的很重,下面是一个正在尝试开发的一个文件系统的头文件,

#ifndef FILESYSTEM_H
#define FILESYSTEM_H
#include <string>
#include <vector>
#include <memory>

using namespace std;

namespace FS{
    class FileSystemImpl;
    class FileSystem{
        public:
            static shared_ptr<FileSystem> init_file_system(const string& configFile);
            static shared_ptr<FileSystem> mount(const string& mountPath);
            ~FileSystem();
        public:
            int create(const string& path, bool isDirectory=false);
            int delete(const string& path);
            int delete(const File& file);
            vector<File> ls(const string& path);
            vector<File> ls(const File& path);
        private:
            FileSystemImpl* impl; 
    };
    class FileImpl;
    class File{
        friend class FileSystem;
        public:
            File(string& path);
            ~File();
        public:
            int     open();
            bool    isDirectory();
            bool    isExist();
            long    length();
            long    available();
            long    position();
            void    seek(long position);
            int     read();
            int     read(char buffer[], int length);
            int     write(char buffer[], int length);
            int     flush();
            int     close();
            string& path();
        private:
            FileImpl* impl;
    };

    enum FileSystemType
    {
        LOCAL,YADFS,HDFS
    };
}
#endif

为什么选择shared_ptr<FileSystem>,不是简单的FileSystem指针,能不能直接返回一个FileSystem引用?为什么不用shared_ptr< FileSystemImpl > impl,又直接用了FileSystemImpl指针,能不能用FileSystemImpl引用呢?参数用引用传递还是值传递,是传一个指针呢还是传一个对象,要加const吗?返回值是返回对象呢还是返回引用还是返回指针,要返回const吗?string怎么考虑国际化的问题?Linux和windows上wstring和string如何选?宏定义,友元类,前向声明,异常,命名空间,虚函数,还有大量的类似typedef int INT32之类的考虑,这个问题列表还能写很长很长,你能想象你写的每一个类都要经过这样的思考过程吗?C++ 1x的引入虽然解决了一些问题,右值引用,移动语义,lambda,天啊,我知道他们都有用,但是真的又增加了很重的语法负担,重到各路大大出来辩护要把C++ 11当做一门全新的语言来学习,唉,为毛人人都喜欢auto,还不是因为减轻了一些声明负担啊。

每个程序员都应该掌握的数据结构 – Bloom Filter

Bloom Filter

这种数据结构的名字来源于他的发明人Burton Howard Bloom的名字,凡是用自己名字命名的东西一般都非常牛逼,思维精巧,独步武林。

Bloom Filter 跟hash有着紧密的关联。首先设想我们有一个比较大的数据集合,每一条记录有一个key,现在有一个需求是问给定一个key,这个集合包含不包含这个数据?我们不太可能不假思索的把整个数据集合load进内存中,因为可能存在多个这样的数据集合。最容易想到也最直接的想法是在内存中构造一个hash的结构保存所有已经存在的key,这其实已经能够解决绝大多数的问题了,但是有没有更好的呢?乍一看对普通人来说不太容易找到突破口,这确实需要非凡的智慧来打破定式思维。Bloom Filter 就设计了这样一种思路,它找到了一种折中,以 一定概率 的错误回答来实现比常规hash表小的多的内存使用量。直白的来说就是当我们问数据集包含不包含key的数据的时候,如果它回答不包含,那100%数据集不包含,但是如果它回答包含的话,却不是一个确定的答案,我们需要进一步的策略去确定它是不是真的包含,牛逼的地方在于这个出错的概率我们是自己可以控制的。

让我们先从一个很笨的但是朴素的方法开始,假设我们知道数据集有1000万条数据,如果我们设计一种很差的hash算法,使得这1000万条数据只有1万个hash值,常规的hash表用链表的结构解决hash冲突的问题,所以即使只有1万个hash值,如果我们用常规的hash表来保存所有key在内存中的话,内存仍然是1000万个key的大小,如果我们的数据结构不解决hash冲突呢?只load这1万个hash值在内存中,那么当有询问一个key在不在这个集合中的时候,很明显如果hash(k)不在这1万个值中,那么这个key一定不在这个数据集合中,hash(k)在的话,那么有可能是包含这个key的,因为我们没解决hash冲突,很明显的直觉告诉我们hash值越多,回答出错的概率就会越低,但是如果沿着这个思路下去的话,我们依然会陷入死胡同,因为你的hash函数越完美,就越需要更多的内存来保存hash值。

让我们再次回到一个基本认知逻辑中,现实生活中,我们经常看到一些娱乐节目玩一种你说我猜的游戏,就是给定一个物品,一个人去描述它的特征,另一个人来回答它是什么,一种食物,圆的,中秋节吃的,那么很容易猜到是月饼,我们模仿这种思路用一组hash函数hash1,hash2 …来为一个key算出一组hash值,然后用一种有效的数据结构来保存这组hash值,当再有询问一个key在不在的时候,我们同时判断hash1(key),hash2(key)…都在不在已经我们的的数据结构里来回答这个key在不在,我们依然依靠直觉这样的判断应该出错的几率会降低了,谈到有效的,内存敏感的,数相关的数据结构我们应该马上会回想到bitset,Bloom Filter 正是依赖着这种数据结构来存储所有的hash值,每个hash(key)都对应着一个bit位。

现在让我们更准确的定义这种数据结构,给定n个元素的集合,k个hash函数,m大小bitset来存储所有的hash值,使得当询问一个key是否在集合中的时候以确定的概率p回答错误。以下只包含经过了严格的数学证明的结论,我们程序员可以直接拿来使用。

n和p是我们可以决定的,当我们选定这两个参数以后,下列公式可以帮我们确定m,

bfm

当m确定后,我们用下列公式确定k,

bfk

当这些变量都确定后,我们需要去设计一组hash函数,我们可以直接拿算法导论Designing a universal class of hash functions章节去实现我们的k个hash函数。

每个程序员都应该掌握的数据结构 – Skip List

Skip List

这种数据结构翻译成中文,大家一般叫它跳表,非常直译,其实我接触这种数据结构比较早,但是看很多技术分享的时候一直听到有人说跳表,跳表,但我始终没有把它和skip list联系起来。

Skip List 也是链表的一种变形,同样是在node结构上做文章,它的出发点非常简单直接,因为一个有序数组我们支持二分查找,那么一个有序链表我们是不是也能支持类似的快速查找呢?于是跳表就出现了,它是典型的空间换时间的一个具体实现,下图引用自 Skip List

500px-Skip_list.svg

每个节点都有一个指针数组指向不同的节点,在每一层上看都是一个节点有序的链表,其实也有一些实现是基于unrolled list的,就在每个节点维护一个有序数组,但是那种方式牵涉到每个节点需要维护多少个值的问题,也是需要在实际的环境中去调优的,说远了,还是回到跳表实现的本身,我们需要注意的是一般跳表的实现在查找的时候都不能保证二分查找,要完美支持二分查找的话,跳表的实现复杂度相当大,而且结构的重整非常频繁,反而得不偿失,一般跳表插入元素的时候会有个随机数来表示这个节点需要扩展到多高的高度,大于这个高度的那层链表不必包含这个新增的节点,低于这个高度的链表必须包含这个节点,在插入节点后,具体要更新哪些节点的next数组的哪些位置的值可以在查找插入位置的过程中把它记下来,这些需要更新的节点数量不会超过跳表节点的最高高度。

template<typename T>
struct SkipListNode{
    SkipListNode** next; //dynamic allocate
    int length; //next array length and also is node level
    T data
}

每个程序员都应该掌握的数据结构 – Unrolled List

Unrolled List

链表是我们每个程序员都烂熟于胸的一个数据结构,它有很多优点,递归的结构,动态的节点内存分配适应不确定长度的情况,但是它的这些特性决定了它会导致内存的碎片化,访问的冗余化——总是先访问指针,再访问指针指向的内存内容,所以如果长度确定,那么数组显然是更好的选择,数组能够保持连续的内存分配,更快的访问速度。

Unrolled List 就是这样一个折中的实现,它在标准链表的节点存储了一个不定长数组来保存部分原来需要link来迭代访问的后续节点,增加了操作的复杂性,比如每个节点应该如何决定存多少个值,每个节点要存相同数量的值吗,扩展的思考能带来一些轻微不同的实现,但总体来说它比原来的链表具有更小的内存用量,更好的效率,在动态增长方面又强于数组。可能标准的C++程序员会建议直接使用vector,很好的效率,动态的增长,也是非常不错的选择,这个系列的目的在于我们能不能从一些数据结构的设计来思考一些更抽象范围内的设计思路。比如在复杂性和效率之间的折中,在空间与时间之间的折中。

template<typename T>
struct UnrolledListNode{
    T* items;
    int items_length;
    UnrolledListNode* next;
}

支付最后一公里

今天下班后,照例去旁边的便利店买牛奶,一进店,两个服务员马上招呼,有支付宝吗,支付8折,12/12五折优惠,只需要在手机打开支付码,然后扫描一过,非常方便的支付完成,在支付方面我们国家是走在前面了,感谢支付宝,当然也得感谢党,感谢政府,不然政策大棒一挥,什么也都玩完了。