Terark & Topling 创始人雷鹏 | 没有上限，只有突破

当搜索词中有错别字时，搜索引擎会尝试纠错

通过相似拼音纠错

搜索引擎把这些字还原成拼音，用一个拼音相同的已知的搜索词代替。

这是一种众所周知的纠错策略，但是，当输错的字是多音字，特别是有多个这样的错误输入时，所有的搜索引擎都尽量绕开这个问题，或者仅使用最常用的那些音去纠错。因为要考虑所有可能的拼音组合，在极端情况下会导致指数爆炸！例如某互联网大厂的实现(枚举多音字全排列)。

基于自动机的算法可以完美解决这个指数爆炸问题

这是自动机应用的又一个绝佳范例，作为演示，这个页面只收录了 800万 条 搜索词+词频，数据也不太干净
该算法全部在内存中运行，使用了 293M 内存，这个数据量，如果用传统方法暴力实现，并且达到这个性能，需要 几十G 的内存
暴力方法是 Query 越长越可怕，该算法则是 Query 越长，优势越大
纠错耗时仅供参考(单核虚拟云主机: Xeon E5-2430 2.20GHz + RAM:1G)，如果你看到搜索耗时过长，很可能是 mmap 数据被 swap 到了硬盘上，再搜索一次会得到客观的搜索耗时

这个算法也可以用来解决用户输入预测(智能提示)功能

用户只输入Query开头部分，就自动提示出整个Query，例如用户输入举头望，就提示出举头望明月。就像现在各种搜索引擎做的那样。

基于编辑距离的纠错

在已知的搜索词中寻找编辑距离与用户 Query 最小的词，使用我的算法也可以高效解决（还没做演示页面）

memory FILE in C

作者: rockeet 发表日期: 2009年06月30日分类: C++ 评论: 1 条阅读次数: 2,319 次

一直希望有个可以像 FILE* 一样使用的 memory file，正好，今天，在linux的stdio.h中找到了这个东西。

#define _GNU_SOURCE
#include <stdio.h>

FILE *fmemopen(void *buf, size_t size, const char *mode);

FILE *open_memstream(char ** ptr, size_t *sizeloc) ;

详细说明：http://linux.die.net/man/3/open_memstream

fmemopen 有用之处主要在于从内存中读取，使用 fscanf。当然也可以写，如果是为了写，并且随后再读，可以将 buf 和 size指定为 NULL，0，这样写时会自动增加内存。

open_memstream 就主要用于写了，比如生成sql语句：

int i;
char* sql = NULL;
size_t len = 0;
FILE* mf = open_memstream(&sql, &len);
fprintf(mf, "insert into test(a,b,c) values");
for (i = 0; i < 100; ++i)
   fprintf(mf, "(%d,%d,%d),", i, i*i, i*i*i);
fclose(mf); // write a /0 at the end of sql, now len==strlen(sql)
sql[len-1] = 0; // trim last ','
execute(sql);
free(sql); // sql should be freed by the caller

int i;

char* sql = NULL;

size_t len = 0;

FILE* mf = open_memstream(&sql, &len);

fprintf(mf, "insert into test(a,b,c) values");

for (i = 0; i < 100; ++i)

fprintf(mf, "(%d,%d,%d),", i, i*i, i*i*i);

fclose(mf); // write a /0 at the end of sql, now len==strlen(sql)

sql[len-1] = 0; // trim last ','

execute(sql);

free(sql); // sql should be freed by the caller

张功耀：比毒乃分危害更大的是毒中药

作者: rockeet 发表日期: 2009年06月23日分类: 杂谈评论: 0 条阅读次数: 1,955 次

张功耀：比毒乃分危害更大的是毒中药

张功耀中南大学教授

最近被揭露出来的毒乃分事件，不是一个孤立的事件。它是公蝉档即将革皮的标志，也是对我国腐朽的中医药文化根深蒂固，不断沉渣泛起，使我们中国人长时期地对于食品和药品的安全问题麻木不仁的一种报答。

事实上，在我们中国，还有一种比毒奶粉危害更大的东西，那就是毒中药。

xxx、潲水油、吊白块、毒奶粉，这样一些东西，因为可能涉及到每一个中国人（享受特供待遇的除外），所以，它能够激起差不多每一个中国人的义愤。由于现在吃中药的人已经不多，加之一些别有用心的人至今还在为中药毒害做掩盖、粉饰和辩护，所以，对毒奶粉恨之入骨的人未必会对毒中药有相同的觉悟。

为什么说毒中药是一种更严重的毒害呢？

一、毒中药害人是以有意或无意两种方式进行的。

明明那中药都已经陈化、变质、发霉、虫蛀了，中医骗子一句“越陈越好”的话就可以轻而易举地把所有陈药卖掉。这种欺骗本属于“有意的欺骗”。可是，我国那些愚昧得可爱的人，在理直气壮地接受“越陈越好”的歪理邪说之后，不但不对这种“有意的欺骗”恨之入骨，而且还会对它感恩戴德，山呼万岁。

中药毒害的更大一部分源自“无意的欺骗”。

熟悉中医的知道，中医的医和药都没有实验基础。它是用“意”来决定“医”的，即所谓“医者意也”。

中医生的“意”来自两个方面：

一是通过观察附会得到的“意”。孙思邈在《千金方》当中告诉读者，把蛇蜕用一个绢带装好，扎在孕妇的腰上，就可以防止孕妇横生逆产。这其中的“意”就来自对“蛇能够蜕皮”的观察。把这个蛇蜕皮的“意”附会到孕妇生产上，就形成了用蛇蜕预防孕妇难产的“医”。附会到眼睛里边的翳，就形成了用蛇蜕除翳的“医”。南宋的时候，江浙一带的农民学会了养蚕。中医生发现蚕虫也蜕皮。于是，蚕蜕也被用来治疗妇女难产和为眼睛除翳了。再后来，中医生发现母鸡孵小鸡的时候，那小鸡居然可以破壳而出，把这个“破壳而出”的“意”附会到妇女难产，母鸡孵小鸡时留下的鸡蛋壳也用来为妇女催产。有人说，中医是“唯物主义”，读者可以判断一下，这种“医者意也”的中医哲学究竟唯物到了什么程度？

中医形成“意”的第二个源头是《黄帝内经》之类的文化垃圾。中医推荐患者吃屎和喝尿，其“理论依据”就来自这本混账透顶的《黄帝内经》。

据《本草纲目》记载，“人中黄”（也就是人屎）可以用五种不同的方法入药。中医生通常用它来治疗咳嗽、食积、劳极骨蒸、噎食不下、心腹急痛、解疔疮肿毒，等等。

中医推荐患者吃屎的这个医术，其“意”是怎样形成的呢？

《黄帝内经·素问》第五篇《阴阳应象大论》中说：“清阳出上窍，浊阴出下窍；清阳发腠理，浊阴走五脏；清阳实四肢，浊阴归六腑。”这里的“上窍”，就是指耳、目、口、鼻头部七窍；“下窍”就是指的前后二阴。这里的“清阳”，是指“上窍”发出的声音，和经由耳、鼻、口腔出入的各种气。“浊阴”也就是大便和小便。由于最后修改《黄帝内经》的混蛋王冰，说了“清阳发腠理，浊阴走五脏；清阳实四肢，浊阴归六腑”，食古不化的中医后生，就从这里得出一个推论：既然浊阴是“走五脏”“归六腑”的东西，“人中黄”（人屎）和“轮回酒”（人尿）可以入药，也就变得“理直气壮”了！

只要能够形成“意”，就可以采取与这个“意”对应的“医”，既不需要做任何有效性实验，更不要做任何安全性实验，不管三七二十一地“先吃两付药试试”，这就是所谓的“中医”。由于被中医生治疗过的病人，没有被当场毒死，甚至还有不少中医医术与某些疾病的自愈性相偶合了，“治愈”了不少病人，于是，麻木而愚顽的中医信徒就这样造就出来了。

由于中医生是依据他们想当然的“意”来决定“医”的，所以，每一个中医生在采取某种医术的时候都十分盲目。这就导致了中医生无意地先将别人毒死，然后又无意地将自己也毒死的荒唐故事。2006年8月，河北省行唐县龙岗卫生院的阎山川老中医，先无意地将郝淑琴毒死，后为了“证明自己的清白和自己行医几十年的医术”，用同样的中药将自己也毒死，就是这样的一个典型案例。

注：原文以被当山掉了，所以拷贝过来

vim –cmd "set fileencoding=utf-8"

作者: rockeet 发表日期: 2009年06月19日分类: 杂谈评论: 0 条阅读次数: 2,112 次

在很多时候，这个fileencoding无法发挥作用：

在windows上，用notepad将一个文本文件 test.txt 存储为unicode16或unicode16be

然后：vim –cmd “set fileencoding=utf-16” test.txt

它还是乱码，用 :set fileecoding 显示是 cp936

但是：vim –cmd “set fileencoding=utf-16”

不提供文件名，:set fileecoding 显示正确，是 utf-16

vim –help 提示：

–cmd <command> 加载任何 vimrc 文件前执行 <command>

说明 fileencoding 是在某个 vimrc 中被修改了，这个“聪明的”vimrc 非常聪明地将fileencoding修改了

不过我好想没找到那个可以再执行完 vimrc 再执行命令的选项。

——————————————————————————

找到了一个办法，在 .vimrc 中，把fileencodings【注意，是复数】那行改成：

set fileencodings=utf-bom,UTF-8,UTF-16BE,UTF-16,g18030,big5,euc-jp,euc-kr,iso8859-1

因为utf，前四个，都是非常严格的编码，而 fileencodings 是需要把严格的编码放在最前的，因为它一旦尝试到一种成功的编码之后就不再继续尝试（没有做概率分析，看哪种编码最合适）。

有个插件，用概率分析判断编码：http://www.vim.org/scripts/script.php?script_id=1708

函数调用太快了

作者: rockeet 发表日期: 2009年06月10日分类: C++ 评论: 0 条阅读次数: 2,180 次

在至强服务器上，使用 febird/vcproj/test_trb 测试 trb。结果发现使用compare函数指针的find仅比直接比较快17%！我原本以为至少要快一倍，因为在Windows（PentiumM Dual Core）上，直接比较的版本要快80%左右。

经过测试，发现：现代Cpu的流水线真强！

    long long t32 = pf.current();
    
    for (int i = 0, n=cc; i < n; ++i)
    {
        KeyType x = i + 100, y = i & 0xFFF;
        int cmp = vslow.pf_compare(&vslow, &m1, &x, &y);
    }
    long long t33 = pf.current();

    for (int i = 0, n=cc; i < n; ++i)
    {
        volatile KeyType x = i + 100, y = i & 0xFFF;
    }
    long long t34 = pf.current();

    int su = 0;
    for (int i = 0, n=cc; i < n; ++i)
    {
        KeyType x = i + 100, y = i & 0xFFF;
        if (x < y)
            su += 1;
        else if (y < x)
            su += 2;
        else
            su += 3;
    }
    long long t35 = pf.current();

long long t32 = pf.current();

for (int i = 0, n=cc; i < n; ++i)

{

KeyType x = i + 100, y = i & 0xFFF;

int cmp = vslow.pf_compare(&vslow, &m1, &x, &y);

}

long long t33 = pf.current();

for (int i = 0, n=cc; i < n; ++i)

{

volatile KeyType x = i + 100, y = i & 0xFFF;

}

long long t34 = pf.current();

int su = 0;

for (int i = 0, n=cc; i < n; ++i)

{

KeyType x = i + 100, y = i & 0xFFF;

if (x < y)

su += 1;

else if (y < x)

su += 2;

else

su += 3;

}

long long t35 = pf.current();

运行时间显示（单位是纳秒）：

服务器（至强四核 2.29G）： [doit=4971: 3.952, null=1648: 1.310, pse=4327: 3.440]

台式机（奔腾双核 2.49G）： [doit=6585: 5.301, null=1679: 1.352, pse=2246: 1.808]

doit表示pf_compare的那个循环

null表示那个啥也没干（volatile 用来禁止编译器优化）

pse表示那个累加循环

虽然主频低，但是服务器明显要快得多（不然至强怎么比奔腾贵那么多？）。

我看过pc下vc 2008 生成的代码，累加的那个循环，其中循环体26条指令（包含跳转指令）。平均每次循环仅消耗约4.5个时钟周期！流水线、分支预测这么强，在包含跳转的情况下，每个时钟周期还能执行3~4条指令！

更可怕的，在服务器上，一个包含函数调用的循环，仅需要9个时钟周期（2.29*3.95=9.05）！这完全颠覆了我对现代CPU的世界观。

这个简单的测试也说明，为什么find函数的compare_fun_ptr版本这么快（比较两个整数的函数是非常trivial的）。

完整的测试代码在：http://code.google.com/p/febird

在其中：$febird_home/vcproj/test_trb

函数指针之间的比较

作者: rockeet 发表日期: 2009年06月02日分类: C++ 评论: 3 条阅读次数: 2,680 次

因为某种原因（Threaded Red black tree C++ warpper），需要比较两个函数指针是否相等。但是，这么貌似很简单的需求却得不到满足。

下表，是在Visual C++ 2008 中，同一个函数通过不同途径得到的指针

key_comp	0x0041158c _febird_trb_compare_less
febird::G_relocate_febird_trb_compare_less	0x101cb4a4 _febird_trb_compare_less
febird_trb_compare_less	0x1051af60 febird_trb_compare_less(const trb_vtab , const void , const void *)

函数 febird_trb_compare_less 在 febird.dll 动态库中，并且导出。

febird::G_relocate_febird_trb_compare_less 是在 febird.dll 中定义了一个全局函数指针变量，并初始化为 &febird_trb_compare_less 。

key_comp 是使用 febird.dll 并将 &febird_trb_compare_less 传递给febird.dll中的另一个函数（假设函数名为foo）。以上三个不同的指针值就是在foo中查看到的。

在网上搜索了很多关于函数指针比较的东西，最终得出的结论是：跨越dll的函数指针比较是未定义的，除非是其中一个是NULL指针。不光vc，很多其他编译器也做不到跨dll的已定义的函数指针比较。

原本以为是dll重定位的问题，但是将函数指针放到 febird::G_relocate_febird_trb_compare_less 中也无济于事，反而更多出了一个指针值（0x101cb4a4 ）。

最终我的问题也解决了，就是在把这个比较放在头文件中，并且，key_comp作为一个模板参数来直接和&febird_trb_compare_less比较。

另外，函数指针作为模板参数时，不能将NULL之类的东西作为该模板参数传递。因为这个时候模板参数必须是一个const extern变量。如果试图传递NULL，在不同的编译器下会得到不同的错误信息（这样做在GCC4.1下编译过了，但连接错误）。

骂人的最高境界

作者: rockeet 发表日期: 2009年06月02日分类: 杂谈评论: 0 条阅读次数: 1,931 次

这个世界上奇人真不少：

http://www.tianya.cn/publicforum/content/feeling/1/931833.shtml

Threaded Red-Black Tree 线索红黑树

作者: rockeet 发表日期: 2009年05月26日分类: C++, 算法评论: 0 条阅读次数: 2,115 次

项目地址：http://code.google.com/p/febird

使用 libavl 中的 trb ，经过修改，实现了一个更高效更友好易用的版本，并且也支持范围查询，提供完备的std::map/set接口。

对基本类型的key，实现高效search
支持 lower_bound/upper_bound/equal_range
结点采用压缩方式，将colorbit(1bit)和tagbit(2bit)压缩到指针中
1. 从而每个结点的overhead是2ptr(32位环境下8byte，64位环境下16bits)
2. stl::map/stl::set 的节点overhead 一般是 4ptr
遍历tree的速度比stl::map/set快一倍
1. 线索树的线索(thread)可以直接访问next/prev，而不需要回溯到祖先结点再访问其最左/右叶子
2. 通过线索(thread)直接访问到next/prev的概率大约有50%
key的访问使用fieldoffset，C标准中有 offsetof(T,f) 宏来计算字段偏移
因为使用C模拟template，从而没有C++的代码膨胀问题
C接口需要手工打造vtable
vtable指针通过参数传递，而不是将它作为trb_tree的一部分，更节约内存
1. 也许仅仅一个vtable指针用不了多少内存
2. 但是当有若干个【在我的应用中，大约2M个】trb_tree时，节省的内存相当可观
使用C实现核心功能，同时提供更易用的C++接口（trbset/trbmap/trbtab）
1. 类似stl中的相应东西
2. trbset相当于stl::set
3. trbmap相当于stl::map
4. trbtab提供更多的控制
C++接口只是一个语法糖wrapper，将调用转发到C，但是使用C++可以避免几乎一切误用
1. C++将vtable作为模板的static成员，非常合理，非常恰到好处

以前我写过两篇文章：

在 C 语言中实现模板函数的方法

在 C 语言中实现模板函数的方法（续）

对基本类型的key，实现高效search，其核心思想就来源于这两篇文章，但是有许多精化。其间使用了更之前的一些东西：

基本类型enum
类型迭代（使用preprocessor）

基本类型enum，使用enum的目的在于：使用这个enum，查找到相应的处理函数。

enum field_type_t {
	tev_char,
	tev_byte,
	tev_int16,
	tev_uint16,
	tev_int32,
	tev_uint32,
	tev_int64,
	tev_uint64,
	tev_float,
	tev_double,
	tev_int,
	tev_uint,
	tev_long,
	tev_ulong,
	tev_ptr,
	tev_blob,  ///< blob
	tev_cstr,
	tev_std_string, ///< for c++ std::string, only used in c++
	tev_std_wstring, ///< for c++ std::wstring, only used in c++
	tev_app    ///< application defined type
#define	tev_type_count__  tev_int
};

enum field_type_t {

tev_char,

tev_byte,

tev_int16,

tev_uint16,

tev_int32,

tev_uint32,

tev_int64,

tev_uint64,

tev_float,

tev_double,

tev_int,

tev_uint,

tev_long,

tev_ulong,

tev_ptr,

tev_blob, ///< blob

tev_cstr,

tev_std_string, ///< for c++ std::string, only used in c++

tev_std_wstring, ///< for c++ std::wstring, only used in c++

tev_app ///< application defined type

#define tev_type_count__ tev_int

};

类型迭代：p_field_type_loop.h

// field type loop without judge VALUE_SIZE
// input macro:
//	 FIELD_TYPE_FILE

#  define FIELD_TYPE_TYPE signed char
#  define FIELD_TYPE_PROMOTED int
#  define FIELD_TYPE_NAME tev_char
#  include FIELD_TYPE_FILE
#  undef FIELD_TYPE_PROMOTED

#  define FIELD_TYPE_TYPE unsigned char
#  define FIELD_TYPE_PROMOTED unsigned
#  define FIELD_TYPE_NAME tev_byte
#  include FIELD_TYPE_FILE
#  undef FIELD_TYPE_PROMOTED

// and so on ....
// more types

// field type loop without judge VALUE_SIZE

// input macro:

// FIELD_TYPE_FILE

# define FIELD_TYPE_TYPE signed char

# define FIELD_TYPE_PROMOTED int

# define FIELD_TYPE_NAME tev_char

# include FIELD_TYPE_FILE

# undef FIELD_TYPE_PROMOTED

# define FIELD_TYPE_TYPE unsigned char

# define FIELD_TYPE_PROMOTED unsigned

# define FIELD_TYPE_NAME tev_byte

# include FIELD_TYPE_FILE

# undef FIELD_TYPE_PROMOTED

// and so on ....

// more types

在包含该文件之前，需要定义 FIELD_TYPE_FILE ，从而p_field_type_loop.h可以作为一个通用的代码生成器。在FIELD_TYPE_FILE中，实现具体的代码，在需要参数化类型的地方，使用FIELD_TYPE_TYPE来代替。FIELD_TYPE_PROMOTED用来提升相应的FIELD_TYPE_TYPE，例如 signed char 被提升到 int，float 被提升到double，这一点，在使用C的vararg时是绝对必要的。

另外，在包含该文件之前，还要将FIELD_TYPE_FILE中实现的函数名定义成宏，如：

#define trb_compare_kd  CAT_TOKEN2(trb_compare_, FIELD_TYPE_NAME)
#define trb_find_xx CAT_TOKEN2(trb_find_, FIELD_TYPE_NAME)
#define trb_lower_bound_xx CAT_TOKEN2(trb_lower_bound_, FIELD_TYPE_NAME)
#define trb_upper_bound_xx CAT_TOKEN2(trb_upper_bound_, FIELD_TYPE_NAME)
#define trb_equal_range_xx CAT_TOKEN2(trb_equal_range_, FIELD_TYPE_NAME)
#define trb_find_path_xx  CAT_TOKEN2(trb_find_path_, FIELD_TYPE_NAME)

#define FIELD_TYPE_FILE "trb_fun_field_type.h"
#include "p_field_type_loop.h"
#undef FIELD_TYPE_FILE

#define trb_compare_kd CAT_TOKEN2(trb_compare_, FIELD_TYPE_NAME)

#define trb_find_xx CAT_TOKEN2(trb_find_, FIELD_TYPE_NAME)

#define trb_lower_bound_xx CAT_TOKEN2(trb_lower_bound_, FIELD_TYPE_NAME)

#define trb_upper_bound_xx CAT_TOKEN2(trb_upper_bound_, FIELD_TYPE_NAME)

#define trb_equal_range_xx CAT_TOKEN2(trb_equal_range_, FIELD_TYPE_NAME)

#define trb_find_path_xx CAT_TOKEN2(trb_find_path_, FIELD_TYPE_NAME)

#define FIELD_TYPE_FILE "trb_fun_field_type.h"

#include "p_field_type_loop.h"

#undef FIELD_TYPE_FILE

以trb_find_xx为例，当trb_find_xx被展开后，变成trb_find_tev_double等等。

为什么要搞这么多呢？因为在这些函数中，对key值的大小比较实际上是个trivial操作，而一般传统的方法是传递一个compare函数指针，通过该指针调用compare函数，来实现灵活性（对任意类型的key）。

但是，通过函数指针调用一个非常trivial的操作，有很多不必要的性能损失（经过测试，对int的key，trb_find_xx会慢约20%~80%，服务器GCC+至强2.29G中慢20%，台式机VC+奔腾2.49G中慢80%）。

使用这种编程范式，可以在不必造成冗余代码的情况下，大幅提升性能。

全部的代码在这里

发现用混合C的C++很难写出完全正确的程序

作者: rockeet 发表日期: 2009年05月04日分类: C++ 评论: 2 条阅读次数: 3,025 次

#include <stdio.h>
#include <stdlib.h>
#include <stdexcept>

using namespace std;

struct A {
    A() { printf("A::A()/n"); }
    ~A() { printf("A::~A()/n"); }
};

struct G {
    G() { printf("G::G()/n"); }
    ~G() { printf("G::~G()/n"); }
};

G g;

int main(int argc, char* argv[])
{
    if (argc < 2) return 1;
    A a;
    char szbuf[32]; // 这里不管分配多少，总有可能不够, gcc3.4 环境下 ret 可能大于 32, 内容被截断
    int ret = snprintf(szbuf, sizeof(szbuf), "arg1=%s", argv[1]);
    printf("ret=%d, szbuf=%s/n", ret, szbuf);
    if (ret >= sizeof(szbuf)) {
        perror("snprintf");
        exit(1); // 如果是在深层函数调用，除了 exit(), 可用的就只剩下 throw
        // 实际上 exit 有陷阱，exit 只析析构全局对象，
        // C++ 规范说 exit 只析析构全局对象，不保证可以析构局部对象
    }
    char* psz;
    // 发现一个法宝，可以 sprintf 动态申请的内存
    // 但是也可能失败
    ret = asprintf(&psz, "%.*s", 1000000000000, argv[1]);
    if (ret < 0) {
        perror("snprintf");
        throw bad_alloc(); // 这里没有陷阱，但是如果没有外层 try-catch, 会 terminate
    }
    return 0;
}

难啊，想简单，好像只能用 sstream 了

#include <stdio.h>

#include <stdlib.h>

#include <stdexcept>

using namespace std;

struct A {

A() { printf("A::A()/n"); }

~A() { printf("A::~A()/n"); }

};

struct G {

G() { printf("G::G()/n"); }

~G() { printf("G::~G()/n"); }

};

G g;

int main(int argc, char* argv[])

{

if (argc < 2) return 1;

A a;

char szbuf[32]; // 这里不管分配多少，总有可能不够, gcc3.4 环境下 ret 可能大于 32, 内容被截断

int ret = snprintf(szbuf, sizeof(szbuf), "arg1=%s", argv[1]);

printf("ret=%d, szbuf=%s/n", ret, szbuf);

if (ret >= sizeof(szbuf)) {

perror("snprintf");

exit(1); // 如果是在深层函数调用，除了 exit(), 可用的就只剩下 throw

// 实际上 exit 有陷阱，exit 只析析构全局对象，

// C++ 规范说 exit 只析析构全局对象，不保证可以析构局部对象

}

char* psz;

// 发现一个法宝，可以 sprintf 动态申请的内存

// 但是也可能失败

ret = asprintf(&psz, "%.*s", 1000000000000, argv[1]);

if (ret < 0) {

perror("snprintf");

throw bad_alloc(); // 这里没有陷阱，但是如果没有外层 try-catch, 会 terminate

}

return 0;

}

难啊，想简单，好像只能用 sstream 了

很久以前发现的 vc2008 的一个bug（关于模板匹配）

作者: rockeet 发表日期: 2009年04月18日分类: C++ 评论: 0 条阅读次数: 1,851 次

使用操作符重载时，出现模板匹配错误，bug 的出现很简单，下面是代码：

#include <stdio.h>
#include <string>
struct A1
{
    template<class Ch, class Tr, class Al>
    void operator<<(std::basic_string<Ch, Tr, Al>& x)
    {
        printf("void operator<<(std::basic_string<Ch, Tr, Al>& x)/n");
    }
};
struct A2
{
    void operator<<(std::string& x)
    {
        printf("void operator<<(std::string& x)/n");
    }
};
struct B1 : A1
{
    using A1::operator<<;
    template<class T>
    void operator<<(T& x)
    {
        printf("void operator<<(T& x)/n");
    }
};
struct B2 : A2
{
    using A2::operator<<;
    template<class T>
    void operator<<(T& x)
    {
        printf("void operator<<(T& x)/n");
    }
};

int main(int argc, char* argv[])
{
    std::string s = "abc";
    
    B1 b1;
    // 下面两行调用了不同的函数，为什么？
    // these two line call different function, why?
    b1 << s;
    b1.operator<<(s);
    printf("/n");
    B2 b2;
    // OK, 完全正确
    // OK, all right
    b2 << s;
    b2.operator<<(s);
    return 0;
}

#include <stdio.h>

#include <string>

struct A1

{

template<class Ch, class Tr, class Al>

void operator<<(std::basic_string<Ch, Tr, Al>& x)

{

printf("void operator<<(std::basic_string<Ch, Tr, Al>& x)/n");

}

};

struct A2

{

void operator<<(std::string& x)

{

printf("void operator<<(std::string& x)/n");

}

};

struct B1 : A1

{

using A1::operator<<;

template<class T>

void operator<<(T& x)

{

printf("void operator<<(T& x)/n");

}

};

struct B2 : A2

{

using A2::operator<<;

template<class T>

void operator<<(T& x)

{

printf("void operator<<(T& x)/n");

}

};

int main(int argc, char* argv[])

{

std::string s = "abc";

B1 b1;

// 下面两行调用了不同的函数，为什么？

// these two line call different function, why?

b1 << s;

b1.operator<<(s);

printf("/n");

B2 b2;

// OK, 完全正确

// OK, all right

b2 << s;

b2.operator<<(s);

return 0;

}

vc2008 比 gcc4.3 真是差太多了

作者: rockeet 发表日期: 2009年04月18日分类: C++ 评论: 0 条阅读次数: 2,055 次

项目地址：http://code.google.com/p/febird

用gcc4.3重新编译了一下febird，出现了很多错误，仔细观察，这些错误都是因为不符合C++标准，重新改成符合标准的，比想象的改动量要大。
又测试了一下纯 C 实现的 algorithm: febird.c，是从VC2008的stl代码改过来的，在VC2008中测试比std::sort快20%，但是一到gcc中，却比std::sort慢了一倍还不止！不知到dinkware怎么写的。他有没有和sgi的比较过。重新研读了一下 gcc4.3 的 algorithm代码，gcc.stl.sort把insertion_sort放到sort的最后一个阶段，而ms.stl.sort把insertion_sort放到小区间内，就仅从这点上讲，gcc.stl.sort就少了很多函数调用的开销，ms又做了一些看似聪明的优化，比如递归层次按log(1.5,n)来计算，partition时又“跳过”连续相等的一段序列，等等，它的这些“优化”的结果就是速度只有gcc的1/3。

当搜索词中有错别字时，搜索引擎会尝试纠错

通过相似拼音纠错

基于自动机的算法可以完美解决这个指数爆炸问题

这个算法也可以用来解决用户输入预测(智能提示)功能

基于编辑距离的纠错

memory FILE in C

张功耀：比毒乃分危害更大的是毒中药

张功耀：比毒乃分危害更大的是毒中药

vim –cmd "set fileencoding=utf-8"

函数调用太快了

函数指针之间的比较

骂人的最高境界

Threaded Red-Black Tree 线索红黑树

发现用混合C的C++很难写出完全正确的程序

很久以前发现的 vc2008 的一个bug（关于模板匹配）

vc2008 比 gcc4.3 真是差太多了

近期文章

近期评论

文章归档

分类目录

功能