数码天地 今日: 0|主题: 4756|排名: 52 

最后发表： ubuntuhk
回复内容：
还是装个杀毒软件防身吧，这年头只要上网，电脑就是不安全的

最后发表： troublemaker
回复内容：
博客贴，顶一下～～～·

最后发表： justinli79
回复内容：
big-O notation
(definition)

Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). The notation is read, "f of n is big oh of g of n".

Formal Definition: f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

little-o notation
(definition)

Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = o(g(n)) means f(n) becomes insignificant relative to g(n) as n approaches infinity. The notation is read, "f of n is little oh of g of n".

Formal Definition: f(n) = o(g(n)) means for all c > 0 there exists some k > 0 such that 0 ≤ f(n) < cg(n) for all n ≥ k. The value of k must not depend on n, but may depend on c.

最后发表： justinli79
回复内容：
如题，有没有知道Black-Scholes期权定价模型的？
简单来说这个模型啥意思啊？

最后发表： someonehappy
回复内容：
问题的关键就是在这里。你说的５０％很对，不过那是建立在一扇门被打开以后的基础上的。而这个原始题目本身是严格的从一开始三扇门的时候开始的，初始条件完全不同，所以这其实是两个题目了。所以有两个答案。

另外我总感觉，概率的数字结果，和人的直观的对问题的感觉经常是不一样的，也许是因为人思考问题往往是从表面或者是比较明显的现状开始，而如果问题比较复杂，步骤比较多，脑子就开始不够使了，就需要一步步写下来分析。分析的多了，抽象总结出来，就成了概率论之类的东西了。

最后发表： someonehappy
回复内容：
清cache
重起
杀毒
恢复ie安全和高级设置的缺省设置
安装其他不同核心的浏览器
重装操作系统

以上方法组合使用

最后发表： 青山
回复内容：
是啊，我现在做大计算量的人工智能程序，都用java，而不用C了。
我现在的瓶颈是内存和I/O速度，不是计算速度。

最后发表： beysup
回复内容：
CCNA飘过

最后发表： key
回复内容：


我写东西很少不是原创的，哈哈。。。你一个个去支持吧，哈哈。。
即使是参考了别人的东西，内容和代码都是我重新写的
没办法，打英文我快，打中文我更快。。。

最后发表： key
回复内容：
了解Java语言的人都知道，access modifier的排序是：
public > protected > default > private

protected描述的对象能在子类中被使用。看下面的程序：这个程序没有问题。再请看，如果把程序分成两个文件，一个是BX.java，另一个是B.java
BX.javaB.java上面的程序编译是出错的。问题出在Line-8。它和前面的程序的最大不同，
是两个类处在不同的package下。这样一来，虽然B extends BX，但
在static方法下还是不能用protected描述的方法。

事实上，用protected描述的数据成员也不能用，static nested class，
如果放在非静态成员函数中，如果使用BX bx = new BX();这样的形式生成对象再
访问其protected成员，还是不行，但如果用this或直接访问其成员还是可以的，
只是nested class还是不行，下面的代码放在class B中：第9行还是出错，其他是正确的。

最后发表： key
回复内容：
区别是：前者只能向前，后者可以向后。。。。

最后发表： chenlocus
回复内容：


我看到seek上C++的工作也不少嘛。我就不明白，为什么C/C++还被认定为紧缺职业呢？

最后发表： boskey
回复内容：
LZ写得不错啊，这么一整，还真清楚明了啊！！哈哈

最后发表： key
回复内容：
int x = 0;
System.out.printf("%b", x);

得到的是true，这会让一个C/C++程序员疯掉。
这是因为Java在处理这个printf的时候，会做下面的工作：
1. 把int x转成Integer ix，即做autoboxing，值不变，还是0
2. 尝试显示，因为Integer ix != null，通过%b显示时，由于对象不是null，所以相当于 b = true
3. 通过String.valueOf(b)显示成"true"

总结起来，在.printf("%b")或.format("%b")的时候，只有两种情况会显示false，其他都是true，
这两种情况是：
1. boolean或Boolean值，false
2. 对象null

另外，对于%b，是不会出现runtime exception的

而%c, %d, %f都有可能出现runtime exception，而这三个标志对于boolean都是不接受，这也是和C程序中
非常不同的地方。更有过份的地方，用%f是不能显示integer值的，如下面的程序会引起RuntimeException
System.out.println("%f", 10);

原因？看看SDK的源代码就知道了：
显示Integer处理float即是说，Java是hardcode了这部分显示，没有道理可言。

最后发表： yuba
回复内容：
B的构造函数不是public的，是default (package visibility)的

最后发表： Tux
回复内容：
Swing是基于AWT的，也有Layout的概念，至少1.4/1.5里是。

当初懒，就用JBuilder和Eclipse的插件拖，结果后者生成的代码好烂！xyLayout应该不是Sun的东西。

当初学习Java写了个IPSearch，花了不少时间。Java Swing作UI真是活受罪。SWT相对好一些，应该都是通过JNI调OS的API，所以速度上接近于native的...

最后发表： key
回复内容：
我的一本烂书中说到，any nested class can be declared within any block of code,
such as a class and a method. 我差点中招了。

事实上上面的nested class改成inner class就没问题。而static nested class只能紧随outer class，
或者其上一级也是一个static nested class.

最后发表： key
回复内容：


我在准备扛个牌子出街，写上
Coding Java for Food

Sample可以参考core总的头像

最后发表： kickstar
回复内容：
会的越多，才发现不会的越多

最后发表： ubuntuhk
回复内容：

最后发表： coredump
回复内容：
Javascript有太多tricky的地方，不同的引擎和执行环境效果也不同，只能多试了，没有办法。

最后发表： flyspirit
回复内容：
Javascript虽然基于对象，却不是传统意义上的面向对象语言。需要另外包装才能面向对象化。

最后发表： figaro
回复内容：
很好，以后慢慢看

最后发表： micchy
回复内容：
恩，域名放弃了，有备用的，谢谢哈

最后发表： procoder
回复内容：
powerscript好像很容易反编译的，读书的时候学过，但是没有用过。

最后发表： key
回复内容：
我把之前用Java写的程序用FLTK重写一次，时间基本上差不多。
采用固定窗口大小，没有resize，通过计算得到了layout的位置后就直接写上去，
这样省了不少时间。

不过我这个小程序GUI任务不重，还不能说明问题

最后发表： flyspirit
回复内容：
什么上层的东西不是对底层的包装呢？

最后发表： key
回复内容：


背O()呀？
推荐看＜Data Structures, Algorithms, and Applications in C++＞，Sartaj Sahni，
中文版＜数据结构、算法与应用－－C＋＋语言描述＞，机械工业出版社，汪诗林等译
这本书第二章 程序性能中对于时间复杂性的讨论比较好，有空可以看一下。

然后就是klux说的MIT的Introduction to Algorithm，但这本书主要是数学计算，不头昏可以看一下

最后发表： ubuntuhk
回复内容：
不敢冒充砖家，就是混了个学位。

我的硕士论文是做基于Maximum Entropy建模方式来进行自然语言处理，那时候MaxEnt比较流行，现在换SVM统领江山了

最后发表： key
回复内容：
分类器部分的代码就更没技术含量，这里就不说了。我只是想联系一下bmf的实现，说一下一些关键的数据结构和流程。

bmf的程序入口在lex_*系统函数中。重要数据结构是typedef struct _tok tok_t, typedef struct _lex lex_t (lex.h)程序通过lex_load()把整封邮件读入lex_t数据结构中，保存在pbuf上。然后通过lex_nextline()找到下一行的起止位
（事实上lex_nextline是通过lex_nexttoken来调用），在lex_nexttoken中查找token，并记录到tok_t数据结构中。
其中tok_t数据结构只记录token的位置，数据还是保存在lex_t::pbuf指针里头。（lex.c）

词频记录放置在vec_t数据结构中，包括了token的保存和排队。而最后统计一封邮件中某个token出现的count是由
uint db_getnewcount( veciter_t* piter )函数获得的。总邮件数保存在struct _dbtdb数据结构中的nmsgs字段。

由于bmf的词频记录保存了总邮件数和单个词的词频，所以容易增删记录。

过滤时的运算程序如下：prob的计算如下：那行NON_EQUIPROBABLE。。。。顶，bmf的作者注释说他也不知道，照抄bogofilter的。。。。一般用另一个式子，那个式子和我们
前面的公式一致。

最后发表： coredump
回复内容：

一般而言，只有动态类型的编程语言可以在运行时更改程序自身的逻辑, 或者至少是像Java, C#这样的具有完整元数据,可以在运行时完成自省和反射能力的静态类型语言。一旦拥有了可以在运行时修改程序行为了魔力，就可以完成很多有趣的功能，以Java/C#举例，尽管都是静态类型的编程语言，但是凭借JDK/.NET CLR中的完备的元数据和反射API使得很多功能强大的框架，类库和设计模式的出现成为可能。比如Hibernate 的自动OR Mapping, Spring 等框架的IoC实现, JBoss 中的AOP 实现等等，而同样属于静态类型语言的 C++却缺少对应的实现，或者至少实现起来不是那么的自然和优雅。比如C++中也有个著名的AOP实现Aspect C++ ,但是却只能够对关注点进行静态织入,使得可用性大打折扣，接受度自然不如Java AOP高, 广大的C++程序员也只能够看着Hibernate, Spring之类的让人眼花缭乱的技术咽咽口水，然后埋头苦干地去和各种丑陋不堪的API战斗。


总有些人是不相信宿命的, 比如DynInst 库的作者们,硬是让人匪夷所思地实现了C/C++程序的运行时代码注入功能，下面一个小例子 ,可以牛刀小试下DynInst的威力：





上图右边表示一个运行中的进程(姑且称为FOO进程)，这个进程中有个叫foo()的函数和另一个sendMsg函数。左边红色的3个代码块是我们企图在不中断程序运行的前提下动态插入的代码逻辑片段，箭头表示了动态插入的位置。简单地说就是希望在执行foo()时,fooCnt变量加1，退出foo()时fooCnt变量减1，进入sendMsg函数时根据fooCnt值的不同决定是否运行addCounter函数。


要达到上图的目的，需要以下一种能力：
1. 在FOO进程中动态生成int型的变量fooCnt和bytes,并初始化为零
2. 找到foo()和sendMsg函数的位置，并确定3个代码插入点：foo()入口, foo()出口，sendMsg()入口
3. 动态产生3行待插入的代码
4. 讲代码依次插入到相应位置


下面我们来看看DynInst如何做到上面4个步骤：


1. 生成fooCnt和bytes并初始化,用的是BPatch_variableExpr,初始化用writeValue方法
BPatch_variableExpr *fooCnt = appThread->malloc(appImage->findType("int"));     BPatch_variableExpr *bytes = appThread->malloc(appImage->findType("int"));int zero = 0;fooCnt.writeValue(&zero);bytes.writeValue(&zero);

2. 用BPatch_arithExpr生成addCounter代码
BPatch_arithExpr fooCntPlusOne(BPatch_plus, *fooCnt, BPatch_constExpr(1));BPatch_arithExpr addCounter(BPatch_assign, *fooCnt, fooCntPlusOne);

相似的， 生成subCounter
BPatch_arithExpr fooCntMinusOne(BPatch_minus, *fooCnt, BPatch_constExpr(1));BPatch_assign subCounter(BPatch_assign, *fooCnt, fooCntMinusOne);
3. 插入到sendMsg的代码比较复杂一点
BPatch_paramExpr cntParam(2), sizeParam(3);BPatch_arithExpr calcBytes(BPatch_times, cntParam, sizeParam);BPatch_arithExpr addBytes(BPatch_plus, *bytes, calcBytes);BPatch_arithExpr addCounter(BPatch_assign, *bytes, addBytes);


对 "if (fooCnt)"的实现
BPatch_boolExpr fooCntCheck(BPatch_gt, *fooCnt, BPatch_constExpr(0));
BPatch_ifExpr addCounterIfInFoo(fooCntCheck, addCounter);


4. 找到插入第一行"addCounter(fooCnt, 1)"的插入点位置BPatch_Vector<BPatch_point*> *pointsFooEntry;BPatch_Vector<BPatch_point*> *pointsFooExit;BPatch_Vector<BPatch_point*> *pointsSendmsgEntry;pointsFooEntry = appImage->findProcedurePoint("foo", BPatch_entry);pointsFooExit  = appImage->findProcedurePoint("foo", BPatch_exit);pointsSendmsgEntry = appImage->findProcedurePoint("sendMsg", BPatch_entry);




终于可以动真格的插入了 ^_^
appThread->insertBlock(addCounter, *pointsFooEntry);appThread->insertBlock(subCounter, *pointsFooExit);appThread->insertBlock(addCounterIfInFoo, *pointsFooExit);

完整代码如下：


/*
Program:foo_patch
File:foo_patch.cpp
Usage:./foo_patch

*/
　　#include
　　#include
　　#include
　　#include
　　#include "BPatch.h"
　　#include "BPatch_Vector.h"
　　#include "BPatch_thread.h"
　　#include "BPatch_snippet.h"
　　int main(int argc, char **argv)
　　{
　　BPatch * bpatch = new BPatch;
　　BPatch_thread *appThread = bpatch->attachProcess(argv[1], atoi(argv[2]));
　　BPatch_image *appImage = appThread->getImage();


    BPatch_Vector *pointsFooEntry;
    BPatch_Vector *pointsFooExit;
    BPatch_Vector *pointsSendmsgEntry;


    pointsFooEntry = appImage->findProcedurePoint("foo", BPatch_entry);
    pointsFooExit  = appImage->findProcedurePoint("foo", BPatch_exit);
    pointsSendmsgEntry = appImage->findProcedurePoint("sendMsg", BPatch_entry);


    BPatch_variableExpr *fooCnt = appThread->malloc(appImage->findType("int"));
    BPatch_variableExpr *bytes = appThread->malloc(appImage->findType("int"));


    int zero = 0;
    fooCnt.writeValue(&zero);
    bytes.writeValue(&zero);


    BPatch_arithExpr fooCntPlusOne(BPatch_plus, *fooCnt, BPatch_constExpr(1));
    BPatch_arithExpr addCounter(BPatch_assign, *fooCnt, fooCntPlusOne);


    BPatch_arithExpr fooCntMinusOne(BPatch_minus, *fooCnt, BPatch_constExpr(1));
    BPatch_assign subCounter(BPatch_assign, *fooCnt, fooCntMinusOne);


    BPatch_paramExpr cntParam(2), sizeParam(3);
    BPatch_arithExpr calcBytes(BPatch_times, cntParam, sizeParam);
    BPatch_arithExpr addBytes(BPatch_plus, *bytes, calcBytes);
    BPatch_arithExpr addCounter(BPatch_assign, *bytes, addBytes);


    BPatch_boolExpr fooCntCheck(BPatch_gt, *fooCnt, BPatch_constExpr(0));
    BPatch_ifExpr addCounterIfInFoo(fooCntCheck, addCounter);


    appThread->insertBlock(addCounter, *pointsFooEntry);
    appThread->insertBlock(subCounter, *pointsFooExit);
    appThread->insertBlock(addCounterIfInFoo, *pointsFooExit);


　　appThread->detach(1);
　　}



从代码中可以看出，所有DynInst API类型或函数都以BPatch_开头, 其详细参考 可以从DynInst.org下载，大体上所有DynInst API分为以下几类：
1. BPatch
DynInst全局管理类, 同一时间只能实例化一次


2. BPatch_thread
代表一个执行线程，对单线程进程就代表整个进程，对多线程程序则代表其中一个线程。可以通过这个接口对相应线程进行启动,停止,退出等操作，如果在多线程环境中patch其中一个线程，其它线程将不受影响。


3. BPatch_image
代表正在执行中的代码.


4. BPatch_module
代表代码中的一个模块，或者是一个源代码文件，或者是一个动态库。


5. BPatch_function
函数，通过这个接口我们可以得到函数的入口，出口点


6. BPatch_point
代码注入点，注入点可以是函数的入口，出口，也可以是代码的片断位置，比如一个for循环之前/后,或者是一个纯粹的虚地址。


7. BPatch_type
类型，可以是内建类型，也可以是自定义类型，对于自定义类型，必须是存在于目标进程内的类型。


8. BPatch_snippet
代表各种可被用来注入的代码片段，大致上一个BPatch_snippet是有以下各种snippet组合而成：
8.1 BPatch_variableExpr
用于构造变量


8.2 BPatch_arithExpr
算术表达式, +-*/等


8.3 BPatch_boolExpr
布尔表达式, ><>=, and, or等


8.4 BPatch_gotoExpr
goto表达式，用来控制流程，可以用于构造循环代码，对于复杂的代码，最好先写好函数，否则你会被弄晕的 :-)




DynInst的实现原理


在上图中, 我们准备控制的进程是Application, 我们编写的patch程序是Mutator。在底层实现上Mutator依赖ptrace, /proc这样的系统级API用于实现进程的信息获取和控制权转移， 同时对于不同的系统，DynInst会把Mutator中编写的代码动态编译为相应格式的机器码，然后写入正在运行的目标进程所在的内存空间。对DynInst实现的细节感兴趣的朋友可以读一读这些Paper。




有了DynInst可以做什么？


DynInst把最难的部分解决了，一下子给出了巨大的想象空间，似乎C、C++这样的静态语言面对的所有障碍都消失了，剩下的事情就是充分发挥你的想像力了，下面是一坨坨已经用DynInst实现了的功能 (software/paper):

• DPCL 用DynInst实现的软件Profiling工具框架
• Dynaprof 用DynInst和DPCL实现的软件性能分析工具
• Open SpeedShop™ for Linux® SGI的商业软件调优工具,类似IBM PurifyPlus和Intel的VTune。 （可怜的SGI，默哀一下~~)
• TinyC2: Towards building a dynamic weaving aspect language for C 用DynInst实现的动态AOP，果然，呵呵。不过这个只实现了对C的AOP,这里还有个对C++的实现 (不过似乎不是用的DynInst), 另一对C++的Dynamic AOP实现Paper ，更多的关于C++ Dynamic AOP Papers 。
• ParaDyn 用于并行和分布式系统的软件性能测量和调整工具集

和DynInst类似的项目
微软研究院有一个Detours 的项目，在Windows上实现了类似DynInst的功能，不过主要用于拦截WINDOWS API，实现类似Hooks的功能，同时能够直接永久修改DLL,EXE对应的磁盘文件，对商业使用收费。



DynInst的现状


这里 和这里 有很多2009年DynInst年会的presentations，感兴趣的可以进一步了解。

最后发表： ubuntuhk
回复内容：
这么惨啊，安慰一下

最后发表： key
回复内容：



满树是一种特殊的二叉树，它除了最底的一层外，其他层都有2^(n-1)个结点。
完全二叉树则是一种特殊的满树，它的所有层，包括最底的一层都有2^(n-1)个结点。

最后发表： coredump
回复内容：
结论：

STM很好很强大, TBoost.STM的实现也的确很优雅，不过仍然有不少很tricky的地方，特别是在处理pointer和reference的时候。

在被Boost选为候选STM库之后, TBoost.STM已经比它的前身DracoSTM 快了10倍, 可见这帮哥们干活还是挺卖力的，TBoost.STM的开发目标是2010年随着Boost 1.39一起推出Boost.STM 1.0版，如果你等不及了，可以到Boost的sandbox的svn版本仓库中下载正在开发中的Boost.STM.

最后发表： coredump
回复内容：
COM太重了

最后发表： key
回复内容：
代码很短，直接贴代码好了。由于C++中的stack不支持遍历，只好用vector来做栈（其实应该用list）其中第32条的循环条件有点tricky

最后发表： coredump
回复内容：
只要visitor对应的场景是相对稳定的即可，visitor这个模式一开始就是应用在编译器语法检查，语法生成，语法映射等场合下，在这种情形下，语法规范被认为是稳定的，而由语法规范visitor生成的衍生功能是异变的。类似情形比如网络协议，框架，正规的商业规范等等都适合visitor模式。

如果想对稳定的那个发生了变化，则所以依赖的visitor需要跟着变也是合情合理的，比如.NET CLR发生了变化，Java语法发生了变化，http协议发生了变化等等。

最后发表： hoopoos
回复内容：
如果是数据结构和算法，我觉得还是用传统的面对过程的方式去做，因为效率高。对遍历，树，递归，之类的算法来说，基本类型比对象更节约内存，效率更高，速度更快。这些算法完成后封装成类，再用OO的方式被调用，更合适。算法这样的粒度，对设计模式来说，还是太细了点，按你标题来说，是有点小题大作了。

最后发表： 周星星1832
回复内容：

??

最后发表： key
回复内容：
这个总结来自C++ FAQ Lite：

14.4 友元不能被传递，不能被继承，也不是互利的
14.4 friendship isn't inherited, transitive, or reciprocal

1. I don't necessarily trust the kids of my friends.
2. I don't necessarily trust the friends of my friends.
3. You don't necessarily trust me simply because I declare you my friend.

另外应该还有一个：
你是我的朋友，但不代表你能访问我小孩的专用成员
My children doesn't necessarily trust you regarding their own properties.