Tuesday, December 18, 2007
Thursday, December 13, 2007
C++ virtual methods
1.简介
虚函数是C++中用于实现多态(polymorphism)的机制。核心理念就是通过基类访问派生类定义的函数。假设我们有下面的类层次：
class A
{
public:
virtual void foo() { cout << "A::foo() is called" << a =" new">foo(); // 在这里，a虽然是指向A的指针，但是被调用的函数(foo)却是B的!
这个例子是虚函数的一个典型应用，通过这个例子，也许你就对虚函数有了一些概念。它虚就虚在所谓“推迟联编”或者“动态联编”上，一个类函数的调用并不是在编译时刻被确定的，而是在运行时刻被确定的。由于编写代码的时候并不能确定被调用的是基类的函数还是哪个派生类的函数，所以被成为“虚”函数。
虚函数只能借助于指针或者引用来达到多态的效果，如果是下面这样的代码，则虽然是虚函数，但它不是多态的：
class A
{
public:
virtual void foo();
};
class B: public A
{
virtual void foo();
};
void bar()
{
A a;
a.foo(); // A::foo()被调用
}
1.1 多态
在了解了虚函数的意思之后，再考虑什么是多态就很容易了。仍然针对上面的类层次，但是使用的方法变的复杂了一些：
void bar(A * a)
{
a->foo(); // 被调用的是A::foo() 还是B::foo()？
}
因为foo()是个虚函数，所以在bar这个函数中，只根据这段代码，无从确定这里被调用的是A::foo()还是B::foo()，但是可以肯定的说：如果a指向的是A类的实例，则A::foo()被调用，如果a指向的是B类的实例，则B::foo()被调用。
这种同一代码可以产生不同效果的特点，被称为“多态”。
1.2 多态有什么用？
多态这么神奇，但是能用来做什么呢？这个命题我难以用一两句话概括，一般的C++教程（或者其它面向对象语言的教程）都用一个画图的例子来展示多态的用途，我就不再重复这个例子了，如果你不知道这个例子，随便找本书应该都有介绍。我试图从一个抽象的角度描述一下，回头再结合那个画图的例子，也许你就更容易理解。
在面向对象的编程中，首先会针对数据进行抽象（确定基类）和继承（确定派生类），构成类层次。这个类层次的使用者在使用它们的时候，如果仍然在需要基类的时候写针对基类的代码，在需要派生类的时候写针对派生类的代码，就等于类层次完全暴露在使用者面前。如果这个类层次有任何的改变（增加了新类），都需要使用者“知道”（针对新类写代码）。这样就增加了类层次与其使用者之间的耦合，有人把这种情况列为程序中的“bad smell”之一。
多态可以使程序员脱离这种窘境。再回头看看1.1中的例子，bar()作为A-B这个类层次的使用者，它并不知道这个类层次中有多少个类，每个类都叫什么，但是一样可以很好的工作，当有一个C类从A类派生出来后，bar()也不需要“知道”（修改）。这完全归功于多态--编译器针对虚函数产生了可以在运行时刻确定被调用函数的代码。
1.3 如何“动态联编”
编译器是如何针对虚函数产生可以再运行时刻确定被调用函数的代码呢？也就是说，虚函数实际上是如何被编译器处理的呢？Lippman在深度探索C++对象模型[1]中的不同章节讲到了几种方式，这里把“标准的”方式简单介绍一下。
我所说的“标准”方式，也就是所谓的“VTABLE”机制。编译器发现一个类中有被声明为virtual的函数，就会为其搞一个虚函数表，也就是VTABLE。VTABLE实际上是一个函数指针的数组，每个虚函数占用这个数组的一个slot。一个类只有一个VTABLE，不管它有多少个实例。派生类有自己的VTABLE，但是派生类的VTABLE与基类的VTABLE有相同的函数排列顺序，同名的虚函数被放在两个数组的相同位置上。在创建类实例的时候，编译器还会在每个实例的内存布局中增加一个vptr字段，该字段指向本类的VTABLE。通过这些手段，编译器在看到一个虚函数调用的时候，就会将这个调用改写，针对1.1中的例子：
void bar(A * a)
{
a->foo();
}
会被改写为：
void bar(A * a)
{
(a->vptr[1])();
}
因为派生类和基类的foo()函数具有相同的VTABLE索引，而他们的vptr又指向不同的VTABLE，因此通过这样的方法可以在运行时刻决定调用哪个foo()函数。
虽然实际情况远非这么简单，但是基本原理大致如此。
1.4 overload和override
虚函数总是在派生类中被改写，这种改写被称为“override”。我经常混淆“overload”和“override”这两个单词。但是随着各类C++的书越来越多，后来的程序员也许不会再犯我犯过的错误了。但是我打算澄清一下：
override是指派生类重写基类的虚函数，就象我们前面B类中重写了A类中的foo()函数。重写的函数必须有一致的参数表和返回值（C++标准允许返回值不同的情况，这个我会在“语法”部分简单介绍，但是很少编译器支持这个feature）。这个单词好象一直没有什么合适的中文词汇来对应，有人译为“覆盖”，还贴切一些。
overload约定成俗的被翻译为“重载”。是指编写一个与已有函数同名但是参数表不同的函数。例如一个函数即可以接受整型数作为参数，也可以接受浮点数作为参数。
2. 虚函数的语法
虚函数的标志是“virtual”关键字。
2.1 使用virtual关键字
考虑下面的类层次：
class A
{
public:
virtual void foo();
};
class B: public A
{
public:
void foo(); // 没有virtual关键字!
};
class C: public B // 从B继承，不是从A继承！
{
public:
void foo(); // 也没有virtual关键字！
};
这种情况下，B::foo()是虚函数，C::foo()也同样是虚函数。因此，可以说，基类声明的虚函数，在派生类中也是虚函数，即使不再使用virtual关键字。
2.2 纯虚函数
如下声明表示一个函数为纯虚函数：
class A
{
public:
virtual void foo()=0; // =0标志一个虚函数为纯虚函数
};
一个函数声明为纯虚后，纯虚函数的意思是：我是一个抽象类！不要把我实例化！纯虚函数用来规范派生类的行为，实际上就是所谓的“接口”。它告诉使用者，我的派生类都会有这个函数。
2.3 虚析构函数
析构函数也可以是虚的，甚至是纯虚的。例如：
class A
{
public:
virtual ~A()=0; // 纯虚析构函数
};
当一个类打算被用作其它类的基类时，它的析构函数必须是虚的。考虑下面的例子：
class A
{
public:
A() { ptra_ = new char[10];}
~A() { delete[] ptra_;} // 非虚析构函数
private:
char * ptra_;
};
class B: public A
{
public:
B() { ptrb_ = new char[20];}
~B() { delete[] ptrb_;}
private:
char * ptrb_;
};
void foo()
{
A * a = new B;
delete a;
}
在这个例子中，程序也许不会象你想象的那样运行，在执行delete a的时候，实际上只有A::~A()被调用了，而B类的析构函数并没有被调用！这是否有点儿可怕？
如果将上面A::~A()改为virtual，就可以保证B::~B()也在delete a的时候被调用了。因此基类的析构函数都必须是virtual的。
纯虚的析构函数并没有什么作用，是虚的就够了。通常只有在希望将一个类变成抽象类（不能实例化的类），而这个类又没有合适的函数可以被纯虚化的时候，可以使用纯虚的析构函数来达到目的。
2.4 虚构造函数？
构造函数不能是虚的。
3. 虚函数使用技巧 3.1 private的虚函数
考虑下面的例子：
class A
{
public:
void foo() { bar();}
private:
virtual void bar() { ...}
};
class B: public A
{
private:
virtual void bar() { ...}
};
在这个例子中，虽然bar()在A类中是private的，但是仍然可以出现在派生类中，并仍然可以与public或者protected的虚函数一样产生多态的效果。并不会因为它是private的，就发生A::foo()不能访问B::bar()的情况，也不会发生B::bar()对A::bar()的override不起作用的情况。
这种写法的语意是：A告诉B，你最好override我的bar()函数，但是你不要管它如何使用，也不要自己调用这个函数。
3.2 构造函数和析构函数中的虚函数调用
一个类的虚函数在它自己的构造函数和析构函数中被调用的时候，它们就变成普通函数了，不“虚”了。也就是说不能在构造函数和析构函数中让自己“多态”。例如：
class A
{
public:
A() { foo();} // 在这里，无论如何都是A::foo()被调用！
~A() { foo();} // 同上
virtual void foo();
};
class B: public A
{
public:
virtual void foo();
};
void bar()
{
A * a = new B;
delete a;
}
如果你希望delete a的时候，会导致B::foo()被调用，那么你就错了。同样，在new B的时候，A的构造函数被调用，但是在A的构造函数中，被调用的是A::foo()而不是B::foo()。
3.3 多继承中的虚函数 3.4 什么时候使用虚函数
在你设计一个基类的时候，如果发现一个函数需要在派生类里有不同的表现，那么它就应该是虚的。从设计的角度讲，出现在基类中的虚函数是接口，出现在派生类中的虚函数是接口的具体实现。通过这样的方法，就可以将对象的行为抽象化。
以设计模式[2]中Factory Method模式为例，Creator的factoryMethod()就是虚函数，派生类override这个函数后，产生不同的Product类，被产生的Product类被基类的AnOperation()函数使用。基类的AnOperation()函数针对Product类进行操作，当然Product类一定也有多态（虚函数）。
另外一个例子就是集合操作，假设你有一个以A类为基类的类层次，又用了一个std::vector来保存这个类层次中不同类的实例指针，那么你一定希望在对这个集合中的类进行操作的时候，不要把每个指针再cast回到它原来的类型（派生类），而是希望对他们进行同样的操作。那么就应该将这个“一样的操作”声明为virtual。
现实中，远不只我举的这两个例子，但是大的原则都是我前面说到的“如果发现一个函数需要在派生类里有不同的表现，那么它就应该是虚的”。这句话也可以反过来说：“如果你发现基类提供了虚函数，那么你最好override它”。
4.参考资料
[1] 深度探索C++对象模型，Stanley B.Lippman，侯捷译
[2] Design Patterns, Elements of Reusable Object-Oriented Software, GOF
哪些地方會用到Copy Constructor和Assignment Operator?
C#、Java都沒有copy constructor，所以這對大部分programmer都很陌生，簡單地說，凡需要copy的地方，就需要copy constructor：
1.由copy-initialization方式建立物件。
Ex.
Foo foo1;
Foo foo2(foo1);
以上直接使用copy constructor。
string s = "C++ Primer";
Foo foo = Foo();
此時是先由default constructor建立一個temporary object後，再由copy constructor將temporary object 『copy』給物件。????????????????????????????????????????????????
2.以by value的方式傳進function和由function return值。
Ex.
int Foo(int n);
只要不是使用by reference的方式，就得使用copy constructor。
3.建立STL container中的element。
Ex.vector
先由string的default constructor建立一個temporary string object，再由string的copy constructor『copy』到vector中每個element。
4.由initialization list建立array。
Ex.int ia[] = {1, 2, 3};
先由int default contructor先建立temporary int object，再由int的copy contructor『copy』到array中。
所以copy constructor其實是無所不在的，只是我們從來沒有發現，雖然C++ compiler會自己synthesize copy constructor，但也允許我們自己定義自己的Copy Constructor，這與C#、Java不同。
而assignment operator呢?
Foo foo1;
Foo foo2;
foo2 = foo1;
以上會執行foo2的assignment operator。
所以簡單的說，copy constructor和assignment operator都在做『copy』的動作，當資料是pointer，也就是動態資料時，就必須重新改寫，否則只會copy pointer，而不是copy data。
transaction isolation level
| Isolation level | Dirty reads | Nonrepeatable reads | Phantoms |
| Read uncommitted | Yes | Yes | Yes |
| Read committed | No | Yes | Yes |
| Repeatable read | No | No | Yes |
| Serializable | No | No | No |
- 悲观并发控制
一个锁定系统，可以阻止用户以影响其他用户的方式修改数据。如果用户执行的操作导致应用了某个锁，只有这个锁的所有者释放该锁，其他用户才能执行与该锁冲突的操作。这种方法之所以称为悲观并发控制，是因为它主要用于数据争用激烈的环境中，以及发生并发冲突时用锁保护数据的成本低于回滚事务的成本的环境中。 - 乐观并发控制
在乐观并发控制中，用户读取数据时不锁定数据。当一个用户更新数据时，系统将进行检查，查看该用户读取数据后其他用户是否又更改了该数据。如果其他用户更新了数据，将产生一个错误。一般情况下，收到错误信息的用户将回滚事务并重新开始。这种方法之所以称为乐观并发控制，是因为它主要用于数据争用较少的环境中，以及回滚事务的成本偶尔高于读取数据时锁定数据的成本的环境中。
Microsoft SQL Server 2005 支持某个范围的并发控制。用户通过为游标上的连接或并发选项选择事务隔离级别来指定并发控制的类型。
事务隔离级别控制：
- 读取数据时是否占用锁以及所请求的锁类型。
- 占用读取锁的时间。
- 引用其他事务修改的行的读取操作是否：
- 在该行上的排他锁被释放之前阻塞其他事务。
- 检索在启动语句或事务时存在的行的已提交版本。
- 读取未提交的数据修改。
- 在该行上的排他锁被释放之前阻塞其他事务。
选择事务隔离级别不影响为保护数据修改而获取的锁。事务总是在其修改的任何数据上获取排他锁并在事务完成之前持有该锁，不管为该事务设置了什么样的隔离级别。对于读取操作，事务隔离级别主要定义保护级别，以防受到其他事务所做更改的影响。
读已提交（Read Committed）：当一个事务运行在这个隔离级别时，一个查询只能看到查询开始之前的数据而永远无法看到脏数据或者是在查询执行时其他并行的事务提交做的改变。
如果一个正在执行一个 UPDATE 语句（或者 DELETE 或者 SELECT FOR UPDATE）的查询返回的行正在被另一个并行的未提交的事务更新，那么第二个试图更新此行的事务将等待另一个事务的提交或者回卷。如果发生了回卷，等待中的事务可以继续修改此行。如果发生了提交（并且此行仍然存在；也就是说，没有被另一个事务删除），这个查询将对该行再执行一便以检查新行版本是否满足查询搜索条件。如果新行版本满足查询搜索条件，那么该行将被更新（或删除或被标记为更新）。
可串行化（Serializable）提供最高级别的事务隔离。当一个事务处于可串行化级别，一个查询只能看到在事务开始之前提交的数据而永远看不到脏数据或事务执行中其他并行事务提交的修改。所以，这个级别模拟串行事务执行，就好象事务将被一个接着一个那样串行的，而不是并行的执行。
如果一个正在执行一个 UPDATE 语句（或者 DELETE 或者 SELECT FOR UPDATE）的查询返回的行正在被另一个并行的未提交的事务更新，那么第二个试图更新此行的事务将等待另一个事务的提交或者回卷。如果发生了回卷，等待中的事务可以继续修改此行。如果发生一个并行的事务的提交，一个可串行化的事务将回卷，并返回下面信息。
ERROR: Can't serialize access due to concurrent update
因为一个可串行化的事务在可串行化事务开始之后不能更改被其他事务更改过的行。
Tuesday, December 11, 2007
Java is Pass-By-Value, Dammit!
Introduction
http://javadude.com/articles/passbyvalue.htm
I finally decided to write up a little something about Java's parameter passing. I'm really tired of hearing folks (incorrectly) state "primitives are passed by value, objects are passed by reference".
I'm a compiler guy at heart. The terms "pass-by-value" semantics and "pass-by-reference" semantics have very precise definitions, and they're often horribly abused when folks talk about Java. I want to correct that... The following is how I'd describe these
- Pass-by-value
- The actual parameter (or argument expression) is fully evaluated and the resulting value is copied into a location being used to hold the formal parameter's value during method/function execution. That location is typically a chunk of memory on the runtime stack for the application (which is how Java handles it), but other languages could choose parameter storage differently.
- Pass-by-reference
- The formal parameter merely acts as an alias for the actual parameter. Anytime the method/function uses the formal parameter (for reading or writing), it is actually using the actual parameter.
Java is strictly pass-by-value, exactly as in C. Read the Java Language Specification (JLS). It's spelled out, and it's correct. (See http://java.sun.com/docs/books/jls/second_edition/html/classes.doc.html#37472)
In short: Java has pointers and is strictly pass-by-value. There's no funky rules. It's simple, clean, and clear. (Well, as clear as the evil C++-like syntax will allow ;)
Note: See the note at the end of this article for the semantics of remote method invocation (RMI). What is typically called "pass by reference" for remote objects is actually incredibly bad semantics.
The Litmus Test
There's a simple "litmus test" for whether a language supports pass-by-reference semantics:
Can you write a traditional swap(a,b) method/function in the language?
A traditional swap method or function takes two arguments and swaps them. Its basic structure looks like
// NON-JAVA!
swap(Type arg1, Type arg2) {
Type temp = arg1;
arg1 = arg2;
arg2 = temp;
}
If you can write such a method/function in your language such that calling
// NON-JAVA
Type var1 = ...;
Type var2 = ...;
swap(var1,var2);
actually switches the values of the variables var1 and var2, the language supports pass-by-reference semantics.
For example, in Pascal, you can write
{ Pascal }
procedure swap(var arg1, arg2: SomeType);
var
temp : SomeType;
begin
temp := arg1;
arg1 := arg2;
arg2 := temp;
end;
...
{ in some other procedure/function/program }
var
var1, var2 : SomeType;
begin
var1 := ...;
var2 := ...;
swap(var1, var2);
end;
or in C++ you could write
// C++
void swap(SomeType& arg1, Sometype& arg2) {
SomeType temp = arg1;
arg1 = arg2;
arg2 = temp;
}
...
SomeType var1 = ...;
SomeType var2 = ...;
swap(var1, var2); // swaps their values! (Please let me know if my Pascal or C++ has lapsed and I've messed up the syntax...)
But you cannot do this in Java!
Now the details...
The problem we're facing here is statements like
In Java, Objects are passed by reference, and primitives are passed by value.
This is half incorrect. Everyone can easily agree that primitives are passed by value; there's no such thing in Java as a pointer/reference to a primitive.
However, Objects are not passed by reference. A correct statement would be Object references are passed by value.
This may seem like splitting hairs, bit it is far from it. There is a world of difference in meaning. The following examples should help make the distinction.
In Java, take the case of
public void foo(Dog d) {
d = new Dog("Fifi");
}
Dog aDog = new Dog("Max");
foo(aDog);
the variable passed in (aDog) is not modified! After calling foo, aDog still points to the "Max" Dog!
Many people mistakenly think/state that something like
public void foo(Dog d) {
d.setName("Fifi");
}
shows that Java does in fact pass objects by reference.
The mistake they make is in the definition of
Dog d;
itself. When you write
Dog d;
you are defining a pointer to a Dog object, not a Dog object itself.
Calling
foo(d);
passes the value of d to foo; it does not pass the object that d points to!
The value of the pointer being passed is similar to a memory address. Under the covers it's a tad different, but you can think of it in exactly the same way. The value uniquely identifies some object on the heap.
The use of the word "reference" in Java was an incredibly poor choice (in my not-so-humble opinion...) Java has pointers, plain and simple. The designers of Java wanted to try to make a distinction between C/C++ pointers and Java pointers, so they picked another term. Under the covers, pointers are implemented very differently in Java and C/C++, and Java protects the pointer values, disallowing operations such as pointer arithmetic and invalid runtime casting.
However, it makes no difference how pointers are implemented under the covers. You program with them exactly the same way in Java as you would in C or C++. The syntax is just slightly different.
In Java,
Dog d; // Java is exactly like C or C++'s
Dog *d; // C++ And using
d.setName("Fifi"); // Java
is exactly like C++'s
d->setName("Fifi"); // C++
To sum up: Java has pointers, and the value of the pointer is passed in. There's no way to actually pass an object itself as a parameter. You can only pass a pointer to an object.
Keep in mind, when you call
foo(d); you're not passing an object; you're passing a pointer to the object.
For a slightly different (but still correct) take on this issue, please see http://www-106.ibm.com/developerworks/library/j-praxis/pr1.html. It's from Peter Haggar's excellent book, Practical Java.)
A Note on Remote Method Invocation (RMI)
When passing parameters to remote methods, things get a bit more complex. First, we're (usually) dealing with passing data between two independent virtual machines, which might be on separate physical machines as well. Passing the value of a pointer wouldn't do any good, as the target virtual machine doesn't have access to the caller's heap.
You'll often hear "pass by value" and "pass by reference" used with respect to RMI. These terms have more of a "logical" meaning, and really aren't correct for the intended use.
Here's what is usually meant by these phrases with regard to RMI. Note that this is not proper usage of "pass by value" and "pass by reference" semantics:
- RMI Pass-by-value
- The actual parameter is serialized and passed using a network protocol to the target remote object. Serialization essentially "squeezes" the data out of an object/primitive. On the receiving end, that data is used to build a "clone" of the original object or primitive. Note that this process can be rather expensive if the actual parameters point to large objects (or large graphs of objects).
This isn't quite the right use of "pass-by-value"; I think it should really be called something like "pass-by-memento". (See "Design Patterns" by Gamma et al for a description of the Memento pattern).
- RMI Pass-by-reference
- The actual parameter, which is itself a remote object, is represented by a proxy. The proxy keeps track of where the actual parameter lives, and anytime the target method uses the formal parameter, another remote method invocation occurs to "call back" to the actual parameter. This can be useful if the actual parameter points to a large object (or graph of objects) and there are few call backs.
This isn't quite the right use of "pass-by-reference" (again, you cannot change the actual parameter itself). I think it should be called something like "pass-by-proxy". (Again, see "Design Patterns" for descriptions of the Proxy pattern).
Friday, December 7, 2007
穆罕默德.尤努斯
BBC中文網昨天新聞〈孟加拉人獲諾貝爾和平獎〉報導，諾貝爾基金會 2006 年和平獎由孟加拉籍的經濟學家：穆罕默德.尤努斯與他所創立的銀行共同獲得。
TVBS 新聞網站〈尤諾斯救助貧困 獲諾貝爾和平獎〉有提到 Grameen 銀行最重要的意義：
尤諾斯在自傳中，自許為窮人的銀行家，他認為有錢人如果能幫助窮困的人，才能讓他們有餘力為社會多做貢獻。此外，尤諾斯也常親自下鄉，關心孟加拉鄉村民眾的生活，瞭解他們的需求之後，再藉由鄉村銀行提供適時的幫助，因此廣受孟加拉人的愛戴。
微型信貸（micro-credit），或者微型金融（micro-finance），這種以堅實理論基礎構築女性與鄉村農民等弱勢者的合作經濟模式，近年來在許多國內外場合都有機會被反覆提到。BBC 中文網新聞中有繼續解釋：
小額信貸在70年代發端於孟加拉國，它是滿足窮人信貸需求的一種信貸方式，貸款對象僅限於窮人，額度很小，無需抵押。自創立以來，小額信貸受到了窮人的熱烈歡迎，迅速推廣到亞洲、非洲和拉丁美洲的許多發展中國家，成為一種非常有效的扶貧方式。各國也根據本國特點逐步創新出新的小額信貸模式。
去年5月25日〈工商：張忠謀 榮獲日經亞洲獎〉我有看到日經亞洲獎的「區域成長獎」獎項得獎者，就是穆罕默德.尤努斯；去年也被稱為是國際微型金融的一年，繼社會企業（social enterprise）之後，這種微型的社會實踐變成了眾所皆知的重要概念與實作。在 wikipedia 中 Grameen（格拉明）銀行的介紹文章，關於格拉明電信計畫與乞丐貸款計畫等的介紹，也都讓人驚訝不已。
尤努斯在今年八月的一篇文章〈什麼是微型信貸？〉（What is Microcredit?）中細數不同型態的微型信貸，並且就他 Grameen 銀行所從事的方向做出澄清。這可以讓想要更深入了解這個重要概念的朋友有機會知道細節。
I think this is creating a lot of misunderstanding and confusion in the discussion about microcredit. We really don’t know who is talking about what. I am proposing that we put labels to various types of microcredit so that we can clarify at the beginning of our discussion which microcredit we are talking about. This is very important for arriving at clear conclusions, formulating right policies, designing appropriate institutions and methodologies. Instead of just saying “microcredit” we should specify which category of microcredit.
在諾貝爾和平獎被提名的總數一百九十一名角逐者當中，有很多都是具有全球知名度的國際人士。在公佈評選結果之前，得獎呼聲最高之一的是芬蘭前總統阿赫蒂薩里（Martti Ahtisaari）…這個名字有點耳熟能詳吧。他是現在代表聯合國主要推動 Kosovo 科索伏獨立計畫的幕後推手。在前面 GVO 翻譯計畫：〈塞爾維亞：聯合國代表 Ahtisaari，與 Kosovo、Metohia 的未來〉中他的論點引起塞爾維亞人的抗議（尤其是在塞爾維亞剛通過一部新憲法，宣示科索伏是主權範圍的一部份之後）。中國東突或疆獨人士也因獲選入圍，而讓某些中國媒體全面檢討「諾貝爾和平獎的泛政治化」（〈諾貝爾和平獎變了味〉，以及諾貝爾獎竟提名東突分子 瑞典議員用心不良）。
Wednesday, December 5, 2007
Reservoir Sampling
Problem Statement
source: http://gregable.com/2007/10/reservoir-sampling.html
Now that that is out of the way, Reservoir Sampling is a fun algorithm. Imagine you are given a really large stream of data elements (queries on Google searches in May, products bought at Walmart during the Christmas season, names in a phone book, whatever). Your goal is to efficiently return a random sample of 1,000 elements evenly distributed from the original stream. How would you do it?
The right answer is generating random integers between 0 and N-1, then retrieving the elements at those indices and you have your answer.
So, let me make the problem harder. You don't know N (the size of the stream) in advance and you can't index directly into it !!!!!!!!. You can count it, but that requires making 2 passes of the data. You can do better. There are some heuristics you might try: guess the length and hope to undershoot. It will either not work in one pass or not be evenly distributed.
Simple Solution
A relatively easy and correct solution is to assign a random number to every element as you see them in the stream, and then always keep the top 1,000 numbered elements at all times. This is similar to how mysql does "ORDER BY RAND()" calls.
tu: what is the problem with this simple solution??????????????
A: simpler in this problem, but cannot be extended to the more complex cases, which we will see later.
Classic Reservoir Sampling
Another option is reservoir sampling. In the example I've given you, the algorithm above is a little simpler, but reservoir sampling can be extended in other ways which I will get to, but first the basic algorithm:
First, you want to make a reservoir (array) of 1,000 elements and fill it with the first 1,000 elements in your stream. That way if you have exactly 1,000 elements, the algorithm works. This is the base case.
Next, you want to process the i'th element (starting with i = 1,001) such that at the end of processing that step, the 1,000 elements in your reservoir are randomly sampled amongst the i elements you've seen so far. How can you do this. Start with i = 1,001. With what probability after the 1001'th step should element 1,001 (or any element for that matter) be in the set of 1,000 elements? The answer is easy: 1,000/1,001. So, generate a random number between 0 and 1, and if it is less than 1,000/1,001 you should take element 1,001. In other words, choose to add element 1,001 to your reservoir with probability 1,000/1,001. If you choose to add it (which you likely will), then replace any element in the reservoir chosen randomly. I've shown that this produces a 1,000/1,001 chance of selecting the 1,001'th element, but what about the 2nd element? The second element is definitely in the reservoir at step 1,000 and the probability of it getting removed is the probability of element 1,001 getting selected multiplied by the probability of #2 getting randomly chosen as the replacement candidate. That probability is 1,000/1,001 * 1/1,000 = 1/1,001. So, the probability that #2 survives this round is 1 - that or 1,000/1,001.
This can be extended for the i'th round - keep the i'th element with probability 1,000/i and if you choose to keep it, replace a random element from the reservoir. It is pretty easy to prove that this works for all values of i using induction. It obviously works for the i'th element based on the way the algorithm selects the i'th element with the correct probability outright. The probability any element before this step being in the reservoir is 1,000/(i-1). The probability that they are removed is 1,000/i * 1/1,000 = 1/i. The probability that each element sticks around given that they are already in the reservoir is (i-1)/i and thus the elements' overall probability of being in the reservoir after i rounds is 1,000/(i-1) * (i-1)/i = 1,000/i.
Weighted Reservoir Sampling Variation
tu: seems not quite right. What is the reservoir size?
Take the same problem above but add the extra challenge: How would you sample from a weighted distribution where each element is given a weight? This is sorta tricky. The above algorithm can be found on the web easily, but I don't know where I can find a weighted reservoir sampling version, so I made one up. I'm 100% sure someone has figured this out before me though, I don't take credit.
Start the same way by filling in the first 1,000 elements of the reservoir except keep a sum of the weights seen so far. Call this seen_weight. Also, make sure to store the weights of the individual elements stored in the reservoir. Call these weights a different array named weight[]. Lastly, to keep things efficient, store a variable for the total weight of the elements in the reservoir called reservoir_weight. On step i, generate a random number between 0 and 1 and use this pseudocode:prob_sum = 0;
for(x = 0; x < (1-(weight[x]*seen_weight/reservoir_weight/(seen_weight + input_weight))))/reservoir_size; ++x) {
if (prob_sum > R) {
// replace, the probability of replace is input_weight/(seen_weight+inputweight)
reservoir[x] = input_element;
reservoir_weight += input_weight - weight[x];
weight[x] = input_weight;
break;
}
seen_weight += input_weight
}
The only magic here is: (1-(weight[x] * seen_weight / reservoir_weight / (seen_weight + input_weight))))/reservoir
Distributed Reservoir Sampling Variation
This is the problem that got me looking at the weighted sample above. In both of the above algorithms, I can process the stream in O(N) time where N is length of the stream, in other words: in a single pass. If I want to break break up the problem on say 10 machines and solve it close to 10 times faster, how can I do that?
The answer is to have each of the 10 machines take roughly 1/10th of the input to process and generate their own reservoir sample from their subset of the data. Then, a final process must take the 10 output reservoirs and merge them with another sample. The trick is that the final process must take into account the reservoir weights of each of the input reservoirs. Basically, the final process should reservoir sample every element in the 10 input reservoirs but assign each element a weight of weight[x] * seen_weight / reservoir_weight where weight[x] is the element's original weight, seen_weight is the total weight counted in generating that particular reservoir and reservoir_weight is the sum of the weights of the elements in the reservoir. Proving this works is a little harder, so I will frustrate you by leaving it as an excercise for the dear reader.
Introduction of Hedge Funds
What is a Hedge Fund?
A hedge fund is a loosely regulated private investment fund that charges a management and performance fee.
A hedge fund collects its funds from private wealthy individuals and large institutions and uses funds to trade securities with the hope of capital and income appreciation. Unlike other investment vehicles, hedge funds concentrate on making a consistent absolute return rather than a relative return to a benchmark index. One important distinguishing factor a hedge fund has compared to traditional mutual funds and asset management companies is that a hedge fund is allowed to use almost any structured product. This means that they are allowed to engage in leveraged derivative positions as well as shorting securities, a method usually forbidden at mutual funds. Hedge funds traditionally identify inefficiencies in the financial markets and trade to capture profits from them.
source: http://www.bestwaytoinvest.com/hedge-funds
hedge fund 投资结构 2
好了，为什么分类就讲到这里了，回到今天讲的主题投资结构。咱们按分类来说。
1. Fixed Income Arbitrage
先说说Fixed Income Arbitrage，为什么要先说它呢？对对冲基金有些了解的朋友都应该知道长期资本（Long-Term Capital Management）和大理石基金（Granite Fund）吧！这两家大基金就是栽到这个Fixed Income Arbitrage上了。
他们主要就是玩债（debt instruments，国债了，企业债了）和利率（interest rates）。玩的最主要的原理就是那个yield curve，然后还有其他的东西，比如说volatility curve，cash flow了等等。然后他们把这些又是曲线了，又是数的东西代入到一个模型当中（模型当然得自己做）来洞察商机创造无限吧！
我下面说个例子：
比如说有这么个人，他的模型告诉他US Tbill (Treasury Bill)现在和Eurodollar有100点的差，然后呢有可能Eurodollar的价格被高估了，点差呢可能还会继续加大。这个时候他的策略就是买Tbill卖Eurodollar（这两件事时同时干的，或者相差时间不算太长），这中间不就是有点钱赚了嘛！
玩这种Fixed Income Arbitrage，他们的position里面往往有很多的外国货币在里面，这不又带来了货币风险了吗？他们也不傻，他们是会把这种风险hedge掉的。（一般情况下是hedge掉，但也有人胆子大。）
2. Convertible Arbitrage
第二种Convertible Arbitrage。他们主要是把同一家企业的bond和stock（option有时候也拿进来，作为一个对stock的hedge）捏到一起玩。（这里说的bond是能convert的。）原理呢就是bond和stock的价格有时是有出入的，stock在市场上经常一会高了一会低。
3. Statistical Arbitrage
第三种Statistical Arbitrage。有的人呢，说它是Equity Long/Short，但是呢我在这里还把他拿出来，因为这种trading strategy挺有意思，我管他叫小刀薄薄片型。
说说它的特点，一般这种公司都是一群数学PhD在那里干活，他们做那么一个软件，这种软件呢能自动根据他们设定的条件把overvalued和undervalued的股票挑出来（一挑就是一个basket，一次多买/卖些股票也hedge了一部分他们的风险），然后就开始买或卖或买和卖。我为什么说他们是小刀薄薄片呢？就是因为他们做的这个软件能每天进行上百次交易。（但每次不一定赚太多）
我再说一种Statistical Arbitrage的特例，有人管他叫Equity Market Neutral，也许大伙看了neutral这个字就能差不多知道他的意思了。这个Equity Market Neutral的特点就是他们所有买long的钱和他们卖short的钱是相等的 why why why???（就那么意思，大家不要计10块8块的小节），为什么他们这么做呢？大家可能都知道，股票市场一般是一涨全都涨，一跌全都跌（呵呵！再次说明不要计小节。）
再说一个Equity Long/Short，这种策略呢根上面的Equity Market Neutral的不同之处呢就是他们买long的钱和他们卖short的钱是不相等的，一般都是long多点 why why why?，short少点，他们叫Equity Long/Short Long biased。不过也有一少部分是short biased。
4. Distressed Security(debt)
第四种，有人认为这种人胆子比较大，但是呢他们的胆子大也是建立在心细上的，他们叫什么呢？大名Distressed Security(debt)它们主要玩破产，呵呵！听起来挺恶心？不过挺赚钱。我给大家举个例子：有这么个公司快破产了，自然而然这公司的bond就开始猛跌了。这时这帮所谓胆大的人就开始算了，算算如果他们现在买这公司的bond，等公司破产了之后能分到多少钱（比方说15块），如果这公司的bond跌过头了（一般都能跌过头点，比方说是10块），那就买呗。
5. Risk Arbitrage
第五种，也挺有意思，叫Risk Arbitrage，这种人呢在对冲界里是老实人，其实也不老实。主要他们玩的是takeover。比方说公司A要takeover公司B了，他们的策略就是买公司B的股票，买公司A的股票。呵呵！这种玩法挺老实了吧，真不知道怎么给他们起个名字叫Risk Arbitrage，一点也不risky，但是大伙想想伦敦证交所 bid的事吧，看他们干的，搞得天怒人怨。
6. private equity
第六种，这种呢跟安校长玩的（我看他的文章以前经常提到private equity，不知道现在怎么不写了，就给大家回答一些private equity的问题了。现在开始说IPO的事了）private equity有点关系，叫Regular D。他们主要玩private equity一般呢这种人买private equity的position，（买的是convertible bond，而且呢这种bond有一些down side的protection） lost了, 不懂了！！！呜呜~~~
7. Event Driven
第七种，Event Driven。他们主要玩的就是消息。大家顾名思义，就是呢在一些能把股票推上推下的时候，进行股票的买卖。像第五种和第六种都可以认为是Event Driven。跟大伙说说这个event都包括什么event呢？主要包括以下几种：corporate restructuring(merger, takeover, spin off)，stock buyback，bond upgrade，好的报表等等。如果乐意呢，就自己create点event玩玩。
8. Sector Fund
第八种，Sector Fund，这种人是传统玩法。一般在一个行业内，选那么几只股票，进行long only或是long biased操作。这种人呢对冲界里面的人不愿把他们划进来，不是因为他们操作的方法，而是因为这些人不太经常用leverage。
9. Emerging Market
第九种，这种呢跟祖国有点关系。Emerging Market。他们玩的东西我也说不太清，得了，我就说他们玩概念吧。一般他们都是投发展中国家的股票了，债券了等等securities。想干什么呢？帮助发展中国家发展？屁！那是side effect，主要就是赚钱。就是现在买了等过两年发展中国家发展了，他就赚到钱了。说到这个Emerging Market令我想到了一些不懂行的洋鬼子们都觉得把Emerging Market加到一个portfolio里面，这个portfolio的风险相对要大，实际上这种认识是错误的，具体为什么错我就不说了，一般看过investment psychology书的朋友们都应该知道，很有名的个例子。如果哪位想看看具体为什么，请参见：The Psychology of Investing，2002，J.R.Nofsinger，Prentice Hall why why why???
10. Fund of Fund
第十种，Fund of Fund，他们主要玩对冲基金。他们是搞来一些钱，然后呢把这些钱投到不同的对冲基金里面。
11. Global Macro
什么是Global Macro呢？就是根据国家，国际的宏观经济走向来进行投资。大伙看到这里可能会说：你这是屁话，哪个投资不是根据国家，国际的宏观经济走向来进行投资的？我为我的屁话进行如下辩解，所有的投资都跟宏观经济走向有关系，但是我这里所说的投资是指那些有密切关系的，比如说：forex，index，government bond等。这些东西对一些政府或专业机构（大的比如说世界银行，小的比如说密歇根大学的consumer sentiment）的数据都相当敏感，而这些数据的源头就是宏观经济学。我上面还说了玩政治，玩什么政治呢？比如说玩玩总统大选了，美联储下个人了，政府的fiscal policy了等等，forex，index对这些东西也相当敏感。
大家都知道索罗斯吧！这是玩Global Macro的鼻主。
呵呵！正经的就说这么多吧！以上我说的trading strategy也仅代表了一部分，肯定不全面，但是呢，我还有这个自信，现阶段出现的其他trading strategy，左揉右揉都能揉到我以上说的这11种里面去。
大家看看我说的这些种trading strategy没有什么太难以让人接受的吧？但为什么有些媒体（还是对冲界人人每个星期都看的媒体）总说对冲基金坏呢？坏事吧是干了点，但总是个别人干的呀！不能打击一片呀。想到了以前上大学军训总唱的一首歌，我就重新填个词吧：
嘿——咱对冲的人，
有啥不一样？
保卫了金融的整体安全，
克瑞诶特里溃堤体（create liquidity）