随机数种子的选择
随机数生成器的质量七绝于其产生的序列是否在任意输入下拟合均匀分布,相对而言,选择一个优秀的随机数生成器不是件特别困难的事情,然而选择优质的随机数种子却有许多需要注意的地方。在只需要产生拟合均匀分布的随机序列时,选取随机数种子没有特别的要求。然而随机数生成器往往会被用于产生密钥的哈希算法,此时对于种子的选取就有特定的要求。
有一些反面教材可供参考:
1995年9月时,当时流行的Netscape浏览器使用当前时间、当前Netscape的进程号和父进程号产生随机数种子。当时加州大学伯克利分校的研究员就实现了暴力破解Netscape的加密信息。
另一个例子是Kerberos协议的v4版本,它将当前时间与一些其他信息异或起来产生随机数种子。这个异或位运算直接将其他有效的信息屏蔽了,只留下20位容易预测的值,将密钥的空间从72万亿左右直接减少到1百万多一点,几秒钟时间就可以被暴力破解。
在选择随机数种子的时候容易犯下面这些错误:
- 从一个很小的空间里选取种子:如果你选择的随机数种子只有8位长度,那么无论随机算法怎样,都最多只有256种可能的随机数序列。
- 仅将当前时间作为随机数种子:尽管UNIX API返回精确到毫秒级的时间,但是大多数操作系统处理时间的精度都不到1/60秒,那么,即使在1个小时是邻域内,也只有216000种可能的取值,对于暴力破解来说太容易了。
- 自己泄漏随机数种子:如果种子中使用了当前时间作为产生随机数种子的依据之一,那么就不要以任何方式泄露这个信息,例如不要在未加密的消息头部包含被作为随机数种子产生依据的时间信息。
- 使用网卡或硬件序列号:这种信息往往都是结构化的,而非散列的,结构化的信息被穷举的难度大大降低了。
对于选择安全的随机数种子,有一些比较好的方案:
- 使用真正随机的数据源,比如一些噪点,装配相应的传感器,分析传入的信号的噪声,各种自然界的信号都是可以的。当然设备提供的现成的模拟信号也是可以的,例如/dev/audio在没有插入麦克风时提供的随机噪音,cat /dev/audio | compress,压缩一下可以进一步模糊值的实际含义。
- 获取系统底层的数据,也就是只有本机进程才有权限获取到的,不容易猜测到相近值,无法预先缩小取值范围的数据。比如系统当前使用的内存分页情况、CPU的温度、到某点的网络延迟的情况之类的。
- 让用户输入一串字符,分析用户按键的间隔时间,作为产生随机数种子的依据。千万不要只是取一个平均什么的,从统计的规律来看,按键的间隔时间一般也是在一个比较小的区间内的,要做取模、相乘等运算,产生不能预知可能分布情况的无意义的值。当然,要是结合鼠标移动的信息,就更好了。
CRUSH:受控的、可扩展的数据副本分散存储方案(Part 3)
CRUSH:受控的、可扩展的数据副本分散存储方案
3.2 副本位置策略
动作序列 | 结果 |
---|---|
take(root) | root |
select(1,row) | row2 |
select(3,cabinet) | cab21 cab23 cab24 |
select(1,disk) | disk2107 disk2313 disk 2437 |
emit |
[算法1:CRUSH确定对象x的存放位置]
3.2.1 冲突、故障和过载
3.2.2 副本排序
3.3 映射变更与数据移动
3.4 桶的类型
项目名 | Uniform | List | Tree | Straw |
速度 | O(1) | O(n) | O(log n) | O(n) |
添加项 | 差 | 最优 | 好 | 最优 |
移除项 | 差 | 差 | 好 | 最优 |
3.4.1 Uniform Bucket
3.4.2 List Bucket
3.4.3 Tree Bucket
3.4.4 Straw Bucket
CRUSH:受控的、可扩展的数据副本分散存储方案(Part 2)
CRUSH:受控的、可扩展的数据副本分散存储方案
2 相关工作
3 CRUSH算法
3.1 层次化Cluster Map
CRUSH:受控的、可扩展的数据副本分散存储方案(Part 1)
CRUSH:受控的、可扩展的数据副本分散存储方案
摘要
1 简介
在C++中使用成员函数指针
函数指针的语法相对比较复杂,成员函数指针则在此基础上进一步引入了类作用域限定。让我们来了解一下成员函数指针的写法。
首先回顾一下函数指针的使用方法。有这样一个函数:
double func(double x) { return 3.14 * x; }
我们这样声明函数指针,并且进行调用:
double (*pfunc)(double x); pfunc = &func; cout << (*pfunc)(1.1) << endl;
指针的声明包括返回类型、指针名和函数的参数表,对于一个强类型的编译型语言,这些要素都必不可少。由于运算符优先级的规定,还要特别注意在适当的位置加上括号。
对于成员函数指针,就是增加了一个作用域限定。
首先有一个类A,包含几个类型相同的函数。
class A { public: void f1(int x) { cout << "f1:" << x << endl; } void f2(int x) { cout << "f2:" << x << endl; } void f3(int x) { cout << "f3:" << x << endl; } };
然后类B的对象会调用类A的对象的成员函数,然而具体调用哪一个还不知道,我们通过指针的方式来实现,在运行时将指针指向一个类型兼容的成员函数。
class B { public: void (A::*pf) (int x); //注意作用域运算符和*的次序,括号不能省略 void callF(int x) { A a; (a.*pf)(x); } };
我们在外部实例化B的对象,然后为B的成员函数指针赋值,确定将要调用的是哪一个函数。
cout << "Hello world!" << endl; B b; b.pf = &A::f2; b.callF(5);
MySQL事件调度器的基本使用方法
根据MySQL的官方文档,从MySQL的5.1.6版本开始,MySQL支持了事件调度器,用于处理事件的调度与执行。触发器用于根据DML操作来触发事件,而事件调度器则是定时触发事件,功能类似于Linux的crontab计划任务,但是控制更为精确。在MySQL支持这项功能之前,往往通过Linux的crontab来辅助进行定时任务的触发,而当我们对于任务有更高的定时要求时,或者考虑调用接口处的性能瓶颈时,就需要使用到事件调度器(Event Scheduler)。
首先确保数据库选项event_scheduler处于开启状态。
show variables like 'event_scheduler';
如果我们看到ON,就表示这个功能处于开启状态,如果为OFF,表示关闭,DISABLED表示禁用。请注意,在数据库实例启动的情况下,我们可以随时在on和off间进行切换,但是,无法从on或off切换到disabled,也无法从disabled切换到on或off。只有在数据库关闭的状态下,这种转换才会生效。(DISABLED状态是在5.1.12版本中引入的)
set @@global.event_scheduler=on;
设置完成后,事件调度器就被开启了,实质上,是在MySQL实例中新建了一个事件调度器线程,通过show processlist\G命令,可以找到一个User为event_scheduler的线程,就表示事件调度器现在可以使用了。
接着我们随便创建一个存储过程,比如往某个表插入一条记录,好让事件调度器进行调度。
delimiter // create procedure `do_something`() begin insert into timelog values (); end; // delimiter ;
创建完毕后,我们就开始创建事件,事件最重要的部分有以下几个:
- 事件名称,这个很简单,就是给事件起个名字,加上IF NOT EXISTS的话,如果给定名称的事件已经存在了就不会再创建,并且只抛出一个Warning。
- 调度时间(ON SCHEDULE),可以定义事件被触发的具体时间,也可以指定事件被触发的周期,如果指定周期性任务,还可以指定开始时间和结束时间。
- 事件完成后的行为(ON COMPLETION),默认为NOT PRESERVED,即事件完成以后删除任务本身,注意,对于周期性的任务,不表示事件只做一次,而是指到达结束时间后,再删除这个事件。可以将它指定为PRESERVED,那么当事件完成以后,不会被删除。
- 事件体,就是事件具体需要做什么,定义方式和存储过程类似。
CREATE EVENT IF NOT EXISTS `log_every_minute` ON SCHEDULE EVERY 1 MINUTE ON COMPLETION PRESERVE DO CALL do_something();
在event_scheduler为on的情况下,事件一经创建就会生效。
这样,我们就成功创建了一个事件,每分钟会在timelog表中插入一条记录,当然,我们可以根据自己的需要,让MySQL去做一些更为复杂的任务。
C++中的函数对象与Lambda表达式
函数对象是C++中以参数形式传递函数的一个很好的方法,我们将函数包装成类,并且利用()运算符重载实现。
typedef class hello { public: void operator()(double x) { cout << x << endl; } } hello;
这时候hello是一个类,我们可以实例化一个对象hello h;,然后通过h(3.14)的方式来调用这个类的成员函数,如果某个函数需要这个函数作为回调函数,则可以将这个hello类的对象传入即可。
因为这是一个类的定义,因此我们完全可以在其中定义一些包含额外信息的成员和一些构造函数,让这个函数对象可以做更多不同的可定制的任务,最终的行为实际上只是调用了这个()运算符重载函数。这种做法比C++函数指针要容易理解得多,也不容易写错。
而Lambda表达式则是C++中的新语法,实现了许多程序员渴望的部分闭包特性。C++中Lambda表达式可以被视为一种匿名函数,这样,对于一些非常短,而且不太可能被其他地方的复用的小函数,可以通过Lambda表达式提高代码的可读性。
在Lambda表达式中对于变量生命期的控制还是与完全支持闭包的JavaScript非常不同,总而言之,C++对于变量声明期的控制在新标准中完全向前兼容,也就是局部变量一定在退出代码块时被销毁,而不是观察其是否被引用。因此,尽管C++的Lambda表达式中允许引用其代码上下文中的值,但是实际上并不能够保证引用的对象一定没有被销毁。
Lambda表达式对于上下文变量的引用有值传递和引用传递两种方式,实际上,无论是哪种方式,在产生Lambda表达式对象时,这些上下文值就已经从属于Lambda表达式对象了,也就是说,代码运行至定义Lambda表达式处时,通过值传递方式访问的上下文变量值已经被写入Lambda表达式的栈中,而引用方式传递的上下文变量地址被写入Lambda表达式的栈中。因此,调用Lambda表达式时得到的上下文变量值就是定义Lambda表达式时这些变量的值,而引用的上下文变量,如果已经被销毁,则会出现运行时异常。
Lambda表达式的基本语法是:
[上下文变量说明](Lambda表达式参数表) -> 返回类型 { 语句块 }
上下文变量说明部分就是说明对于上下文变量的引用方式,=表示值传递,&表示引用传递,例如,&s就表示s变量采用引用传递,不同的说明项之间用逗号分隔,可以为空,但是方括号不能够省略。第一项可以是单独的一个=或者&,表示,所有上下文变量若无特殊说明一律采用值传递/引用传递,什么都不写默认为值传递。
Lambda表达式和TR1标准对应的function<返回类型 (参数表)>对象是可以互相类型转换的,这样,我们也可以将Lambda表达式作为参数进行传递,也可以作为返回值返回。
下面看一个Lambda表达式各种使用方法的完整例子:
// compile with: /EHsc #include <iostream> #include <string> #include <functional> //这是TR1的头文件,定义了function类模板 using namespace std; typedef class hello { public: void operator()(double x) { cout << x << endl; } } hello; //函数对象的定义,也是非常常用的回调函数实现方法 void callhello(string s, hello func) { cout << s; func(3.14); } //一个普通的函数 void callhello(string s, const function<void (double x)>& func) { cout << s; func(3.14); } //这个函数会接受一个字符串和一个Lambda表达式作为参数 void callhello(string s, double d) { [=] (double x) { cout << s << x << endl; }(d); } //这个函数体内定义了一个Lambda表达式并立即调用 function<void (double x)> returnLambda(string s) { cout << s << endl; function<void (double x)> f = ([=/*这里必须使用值传递,因为s变量在returnLambda返回后就被销毁*/] (double x) { cout << s << x << endl; }); s = "changed"; //这里对s的修改Lambda表达式是无法感知的,调用这句语句前s在Lambda表达式中的值已经确定了 return f; } //这个函数接受了一个值传递的字符串变量s,我们将Lambda表达式作为返回值返回 function<void (double x)> returnLambda2(string& s) { cout << s << endl; function<void (double x)> f = ([&s/*这里可以使用引用传递,因为s是引用方式传入的,不随函数返回而消亡*/] (double x) { cout << s << x << endl; }); s = "changed"; //这里对s的修改Lambda表达式是可以感知的,因为s以引用方式参与到Lambda表达式上下文中 return f; } //这个函数接受了一个引用传递的字符串变量s,将Lambda表达式作为返回值返回 int main() { hello h; callhello("hello:", h); //用函数对象的方式实现功能 callhello("hello lambda:", -3.14); //这个函数体内定义了一个Lambda表达式并立即调用 int temp = 6; callhello("hello lambda2:", [&] (double x) -> void { cout << x << endl; cout << temp++ << endl; }); //这个函数会接受一个字符串和一个Lambda表达式作为参数 cout << temp << endl; function<void (double x)> f = returnLambda("lambda string"); //这个函数接受了一个值传递的字符串变量s,我们将Lambda表达式作为返回值返回 f(3.3); string lambdastring2 = "lambda string2"; //这个变量在main函数返回时才被销毁 f = returnLambda2(lambdastring2); //这个函数接受了一个引用传递的字符串变量s,将Lambda表达式作为返回值返回 f(6.6); system("pause"); }
C++中的typedef语法简介
根据名字也可以猜测到,typedef这种语法可以用于定义类型,如果某种类型的名称很长,或者未类型增加语义,那么我们就可以考虑使用typedef。看看最简单的例子:
typedef int INT;
上面的一行代码就表示INT也能代表int,这条定义可以在Windows头文件中找到。有什么意义呢?这是一种跨平台编译的考虑,看一下另一个Windows头文件中的例子:
#ifndef UNICODE typedef char TCHAR; #else typede wchar_t TCHAR; #endif
如果当前环境支持Unicode,那么TCHAR就会等价于wchar_t宽字符类型,否则TCHAR等价于char类型,那么程序员就可以借助TCHAR来隐藏具体的编译环境。
此外,typedef还可以增强语义,在Windows中所有的句柄本质都是void*类型,而为了增强语义,产生了HWND、HMENU、HBRUSH等不同的类型,让程序可读性增强。
大多数情况下,typedef是可以用#define来进行替换的,例如:
#define INT int
不过问题在于,#define只是进行了简单的字符替换,在编译前就被预编译器处理了,而typedef的处理则是编译器行为,因此使用typedef,编译器将能够视INT为一个类型,而不是其他东西。下面还有一个用#define容易引起混淆的例子。
#define pINT int*; typedef int *pINT2; pINT a, b; pINT2 c, d;
一般而言,我们通过类型定义,是希望将pINT定义成一种类型,那么用这种类型进行定义得到的变量,都应该是这种类型。而如果使用#define,那么看起来我们用pINT定义了a和b,实际上只有a是int*,而b只是int。使用typedef很好地避免了这个问题,c和d都是int*类型,这样不至于产生混乱的语义。
另外,因为typedef不是预编译指令,而被当作语句执行,因此也是有作用域的,typedef的作用域和一般变量相同。冲突的定义会进行覆盖,较晚执行的typedef会覆盖较早执行的typedef。
最后,typedef还可以用来定义类、结构体、联合体、数组,甚至是函数类型,下面有一个比较全面的代码例子,可以参考注释理解其中的含义:
#include <iostream> using namespace std; typedef int* _int, _int2; //_int是int*类型,而_int2是int类型 typedef int INT; //INT是int类型 typedef _int *INT2, *INT3; //INT2和INT3都是*_int类型,也就是**int类型 typedef void (*funcptr)(double); //funcptr是一个函数指针类型,指向返回值为void,接受一个double类型参数的函数 typedef union { char c; int i; bool b; } Foo; //Foo是一个联合体 typedef class TestClass { int a, b, c; public: TestClass(int a, int b, int c) : a(a), b(b), c(c) { } } TESTCLASS; //TESTCLASS就是TestClass类 void hello(double x) { //funcptr可以指向这个函数 cout << x << endl; } int main() { INT a = 6; _int2 e = 7; _int c = &a; INT2 b = &c; INT3 d = &c; cout << a << e << *c << **b << **d << endl; funcptr p = hello; p(3.333); cout << p << endl; Foo foo; foo.i = 65; cout << foo.b << foo.c << foo.i << endl; TESTCLASS tc(1, 2, 3); system("pause"); return 0; }
C++断言与静态断言
断言是很早之前就有的东西了,只需要引入cassert头文件即可使用。往往assert被用于检查不可能发生的行为,来确保开发者在调试阶段尽早发现“不可能”事件真的发生了,如果真的发生了,那么就表示代码的逻辑存在问题。最好的一点就是,断言只在Debug中生效,因此对于Release版本是没有效率上的影响的。
#include <iostream> #include <cassert> using namespace std; int main() { int i = 22; assert(i != 22); system("pause"); return 0; }
上面的代码就表示,你确认在这里i一定不会等于22,如果事实上真的是22,那么程序就会无情地被abort,并报告出现问题的源文件和行号(使用了魔法常量__FILE__和__LINE__),有助于及时定位问题。
断言有一个问题,就是一定会abort,强制整个程序退出而导致调试也无法继续进行,就像上图这样,出现问题后,我们知道了出现问题的行号,但是我们需要手动在该行的上面设置断点,重新开始调试才能够检查到发生问题时各个变量的状态。而且,有时问题不是那么容易重现,于是就可能出现没法重现错误再检查状态的问题。
所以,我们可以自己写一个类似的宏来解决这个问题,我们希望在违反断言时触发断点陷阱门中断而不是调用abort,这样,在违反断言时程序会暂停下来,等待程序员来检查当前的状态有何异常。
下面是一个Visual C++中的实现。
#include <iostream> #include <cassert> using namespace std; #define _ASSERT(x) if (!(x)) __asm {int 3}; int main() { int i = 22; //assert(i != 22); _ASSERT(i != 22); system("pause"); return 0; }
上面定义了一个宏,名字当然可以自己取,实际上做的一件事就是检查断言,然后如果断言结果为false(0),那么就调用内联汇编指令int 3陷入调试中断。
在2011年的C++标准中出现了静态断言(static_assert)的语法,所谓静态断言,就是在编译时就能够进行检查的断言,static_assert是C++的标准语法,不需要引用头文件。静态断言的另一个好处是,可以自定义违反断言时的编译错误信息。
#include <iostream> using namespace std; int main() { const int i = 22; static_assert(i != 22, "i equals to 22"); system("pause"); return 0; }
这个代码,将无法通过编译,因为i的值违反了静态断言。
静态断言的限制是,断言本身必须是常量表达式,如果这样的i不是常量,静态断言是不符合语法的。
大规模中英文单词模糊搜索问题的分析(二)
经过了大约一个星期时间的考虑,也研究了一下各种开源项目的情况。
本来满怀期待地发现了拼写检查器Jazzy的源码研究起来,不过后来发现Jazzy已经两年无人问津了,还是有那么点失望的,不过总的来讲,从拼写检查这个思路上,还是找到了一点新的思路的。
原来使用编辑距离的方法计算单词之间的距离,现在这个核心思想还是没有变,在索引的问题上也有了更多一些的考虑。
目前考虑下来的主要处理流程是这样的:
1. 对所有库中的人名进行分词,英文按照单词边界进行拆分,而中文按照单个汉字进行拆分,拆分完的汉字全部转换为拼音,这一步比较简单。完成以后就产生了两张二维表,分别是单词表(词典,包含单词、引用计数、是否来自黑名单数据)和倒排索引表(包含单词id、数据库原始条目的id、单词index)。这样就完成了类似Lucene的倒排索引。
2. 为了更好地计算编辑距离,需要建立四张编辑距离权值表(二维表replacement、swap和一维表insert、delete),四张表都不是十分精确的,但是作为索引确实没有十分精确的必要,因为具体的相似度还是依赖于对于单条记录的详细检查。
3. 服务器守护进程随时以流水线方式处理单词与单词之间的相似关系,采用拼写检查器的方法找到字典中的近似单词。
4. 实际向服务器送出查找请求时,服务器首先找到能够精确匹配所有单词的条目,逐条进行相似度检查。如果结果已经过多,那么没有必要再进行后续的查找。如结果较少,那么继续匹配部分单词完全匹配的条目。
5. 如果结果仍然较少,则首先根据编辑距离权值表进行短距离的变换,尝试匹配变换后的结果。
6. 如果仍然没有足够的结果,那么去查找单词近似关系表,如果该单词的近似条目可用,则立即查询得到结果。
7. 如果该单词的近似关系表还没有建立完成,那么提高该单词近似关系处理的优先级,使其立即完成,并进行结果查询。
8. 如果根据待测样本中存在于字典中的单词无法找到足够的项,那么进一步查找不存在于字典中的项,查找流程按照5、6、7的方式进行,建立完成后该单词会被增加到字典中,用以加速下一次的查找。