febird
febird · 共 136 篇文章
实现了一个压缩算法,在数据高度压缩的前提下,还可以快速查找 key
最近写了一个算法,可用于 (key,value) 存储,key 当然是 string 类型。 用一个 2.3G 的 url 集合做测试,如果不计 value 占用的空间,key 集合的存储空间可以被压缩 70倍 !压缩后整个数据结构仅占31M内存!压缩率比 bzip2 还要高。 本质性的不同于: gzip, bzip2 等压缩算法仅仅是压缩而已,无法快速地从压缩数据中查找。 我实现的这个算法能高效地支持对 key 的查找,并且查找的时间复杂度仅与 key 的长度有关,不管数据集合有多大,时间复杂度总是 O(strlen(key))。实际数据:当 key 长度均值为 76 字节时(该 url …
2012-05-06 00:21 · 评论(0)
原地排序与链表翻转
有这样一个问题: 有个长度为 n 的 (key,val) 数组 a,其中 key 是 int 类型,并且其值在 [0, n) 之间(前闭后开,包括 0 不包括 n),该数组按 key 是乱序的,但没有重复 key。 要求:对 a 原地按 key 排序,可以使用常数个临时变量,不允许使用其它额外空间,时间复杂度必须是O(n) 我曾经写过 另外一个问题:排列的分解 (必须看),与此有点类似:但其实不同。 本质的不同在于:那个问题是对循环链表逆时针旋转1个单位,而该问题是要对循环链表顺时针旋转1个单位。逆时针旋转很容易,因为是 forward copy。但是顺时针旋转需要 backward cop…
2012-04-11 10:57 · 评论(0)
C++ 中让对象的拷贝成为 显式 的
C++中对象的拷贝一般使用拷贝构造函数,从而对象的拷贝大多是隐式的,使用拷贝构造函数的隐式拷贝很方便,但是编译器无法识别不必要的拷贝,虽然我们人类可以识别这些不必要的拷贝,比如在写函数原型时,忘了加&,就会引发一个这样的非必要拷贝。 如果这种情况很严重,我们可以禁用拷贝构造函数和赋值函数(声明成private),然后再提供一个显式拷贝函数,如: 这种方法的确可以work,但看上去很不自然,比如: x = y.clone(); 在形式上很自然,但是实现却不容易(在C++11中实现要容易点,让 x 接受 && 即可)。 但的确可以实现:在 C++98 标准中,如果一个函数返回一个非 Primit…
2012-03-11 21:10 · 评论(0)
C++11: 使用 lambda 创建模板类 的 对象
C++ 中 lambda 可以直接传递给模板函数如 std::sort, 但无法传给模板类如 std::map,但是,使用一点小技巧,可以使用 lambda 创建模板类的对象,省了很多麻烦的 coding。这里给出一个示例: make_map 可以被返回值优化掉。
2012-03-09 11:46 · 评论(0)
Recursive Lambda in C++
C++ 标准委员会真是太死板了,既然给 C++ 增加了 lambda,就真的按部就班地套用 lambda 的标准定义,也不加个 lambda的自引用机制。找了半天,除了那些学院派的足以把99%的人搞晕的 Fix Point + Y combinator,一个最实用的解决方案就是把 lambda bind 到 std::function<...>. 我那段需要 recursive lambda 的代码: 这是以 DFS 顺序打印 Tree Shape Automata 的代码,为了各种原因(内存,速度,简洁),设计了一个通用的 for_each_move 来遍历指定 state 的每个直接 t…
2012-03-05 18:43 · 评论(1)
一个很难的字符串问题
问题描述: 有 n 个 RegEx (正则表达式),标号从 0 到 n-1,n 可能很大 (比如说100万) 给定一个字符串,返回能 match 这个字符串的所有正则表达式标号。 用 C++ 来描述这个需求: 这个问题看上去简单,但其实现非常复杂!一个简单生硬的实现是,随便拿一个正则表达式引擎(如boost.regex, pcre, re2, ...),match 时逐个匹配,匹配成功的,加入返回值集合。但这个时间复杂度太高! 原则上,unix 下的 lex 可以匹配多个 RegEx,并返回那个被匹配的 RegEx 标号,但好像无法识别多个成功的 RegEx 匹配。 这个问题的一个简化版:这…
2012-02-20 19:07 · 评论(0)
m 分查找
一个比较产生两个决策结果 二-决策的计算机硬件实现更高效 我们可以想象给一个 array, 一个 key, 在某台 god machine 上有一个操作: cmp-multi array, key, n, m 它能在一个时钟周期内决策出 key 是落在 n-elem array 的 m 等分(最后一分要小点)的哪一份,那在这种情况下 m 分查找就比 2 分查找要快。 实际上,B-Tree 的搜索可以看成是这样的一个 m 分搜索。
2011-12-26 16:15 · 评论(0)
Name lookup take place before access control
Yes, "1." is a floating point number.
2011-12-24 18:03 · 评论(0)
hash_strmap & gold_hash_map update
hash_strmap 在不增加任何额外成本的情况下,string pool 中每个 string 消耗的内存,平均情况下,减少了一个字节。太不值一提。 gold_hash_map 计划新加功能: 使用 FreeList 管理已删除的元素,这样最大的好处是:即使有元素删除,所有未被删除的元素的 id(数组下标)都不会改变。这样,就可以把 id(数组下标)作为元素的永久标识,可以把这个 id 保存在别的地方,来直接访问 gold_hash_map 的元素。这个功能看上去比较简单,但接口设计和实现都还是有不少复杂度的。 hash_strmap 也可以实现这个功能,但是这样会在 string po…
2011-12-03 10:14 · 评论(0)
How do I disable video thumbnails in Windows 7?
How do I disable video thumbnails in Windows 7! 禁用 视频 缩略图 windows 7 不管中文还是英文搜索,关于这个话题的搜索结果超过3,000,000条。我有一个目录中,有100多个视频文件,每次打开那个目录,我可以先去午休一下,再回来看痿大的 Video Thumbnail 的华美壮丽的结果。 有人给出出可行的解决方案: 打开注册表,搜索{c5a40261-cd64-4ccf-84cb-c394da41d590},然后删除。看似很简单,并且,我是用管理员权限启动的 regedit,就这,删除时还被提示没权限。又有人说,这在 windows…
2011-11-27 17:10 · 评论(0)
linux kernel 中的二叉树搜索 与 stl 相应物的对比
代码 Linux kernel 中也使用并实现了红黑树,但是查找算法没有自己实现,而是希望使用者去实现。如果只是实现一个精确查找的函数,这很简单,几乎每个人都能写出正确的代码: 这是 kernel 中 rbtree.h 中给出的示例代码,几乎所有的 kernel search 代码都遵循了这个模式。然而,这个代码的效率有问题,虽然仍是 O(logn) 的。 再看看 stl 中的实现 (这只是个简化示例,不完全等同于 stl 中的实际代码): 分析 kernel 代码的每个循环中有两个条件判断,而 lower_bound 中只有一个条件判断,虽然在 stl 中,即使在找到相应结点后,可能还需要…
2011-11-26 22:11 · 评论(0)
C++ 2-phase lookup
This 2-phase look up of g++ (gnu C++) seems not inconsistency: builtin types are not treat equivalent with user defined type.
2011-11-11 14:46 · 评论(0)
小技巧,大智慧:%n of sscanf
scanf 系列中有个函数 sscanf,可能有人用过,它的普通用法,我就不讲了,可以参考 这里:man 3 sscanf gnu c 实现了 C 标准的 format specify 的 %n,它的含义是返回从该次 XXscanf 调用开始到此读了多少个字节,我们可以利用这一点,来实现不需要内存分配的%s: 假定我们读取一批商品记录,每条记录包含商品ID,商品名称,商品价格,各字段的类型在代码中是自包含的 %*s 用来扫描但跳过(不存储)一个字符串,两个 %n,前一个得到name的起始偏移,后一个得到name的结束偏移……其它的,也就不用我多说了。 %n 应该是 C99 新加入的,不过这一…
2011-10-30 21:54 · 评论(0)
忽悠,也是一种学问
我看了一下我最近几个月的博客浏览记录,发现 这篇 的访问量最高。然而这篇文章里面提到的东西虽然有我这么多年编程生涯中的一些总结,但总体上没有太多实在的东西,缺乏可操作性。 而其它的一些文章,比如: 对数复杂度的聚集算法 将递归转化成迭代的通用技术 排列的分解 ...... 却几乎无人问津。 就如同在实际工作中,某某某通过调节某个参数,让系统的运行效率提升了20%,太牛逼,太了不起了!而通过优化,甚至重写某些代码,提高了200%的效率,你能保证你的代码一定正确,没 bug 吗?我们的 site up 已经太多了,你还给大家添乱?万幸通过了测试,最终上线也没出问题,不过你这人太“拘泥于细节”,那…
2011-10-30 14:44 · 评论(0)