ITeye博客

2012 年文章归档

共 24 篇文章

BWT重编码

关于Burrows–Wheeler transform的详细介绍见wiki http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform 可以重一个字符串重编码,使得重复的一些字符段集中在一起,但是也有代价, 比如将字符串*****abc*****abc***进行bwt重编码,并不能将两个abc集中在一起, 而是要牺牲最后一个字符c作为索引,将两个ab紧凑起来。所以有得必有失。 显然讲一个规律很明显的字符串abcabcabcabc进行bwt重编码是得不偿失的。 bwt的encode可以用后缀数组在O(logN)或O(N)的时间复…

2012-11-30 21:16 · 算法

little endian和big endian的区别

简单概要的说Endian表示数据在存储器中的存放顺序。 内存、硬盘的最小存储单位是字节,一个字节有8个位。 其他数据都是由若干个字节组成,所以我们有必要了解两种存放方式的不同。 google了两个图看一下大端(Big Endian)与小端( Little Endian )的区别。 额。。这里竟然贴不了图。详见wiki吧http://en.wikipedia.org/wiki/Endianness 小端,数值低位在物理低位;大端,数值高位在物理低位。 因为我们把数据写到硬盘的时候是按照这个顺序来的,所以要特别注意。 根据这个特性可以写个简单的验证程序,判断机器使用的是哪种方式。 例如要把一个变…

2012-11-30 20:41 · 常识

原子操作

内核自带的原子操作可以帮助高效地我们实现引用计数等功能。 介于这么一个前提,一个引用对象不可能同时被引用和删除。 以下可以简单地实现引用计数。 内核中的定义: typedef struct { int counter; } atomic_t; 在复制构造函数(A::A(const A&)),和赋值构造函数(const A& A::operator=(const A&))中 使用void atomic_inc(atomic_t *v); 在析构函数里使用 int atomic_dec_and_test(atomic_t *v), 表示自减之后是否为0。 ====================…

2012-11-24 17:42 · C++

通过程序了解高速缓存

cpu进行运算之前会有一个步骤,就是把内存的数据把拿到高速缓存区(L1,L2,...)。 一般说来,当访问内存的某个位置时,会把这个位置附近的数据也搬过去,跟硬盘到内存的pagecache相似。 如果频繁命中这个高速缓存区,可以大大提高程序的运行速度。 所以如果用一个二元对表示一次运算(运行时刻,数据位置), 将此二元序列关于时间排序,那么我们就应该让相邻二元对的数据位置尽可能接近。 见两个程序: const int N = 1 << 12; typedef double Type; Type a[N][N], b[N][N], c[N][N]; int main() { for (int …

2012-11-24 14:02 · 常识

可变参函数的实现

C编译器通常提供了一系列处理这种情况的宏,以屏蔽不同的硬件平台造成的差异, 增加程序的可移植性。这些宏包括va—start、va—arg和va—end等。 这些在stdarg.h中可以找到。 #define _INTSIZEOF(n) ((sizeof(n)+sizeof(int)-1)&~(sizeof(int) - 1) ) #define va_start(ap,v) ( ap = (va_list)&v + _INTSIZEOF(v) ) //第一个可选参数地址 #define va_arg(ap,t) ( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZ…

2012-09-12 20:46 · C++

ICE远程函数调用

用ICE框架可以很容易地实现远程函数调用,广泛使用在分布式系统中。 ICE框架由客户端和服务器组成,支持客户端并发地调用服务器的服务。默认是一个同步调用。可以改成异步调用。 下面给出一个简单的例子。实现客户端和服务器间的一问一答。 服务器部分: 服务器做的工作稍微多点,首先我们需要定义一个ice文件,包含我们需要的接口。 IM.ice #ifndef IM_ICE #define IM_ICE module IM { interface IMInterface { int SendMsg( string req, out string rsp); }; }; #endif 然后使用slice…

2012-08-29 19:21 · ICE

完美哈希

我们想要一种哈希,可以将n个字符串无冲突地匹配到0到n – 1。这种哈希我们称之为完美哈希。 这似乎是难以想象的,冲突是哈希不可以避免的问题,因为我们无法预知每个哈希的值。但是如果需要求解哈希的字符串的集合是预知的,最简单的得到完美哈希的方法就是不断尝试各种哈希方法,直至找到满足我们需求的哈希方法。 但是这个最简单的方法,每次试验获得完美哈希的概率是很小的,将需求退化一点:求一次可以得到n个字符串无冲突地匹配到0到m – 1的哈希的概率F(m, n)。 于是F(m, n) = F(m – 1, n – 1) * [(m – 1) / m]^(n – 1) 可得F(m, n) = (m – 1…

2012-08-24 21:25 · 算法

leveldb学习二

这里主要收集leveldb源码中比较犀利的代码段。 const int C = 1 << 20; void Clear(string& value) { if (value.capacity() > C) { std::string empty; swap(empty, value); } else { value.clear(); } } stl中string自带的clear不会释放内存给OS,从代码可以看出当string申请的空间比较小的时候(不大于1M), 它是不还给OS的,而是自己留着。比较小的内存片还给OS一般内存管理策略下也比较难被利用上的,所以竟然 value还在,就干脆留着,…

2012-08-13 13:52 · ldb

python扫盲0

hello world太简单,看不出语法,写个长点的,也算对python的语法有大概的了解了,哈哈哈。 功能:root是找到没有被包含的头文件,allh是看一个源文件都包含了哪些头文件。 没啥用,当练手。 #!/usr/bin/python #python code practice for include discovery import os pre = "#include" def compact(str): #local variable assignment before referenced l = len(str) i = 0 res = "" while i < l: if …

2012-08-11 20:08 · python

leveldb学习一

下了leveldb的源码,感觉十分给力,代码质量都非常高,非常值得学习。 首先把它用起来先,没什么好说的,直接上代码吧。 #include <leveldb/db.h> #include <string> #include <iostream> using namespace std; void PrintStatus(leveldb::Status& status) { if (status.ok()) cout << "OK!" << endl; else cout << "NO!" << endl; } int main() { leveldb::DB* db; leveldb::Op…

2012-07-25 23:10 · ldb

关于树的复杂度分析

一棵树有N个结点,高度为d。size[i]表示子树i的大小,则sum{size} <= N * d 当d不大时这个结论可以被利用。。

2012-04-13 21:28 · 常识

一个可以用于复杂度分析的结论

最近在想出个题目,但题目没出成。不过想出了一个结论。 给定两个正整数序列a1,a2,...,as; b1,b2,...,bt. 且a1 + a2 ,...., + as = n; b1 + b2,...., + bt = n; D = [x|min(ai, bj), 1 <= i <= s, 1 <= j <= t]; 在D中选K = min(n, s * t)个最大的数。 证明这K个数的和不大于n^1.5 简证: 不妨设A, B是递增序列,且a1 <= b1,显然as = bt。 而且(ai, b1)都会被选为最大数的,不然(a1, bi)就都不是最大数,那就可以将a1的值分给a2, a3…

2012-04-13 14:22 · 数学

分析随笔_2

对于一些稍复杂的问题,并不像简单的问题那样一眼可以将解法看穿, 但是这些题目的解法往往也不会比简单问题的解法高深多少。 我们不妨先得到朴素的解法,但不能停留在该解法表面的观摩, 而是要积极的去挖掘朴素解法的特点, 然后加以优化而获得原本问题的解法。

2012-04-13 13:55 · 分析

分析随笔_1

一个问题,看呈现在我们面前的有哪些对象,哪个对象会是突破口呢? 不妨对他们逐个进行分析,发现了他们之间的联系? 对于单个对象的分析,其实也是要找突破口,有哪些“口”呢? 我们也要善于将思维方法进行分类,正着搞不行,反着呢? 一个对象也可能会由多个对象组成的,这好像又回到了问题的开端。 很多问题往往只是个组合问题,即可以分解为一些已经被解决的简单问题, 在积累一定简单问题的解决方法的基础上,只要善于分析,可以解决很多看似新颖的问题。

2012-04-09 14:08 · 分析

525_1000

一个n * n的矩阵,每次操作如下,选择i, j,交换i, j行,交换i, j列,问从一个初始矩阵到达一个目标矩阵的最小操作步数。 经分析发现,这个矩阵是对称的,然后把它看做一个图的连接矩阵表,每次操作就相当于交换两个点的编号。 所以现在的问题就是枚举点一一对应的方式,然后找置换环,算出最小的答案就好了。 由于可以看出3个点的位置确定了所有点的位置,于是暴力枚举就有办法了。 补充: 如果不对称,而且每次操作是交换行或交换列呢。如果只是问能否到达,其实就是问两张对应的 二部图 是否同构。

2012-03-14 16:42 · SRM

Prüfer sequence

结点编号为1,2,3....,n(n >= 2)的一棵树对应的prufer sequence是长度为n - 2的一个序列(序列元素为{1,2,...,n},于是生产树的总数为n^(n - 2)。 prufer sequence的产生方法: 将树的叶子结点逐个剥去,直至剩下两个结点。 剥第k个:取出当前的叶子编号最小的结点,设为y,设它的邻居的结点编号为x,设置ps[k] = x,剥去y。 显然树的形态和prufer sequence是一一对应的。 所以结论成立!

2012-03-01 16:14 · 数学

526_1000

给出n个单词和一个goodstring,从n个单词中随机选K个(每次选择是独立的)连接起来,称其为longstring, 求goodstring在longstring出现次数的期望。 矩阵乘法卡精度了,而且时间复杂也太高。。 解决这个问题的关键的得到以下结论: 在longstring中第m(m > L)个单词出现goodstring的次数只与前面的L个相关,L = goodstring.size()。 而这L个的每一个的选择都是独立的。即对每两个相同的单词(位置 > L),出现goodstring的期望值是一样的。 所以当K > L时,每加随机一个单词产生的goodstring的期望数也是一…

2012-02-29 20:47 · SRM

533_1000

给出n个频率freq[n],用{"pi", "ka", "chu"}构造n个单词work[n],使得任意一个单词不是另一个单词的前缀,求work[0] * freq[0] + work[1] * freq[1] + ...的最小值,及其方法数。 用{"pi", "ka", "chu"}(2, 2, 3)构造一个字典树,联系哈弗曼编码,将freq降序排列,则长的先构造。 由于任意一个单词不是另一个单词的前缀,所以单词都再叶子结点上。 dp状态为(deep, k, t1, t2, t3) 表示已处理完深度至deep的结点,构造了k个单词, 深度为k + 1的叶子结点有t1个, 深度为k + 2的…

2012-02-28 15:14 · SRM

526.5_1000

从N个三元组{matches, red, blue}取出尽量多的组,使得取出的{matches}的任何非空子集的异或都不为0,也就是两个人用来玩NIM游戏,先手必赢。在必赢的情况下,求出最小的sum{red} * sum{blue}.. 问题1:取出的{matches}任何非空子集都是先手必赢,可以采用贪心的方法,利用|{matches}| == 矩阵的质。 问题2:使得sum{red} * sum{blue}最小,我们定出贪心的顺序。 对于问题2, 对于每个最优解OPT, 定义: sigma{OPT.red[i]} = R and sigma{OPT.blue[i]} = B. 定义: w…

2012-02-15 21:59 · SRM

兔子跳

一只兔子每次可以跳a[0], a[1], ..步,a[k] < a[k + 1], 且a[k] | a[k + 1],这只兔子跳了几步, 总长度是LEN,如果兔子每次都跳得尽可能的远,那么兔子经过的点, 必定是所有总长度是LEN的跳法都经过的点。 http://apps.topcoder.com/wiki/display/tc/SRM+527

2012-02-11 22:59 · 数学