splayx
- 浏览: 82643 次
- 性别:
- 来自: 北京
-
最新评论
-
lazy_：
怎么感觉看起来像ReadWriteLock?
多线程下的一种编程模式 -
splayx：
方世玉 写道自旋锁，用于读远大于写的并发场景很合适，参考JDK ...
多线程下的一种编程模式 -
方世玉：
自旋锁，用于读远大于写的并发场景很合适，参考JDK内部的CAS ...
多线程下的一种编程模式 -
teasp：
你这个是类似轻量级锁的办法，对于写少读多的情况确实很合适。也可 ...
多线程下的一种编程模式
文章列表
这里说一下C的强类型转换，也是C++的static_cast。
在小端的机器实验了一下，
从位数多的类型（例如int64）转到位数少的类型（例如int32）是直接截取的，
这种情形是十分简单明了的。
不过不同环境底层的策略可能不大一样。
而反过来，从位数少的到位数多的，就稍微复杂一点，
在我的实验环境中，例如从a到b，首先会判断a是不是有符号的，
如果a是无符号的，那直接一个内存拷贝完事，
否则会判断是否为负，然后用0或1填充b中的高位，不管b是否有符号。
如果涉及加减乘除等复杂运算的都转为有符号的，都转为有符号的吧。
因为无符号遇到负数就悲剧了，用有符号的，在 ...
在做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的充要性质。
用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 ...
关于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 ...
简单概要的说Endian表示数据在存储器中的存放顺序。
内存、硬盘的最小存储单位是字节，一个字节有8个位。
其他数据都是由若干个字节组成，所以我们有必要了解两种存放方式的不同。
google了两个图看一下大端(Big Endian)与小端(Little Endian)的区别。
额。。这里竟然贴不了图。详见wiki吧http://en.wikipedia.org/wiki/Endianness
小端，数值低位在物理低位；大端，数值高位在物理低位。
因为我们把数据写到硬盘的时候是按照这个顺序来的，所以要特别注意。
根据这个特性可以写个简单的验证程序，判断机器使用的是哪种方式 ...
内核自带的原子操作可以帮助高效地我们实现引用计数等功能。
介于这么一个前提，一个引用对象不可能同时被引用和删除。
以下可以简单地实现引用计数。
内核中的定义：
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)，
表示自减之 ...
通过程序了解高速缓存
- 博客分类：
- 常识
cpu进行运算之前会有一个步骤，就是把内存的数据把拿到高速缓存区（L1,L2,...)。
一般说来，当访问内存的某个位置时，会把这个位置附近的数据也搬过去，跟硬盘到内存的pagecache相似。
如果频繁命中这个高速缓存区，可以大大提高程序的运行速度。
所以如果用一个二元对表示一次运算（运行时刻，数据位置），
将此二元序列关于时间排序，那么我们就应该让相邻二元对的数据位置尽可能接近。
见两个程序：
const int N = 1 << 12;
typedef double Type;
Type a[N][N], b[N][N], c[N][ ...
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) ( ...
用ICE框架可以很容易地实现远程函数调用，广泛使用在分布式系统中。
ICE框架由客户端和服务器组成，支持客户端并发地调用服务器的服务。默认是一个同步调用。可以改成异步调用。
下面给出一个简单的例子。实现客户端和服务器间的一问一答。
服务器部分：
服务器做的工作稍微多点，首先我们需要定义一个ice文件，包含我们需要的接口。
IM.ice
#ifndef IM_ICE
#define IM_ICE
module IM {
interface IMInterface {
int SendMsg(
...
我们想要一种哈希，可以将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) ...
leveldb学习二
- 博客分类：
- ldb
这里主要收集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），
...
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(st ...
leveldb学习一
- 博客分类：
- ldb
下了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 ...
一棵树有N个结点，高度为d。size[i]表示子树i的大小，则sum{size} <= N * d
当d不大时这个结论可以被利用。。
一个可以用于复杂度分析的结论
- 博客分类：
- 数学
最近在想出个题目，但题目没出成。不过想出了一个结论。
给定两个正整数序列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)就都不是最 ...