ITeye博客

Think On Think

splayx · 共 90 篇文章

整型之间的转换

这里说一下C的强类型转换,也是C++的static_cast。 在小端的机器实验了一下, 从位数多的类型(例如int64)转到位数少的类型(例如int32)是直接截取的, 这种情形是十分简单明了的。 不过不同环境底层的策略可能不大一样。 而反过来,从位数少的到位数多的,就稍微复杂一点, 在我的实验环境中,例如从a到b,首先会判断a是不是有符号的, 如果a是无符号的,那直接一个内存拷贝完事, 否则会判断是否为负,然后用0或1填充b中的高位,不管b是否有符号。 如果涉及加减乘除等复杂运算的都转为 有符号的 ,都转为有符号的吧。 因为无符号遇到负数就悲剧了,用有符号的,在数据范围内都不会出错。 这…

2013-01-12 20:39 · C++ · 评论(0)

分析随笔_3

在做srm560div1的中等的时候,遇到个问题,抽象点是这样的, 一个路径: r1,r2,r3......nk... 知道了ri到ri+1的方法,现在知道某个状态nk,求k最大可以是多少? 由于数据比较小,yy了一种暴力方法,就是ni往ni-1回走一步,然后看是否可以从ri-1走回ri。。 但是这个方法在原始问题上是错误的,原因是ri-1可能走不回ri,但却有可能走回rk.. 只有当ri-1能否走回ri等价于ri-1能否走回rk,这个方法才是正确的。 我们最终目的是走回rk,所以我们应该去寻找能走回rk的充要性质。

2013-01-08 15:00 · 分析 · 评论(0)

561_500

用stl的complex挺方便的,记住这几个函数就够用了 arg(t);返回值(-pi, pi] real(t); imag(t); abs(t); 然后把complex的除法运算优化成乘法运算,效率就够用了。 const double pi = acos(-1.0); const double eps = 1e-9; typedef complex<double> cd; //在这里定义vector可以减少局部变量开辟回收的开销 vector<double> w0, w1, d0, d1; bool hasIt(cd t0, cd t1, const vector<cd>& vc) { w…

2013-01-05 00:04 · SRM · 评论(0)

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 · 算法 · 评论(0)

little endian和big endian的区别

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

2012-11-30 20:41 · 常识 · 评论(0)

原子操作

内核自带的原子操作可以帮助高效地我们实现引用计数等功能。 介于这么一个前提,一个引用对象不可能同时被引用和删除。 以下可以简单地实现引用计数。 内核中的定义: 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++ · 评论(0)

通过程序了解高速缓存

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 · 常识 · 评论(0)

可变参函数的实现

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++ · 评论(0)

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 · 评论(0)

完美哈希

我们想要一种哈希,可以将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 · 算法 · 评论(0)

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 · 评论(0)

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 · 评论(0)

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 · 评论(0)

关于树的复杂度分析

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

2012-04-13 21:28 · 常识 · 评论(0)

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

最近在想出个题目,但题目没出成。不过想出了一个结论。 给定两个正整数序列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 · 数学 · 评论(0)