Tuesday, February 01, 2011

rubber

用法
rubber是一个latex的wrapper. 它免去了你先把eps -> pdf, 再latex paper.tex, 再bibtex paper 再 latex paper.tex这个复杂的过程. 你只需要一个命令就能完成
$rubber paper

问题/解决
不同的版本/平台上, rubber可能会有一些问题:
1 eps转pdf的时候报错
GS_OPTIONS=-dPDFSETTINGS=/prepress rubber --pdf -Wrefs -Wmisc paper
running: epstopdf --outfile=aaa.pdf aaa.eps...
Traceback (most recent call last):
  File "/usr/local/bin/rubber", line 4, in 
    sys.exit(Main()(sys.argv[1:]))
  File "/Library/Python/2.6/site-packages/rubber/cmdline.py", line 319, in __call__
    return self.main(cmdline)
  File "/Library/Python/2.6/site-packages/rubber/cmdline.py", line 283, in main
    ret = env.final.make(self.force)
  File "rubber/depend.py", line 157, in make
  File "rubber/depend.py", line 171, in make
  File "rubber/depend.py", line 276, in run
  File "/System/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/subprocess.py", line 595, in __init__
    errread, errwrite)
  File "/System/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/subprocess.py", line 1106, in _execute_child
    raise child_exception
OSError: [Errno 8] Exec format error
make: *** [pdf] Error 1

修改/usr/local/share/rubber/rules.ini
command = epstopdf --outfile=$target $source
改为
command = bash epstopdf --outfile=$target $source

2 无法使用bibtex
在我的Mac上, bibtex后面不能使用绝对路径(Ubuntu上则是好的, 很诡异).所以导致我rubber以后所有reference都不对.

Monday, January 24, 2011

gmail tips

http://email.about.com/od/gmailtips/qt/et_find_mail.htm

所有标题含有hi的邮件 "subject:hi"
所有从apc999处来信 "from:apc999"
所有寄给apc999的来信 "to:apc999"
所有未读邮件 "is:unread"
所有starred邮件 "is:starred"
2005年5月5日以前邮件 "before:2005/05/05"
2005年5月5日以后邮件 "after:2005/05/05"

Wednesday, January 19, 2011

Java笔记

Managing Source and Class Files
Java的Package概念

编译例子
javac -classpath /path/to/foo/foo.jar:./bar.jar \
      -d /path/to/mine/MyStuff_classes MyStuff.java
-classpath: 指定需要的其他目录或者jar文件
-d dirname: 按照class的packagename创建目录结构,把class文件放入相应的目录. 比如MyStuff.java是org.apc999.MyStuff, 那么按照上面的命令, 则会生成目录/path/to/mine/org/apc999/MyStuff.class

make MyStuff.jar
jar cvf MyStuff.jar -C MyStuff_classes/ .

Tuesday, January 11, 2011

[Linux]pthread

文档

史上最好的pthread Tutorial/Reference


使用

Thread
pthread_t mythread;
pthread_create(&mythread, NULL, myfunc, NULL);
pthread_join(mythread, NULL);
Mutex
1 初始化一个mutex有两种方式, 可以动态的声明:
pthread_mutex_t mymutex
pthread_mutex_init(&mymutex, NULL); 
也可以静态的声明:
pthread_mutex_t mymutex = PTHREAD_MUTEX_INITIALIZER;
2 使用mutex来serialize一段程序. mutex就好比一把锁,被锁住的程序段(pthread_mutex_lock和pthread_mutex_unlock两个语句间的code)在同一时间只能被一个thread执行. 其他需要执行这段程序的thread都会在pthread_mutex_lock这里被卡住,直到mutex被unlock才能有一个thread接着往下执行.
pthread_mutex_lock (&mymutex);
dotstr.sum += mysum;
pthread_mutex_unlock (&mymutex);
3 销毁一个mutex
pthread_mutex_destroy(&mymutex);

Spinlock
spinlock是轻量级的lock机制,比较mutex等机制,节省了process re-scheduling以及context switch等开销,所以如果确信thread不会被block很久,spinlock会非常有效.

1 申明一个spinlock
pthread_spinlock_t myspinlock;
pthread_spin_lock(&myspinlock);
2 使用spinlock上锁
pthread_spin_lock(&myspinlock);
critialnum += 1;
pthread_spin_unlock(&myspinlock);
3 销毁
pthread_spin_destroy(&myspinlock);

在MacOS 上, spinlock的原语与linux上的有所不同.
#include <libkern/osatomic.h>
OSSpinLock mylock = OS_SPINLOCK_INIT;
OSSpinLockLock(&mylock);
OSSpinLockUnlock(&mylock);

Misc

Linux上thread的实现和其他UNIX系统有一个重要区别: Linux上pthread_create实际上用一个process来运行一个thread. 所以每个thread都有自己的pid,也有自己的tid.同一个进程中的thread有同样的pid但是不同的tid. 可以用下面的代码查看pid或者tid
fprintf (stderr, "thread pid is %d\n", (int) getpid ());
fprintf (stderr, "thread tid is %d\n", (int) gettid ());

Thrift笔记

文档

Thrift的文档真是不是一般的incomplete 基本上可以说是空白. Facebook不知道干什么去了. 这是我找到的有点帮助的文档:
官方的文档: Using Thrift with C++,
网上其他的: A Intro to Thrift

安装
Thrift 的C++编译器使用了boost,所以你如果要用Thrift配合C++使用的话, 需要先安装boost.
然后下载thrift源代码,编译安装(configure, make, make install),按下不表.

HelloWorld (C++版)

第一步:用thrift描述一个service的接口,比如在Server端提供这样一个函数叫ping, Client端可以通过rpc调用ping这个函数(在thrift帮你marshall这些rpc call),ping会在Server端执行.

namespace cpp Test
service HelloWorld {
  oneway void ping()
}
将这个文件存为比如apc999.thrift. 现在把编译apc999.thrift成C++代码
$thrift --gen cpp apc999.thrift
$ls
gen-cpp/  HelloWorld.thrift/
$ls gen-cpp
apc999_constants.cpp  apc999_types.cpp  
HelloWorld.cpp  HelloWorld_server.skeleton.cpp
apc999_constants.h    apc999_types.h    
HelloWorld.h
在gen-cpp这个目录中, 我们会发现一堆thrift生成的文件. 其中HelloWorld开头的都是和HelloWorld这个service有关, 你可以在apc999.thrift中定义多个service.他们会生成不同的文件. 而apc999开头的是一些常量和类型的定义.

我们需要记住的是: Thrift帮你生成了给定Service的服务器端和客户端代码.Thrift这里的命名规则是对于Service XYZ, 它对应的服务器端代码(具体这个Service的执行)在类XYZHandler中,客户端代码(负责marshall, execute RPC)在类XYZClient中. 所以你需要用这个服务, 你只需要直接修改或者继承这些类.

第二步:编写Server端代码. thrift帮我们生成的HelloWorld_server.skeleton.cpp就是Server端代码的模板. 我们只需要往里面添加我们需要的功能实现. 比如我们添加了一行
// This autogenerated skeleton file illustrates how to build a server.
// You should copy it to another filename to avoid overwriting it.
#include "HelloWorld.h"
#include <protocol/TBinaryProtocol.h>
#include <server/TSimpleServer.h>
#include <transport/TServerSocket.h>
#include <transport/TBufferTransports.h>

using namespace ::apache::thrift;
using namespace ::apache::thrift::protocol;
using namespace ::apache::thrift::transport;
using namespace ::apache::thrift::server;

using boost::shared_ptr;
using namespace Test;

class HelloWorldHandler : virtual public HelloWorldIf {
 public:
  HelloWorldHandler() {
    // Your initialization goes here
  }

  void ping() {
    // Your implementation goes here
    printf("Hello World!\n"); //目前为止我修改的唯一一行
  }
};

int main(int argc, char **argv) {
  int port = 9090;
  shared_ptr<HelloworldHandler> handler(new HelloWorldHandler());
  shared_ptr<TProcessor> processor(new HelloWorldProcessor(handler));
  shared_ptr<TServerTransport> serverTransport(new TServerSocket(port));
  shared_ptr<TTransportfactory> transportFactory(new TBufferedTransportFactory());
  shared_ptr<TProtocolFactory> protocolFactory(new TBinaryProtocolFactory());

  TSimpleServer server(processor, serverTransport, transportFactory, protocolFactory);
  server.serve();
  return 0;
}
这个Server端代码有main函数, 所以你完全可以编译这个程序并运行.它会在9090端口监听. 如果有rpc调用ping这个函数, 它会打印出"Hello World!".

第三步:编写客户端代码.
#include "HelloWorld.h"  // HelloWorldClient这个类在helloWorld.h中被申明

#include <transport/TSocket.h>
#include <transport/TBufferTransports.h>
#include <protocol/TBinaryProtocol.h>

using namespace apache::thrift;
using namespace apache::thrift::protocol;
using namespace apache::thrift::transport;

using namespace Test;

int main(int argc, char **argv) {
  boost::shared_ptr<TTransport> socket(new TSocket("localhost", 9090));
  boost::shared_ptr<TTransport> transport(new TBufferedTransport(socket));
  boost::shared_ptr<TProtocol> protocol(new TBinaryProtocol(transport));

  HelloWorldClient client(protocol);
  transport->open();
  client.ping();
  transport->close();

  return 0;
}

Tips

Thrift生成的server端是thread safe的. 但是client端不是thread safe. 所以需要多个thread和server端通信,则每个thread需要initiate一个自己的client实例.

使用Thrift的C++库有,server端有4种不同的选择: TSimpleServer,TThreadedServer, TThreadPoolServer,以及TNonblockingServer.

当有server和client间有大量的network traffic的时候,可以使用Nagles算法来优化网络性能. Nagles算法通过缓冲来减少收发的packet数目.在Thrift中使用Nagles算法,我们只需要将上面例子中的客户端代码中下面的语句
boost::shared_ptr<TTransport> socket(new TSocket("localhost", 9090));
改为
TSocket* sock = new TSocket("localhost", 9090);
boost::shared_ptr<TTransport>  socket(sock);
然后在调用transport->open();之前 先调用sock->setNoDelay(false);就可以了

Wednesday, January 05, 2011

[Python]Package的安装

1 使用python setup.py install来安装

使用python setup.py install的时候, 默认路径是 /usr/lib/python2.x/site-packages 这样的全局路径底下. 若是没有权限写,可以自己指定安装路径
python setup.py install --home=/your/fav/dir
比如
python setup.py install --home=~


2 使用easy_install来安装egg文件
easy_install foo.egg 

Sunday, January 02, 2011

Firefox tips

给Firefox(3.5,4) 最后一个tab加上close按钮:
地址栏内键入"about:config",回车
搜索"browser.tabs.closeWindowWithLastTab",将Value设为false

Tuesday, December 21, 2010

[Linux]同步ubuntu上的时间

$ sudo aptitude install rdate
$ sudo rdate -s clock-1.cs.cmu.edu
$ sudo hwclock --systohc 

[Emacs]在Emacs中使用gdb

在Emacs中使用gdb调试程序 (推荐)
http://www.inet.net.nz/~nickrob/
An Introduction To Using GDB Under Emacs


1 M-x gdb 回车

2 Run gdb (like this): gdb --annotate=3 myprogname 回车
如果使用的是emacs 23.1 比如ubuntu 10.10当中的emacs-snapshot, 如下
Run gdb (like this): gdb -i=mi myprogname 回车

Gud->GDB-MI->Display other windows

Tuesday, November 16, 2010

[Python]String的decode, encode

string的decode用法:
str.decode(encoding="gb2312",errors="strict"
在这里我们告诉python解释器用encoding参数所指定的来对str解码.标准的encoding可以查看这里

和简体中文相关的通常有gb2312,gb18030以及gbk(大多数BBS的中文encoding)

一篇参考http://hi.baidu.com/tornadory/blog/item/2fa5f0c36cf7bd5fb219a801.html

[Linux]Profiling

gprof

gprof是GNU的profiling工具,使用的时候需要编译期的支持
使用:
1 编译:时需要使用"-pg"选项
$cc -g -c myprog.c utils.c -pg
$cc -o myprog myprog.o utils.o -pg
如果加上了"-g"选项(如上),则可以支持Line-by-line Profiling
2 运行: 执行生成的可执行文件(比如上面的myprof), 这时会生成一个"gmon.out"的文件
3 查看: 用gprof 查看profiling结果
$gprof myprof | more
参考:
gprof Quick-Start Guide

perf

perf是Linux下非常强大的profiling工具,也非常好用.
perf类似于git那样,有一堆子命令,比较常用的有record,report,annotate,stat等.
运行一个程序foo并记录下profile(默认为perf.data):
$ sudo perf record ./foo
读取刚才生成的profile结果(默认perf.data)并显示分析结果:
$ sudo perf report
输出结果类似
    49.97%  foo  filter_bench         [.] main
     5.31%  foo  libc-2.12.1.so       [.] 0x7aeab
     0.36%  foo  libstdc++.so.6.0.15  [.] operator new[](unsigned long)
注意这里libc-2.12.1.so中的symbol没有被load进来,所以无法显示具体的函数名而只能看见一个入口地址0x7aeab.
在ubuntu/debian上你可以安装libc6-dbg(注意不是libc6-dev)帮助gdb,perf这样的工具traceback.libc6-dbg包含了libc6的debug信息
$ apt-get install libc6-dbg
显示annotated code
$ sudo perf annotate
运行一个命令并查看硬件counter:
$ perf stat --repeat 10 -e cycles:u \
-e instructions:u -e l1-dcache-loads:u -e l1-dcache-load-misses:u ./foo
查看所有支持的硬件counter:
$ perf list
参考:
Linux kernel profiling with perf

OProfile

OProfile利用硬件支持来profile系统或者application. 与gprof不同,OProfile不会在binary中添加指令
启动:
1 加载oprofile
$sudo opcontrol --init
2 设置是否需要profile kernel,如果需要
$sudo opcontrol --vmlinux=/boot/vmlinux-`uname -r`
如果不需要
$sudo opcontrol --no-vmlinux
3 开始采集数据
$sudo opcontrol --start 
Using default event: CPU_CLK_UNHALTED:100000:0:1:1
Using 2.6+ OProfile kernel interface.
Using log file /home/apc999/tempsession/samples/oprofiled.log
Daemon started.
Profiler running.
4 查看oprofile状态
$sudo opcontrol --status
Daemon running: pid 13892
Separate options: none
vmlinux file: none
Image filter: none
Call-graph depth: 0
5 结束采集数据
$sudo opcontrol --stop 
6 结束oprofile daemon
$sudo opcontrol --shutdown 

参考:
OProfile Manual

Sunday, October 31, 2010

[Linux]用gs合并几个pdf文件

gs -dBATCH -dNOPAUSE -q -sDEVICE=pdfwrite -sOutputFile=finished.pdf file1.pdf file2.pdf

Thursday, October 21, 2010

PPT 热键

Press F5 in PowerPoint/Windows or Control-Shift-S in PowerPoint X/Mac to start a slide presentation from the beginning

Press Shift+F5 in PowerPoint 2003 or Control+Shift+B in PowerPoint X/Macintosh to start a presentation from the current slide

Friday, October 15, 2010

手机配置

Apple iPhone 4
  • CPU: Apple A4 - fully compatible with ARM Cortex-A8, running at 1 GHz, 64 L1 Cache, 640 L2 Cache
  • Memory: 512 MB eDRAM
  • Storage: 16 GB or 32 GB flash memory
Nokia N900
  • CPU: ARM Cortex-A8, running at 600 MHz
  • Memory: 256 MB
  • Storage: 32 GB internal; Expandable to up to 48 GB with an external microSD card

Thursday, October 14, 2010

Cocoa编程笔记(update中)

Cocoa是Mac上使用的图形界面framework, 简单说来就是一个库使开发人员可以定制自己的基于GUI的 Application。Cocoa使用的语言是Object-C(参见我的Object-C笔记)。 Cocoa编程的学习曲线比其他GUI编程的要陡,因为有很多概念要理解。我在学习过程中,参照如下的一些tutorial或者文档:

Cocoa Fundamental Guide:这是最核心最基础的文档。介绍了最重要的概念

Cocoa Event Handling:Cocoa中如何处理事件

Introduction to Text System User Interface Layer,介绍了比如如何programatically 创建一个NSTextView,添加至NSScrollView,如何调整Text边距等等.

Introduction to Text Editing Programming Guide for Cocoa, 介绍如何使用Cocoa的Text System来完成编辑工作,比如key binding, 如何delegate message等.

一个简单界面的Cocoa Application:最最简单的一个Application.如果想学习一个最简单的Cocoa Application,从这个文档看起.

Model-View-Control模型

Cocoa中广泛使用了MVC这种的Design Pattern,把一个application功能分解为如下三个部分:

Model objects: 负责逻辑处理,不直接和用户界面打交道
View objects: 用户界面.比如label, textfield等
Controller objects: 连结Model和View, 比如处理界面送来的用户action,应用后台逻辑做出update等


内存管理
alloc, init, dealloc, retain, release, autorelease. 所有从NSObject继承而来的类都有这些方法,这些涉及到内存管理.

alloc: 从内存中分配一块内存,但仅仅是获得一块内存空间,未作任何初始化
init:初始化一个类,类似于C++中的构造函数,一般和alloc配合使用:
id  myObject = [[NSString alloc] init];
dealloc: 销毁一个类,释放内存空间
[myObject dealloc];
retain: 将一个对象的引用计数加1
[myObject retain];
release: 将一个对象的引用计数减1
[myObject release];
autorelease:每当一个对象得到autorelease消息,这个对象就将被添加到autorelease pool当中. 当改eventloop结束时,所有autorelease pool当中的对象将被release.通常一个method要返回一个对象的时候,autorelease这个对象是个好主意.
- (NSString)autoreleasedString
{
  NSString *string = [[NSString alloc] initWithString:
      @"The Sender of this message will never see this string…"];
  [string autorelease]; // we have to do this or we'll get a memory leak
  return string;
}


神秘的IBAction和IBOutlet?

经过预处理以后,IBAction实际上就是void而IBOutlet实际上根本就是一个空的宏(见定义在NSNibDeclarations.h).它们的作用是在于作为一种syntax sugar,提醒Interface Builder,"嗨,这几个被我修饰的变量或者函数是你应该知道的~".



事件处理(Event Handling)
有两种Message: 由外部设备比如键盘或者鼠标发起的Event message,以及由其他对象发起的Action message.

Event message 通常已知,所以NSResponder提供了声明以及缺省的实现.
NSResponder是一个抽象类.而Cocoa中最核心的三个类NSApplication, NSWindow, 以及 NSView都继承了NSResponder.

比如我们要处理mouseDown这个事件,我们可以继承一个NSView类(或者NSView的子类,比如NSTextView,NSTabView),然后重载mouseDown:这个方法。如果一个NSWindow上有多个NSView(或其子类), 则应该重载最上面的View,否则盖在底下的不能接受到该消息

- (void)mouseDown:(NSEvent *)theEvent {
    // determine if I handle theEvent
    // if not...
    [super mouseDown:theEvent];
}


Delegate
Common mistakes with delegation in Cocoa
一个在NSImageView中delegate mouseDown等消息的例子:
http://it.toolbox.com/blogs/macsploitation/adding-delegates-to-nsviews-21138

Text System
NSTextStorage 是NSMutableAttributedString的子类. 一般作为NSTextView 的text repository. Introduction to Text System Storage Layer Overview

NSTextView 和用户打交道的界面
NSTextContainer:Introduction to Text Layout Programming Guide


NSScrollView: Introduction to Scroll View Programming Guide for Cocoa
NSClipView:


NSParagraphStyle:Introduction to Rulers and Paragraph Styles

一个超级简单的Cocoa Text System Application
HelloWorld.h:
#import 

@interface HelloWorld : NSObject  {
    NSWindow *window;
 
 NSTextStorage *textStorage;
 NSLayoutManager *layoutManager;
 NSTextContainer *textContainer;
 NSTextView *textView;
}

@property (assign) IBOutlet NSWindow *window;

@end
HelloWorld.m
#import "HelloWorld.h"

@implementation HelloWorld

@synthesize window;

- (void)applicationDidFinishLaunching:(NSNotification *)aNotification {
 // Insert code here to initialize your application 
 
 //setup textStorge
 textStorage = [[NSTextStorage alloc] initWithString:@"123abcde\n456"];
 
 //setup layoutManager
 layoutManager = [[NSLayoutManager alloc] init]; 
 [textStorage addLayoutManager:layoutManager]; 
 [layoutManager release];
 
 //setup textContainer
 NSRect cFrame = [[window contentView] frame];  
 textContainer = [[NSTextContainer alloc] initWithContainerSize:cFrame.size];
 [layoutManager addTextContainer:textContainer]; 
 [textContainer release];
 
 //setup textView
 textView = [[NSTextView alloc] initWithFrame:cFrame textContainer:textContainer]; 
 [window setContentView:textView]; 
 [window makeKeyAndOrderFront:nil]; 
 [textView release];
}

@end


常用数据结构:
NSArray: 类似list, 不能添加元素
Objective-C Tutorial: NSArray读取index位置的元素
[myArray objectAtIndex:index]

NSMutableArray:一个类似python中list的存在.可以通过addObject:来添加元素.

NSDictionary
NSMutableDictionary:一个类似于python中dict的存在,提供setObject:forKey:和removeObjectForKey:


Do things Programatically

获取中文encoding
http://www.cocoadev.com/index.pl?CharacterEncoding
NSStringEncoding gb18030 = CFStringConvertEncodingToNSStringEncoding 
    (kCFStringEncodingGB_18030_2000);
用中文encoding读文件
[options setObject:absoluteURL
    forKey:NSBaseURLDocumentOption];
[options setObject:[NSNumber numberWithUnsignedInteger:gb18030] 
    forKey:NSCharacterEncodingDocumentOption];
[options setObject:NSPlainTextDocumentType
    forKey:NSDocumentTypeDocumentOption];
 
NSAttributedString *fileContents = [[NSAttributedString alloc]
      initWithURL:absoluteURL options:options 
    documentAttributes:NULL error:outError];
NSTextView背景设为透明
[[textView enclosingScrollView] setDrawsBackground:NO];
[textView setDrawsBackground:NO];
NSImageView显示图片
NSImage *image = [NSImage imageNamed:@"yellow_background.bmp"];
[imageView setImage: image];
给NSTextView和NSTextContainer之间添加空白区域
[myNSTextView setTextContainerInset:NSMakeSize (width, height)];
使用NSLog,NSAssert输出信息,帮助调试
NSLog(@"init, %p, %p",backgroundImage, textView);
NSAssert([myWindow delegate] == self, @"You forgot to connect the window delegate.!");

NSLog 格式化字符串


其他
If you want to name your NSDocument subclass something other than MyDocument (the default name), change the name in Interface Builder and wherever it occurs in the Document header (.h) and implementation (.m) files. You must also change the name under the NSDocumentClass key in the Info.plist file.

http://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/TextArchitecture/Tasks/TextEditor.html#//apple_ref/doc/uid/20001798-CJBHAJJJ

Monday, October 11, 2010

[Math]凑硬币

有6分9分和25分的硬币,不能用这3种硬币凑出来的面值最大是多少

Sol: General problem 叫 Coin Problem

对于这题, 考察面值N分
(1) N = 3k, 当k>1的时候都可以用6和9凑出来
(2) N = 3k + 1, 当k>=10的时候, N-25是3的倍数且大于等于6,可以用(1)得出
(3) N = 3k + 2, 当k>=18的时候, N-50是3的倍数且大于等于6,可以用(1)得出

所以最大不能表出的面值为53

Sunday, October 03, 2010

[Math]扔骰子

Q: 能否重新设计两个六面骰子,每个骰子上是正整数并且两个骰子之和的分布与两个正常骰子之和相同(Is it possible to change the numbers on two six sided dice to other positive numbers so that the probability distribution of their sum remains unchanged?)

Sol: 考虑两个普通骰子之和的分布的generating function:
(x/6+x^2/6+x^3/6+x^4/6+x^5/6+x^6/6)*(x/6+x^2/6+x^3/6+x^4/6+x^5/6+x^6/6)
= (x/6+2*x^2/6+2*x^3/6+x^4/6)*(x/6+x^3/6+x^4/6+x^5/6+x^6/6+x^8/6)

也就是说可以设计第一个骰子的六面为(1,2,2,3,3,4),第二个骰子的六面为(1,3,4,5,6,8)
这样可以满足新的骰子的和的分布和从前相同

Friday, September 24, 2010

[Linux]resize image

比如我有一个image叫old.png想要resize成320x240的文件,可以使用如下命令
convert -geometry  320x240 old.png new.png
注意new.png依然保持了原图片的横宽比例,所以未必能得到你想要的大小, 如果不想保持横宽比例
convert -resize  '320x240!' old.png new.png

[Math]老鼠,毒药和酒

如果你有9瓶酒,其中一瓶有毒但你不知道究竟是哪一瓶.幸运的是你有两只老鼠可以拿来测试--老鼠碰到毒酒立刻就被毒死了.给定这两只老鼠,如果测试两轮(一轮指你可以对部分或者全部老鼠喂一次酒),如何能够测试出哪瓶是毒酒? 进一步,如果给你5只老鼠,如何在两轮内找出243瓶酒中哪一瓶是毒酒.

Sol:
part1
给酒编号,编号为1 2 3的酒喂老鼠A, 编号为3 4 5的酒喂老鼠B.
case1 A alive, B alive -> poised in 6, 7, 8, 9.
case2 A dead, B alive -> poised in 1, 2
case3 A alive, B dead -> poised in 4, 5
case4 A dead, B dead -> poised is 3, done

case1的情况下, 使用A测试6,7, 使用B测试7,8就可以得到最后结果
case2和case3的情况下, 让活着的一只老鼠喝一瓶酒,也可以得到结果.

part2
让我们用N(k,1)指代给定k只老鼠,只能测试一轮的情况下,最多能找出多少瓶酒中的一瓶毒酒.不难发现N(k,1)=2^k (特别的N(0,1)=1 也就是说一只老鼠都不给,只能断定:只有1瓶的时候这瓶一定是毒酒)

N(k,2)=N(k,1)*C(0,k) + N(k-1,1)*C(1,k) + N(k-2,1)*C(2,k) + ... + N(0,1)*C(k,k)
= 3^k
=> N(5,2)=243

Thursday, September 23, 2010

[Python]几个常用数据结构的高效实现

Python中最广为熟知的container就是list和dict了. 但是对于特定的用途, 这二者未必是最高效的.比如判断容器中是否包括x(x in container),如果容器是list就需要O(n)的时间.而使用set的话这个就只需要O(1)的时间. 我的血泪教训是: 在list很长的时候, x in list这个操作是非常非常低效的.一个好的主意是在另一个set容器来保存membership的信息.

集合(Set)
set是Python的built-in类型,对于membership testing, removing duplicates 的操作非常高校(O(1)时间).另外对集合操作也非常方便.如果对容器元素的顺序没有要求,set是非常好的选择对象
>>>s= set()
>>>s.add(1)
>>>s.add(2)
>>>s.remove(1)  #throw exception if not in set
>>>s.discard(1) #remove if present
>>>print set([1,2,3]) | set([3,4,5]) #union
set([1, 2, 3, 4, 5])
>>>print set([1,2,3]) & set([3,4,5]) #intersection
set([1])
>>>print set([1,2,3]) - set([3,4,5]) #difference
set([1, 2])
>>>print set([1,2,3]) ^ set([3,4,5]) #symetric difference
set([1, 2, 4, 5])
栈(Stack)
栈的特点是先进后出(FILO).built-in的list用来实现栈非常合适.对于append和pop的实现非常高效.

FIFO队列(FIFO Queue)
队列的特点是先进先出(FIFO). list用来实现队列不够有效.collections.deque可以弥补这一缺点(fast appends and pops from both ends)
>>>from collections import deque
>>>queue = deque()
>>>queue.append(1)
>>>queue.append(2)
>>>queue.appendleft(3)
>>>print queue
deque([3, 1, 2])
>>>queue.pop()
2
>>>queue.popleft()
3

利用deque,我们可以实现一个时间上高效的FIFO queue:
class FIFOQueue():
    def __init__(self):
        self.queue = deque()
        self.counter = itertools.count(1)    # unique sequence count
        self.task_finder = {}                # mapping of tasks to entries

    def append(self, task):
        if debug:
            print "FIFOQueue.append "+repr(task)

        if task in self:
            return
        count = next(self.counter)

        entry = [count, task]
        self.task_finder[task] = entry
        self.queue.append(entry)
        if debug:
            print "FIFOQueue.append "+repr(task)+" done"

    def top(self):
        if debug:
            print "FIFOQueue.top "
        while self.queue:
            count, task  = self.queue[0]
            if count:
                if debug:
                    print "FIFOQueue.pop "+repr(task)+" done"
                return task
            else:
                self.queue.popleft()
        if debug:
            print "FIFOQueue.top none"
        return None

    def pop(self):
        if debug:
            print "FIFOQueue.pop "
        while not self.top():
            continue
        if self.queue:
            entry  = self.queue.popleft()
            count, task = entry
            assert(count != None)
            assert(self.task_finder[task] == entry)
            del self.task_finder[task]
            if debug:
                print "FIFOQueue.pop "+repr(task)+" done"
            return task
        if debug:
            print "FIFOQueue.pop none"
        return None

    def remove(self, task):
        if debug:
            print "FIFQueue.remove "+repr(task)
        if task not in self:
            return
        entry = self.task_finder[task]
        assert(entry[0] != None)
        entry[0] = None
        del self.task_finder[task]
        if debug:
            print "FIFOQueue.remove "+repr(task)+" done"

    def __len__(self):
        return len(self.task_finder)

    def __contains__(self, task):
        return self.task_finder.has_key(task)

    def __repr__(self):
        return repr(self.queue)
这个实现的好处在于可以常数时间删除一个元素以及在常数时间内判定一个元素是否属于这个queue

优先队列(Priority Queue)
使用堆(heap)实现的优先队列(priority queue)可以在O(1)时间内得到队列中最小元素,O(logn)时间内插入或者删除一个元素.我通常在simulator中会使用priority queue来管理所有事件.

Python提供了heapq来实现.值得注意的是heapq并不是一个容器,而是操作在list上的一系列的heap算法(包括heappush,heappop,heapify)等.http://docs.python.org/library/heapq.html给出了用这一些算法实现堆排序(heapsort)以及优先队列的. 不过在那个优先队列的例子里有一点小bug. 这里是我给出的代码
import itertools
from heapq import heappush, heappop
class PriorityQueue():
    def __init__(self):
        self.pq = []                         # the priority queue list
        self.counter = itertools.count(1)    # unique sequence count
        self.task_finder = {}                # mapping of tasks to entries
        self.size = 0
 
    def add_task(self, priority, task, count=None):
        if count is None:
            count = next(self.counter)
        entry = [priority, count, task]
        self.task_finder[task] = entry
        heappush(self.pq, entry)
        self.size  += 1

    def pop_task(self):
        while self.pq:
            entry = heappop(self.pq)
            priority, count, task = entry
            if self.task_finder[task] == entry:
                del self.task_finder[task]
            if count is not None:
                self.size -= 1
                return (priority, task)
        return None


    def del_task(self, task):
        entry = self.task_finder[task]
        if entry[1] != None:
            self.size -= 1
        entry[1] = None

    def reprioritize(self, priority, task):
        entry = self.task_finder[task]
        self.add_task(priority, task, entry[1])
        if entry[1] != None:
            self.size -= 1
        entry[1] = None

    def __len__(self):
        return self.size

Intel CPU Lineup, roadmap

从Intel的主页来看Processor产品线的划分

按照处理器的品牌

  • Core(酷睿)主要是针对中端到高端的处理器.
    - 早期(2006年)的32位CPU使用NetBurst架构,分为Core Solo(单核)和Core Duo(双核)
    - 升级到64位CPU以后, 使用了Core架构,从低端到高端分为Core 2 Solo, Core 2 Duo, Core 2 Quad和Core 2 Extreme
    - 升级到Nehalem微架构以后, 从低端到高端可以具体划分为Core i3, Core i5, Core i7. i3,i5,i7在不同的时间使用不同的微架构. 这3个系列的区别可见下表
  • Pentium
  • Celeron
  • Atom
  • Xeon(至强), 主要针对服务器以及工作站

按照处理器的微架构
  • Sandy Bridge
  • 在2011年1月份发布. 苹果在2月份就宣布新的Macbook Pro使用基于Sandy Bridge 的i5和i7. 相比上代的Nehalem的Westmere架构,同样为32nm,而这次的革新意义是在于完美的将CPU和GPU真正融合在了一起。64KB L1 Cache (32KB iCache + 32KB dCache) , 256KB L2 Cache per core.与集成的GPU共享L3 Cache
  • Nehalem
  • 2008年9月发布(i7). 重新引入超线程(Hyper Threading)技术使得每一个core可以同时运行2个线程

Intel Microarchitecture 所有Intel Microarchitecture列表 这是从wiki上偷来的图,展示从Netburst和P6到Nehalem的变迁
Intel CPU的家族史: Intel CPU 家族一覽 - 桌上電腦(上篇) Intel CPU 家族一覽 - 桌上電腦(中篇) Intel CPU 家族一覽 - 桌上電腦(下篇)

Monday, September 20, 2010

[Python]glob

glob用于寻找符合pattern的文件名/目录名, 相当于shell下的ls, 很好用
>>import glob
>>glob.glob(”/path/to/me/*.txt”)
['./1.txt', './2.txt']

Monday, September 13, 2010

[Linux]查看系统信息相关命令

Linux版本信息

$uname -a
Linux gs7600 2.6.32-24-generic #42-Ubuntu SMP Fri Aug 20 14:21:58 UTC 2010 x86_64 GNU/Linux

CPU信息


$cat /proc/cpuinfo

Cache大小

cat /sys/devices/system/cpu/cpu0/cache/index*/size
系统内存使用信息

系统当前内存使用状况
$cat /proc/meminfo
或者
$free -m

如果要看具体某个进程的内存使用情况,/proc/pid/底下有一些 比如statm, maps, smaps, status.

mem_usage.py是另一个脚本可以查看具体进城的内存使用. 比如要查看pid为4418的进程
$mem_usage.py 4418
Mapped memory:
               Shared            Private
           Clean    Dirty    Clean    Dirty
    r-xp    8364        0    15484        0  -- Code
    rw-p       0        0        0     1704  -- Data
    r--p     704        0      648      516  -- Read-only data
    ---p       0        0        0        0
    rw-s       0      304        0        0
    r--s     800        0       40        0
   total    9868      304    16172     2220
Anonymous memory:
               Shared            Private
           Clean    Dirty    Clean    Dirty
    rwxp       0        0        0     1340  -- Writable code (stack)
    r-xp       0        0        0        0
    rw-p       0        0        0    81048  -- Data (malloc, mmap)
    ---p       0        0        0        0
   total       0        0        0    82388
   ----------------------------------------
   total    9868      304    16172    84608

更多详细的可以参见http://elinux.org/Runtime_Memory_Measurement

进程的信息

最基本的命令就是广为人知的top.
htop是更fancy的一个版本, 可以看到每个线程使用的内存和CPU

当前mount的设备
$cat /proc/mounts 
或者等同的
$mount

I/O的统计信息

$ iostat
Linux 2.6.38-8-server (fawnserver)  04/15/2011  _x86_64_ (12 CPU)

avg-cpu:  %user   %nice %system %iowait  %steal   %idle
           4.47    0.00    2.07    0.16    0.00   93.30

Device:            tps   Blk_read/s   Blk_wrtn/s   Blk_read   Blk_wrtn
sda               6.24        51.31      1011.76     676334   13337192
sdb               0.00         0.03         0.00        408          0
$ iotop
Total DISK READ: 0.00 B/s | Total DISK WRITE: 0.00 B/s
  TID  PRIO  USER     DISK READ  DISK WRITE  SWAPIN     IO>    COMMAND                                                                       
    1 be/4 root        0.00 B/s    0.00 B/s  0.00 %  0.00 % init
    2 be/4 root        0.00 B/s    0.00 B/s  0.00 %  0.00 % [kthreadd]
    3 be/4 root        0.00 B/s    0.00 B/s  0.00 %  0.00 % [ksoftirqd/0]
    4 be/4 root        0.00 B/s    0.00 B/s  0.00 %  0.00 % [kworker/0:0]
...

网络流量的统计信息

每块网卡的收发packet数目:
$cat /proc/net/dev
Inter-|   Receive                                                |  Transmit
 face |bytes    packets errs drop fifo frame compressed multicast|bytes    packets errs drop fifo colls carrier compressed
    lo:896689377 11170911    0    0    0     0          0         0 896689377 11170911    0    0    0     0       0          0
  eth0:708410727 3925021    0    0    0     0          0      5468 84085137  732531    0    0    0     0       0          0

bwm-ng:基于/proc/net/dev信息,动态显示各个网卡的traffic

iftop:动态显示各台主机之间traffic

nethogs: 如果要查看每个process使用的网络情况,可以使用
http://www.ubuntugeek.com/nethogs-net-top-tool-grouping-bandwidth-per-process.html

能耗

如果是基于Intel的CPU, 可以用powertop查看power consumption

内核消息

dmesg将内核消息输出至标准输出
$dmesg

Ref:

http://www.ubuntugeek.com/category/monitoring
http://www.cyberciti.biz/tips/how-do-i-find-out-linux-cpu-utilization.html

Thursday, September 09, 2010

[Linux/Mac]删除所有.svn文件夹

用于删除一个目录下(以及其子目录下)所有的.svn目录
$ rm -rf `find . -type d -name .svn`

Monday, July 26, 2010

tbb: Intel® Threading Building Blocks笔记

tbb(Threading Building Blocks)是Intel开发的一个C++模板库, 类似于STL. 其特点是针对对于多核(multi-core)CPU的优化.提高在多线程的环境下程序并发性. tbb提供了多种类似于STL但高度并行的容器类.

安装

Ubuntu:
sudo apt-get install libtbb2 libtbb-dev libtbb-doc
MacOS上:
sudo port install tbb
编译

g++ -ltbb foo.cpp
使用

concurrent_hash_map
此容器是类似于STL中的map的存在. 同std::map一样,concurrent_hash_map为一个从Key类型读取T类型的容器. 为提高并发性,我们需要用accessor或者const_accessor两种不同方式访问此容器的某元素.accessor和const_accessor均为智能指针,其中accessor写和修改访问,会lock相应的key直到访问结束.而const_accessor用于只读方式访问,这样可以同时有多个不同的const_accessor同时指向同一个key.区分不同的访问方式有助于增加程序的并发性.


#include <iostream>
#include <string>
#include <tbb/concurrent_hash_map.h>

using namespace tbb;
using namespace std;
typedef concurrent_hash_map<string,string> CacheTable;

int main() {
    CacheTable cache;

    // insert an element to the map
    CacheTable::accessor a;
    cache.insert(a, s);
    a->second = "value1";
    a.release();
    
    // look for an element in the map
    CacheTable::const_accessor ca;
    if (cache.find(ca, "key1"))
         cout << "the value is " << ca->second << endl;
    else
         cout << "not found" << endl;

    // iterate over the map
    for(CacheTable::const_iterator itr=cache.begin(); itr!=cache.end(); ++itr)
         std::cout << itr->first << " - " << itr->second << std::endl;

}
concurrent_queue
一个类似于stl中queue的存在. 提供包括push(item),pop(item)以及try_pop(item)等等的操作.
下面是对于一个concurrent_queue的iteration操作:
#include <iostream>
typedef concurrent_queue::const_iterator iter;
for(iter i(q.unsafe_begin()); i!=q.unsafe_end(); ++i ) {
   do sth 
}

atomic
如果atomic< your data type> x, 以下操作为原子操作
= x  read the value of x
x =  write the value of x, and return it
x.fetch_and_store(y)  do y=x and return the old value of x
x.fetch_and_add(y)  do x+=y and return the old value of x
x.compare_and_swap(y,z)  if x equals z, then do x=y. In either case, return old value of x

Wednesday, July 21, 2010

git笔记

git是Linus亲自操刀设计实现的版本控制工具(据说Linus在两个礼拜内搞定了git,教主威武).git功能上比SVN要强,但是学习曲线也陡了很多. 这里是我对SVN的笔记


文档

关于git的教程和手册网上很多, 但很多写的都不好.最推荐:
Git Workflow (这里的diagram非常给力)
How to version projects with Git 图文并茂,有木有?
git quick reference

这几个也不错
Git Magic 中文,英文
Pro Git(中文)

其他的还有:
Understanding Git Conceptually
Git User Manual写的比较晦涩
Git - SVN Crash Course. 我觉得帮助不是很大, 因为git和svn在用法上区别是在太大了
GIT cheat sheet这个不错
Basic Branch Merging
关于stash, log, 以及gitconfig的用法

用法

初始化一个workspace
从远端克隆一个repository到本地
$git clone git://path/to/your/git/repo
注意git是一个分布式的版本控制系统. 如果你从server1上clone的repo, 那么以后server1就相当于你的源.如果以后server2再clone了你的repo, 你就相当于server2的源.我发现这种结构很方便调试 -- 在其他机器上可以从我本地repo来pull 文件. clone的时候除了git协议还可以使用ssh, 比如
$git clone ssh://hostname/path/to/your/git/repo

工作流程
进入你的工作目录,通常大家首先将本地repository更新到源上的最新版本(大致相当于svn update, 但是因为git是分布式的设计,更新到源上最新未必是全局最新). 下面的命令从origin 这个remote 更新 master这个branch的update.
$git pull origin master
未必需要从自己所在的branch来更新. 比如你实际在master这个branch, 你也可以更新branch foo的东西,即使你还是留在master这个branch里:
$git pull origin foo
有时候每次都是默认同样的remote同样的branch,那么我们可以修改工作目录下的.git/config文件,
[branch "master"]
    remote = origin
    merge = refs/heads/master
这样就可以直接用下面命令来更新而无须指定remote和branch
$git pull


做了修改后, 为了查看当前工作目录的状态,比如哪些文件被改动, 哪些文件没有commit, 可以使用status (大致相当于svn st)
$git status
如果需要git status的时候忽略某些文件,比如.o文件或者.pyc文件, 我们可以在.gitignore这个文件中加入两行*.o以及*.pyc.

修改了本地的文件后, 需要将其用add命令将其加入index. svn里没有index的概念,而且add这个命令在svn中是将一个文件加入版本控制. 而git里, 一个文件每次的修改都会需要你用add加入index后才能commit.
$git add file1 file2
然后将index的修改commit到本地.
$git commit file1 file2 -m "go! commit file1, file2"
以上两步(add, commit)也可以被合并成一步
$git commit -a file1 file2 -m "go! commit file1, file2"
如果需要更改上一次commit的信息
$git commit --amend -m "this is the right commit!"

这个时候文件只是在本地commit, 如果希望更新到远端的repositiory中, 还需要push(和更新源到本地的pull命令对应). 默认git push的话是push到origin的master分支
$git push
你也可以指定remote repo以及branch
$git push repo5 branch12
如果当前工作目录下checkout了多个branch, 但是你一般只会push正在tracking的这个branch,可以在config文件(比如.git/config)里设置
[push]
    default = tracking
或者使用命令
$git config push.default tracking

提取给定版本 checkout
checkout最新commit里的foo
$git checkout foo
如果需要提前两个版本的foo,可以
$git checkout HEAD~2 foo
从最新的stash(stash@{0})里checkout foo这个文件
$git checkout stash@{0} foo

撤销更改 revert, checkout, reset
比如你刚刚修改了一个文件foo, 但现在想撤销这个更改. 这需要根据foo的状态来选择不同的方法:
  • Changed but not updated: 如果一个文件foo被删除了, 或者被修改了但完全还在本地workspace中,还没有使用git add把foo加入index当中, 那么我们只需要重新checkout 这个文件
    $git checkout foo
    如果你不幸有一个branch也叫foo
    $git checkout -- foo
    如果你需要恢复当前目录所有文件
    $git checkout . 
    有时候需要把当前workspace中所有的修改都撤销,可以简单的使用:
    $git stash
  • Changes to be committed: 这时候修改已经加入index当中,但是还没有commit 提交到本地repo,我们可以使用reset使的当前workspace回到上一个commit的时候, 然后使用checkout恢复修改.
    $git reset HEAD foo
    $git checkout foo
    撤销所有index当中的修改:
    $git reset HEAD
  • 如果已经使用git commit把修改提交到了本地repo当中, 我们可以把本地repo rollback到上一次commit前的状态:
    $git reset --hard HEAD~1
    --hard选项会overwrite的所有的改动.

    如果我们只需要undo某一次的commit,可以使用git revert:
    $git revert b38155cbf671d55ceb027687c39508de8cef2463
    这样实际上是提交了另一个commit来抵消指定的commit.

查看日志 log
当前branch的commit日志
$git log
当前branch的commit日志,显示内容
$git log -p
当前branch的commit日志,但只显示上3次提交的内容
$git log -3
当前branch的commit日志,但只显示被修改的文件名
$git log --name-only

处理冲突 conflict
参考手册http://www.kernel.org/pub/software/scm/git/docs/user-manual.html
以及 http://www.kernel.org/pub/software/scm/git/docs/git-push.html

pull的时候如果有本地修改会导致无法成功. 如果希望能把远端的commit merge到本地
$git checkout -m foo
Auto-merging foo
有可能会失败,这时候就需要你手动来编辑这个文件来merge了

push的时候, 当前commit到远端repo的时候,有时候会出现如下问题:
$git push
To git@example.come:example.git
 ! [rejected]        master -> master (non-fast-forward)
error: failed to push some refs to 'git@example.com:example.git'
To prevent you from losing history, non-fast-forward updates were rejected
Merge the remote changes before pushing again.  See the 'Note about
fast-forwards' section of 'git push --help' for details.
这是由于你的工作目录没有update到最新的版本.换言之有人在你上一次pull之后又push了新的commit进去.所以如果你的push生效, 可能会导致别人push的commit失效. 解决方法有两种:
$git pull
$git push
这种方法先把当前工作目录更新到最新 -- 这一步可能会产生冲突. 解决冲突后把更新提交. 这种方法会产生两个commit信息. 一次是说你自己的更新,另一次是将你的分支和repo上分支的merge.
如果不希望产生两次commit信息, 可以用第二种方法:
$git pull --rebase
$git push
这种方法直接将你的commit重新rebase到最新的版本上, 然后再进行提交.

分支 branch
一个repo可以有不同的分支,branch命令查看本地已有的分支, *表示当前使用的branch
$git branch
* master
  testbranch
可以用branch -r 查看remote所有的分支
$git branch -r
也可以用branch -a 同时查看local和remote所有的分支
$git branch -a
以当前branch的HEAD为起始点,新建新的branch叫newbranch
$git branch newbranch
也可以指定起始点(比如testbranch), 创建一个新的分支叫newbranch
$git branch newbranch testbranch

将当前分支从master切换到testbranch
$git checkout testbranch
$git branch
  master
* testbranch

删除一个local的branch
$git branch -d branch_to_delete
删除一个remote的branch
$git branch push origin --delete branch_to_delete
远端 remote
查看当前branch有哪些remote
$git remote
origin
查看当前branch有哪些remote,显示具体一些的信息
$git remote -v
origin git@example.com:bar.git (fetch)
origin git@example.com:bar.git (push)

查看origin这个remote的具体信息
$git remote show origin
一个repo可以有多个remote.比如给分支branch_foo添加一个新的remote:
$git remote add branch_foo git@host-for-new-remote:repo-name.git
将新添加的remote添加为tracking的branch
$git branch --set-upstream branch_foo   remote_bar/branch_foo

查看历史版本
查看某个版本(some-sha1)的某个文件
$git show some-sha1-number:some-file
查看某个版本(some-sha1)的和最新版本(HEAD)之间的所有区别
$git diff some-sha1 HEAD
查看某个版本(some-sha1)的和最新版本(HEAD)之间的某个文件的区别
$git diff some-sha1 HEAD --somefile

比较当前branch和另外一个branch比如叫foo的区别
$git diff foo
比较branch foo和另外一个branch bar的区别
$git diff foo bar
查看远端repo里的文件
查看当前HEAD中所有加入git管理的个文件
$ git ls-tree -r  HEAD

其他相关工具
tig - text-mode interface for git 设置git ignore的方法: http://help.github.com/ignore-files/

Saturday, July 17, 2010

赶个时髦,学习一下Object-C

(未完)
由于iPhone等Mac系产品无比红火的存在,Object-C也变得重要起来。Object-C是Apple的御用语言(类似C#之于Microsoft)。如果要开发个iPhone App啥的,就需要用到Object-C。如果要在MacOS里写点基于Cocoa的应用程序,也需要用到Object-C(其实Cocoa有python等其他语言的绑定,不过我试了一下不太喜欢)。

话说当年水果教教主Steve Jobs被董事会一脚踢出了自己创立的Apple,就搞了一个Startup叫做NeXT。Object-C就是NeXT从别人手里买下的。Steve Jobs在NeXT待了十年,期间潜心研发硬件软件,修为大为精进。而Apple这段时间却止步不前,终于在1997年被Steve Jobs夺舍而复辟回到了Apple。Steve Jobs顺道也把在NeXT修炼的OpenStep操作系统(打包了Object-C,Cocoa和Xcode等)带回了Apple,也就是后来广为人知的MacOS X。在使用Object-C的时候会发现大量NS开头的类(NeXTstep的意思),就是在纪念这段历史。

Object-C从名字上来看顾名思义就是包括了面向对象的C。道友可能会问,C++不就是用面向对象版的加强的C么?对,但其实现在我们看到的C++是那轮改造中涌现出来的最流行的那个。Object-C和C++都说自己继承了C语言,是C的超集--当你用不到面向对象的时候确实是这样。但是用上面向对象以后,两者的语法就存在着不小的区别。Object-C的面象对象部分其实处处都流露出从更加上古时期就流传下来的Smalltalk的影子。为了以示区别,Object-C中对于C扩充的关键字多以@开头,比如@interface,@end等。

下面开始步入正题:
第一个Object-C程序:Hello World

像学习其他所有语言一样,我们也不能免俗的从Hello World开始。下面是Object-C版本的Hello World
#import <stdio.h>

int main( int argc, const char *argv[] ) {
    printf( "hello world\n" );
    return 0;
}
不难发现,Object-C的Hello World和C版本的基本一样,唯一区别在于把#include换成了#import。没错,谁让Object-C就是C的扩充呢。

面向对象:类的创建

在Object-C当中, 首先用@interface定义一个类的成员变量和成员函数,然后在@implement中实现成员函数
Object-CC++
//Foo.h
@interface Foo : NSObject 
{ 
@private:
    double x;
@protected:
    double y;
@public:
    double z;
} 
-(int) f:(int)x; 
-(float) g:(int)x :(int)y; 
@end
//Foo.h
class Foo 
{ 
private:
    double x;
protected:
    double y;
public:
    double z;
    int f(int x); 
    float g(int x, int y); 
};
//Foo.m
#import "Foo.h"
@implementation Foo 
-(int) f:(int)x {...} 
-(float) g:(int)x :(int)y {...} 
@end 
//Foo.cpp
#include "Foo.h"
int Foo::f(int x) {...} 
float Foo::g(int x, int y) {...}

调用类方法

Object-CC++
[myObj method]
[myObj method:para1:para2]
output=[myObj method:para1:para2]
[obj1 func1:[obj2 func2]]
myObj.method()
myObj.method(para1,para2)
output=myObj.method(para1,para2)
obj1.func1(obj2.func2())
在Object-C当中,类方法的调用并不是传统的C/C++方式。而是采取了贴近Smalltalk的设计--消息。

Instance Method vs Class Method
在Object-C中,类的方法分为Instance 和Class两种,定义的时候分别使用"-"以及"+". Class method在大多数其他语言比如C++以及Java中又叫静态方法(static method).
@interface MyClass : NSObject

+ (void)aClassMethod;
- (void)anInstanceMethod;

@end
调用的时候
[MyClass aClassMethod];

MyClass *object = [[MyClass alloc] init];
[object anInstanceMethod];

Duck Typing

同受Smalltalk影响,Object-C和Python一样可以归入Duck Typing:一个类的实例可以调用该类中定义都方法,也可以调用该类中并没有定义的方法。在C++中如果一个类foo没有定义方法bar,那么foo的实例是无论如何也不能调用bar的--编译就无法通过。但是在Object-C(以及Python)中却没有问题--至少在编译期没有问题,但在运行期会有异常.

参考

从C/C++语言到Objective-C语言
Learning Object-C

Thursday, July 08, 2010

[Linux]readline

使用gnuplot的时候, 使用backspace 或者del这样的键总是显示~这样的字符
rlwrap -a -c gnuplot

这有一篇Consistent BackSpace and Delete Configuration
没有来得及仔细看

Tuesday, July 06, 2010

Virtualbox


Guest OS Addition
启动虚拟OS以后, 在device的menu里找到安装Guest OS Addition
安装这个的好处是鼠标可以自由移动, Guest OS的分辨率也会调整的比较好

共享文件夹
Host OS: Mac OS X
Guest OS: Ubuntu 9.04
为了在Guest OS中访问Host的文件系统,我们需要把Host的目录mount上

mount -t vboxsf [-o OPTIONS] sharename mountpoint
e.g. mount -t vboxsf -o uid=500,gid=500 /path/in/host /mount/point/in/guest

Guest OS: Windows XP
在Guest的Windows系统中访问MacOS上的目录,是通过映射网络硬盘实现的
在windows的命令行中输入
net use x: \\vboxsvr\sharename
这里x是你在Windows系统中分配的网络硬盘盘符,而sharename则是你在虚拟机中设置的共享文件夹(不一定是路径)

[Linux]动态链接库相关命令

Linux下动态链接库的管理
ldconfig 管理系统中的动态链接库文件

ldconfig这个命令会在“特定的路径”下搜寻可以共享的动态链接库文件(在Linux底下格式为lib*.so*),进而创建出动态装入程序(ld.so)所需的连接和cache文件.这里"特定的路径"指/lib和/usr/lib这些默认路径以及动态库配置文件/etc/ld.so.conf内所列的目录以及文件.

如果刚刚安装了一个lib之后,相关文件仍然说找不到,可能是动态链接文件的cache没有更新.可以ldconfig把ld.so的cache更新一下:
ldconfig
只处理foo文件夹下的动态链接文件(前面描述的特定路径下就不处理了)
ldconfig -n foo
显示当前cache的动态链接文件
ldconfig -p

ldd
作用: 查看可执行文件需要的动态链接库
例子:
>ldd /bin/ls
 linux-vdso.so.1 =>  (0x00007fff549ff000)
 librt.so.1 => /lib/librt.so.1 (0x00007fd82409c000)
 libselinux.so.1 => /lib/libselinux.so.1 (0x00007fd823e7e000)
 libacl.so.1 => /lib/libacl.so.1 (0x00007fd823c75000)
 libc.so.6 => /lib/libc.so.6 (0x00007fd8238f2000)
 libpthread.so.0 => /lib/libpthread.so.0 (0x00007fd8236d5000)
 /lib64/ld-linux-x86-64.so.2 (0x00007fd8242c8000)
 libdl.so.2 => /lib/libdl.so.2 (0x00007fd8234d0000)
 libattr.so.1 => /lib/libattr.so.1 (0x00007fd8232cb000)


是否应该使用环境变量LD_LIBRARY_PATH?
答案是no.尽量不要设置这个变量.理由参见http://linuxmafia.com/faq/Admin/ld-lib-path.html


Mac下的动态链接
ldd对应otool

Ref
http://wiki.linuxquestions.org/wiki/Library
http://tldp.org/HOWTO/Program-Library-HOWTO/shared-libraries.html

[Latex]几招压缩Latex paper的页数

写paper的时候要压缩页数常常让人很痛苦.其实默认的Latex的paper尚有很大的空间,让你不动太多的内容改动就大大的压缩论文页数.下面我贡献常用的几招
调整Section title的font和spacing
\usepackage[medium,compact]{titlesec}
默认的section title啥的其实spacing相当大.所以别看这招简单, 但其实相当狠, 能省下来很大的空间.

对于Bibliography参考文献用小号字体
可以用 \small, 再小点用 \footnotesize, \scriptsize 也有人用. 不过\tiny就太小了,reviewer会有意见的.
\footnotesize
\bibliography{ref}
\bibliographystyle{abbrvnat}

标准的itemize环境里的indent吃掉了很多空间,可以用list环境来自定义左右间距等参数
\begin{list}{\labelitemi}{\leftmargin=1em}
  \setlength{\topmargin}{0pt}
  \setlength{\itemsep}{0em}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
\item blablabla
\item blablabla
\end{list}
在这里我们用\labelitemi (实心圆点)作为每个item开头的bullet.还可以用预定义好的\labelitemii (一个-)或者\quad (空白)甚至 $\star$这样的.
或者可以这样全局的来设置:
\usepackage{enumitem}
\setlist{itemsep=0pt,parsep=0pt}

调整Equation和前面文字的空间
公式和文字之间有时候会留下很大的间距,可以通过\vspace来压缩这个间距
Therefore,
\vspace*{-0.5\baselineskip}
\begin{eqnarray}
     A = B
\end{eqnarray}

Monday, June 28, 2010

[Linux]以安全模式启动firefox或是thunderbird

不小心装了有问题的add-on然后firefox或者thunderbird就启动不起来了?
/path/to/firefox/firefox -safe-mode
/path/to/thunderbird/thunderbird -safe-mode

卸载掉有问题的add-on之后就好了

Saturday, April 17, 2010

[Python]py2app:将python程序转换为Mac OS Application的工具

先安装py2app
安装完毕后会有一个叫py2applet的程序出现
接下来进入我们python程序的目录,比如我们的程序叫HelloWorld.py
第一步: 生成HelloWorld的setup.py
$ py2applet --make-setup HelloWorld.py
第二步: 生成HelloWorld.app的结构
$ python setup.py py2app -A

[Linux]cheeting sheet of sh, csh, bash

sh, csh, bash 比较

Statement sh tcsh bash
if-then-else
if [ expression ] 
then
    ...
else
    ...
fi
if (expression) then
    ...
else
    ...
endif
注:then必须和if同一行
if [ expression ]
then
    ...
else 
    ...
fi 
for-loop
for var in (list)
do
    ....
done
foreach var (list)
    ...
end
for var in [list]
do
    ...
done 
Loop in Bash: http://www.cyberciti.biz/faq/bash-for-loop/

Sh: http://www.freeos.com/guides/lsst/
Bash: http://tldp.org/LDP/abs/html/

Monday, March 29, 2010

[Linux/Mac]package/library管理工具

Ubuntu


很好的一个reference: Ubuntu Skills

安装软件
  • 从源安装是最方便最快捷的方式. 源的设置在/etc/apt/sources.list当中.
    如果知道需要安装的包的名称, 比如叫foo. 那么安装foo只需要
    apt-get install foo
    如果不知道确切名字,只知道大概是关于foo这个东西的, 可以通过下面的命令来搜索所有关于foo的包
    apt-cache search foo
    还有时候连包都不知道, 但是只知道需要某个文件比如叫foo.c,但不清楚应该装哪个包, 这时候可以先安装apt-file
    apt-get install apt-file
    然后用apt-file来帮你找可能是哪个包有这个文件
    apt-file search foo.c
  • 也可以下载deb文件来安装
    dpkg -i foo.deb


自动更新所有过时的package
apt-get update
卸载package foo
apt-get remove foo
彻底卸载package foo (连同配置文件一起删除)
apt-get remove --purge foo
自动卸载不需要的包
apt-get autoremove
查看某个包foo的详细信息
apt-cache show foo
查看repository中package foo的版本
apt-cache policy foo
添加某个源的key
apt-key add bar.asc

安装完之后, 通常用dpkg来管理包
查看package foo所安装的文件以及路径
dpkg -L foo
显示包的信息
dpkg -s packagename
显示包括指定文件的包
dpkg -S filename
显示指定包的状态
dpkg --get-selections packagename
配置某个包
dpkg --configure packagename
配置所有的包
dpkg --configure -a


MacOS中的home brew

https://github.com/mxcl/homebrew/wiki/The-brew-command
非常好用的MacOS下的包管理软件.强烈推荐.
一个brew的cheatsheet: http://cheat.errtheblog.com/s/brew/ 一个安装包时候常遇到的问题
$ sudo brew install ruby
Cowardly refusing to `sudo brew install'
这是by design. 我的解决方法是吧brew的onwer设成root
brew install foo
brew cleanup foo

如何为brew制作Formula:Formula Cookbook

MacOS中的port

关于port的使用MacPorts Guide
安装包foo
port install foo
删除包foo
port uninstall foo
查看包foo的相关信息
port info foo
查看所有过时的包
port outdated
更新所有过时的包
port upgrade outdated
查看已经安装的包
port installed
清除所有已安装包的临时文件
port clean --all installed
彻底删除旧的包
port -f uninstall inactive
删除inactive的包
port -u uninstall
port uninstall inactive
清理foo包的中间文件(比如损坏了)
port clean foo
安装foo这个包之前先将其deactivate
port deactivate foo
port activate foo
查看foo这个包都在本机安装了哪些文件
port contents foo
查看foo这个包都依赖哪些其他包
port deps foo
查看哪些包依赖foo
port dependents foo

Hadoop Related

参考文档

收集的一些关于Hadoop的链接
Official Docs
Hadoop Quick Start (Official)
Hadoop MapReduce Tutorial using Java
Hadoop MapReduce Tutorial using Streaming
Hadoop Command Line
Jobconf parameters
Hadoop API Doc (Java)

Cluster Setup
Job Configuration的选项和默认值(有点老, 0.15的, 不过大部分没变)
Other Tutorials
Cloud 9: 关于hadoop的介绍很好很具体.有一些关于具体的programming的指导.
Hadoop Really Quick Start
Cloud computing with Linux and Apache Hadoop
The Hadoop Distributed File System

Hadoop自带工具

大部分初学者可能的问题, 先看Hadoop FAQ

DistCp

bash$ hadoop distcp hdfs://nn1:8020/foo/src1 \ 
            hdfs://nn1:8020/foo/src2 \ 
            hdfs://nn2:8020/bar/dest 

bash$ hadoop distcp -f hdfs://nn1:8020/srclist \ 
            hdfs://nn2:8020/bar/foo 

用RandomTextWriter生成随机文本
hadoop jar ${HADOOP_HOME}/hadoop-*-examples.jar randomtextwriter\
  -D test.randomtextwrite.total_bytes=52428800 \
  -D test.randomtextwrite.bytes_per_map=5242880 \
  /data/rand-text
参数test.randomtextwrite.total_bytes指定总共有多少字节要写;参数test.randomtextwrite.bytes_per_map指定每个map写多少字节.

Sort
hadoop jar ${HADOOP_HOME}/hadoop-*-examples.jar sort \
  -outKey org.apache.hadoop.io.Text \
  -outValue org.apache.hadoop.io.Text \
   /data/rand-text /data/sorted-text

Grep
hadoop jar ${HADOOP_HOME_DIR}/hadoop-*-examples.jar grep \
  /data/rand-text /data/greped-text dfs[a-z.]+' 

参数tips

reducer需要内存超过默认的1024MB的话,可以通过参数调整:
-D mapred.job.reduce.memory.mb=2048

使用Java作Hadoop MapReduce的时候,如果用到其他第三方的jar文件,用-libjars 选项来include

可以用-file选项指定需要使用的脚本
-file=myscript.sh

使用Streaming的时候,每个map task最多只能处理一个输入文件. 因此如果输入包括100个文件,则至少需要100个map.如果设定的mapred.map.tasks数目小于100,Hadoop会自动调整为100.

压缩格式的输入
当输入是gz或者是bz2文件时,不需要做特殊的处理.
-D stream.recordreader.compression=gzip

压缩格式的输出
当希望输出是压缩格式(比如.gz文件)时, 可以加上下面的选项
-D mapred.output.compress=true \
-D mapred.output.compression.codec=org.apache.hadoop.io.compress.GzipCode

指定map以及reduce的数目
指定map数目
-D mapred.map.tasks=your_map_number
指定reduce数目
-D mapred.map.tasks=your_reduce_number
特别的,使用map only 的MapReduce job时,
-D mapred.reduce.tasks=0

使用identityMapper作为mapper或者reducer
-mapper org.apache.hadoop.mapred.lib.IdentityMapper
-reducer org.apache.hadoop.mapred.lib.IdentityReducer

Key,Value的划分
对于streaming job,需要将map的输出划分成key和value.默认的划分是第一个"\t"之前的是key,之后的是value.但是我们可以自定义分隔符,比如要用=作为分割:
-D stream.map.output.field.separator==
也可以指定第几个分隔符之前的作为key:
-D stream.num.map.output.key.fields=4

Primary, Secondary Key
Hadoop Mapreduce 默认根据key来分配reducer使得所有key一样的record都被同一个reducer处理.有时候我们希望每个record是这样的格式 (k1,k2,v), 然后所有k1(也就是primary key)一样的record被同一个reducer处理, 而这个reducer看见的所有k1的record按照k2来排序.这样的要求可以通过类似下面的代码来实现: 比如这里将map输出里每行的前2个field作为k1也就是partition参考, 而第3第4个field作为k2来排序
-partitioner org.apache.hadoop.mapred.lib.KeyFieldBasedPartitioner \
-D stream.num.map.output.key.fields=4 \
-D num.key.fields.for.partition=2


输出路径可以在命令行中用${mapred.output.dir}指定或者在程序中用JobConf.setOutputPath来指定

Friday, February 19, 2010

[Linux]Makefile速查

基本语法:
target: prerequisites
    command
target:规则生成的目标. 可以是最终的目标文件,也可以是中间文件,还可以是“伪目标”(比如all,clean)
prerequisites:生成规则目标所需要的文件名列表
command:生成规则目标所要执行的动作,可以是一行也可以多行.但每行必须以tab开头

一个Makefile就是由一个或多个规则构成.默认的情况下,make执行的是Makefile中的第一个规则.比如下面例子:
# 定义变量可以方便修改
objects = main.o utils.o
#默认最终生成目标:edit
edit : $(objects)
    cc -o edit $(objects)
#指给定.o目标所需要的.h文件,make自动使用.o文件同名的.c文件,并且使用cc编译
main.o : defs.h
utils.o : defs.h
#告诉make clean是一个伪目标而不是真实文件
.PHONY : clean
clean :
    rm edit $(objects)

内部宏:
$?:比目标的修改时间更晚的那些依赖模块表。
$@ :当前目标的全路径名。可用于用户定义的目标名的相关行中。
$<:比给定的目标文件时间标记更新的依赖文件名。
$* :去掉后缀的当前目标名。例如,若当前目标是pro.o,则$*表示pro。

通配符
HEADERS=$(wildcard ./*.h)

参考:
[1] GNU Make中文手册

Thursday, February 18, 2010

[数学]抽扑克

2n张牌,n张红n张黑.随机从这副牌里连续抽牌(抽出来后就不扔回去了),平均能够看见多少次连续两张红牌?如连续三张红牌,视为看见两次.平均能看见多少次前一张红牌后一张黑牌?

Sol: 先定义随机变量
I_{i}=\begin{cases} 1 & \textrm{ith,(i+1)th are both read}\\
0 & \textrm{otherwise}
\end{cases}
这样能看见的连续红牌次数X = I_1+I_2+...+I_(2n-1). 虽然I_i和I_j之间并不独立(比如你前n张都抽的是红牌,那么后n张只能是黑牌了),但是如果是对X求期望,就可以把各个I_i单独拎出来求期望,再对期望求和:
E[X] = E[I_1]+\cdots+E[I_{2n-1}]=(2n-1)\frac{n}{2n}\frac{n-1}{2n-1}=\frac{n-1}{2}
同理可以得到看见先红后黑的平均次数是 n/2

Saturday, February 06, 2010

[数学]关于扔硬币得到的序列

现在有一枚硬币, 每次以概率p得到正面(下面以H代表),概率q=1-p得到反面(以T代表).反复投掷这枚硬币并记录出现的结果序列, 比如 T H H T T T H H T H...这样的一个序列. 针对这个序列我们可以说,在时间4我们完成了一个pattern THHT, 在时间6我们完成pattern TTT, 时间9又重复出现了pattern THHT.

下面是一些直观上容易理解的以及费解的:)结论: 

  1. 一个长度为k的给定pattern,在t时刻出现的概率为 p^i q^(k-i).这里i是pattern中T出现的次数. 这个很好理解.比如TTT在任意时刻出现的概率是p^3,  THHT是p^2 q^2, HTHT也是p^2 q^2
  2. 同一个pattern, 两次出现的时间间隔的期望是 1/[p^i q^(k-i)]. 这个结果也很直观. 可以根据Delayed Renewal Process得到. 所以THHT出现间隔是1/(p^2 q^2),HTHT出现间隔也是1/(p^2 q^2)
  3. 一个pattern, 从第一次扔硬币开始到第一次出现的时间期望

    E[time until HTHT] =  E[time until HT] + E[time between HTHT] = E[time between HT] + E[time between HTHT] = 1/(pq) + 1/(p^2 q^2)

    这里的一个trick是把pattern HT和HTHT之间的时间间隔等同于出现pattern HTHT 的间隔. 仔细想一下的话, 出现一次HTHT后这个pattern对下一次出现HTHT的贡献(或者影响)就是它的尾巴HT了. 同理我们还有

    E[time until THHT] =  E[time until T] + E[time between THHT] = E[time between T] + E[time between THHT] = 1/p + 1/(p^2 q^2)

    所以从第一次投硬币开始观察的话,  HTHT和THHT第一次出现的平均时间是不同的.
    同样我们也可以得到连续k个T出现的平均时间, 注意每一次连续出现i个T都对i+1个T有贡献

    E[time until k consecutive T] = 1/p + 1/p^2 + ... + 1/p^k

这个问题还有一个利用Martingale的方法来算,而且是Bob Li提出来的(A martingale approach to the study of occurrence of sequence
patterns in repeated experiments, Annals of Probability, 1980).比如我们要求E[time until HTHT].设在第i轮,一个赌徒下注1块钱.如果第i轮结果是H,赌徒就赢得1/p块钱,接下来第i+1轮结果是T,赌徒就赢得1/(pq)块钱,以此类推.不过如果一旦没有压准,所有钱就输了.请注意这是一个公平赌博.如果每一轮都有一个赌徒来下注.设Xn为第n轮下来赌场的收入:
Xn=(n-4) - [1/(p^2 q^2) -1] + 1 - [1/(pq) -1 ] + 1

因为Xn是Martingale,所以 0 = E[Xn] = (E[n]-4) - [1/(p^2 q^2) -1] + 1 - [1/(pq) -1 ] + 1
也就得出E[n] = 1/(pq) + 1/(p^2 q^2)

Monday, February 01, 2010

[数学]比较k个随机数加权后的大小

如果有k个随机变量x_1..x_k独立同分布于U[0,1],每个随机变量对应一个非负权重a_1...a_k.
那么加权后第一个随机变量比其他随机变量加权后都大的概率(i.e., a_1x_1>= a_ix_i for all i):

Sol:
如果给定x_1=x, a_1x_1比a_ix_i大的概率为min(a_1x_1/a_k,1)

\int_{0}^1\min(\frac{a_1x}{a_2},1)\cdots \min(\frac{a_1x}{a_k},1) d x

Tuesday, January 19, 2010

[数学]关于Coupon Collector的问题

原题在这里.简单的说,市面上有一种coupon有n个样式.每一个你新收集的coupon以1/n的概率为其中任意一种.如果说你需要收集T个coupon你才能把所有的样式都拿到,那么T的均值是多少呢?

假设我们手里已经有了i-1种不同的coupon.那么在收集了i-1种不同coupon后,出现一个新式的coupon所需要的尝试次数服从参数为pi的几何分布.pi=(n-i+1)/n 也就是出现第i种新coupon的概率.
E[T]=1/p_1+1/p_2+\cdots+1/p_n =  \frac{n}{n}+\frac{n}{n-1}+\cdots+\frac{n}{n} = n H_n\approx n \ln n


该问题的一个变种是:求当我们收集齐了所有n种coupon,其中某个样式(比如印着机器猫的)coupon只拿到了一张的概率.

该珍贵的coupon,可以是第1种收集到的,也可以是第j种收集到的.j服从1,...,n,的均匀分布.如果它是第j种收集到的coupon,则后面不出现该coupon的概率是 1/(n-j+1). 所以全概率是:
\sum_{j=1}^n \frac{1}{n}\frac{1}{n-j+1}= \frac{H_n}{n}\approx \frac{\ln n}{n}

Sunday, January 17, 2010

[Emacs]我总结的Emacs Cheating Sheet

这有一个不错的pdf版本cheat Sheet:Emacs Cheat Sheet

C代表Ctrl键, M代表Meta键, ←和→是右箭头和左箭头
基本操作
这里总结的是基本操作,大多数mode下都可以用
在文本中移动
C-f, C-b 向前(C-f)或是向后(C-b)移动到下一个字符.
M-f, M-b 向前(M-f)或是向后(M-b)移动到下一个单词.
C-M-f, C-M-b 在一对匹配的括号间,向前(C-M-f)或是向后(C-M-b)跳转.
C-a,C-e 移到当前行首(C-a)或者行尾(C-e).
M-a, M-e 向前(M-a)或是向后(M-e)移动到下一个句子.
C-x C-space 跳转到上一个mark的地方
C-v,M-v 向前(C-v)或是向后(M-v)翻页
M-<, M-> 移动到buffer首/尾
M-m 移动到第一个非空格字符。(back-to-indentation)
M-r 加参数,移动到窗口里的某一行。不加参数缺省移动到窗口中间。
M-x goto-char 到文件的第 N 字节。
M-x goto-line 到文件第 N 行。
C-x C-n 设定 goal-column.
C-u C-x C-n 取消 goal-column.
M-g g 移动到指定行

编辑文本
C-o 当前位置插入一行
M-Delback,M-d 以word为单位的前删/后删
C-d 删除后面一个字符且不放入kill-ring
C-M-k 向前删除直到匹配括号
Esc-C-Del,Esc-C-Backspace: 先后删除到匹配括号
M-z : 删除到下一个出现的位置

大小写转换
从光标位置开始,处理单词后半部分
capitalize-word (M-c) -- 首字母改为大写
upcase-word (M-u) -- 全部改为大写
downcase-word (M-l) -- 全部改为小写
从光标位置开始,处理单词前半部分
negtive-argument; capitalize-word (M-- M-c)
negtive-argument; upcase-word (M-- M-u)
negtive-argument; downcase-word (M-- M-l)
改变选定区域的大小写 downcase-region (C-x C-l) -- 选定区域全部改为小写
upcase-region (C-x C-u) -- 选定区域全部改为大写


设定Marker
C-空格,C-@ 设定一个mark
C-x h 整个缓冲区全部mark

对齐 (http://www.emacswiki.org/emacs/AlignCommands#toc2)
M-x align 对齐当前选择
M-x align-current 对齐当前section
M-q fill-paragraph 对一个段落排版

获取帮助
C-h c 简要描述给定键绑定
C-h k 详细描述给定键帮定
C-h f 描述给定函数
C-h v 描述给定变量
C-h m 描述当前mode
键/键组合 C-h 以当前键/键组合开头的绑定
M-x `finder-commentary' RET foo RET.

查找
C-s 向前方查找
C-r 向后方查找

注释
M-; 注释一个区域或者去掉区域的注释 (需要开启transient-mark-mode以后)

操作矩形
首先Set Marker然后移动光标围成一个矩形区域
C-x r k 删除矩形区域
C-x r t 矩形区域中插入文本

切换不同窗口
C-x 0 删除当前窗口(注意是零不是o)
C-x o 把光标在屏幕上的窗口间进行切换。记忆方法:其它(other)窗口。
C-x 1 把当前光标所在的窗口放到最大,隐藏其它所有的窗口。记忆方法:只剩一(1)个。
C-x 2 水平切分屏幕
C-x 3 竖直切分
C-x w r 1 存储当前窗口layout到寄存器1(可以为其他数字)
C-x j r 1 读取寄存器1(可以为其他数字)中的窗口layout

切换不同buffer
C-x b 缓冲区名称. emacs会提供一个缺省的缓冲区,一般是上一个用到的.如果不行,手动输入缓冲区名称,支持和自动补全.
C-x C-b 列出缓冲区菜单. 但这个命令不会将光标移动到缓冲区菜单的窗口中,需要C-x o命令切换过去.
C-x →,C-x ←. 循环切换到前一个(后一个)缓冲区
C-x k 杀死一个缓冲区(默认是当前缓冲区)
C-x C-s 保存当前缓冲区

切换不同frame
C-x 5 0 切换frame

在Emacs中使用Shell buffer
M-x ansi-term 带有色彩支持的term
M-x shell 系统默认shell
M-x eshell emacs自带shell

参数
M-<数字> : 执行 <数字>这么多次
C-u <数字> : 同上



常用Mode下的操作
AucTex LaTeX mode
C-c C-b 编译buffer / 预览编译结果
C-c C-r 编译选定的region
C-c C-c 运行定义好的命令比如 latex, view, bibtex
C-c C-v 查看当前的output file
C-c C-e 添加指定的环境
C-u C-c C-e 替换当前的环境
C-c ] 添加\end{...} 来匹配当前环境
C-c ; 注释选定区域,再操作一次就是去除选定区域的注释

CC mode
子模式:
auto-state 当你输入时自动缩进,自动换行
hungry-state 当你Backspace时,自动删除尽可能多的空白和空行
C-c C-t 同时转换(开/关)auto-state和hungry-state子模式
C-c C-a 转换 auto-state 子模式
C-c C-d 转换 hungry-state 子模式

M-/ 自动补齐(缓冲区中能找得到的串)
M-; 行尾加入注释
C-c C-e 扩展宏
C-c C-c 注释掉整个区域
C-c C-\ 将区域中的每一行结尾都加入一个'\'字符

cc-mode下的缩进
C-c . 设置缩进风格(按TAB键可列出可用的风格,缺省的为gnu,其 缩进为2个字符;linux为8个;k&r为5个…)
C-c C-q 缩进当前函数
C-M-q 缩进当前表达式
tab 缩进当前行
C-x h C-M-\ 缩进当前buffer
C-M-u C-M-q 缩进当前block

Lisp mode (http://www.delorie.com/gnu/docs/emacs/emacs_329.html)
C-: 执行一行lisp
C-x C-e 执行光标前的lisp

VC (version control) mode(http://lifegoo.pluskid.org/wiki/EmacsVC.html ,http://lifegoo.pluskid.org/wiki/EmacsVC.html , http://www.credmp.org/?p=65)
C-x v i 添加当前buffer的文件到version control当中
C-x v v 下一个合理的version control 动作(通常在一个状态下只有一个合理动作)
C-x v m 更新当前文件
C-x v + 更新当前文件集合
C-x v d 显示一个目录下所有注册到版本控制下的文件
C-x v l 查看log
C-x v = 和repository上代码作比较
C-x v ~ 查看以前版本

org mode (官方手册 , 中文教程)
Org mode是Emacs上一个用于组织信息,管理信息,撰写大纲的利器.可以帮助你非常快速的组织思路,查找信息.
C-c C-t Rotate the TODO state of the current item among
C-Shit-Enter 新建一个TODO 项目
Shit+Tab 切换view
链接:
[[链接地址][链接名称]]比如 [[http://www.gnu.org/software/emacs/][GNU Emacs]]
或者 [[链接地址]]如果你不需要名称


Cscope Mode
C-c s a 设定初始化的目录,一般是你代码的根目录
C-c s I 对目录中的相关文件建立列表并进行索引
C-c s s 序找符号
C-c s g 寻找全局的定义
C-c s c 看看指定函数被哪些函数所调用
C-c s C 看看指定函数调用了哪些函数
C-c s e 寻找正则表达式
C-c s f 寻找文件
C-c s i 看看指定的文件被哪些文件include

Dired mode (http://jamesthornton.com/emacs/node/emacs_396.html#SEC396 , http://www.20seven.org/journal/2008/11/emacs-dired-directory-management.html)
Dired mode用于文件管理
C-x d/M-x dired 进入Dired模式
C copy
D delete
# 标记所有atusave文件
R rename
s sort

iBuffer mode (http://www.emacswiki.org/emacs/IbufferMode)
和Dired mode相仿,但是用于buffer管理
M-x ibuffer 进入ibuffer模式
m 选定当前位置buffer
u 去除选定当前位置buffer
t 改变buffer list里每个buffer的选定状态
D 删除当前选定的buffer(们)
g 刷新
% n 选定所有那些buffer名称符合给定正则表达式的
% m 选定所有那些mode名符合给定正则表达式的
% f 选定所有那些文件名符合给定正则表达式的

GDB
M-x compile RET 编译
M-x gdb RET 调试
gdb --annotate=3 a.out 或者 gdb -i=mi a.out
C-x ` (出错信息中)下一个错误,一个窗口显示错误信息,另一个显示源码的出错位置
C-c C-c 转到出错位置

启动gdb调试器后,光标在源码文件缓冲区中时:
C-x SPC 在当前行设置断点
C-x C-a C-s step
C-x C-a C-n next
C-x C-a C-t tbreak
C-x C-a C-r continue

其他一些七七八八的

设置AucTex中的viewer. AUCTeX以前是通过设置TeX-output-view-style和TeX-view-style来决定如何根据output文件的后缀来用不同的viewer打开output文件. 新的实现是通过设置TeX-view-program-list和TeX-view-program-selection两个变量来实现:
比如把pdf和dvi文件关联到Evince.
(setq TeX-view-program-list '(("Evince" "/usr/bin/evince --page-index=%(outpage) %o")) )
(setq TeX-view-program-selection '((output-pdf "Evince") (output-dvi "Evince")) )

--could be out of date---
改变AUCTeX默认pdf viewer:
"Customize group - Auctex - Tex Command" entry for the "^pdf" extension in
"Tex Output View Style" => "evince %o"

重要变量
major-mode: 当前mode

载入.emacs文件
M-x load-file RET ~/.emacs RET Reload .emacs without restarting

check the value of your load-path by asking for help on the variable: ‘C-h v load-path RET’

By default Emacs doesn’t include subdirectories of a directory which is added to load-path. But you can do it by issuing a command in startup file:

(normal-top-level-add-subdirs-to-load-path)

Recover Data
M-x recover-file <ret> foo.c <ret>
yes <ret>
C-x C-s

查看package路径
M-x locate-library

在eclipse当中绑定emacs键位设定
Window->Preferences->General->Keys Scheme中选emacs

强制使用某种mode 比如xxx-mode
M-x xxx-mode

刷新当前文件
M-x revert-buffer
刷新所有已经打开的文件
M-x revert-all-buffers

去除所有结尾的whitespace
M-x delete-trailing-whitespace

绑定key http://www.xemacs.org/Links/tutorials_2.html http://www.gnu.org/s/emacs/manual/html_node/elisp/Key-Binding-Commands.html
(global-set-key (kbd "C-x C-\\") 'next-line)

显示行号(类似vi中的 :set nu)
(global-linum-mode t)

如果希望emacs帮你自动wrap line,
M-x auto-fill-mode

判断当前系统
(if (eq system-type 'windows-nt) do-what-you-like)
如果是MacOSX, 把'windows-nt换成'darwin

C-\ 切换 "拼符"输入法

Friday, December 25, 2009

[Linux]Squid--便捷的Proxy Server

unbuntu下安装squid
sudo apt-get install squid
接着对/etc/squid/squid.conf作如下修改
http_port 8888   #设定proxy的端口为8888
acl homenet src 98.219.0.0/16     #把访问proxy的机器的网段设为homenet
http_access allow homenet         #所有从homenet定义的网段的访问许可设为允许

Thursday, December 24, 2009

[数学]停车问题

Mathproblem上看来的问题. 一条街长度为4,最初这条街是空的.大家都开着长度为1的车子来来往往,寻寻觅觅.一旦发现街上有足够大的长度空着, 就会把车停下来.糟糕的是大家停车的时候在所有可能的泊车位随机的挑选,丝毫不会去为后面的人考虑.那么这条街,平均能停几辆车.

Sol:假设f(x)是在一条长度为x的空街上平均能停的汽车数目,当x>1的时候
f(x) = 1+\frac{\int_0^{x-1}[f(t)+f(x-1-t)]dt}{x-1} = 1 + \frac{2}{x-1}\int_0^{x-1}f(t)dt
不难得知
  • 0<x<1: f(t)=0
  • 1<x<2: f(t)=1
  • 2<x<3:
    f(t)=1+2\frac{\int_0^{t-1}f(u)du}{(t-1)} = 1+\frac{2(t-2}{t-1}
    
  • 所以
f(4)=1+\frac{2}{3}[\int_0^{1}f(t)dt + \int_1^{2}f(t)dt + \int_2^{3}f(t)dt] = \frac{11}{3} - \frac{4}{3}ln 2

Monday, November 30, 2009

[Emacs]一个locale引起的emacs中文输入问题

突然发现我的emacs-snapshot 23里无法呼叫出ibus中文输入法了.网上查了一下,说是LC_CTYPE环境变量应该设置为zh_CN.UTF-8. 于是在/etc/environment中修改完毕,结果还是没有效果.回想起升级到ubuntu9.10后, 总是碰到"locale: Cannot set LC_CTYPE to default locale: No such file or directory"这个错误信息.于是用locale -a 查看了一下系统支持的locale,不知道为什么没有zh_CN.UTF-8, 于是就用sudo locale-gen zh_CN.UTF-8 一下,再用locale -a查看zh_CN.UTF-8已经赫然在列了,那个错误信息也不再出现了.同时emacs 23里面也恢复了输入中文的功能.

Thursday, November 19, 2009

[Python]抓取豆瓣电台里被标记喜欢的歌曲名称

一段时间前开始使用豆瓣电台,很喜欢一个功能就是听到一个好听的歌就可以标记上.以后就可以从我的音乐里看到按标记时间排列出的所有曾经标记过的歌曲.但是有个功能豆瓣电台还不支持,就是按照专辑来对所有标记的歌曲分类.因为我想看一下哪一张专辑我标记的喜欢的歌曲最多. 所以就用python写了下面的脚本. 使用的时候不要忘记把下面源码里 current_url里面的apc字串换成你的用户名, 并且登录豆瓣.

#!/usr/bin/python
from urlparse import urlparse, urljoin
import urllib, sgmllib
from HTMLParser import HTMLParser
import re, sys

class MyParser(HTMLParser):
    def __init__(self):
        HTMLParser.__init__(self)
        self.num = 0
        self.albums = {}
        
    def parse(self, url):
        req = urllib.urlopen(url)
        self.state       = 0
        self.raw_text = req.read()
        self.feed(self.raw_text)
        
    def handle_starttag(self, tag, attrs):
        #print "Encountered the beginning of a %s tag" % tag
        try:
            if self.state == 0:
                if  tag == "table" and dict(attrs)["class"] =="olts":
                    self.state = 1
                    self.row = 0

            elif self.state == 1:
                if  tag == "tr":
                    self.row += 1
                    self.state = 2

            elif self.state == 2:
                if  tag == "td":
                    self.state = 3

            elif self.state == 3:
                if tag == "a":
                    self.state = 4
                else:
                    self.state = 1

            elif self.state == 4:
                self.state = 1
        except KeyError:
            pass

    def handle_endtag(self, tag):
        #print "Encountered the end of a %s tag" % tag
        if self.state >= 1 and tag == "table":
            self.state = 0

    def handle_data(self, data):
        if self.state == 3:
            if self.row > 1:
                print "%d title"%(self.num), data[:-2],
                self.num += 1
                self.title = data[:-2]
        elif self.state == 4:
            if data.strip():
                print "album", data
                try:
                    self.albums[data].append(self.title)
                except KeyError:
                    self.albums[data] =  [self.title]
            
        
numsongs   = int(raw_input("How many songs do you have?"))
myparser    = MyParser()
base = 0
while base < numsongs: 
    current_url = "http://www.douban.com/people/apc/songs?start=%d"%(base)
    print current_url
    myparser.parse(current_url)
    base += 20
print "done, all together %d songs"%(myparser.num)
al = myparser.albums.keys()[:]
al.sort(cmp= lambda x,y: len(myparser.albums[x]) - len(myparser.albums[y]))
for a  in al:
    print a, "%d songs"%(len(myparser.albums[a]))
我输出的结果是这两张专辑我标记的最多:
Schindler's List 6 songs
Le Fabuleux destin d'Amélie Poulain 9 songs
辛德勒的名单的OST以及天使爱美丽的OST. 我果然是个电影控.

无比强大的绘图脚本Asymptote

未完
写paper就免不了要绘制一些示意图,而且又需要是矢量图.其中的一些简单的也就用ppt之类的对付了.还有一些对于位置或者每个部分的尺寸精度要求比较高,更适合用脚本来生成.曾经用过一段时间metapost.但是它古怪的语法最后还是让我放弃了.之后便一直忍受着Visio或者用tgif这样的古董.直到我发现了Asymptote.这是一个用于绘制矢量图的脚本语言.其语法一方面继承了很多metapost的优秀的部分,另一方面又加入了一些类似于Python等现代脚本语言的特性.所以上手起来很快.最让我惊奇的是asymptote这样一个用于制图的语言还支持面向对象,high order function以及匿名函数这样的功能.不得不赞叹:asymptote 麻雀虽小五脏俱全.

这里有一个Gallery(link),大家可以看看这个语言的强大.

基本用法是
$asy inputfilename
inputfilename是你的asy输入源文件名称.如果它是helloworld.asy,那么asy就把这个源文件编译,输出为helloworld.eps.可以用-o选项指定输出文件名.

这里是我总结的Asymptote中最常用的命令和语法
在指定位置绘制一个点:
  • 在(0,0)这个坐标处绘制一个点

    dot((0,0));
  • 在(0,0)这个坐标处绘制一个蓝色的点

    dot((0,0), blue);

给定两个点,绘制直线:
  • 直线

    draw((0,0)--(2,1));
  • 带Arrow的直线

    draw((0,0)--(50,0),BeginArrow);
    draw((0,-10)--(50,-10),MidArrow);
    draw((0,-20)--(50,-20),EndArrow);
    draw((0,-30)--(50,-30),Arrows);
    这里设置arrow的参数可以为None(没有箭头,默认), Blank (不但不画箭头,线都不画), BeginArrow(箭头在起始端), MidArrow(箭头在正中间), EndArrow(箭头在末端,也简写成Arrow), 以及Arrows(两端都有)
  • 带Bar的直线

    draw((0,0)--(2,1),Bar);
    这里的参数还可以是None, BeginBar, EndBar (或者等价的简写为Bar), Bars(两端都是Bar)

在制定位置写文本:
  • 可以与LaTeX配合,写数学公式:

    unitsize(1cm);
    draw(unitsquare);
    label("$P_{0,0}$", (0,0), SW);
    label("$P_{1,1}$", (1,1), NE);

调整图的大小:
asymptote中用直角坐标绘图,默认时候一个点的大小是1/72 inch. 所以从(0,0)到(0,72)的线段长度是1 inch.有两种方法可以调整图的尺寸:
  • 设置单位长度

    unitsize(1cm);
    这样(0,0)到(0,72)的距离就是72 inch而不是1 inch
  • 设置最大尺寸

    size(100,200);
    这样所画的图会被自动scale到100*200这样的大小. 如果使用

    size(0,200);
    x轴方向上不scale而在y方向上scale到200个pt

调试:
write(a)
输出a的值,

例子:
我作业中要画的马尔科夫链
size(400,200);
import flowchart;
block state0 = circle(" $0$ ", (0,0));
block state1 = circle(" $1$ ", (10,0));
block state2 = circle(" $2$ ", (20,0));
block state3 = circle(" $3$ ", (30,0));
block state4 = circle(" ... ", (40,0), fillpen=invisible, drawpen = invisible);

draw(state0);
draw(state1);
draw(state2);
draw(state3);
draw(state4);

add(new void(picture pic, transform t) {
    real r = 0.4;
    //state0
    draw(pic,"$\lambda$", state0.position(2-r, t){NE}..{SE}state1.position(r,t),0.5*N, Arrow);
    //state1
    draw(pic,"$\lambda$", state1.position(2-r, t){NE}..{SE}state2.position(r,t),0.5*N, Arrow);
    draw(pic,"$\mu$",state1.position(-r, t){SW}..{NW}state0.position(2+r,t),0.5*N, Arrow);
    //state2
    draw(pic,"$\lambda$", state2.position(2-r, t){NE}..{SE}state3.position(r,t),0.5*N, Arrow);
    draw(pic,"$\mu$",state2.position(-r, t){SW}..{NW}state1.position(2+r,t),0.5*N, Arrow);
    //state3
    draw(pic,"$\lambda$", state3.position(2-r, t){NE}..{SE}state4.position(r,t),0.5*N, Arrow);
    draw(pic,"$\mu$",state3.position(-r, t){SW}..{NW}state2.position(2+r,t),0.5*N, Arrow);
    //state4
    draw(pic,"$\mu$",state4.position(-r, t){SW}..{NW}state3.position(2+r,t),0.5*N, Arrow);
});


参考

Wednesday, November 18, 2009

[数学]挑西瓜 (optimal stopping problem)

有N个房间,每个房间有一个西瓜,需要你挑出最大的那个西瓜.你需要按着房间顺序一个房间一个房间的查看西瓜.每当你看完一个房间的西瓜后,你需要立即决定是(1)挑选当前的西瓜还是(2)接着往下看.如果挑了当前的西瓜你就不能看后面其他房间.如果往下看了就要放弃当前西瓜而只能选择后面房间里的西瓜.使用怎样的策略能够让你最大化自己挑到最大西瓜的概率.

Sol: 这是传说中的Secretary Problem. 一个众所周知的算法是: 对于前s个房间只用于观察,我们记下前s-1个房间最大西瓜的尺寸.然后从第s+1个房间开始,一旦碰到比我们记下的尺寸还大的,就挑选之.如果一直没有碰到,就挑选最后一个房间里的.记Pr(s)为挑到最大西瓜的概率.
Pr(s) = \sum_{j=s}^n \frac{1}{n}\frac{s-1}{j-1}=\frac{s-1}{n}\sum_{j=s}^n \frac{1}{j-1}
这里1/n 是最大西瓜在第j个房间的概率,(s-1)/(j-1)是之前j-1个房间中最大的西瓜在房间1到房间s-1的概率. 可以证明s取n/e的时候这个概率取最大值.


Odds算法是该题另一种解法,事实上它的实用性更广.

Thursday, October 22, 2009

[Linux]在ubuntu上安装/使用Chrome

1 获取并安装:

安装Chromium: http://www.ubuntugeek.com/how-to-install-chromium-google-chrome-in-ubuntu-using-deb-package.html
安装Google Chrome: http://dev.chromium.org/getting-involved/dev-channel

二者稍微有一些区别.Chromium是Google主持的开源项目. 任何人都可以去www.chromium.org去下载并编译Chromium. Google从Chromium获取源码后加入一些东西比如Updater然后以Google Chrome的名字发布.外观上二者图标颜色不一样.

2 字体小:
我在Ubuntu上运行的Chrome中文字体偏小.
在~/.config/google-chrome/Default路径下修改Preferences. 加入了红色显示的两行后,字体就正常了.
"webkit": {
      "webprefs": {
         "default_fixed_font_size": 16,
         "default_font_size": 16,
         "fixed_font_family": "Microsoft YaHei",
         "minimum_font_size": 16,
         "minimum_logical_font_siz": 16,
         "sansserif_font_family": "Microsoft YaHei",
         "serif_font_family": "Microsoft YaHei"
      }
   }

Wednesday, October 21, 2009

[数学]连续两天降雨的概率

问题:(from mitbbs) Weather forecast: 50% chance of rain tomorrow, 75% chance of rain the day after tomorrow. What is the chance of rain for both tomorrow and the day after tomorrow?

Sol: 50%*75%? 这并不是一个严谨的答案.因为明天降雨和后天降雨未必是两个独立事件. 所以应该给出的是一个界

1/4=max{0, P[明天降雨]+ P[后天降雨]-1}< P[明天降雨 and 后天降雨] < min{P[明天降雨], P[后天降雨]}=1/2

Saturday, October 17, 2009

[数学]阿里巴巴开门

问题:阿里巴巴试图潜入山洞。在山洞入口处有一面鼓。鼓的侧面有四个一模一样的小孔,组成正方形的四个顶点。在每个孔的里面各装有一个开关。开关有“上”“下”两种状态。(注意:眼睛看不见!)如果四个开关的状态全都一致,洞门即可打开。现允许将手指伸入任意两个孔,触摸开关以了解其状态,并可随自己的意改变或不改变其状态。但每当这样做了之后,鼓就要飞快地旋转,以至在停转之后无法确认刚才触动了哪些开关。证明:阿里巴巴至多需将手指伸入五次,就可以进入山洞。

Sol: 友情鸣谢X公子&S太后奉献的答案! 撒花~~
将开关状态设为A,B两个状态,并用连续四个字母表示当前鼓上四个开关按照顺时针方向排列的状态。由于每次操作后鼓都会旋转,可以认为每一步只有两种可能的操作:选一条边上两个开关(下称“边”)或者选一条对角线上的两个开关(下称“对角”)

第一步:对角。若不一致则调为一致。此时若门没开,则只可能有两种状态:AAAB或者ABAB。

第二步:对角。分两种情况:
1)手伸入时状态一致,则一起翻转状态。若之前为ABAB状态则门开。若门没开,则之前为AAAB状态,翻后仍然为AAAB状态(A,B对称)。
2)手伸入时状态不一致,则之前为AAAB状态。保持原样。
第二步结束后可知此时状态为AAAB。

第三步:对角。分两种情况:
1)手伸入时状态一致,则翻转其中一个。可知结束时为AABB状态。
2)手伸入时状态不一致,则翻转其中一个。若门没开,则结束时为ABAB状态。

第四步:
(若上一次结束时知道是ABAB状态,跳过这一步,直接进入第五步)
上一次结束时知道是AABB状态,则选边,无论状态如何同时翻转两个开关。分两种情况:
1)手伸入时状态一致,则一起翻转,门开。
2)手伸入时状态不一致,则翻转后变成ABAB状态。

第五步:对角。同时翻转两个开关。由于之前状态为ABAB,则翻转后门开。

[SVN]SVN速查

参考

SVN refence
SVN: How to resolve a conflict

常用命令

1 创建工程myproject1
svnadmin create /home/svn/myproject1
在/home/svn目录底下, 你可以看见每个工程都对应一个目录. 目录里存放的是改工程的相关数据库.每个工程有不同的设置,也有自己独立的commit number.

2 导入目录mydir1进入myproject1
$ svn import -m "New import" /path/to/mydir1 file:///home/svn/myproject1/mydir1
Adding         mydir1/file1
Adding         mydir1/file2
…
Transmitting file data .........
Committed revision 1.

3 检出工程
svn co file:///home/svn/myproject1
或者
svn co svn+ssh://hostname/home/svn/myproject1

4 添加文件或者文件夹
svn add newfile
如果要添加文件夹newdir,但是不包括newdir底下的已有文件(默认是递归添加的)
svn add --depth empty newdir

5 提交更改
svn commit -m "add newfile"

6 查看本地或者网络svn工程目录的情况
svn list http://192.168.61.79/repos/server
svn list -v http://192.168.61.79/repos/server

7 查看服务器端foo.c的内容,保存到当前目录的foo.c.tmp中.
svn cat foo.c > foo.c.tmp
查看foo.c在111版本时的内容
svn cat foo.c -r 111

8 检出某一版本的工程文件
svn co http://192.168.61.79/repos/server -r 4

9 改变当前已存在的工程文件到某个版本
svn update -r 4

10 删除某个文件或者目录
svn delete foo.c

11 查看当前目录或者网络上的svn工程的情况
svn -v status

12 查看工程的更新信息
svn log
svn log http://192.168.61.79/repos/server

13 只更新某个文件(比如foo.c)
svn update foo.c

14 放弃foo.c中的地修改,将其恢复到服务器上的版本
svn revert foo.c

15 消除foo.c的conflict标记
svn revert foo.c

冲突解决

多人使用svn合作的时候,常常发生对文件修改的冲突.比如user1 checkout了foo.c的一个版本后,做了本地修改, 然后commit. 但是user2 在user1 commit之前也checkout 了foo.c.等到user2来commit的时候就会被告知:
svn: Commit failed (details follow):
svn: File or directory 'foo.c' is out of date; try updating
svn: resource out of date; try updating
user2这个时候运行
svn up
Conflict discovered in 'foo.c'.
Select: (p) postpone, (df) diff-full, (e) edit,
        (mc) mine-conflict, (tc) theirs-conflict,
        (s) show all options:
这是因为svn发现了conflict, 需要user2采取措施解决. user2可以采取的动作总共包括
(e)  edit             - change merged file in an editor
(df) diff-full        - show all changes made to merged file
(r)  resolved         - accept merged version of file

(dc) display-conflict - show all conflicts (ignoring merged version)
(mc) mine-conflict    - accept my version for all conflicts (same)
(tc) theirs-conflict  - accept their version for all conflicts (same)

(mf) mine-full        - accept my version of entire file (even non-conflicts)
(tf) theirs-full      - accept their version of entire file (same)

(p)  postpone         - mark the conflict to be resolved later
(l)  launch           - launch external tool to resolve conflict
(s)  show all         - show this list
这里我们的选择包括
  • 如果接受user1的版本而放弃本地修改,选择tc或者tf. 使用tf的话会整个文件一起使用user1的版本,哪怕中间有不冲突的部分.
  • 如果坚持本地修改,选择mc或者mf. mf就整个文件都使用user2的版本
  • 如果想要手动修改解决冲突,就使用e (edit)
  • 如果暂时不做决定,等一会再说, p (postpone)

Thursday, October 15, 2009

[数学]比较两个随机数大小

问题:(zz from mitbbs)在两张纸A,B上分别随机写两个数字,两个数字不相等。所以猜对哪个大的概率为1/2。现在随机翻开A或者B,再猜A或者B上哪个数字大。设计一种策略使得你猜对的概率大于1/2。

答案:不妨设A,B都为[0,1]之间的均匀分布.如果我们在猜之前知道A=x,那么当x<1/2的时候我们以概率(1-x)猜测B大,如果x>1/2我们以概率x猜测A大.采用这种随机策略,我们可以获得准确率:
\int_{x=0}^{1}x^2+(1-x)^2 d x = \frac{2}{3}

Sunday, October 11, 2009

[TeX]TDS: TeX文件目录结构

本篇尚未完成

理论篇

什么是TDS

TeX系统目录结构(TeX Directory Structure)简称 TDS,是 TUG(TeX Users Group)主持制定的标准,目的在于方便TeX的开发者和用户.目前流行的 MiKTeX 套装和 TexLive 套装都支持 TDS.

TEXMF树

TEXMF = TeX + MetaFont
texmf树,由于其不必要的庞大和复杂,而被诟病.但是它也带来了一些好处.比如你可以在不同的树下,分开安装维护不同版本的TeX.
一般我们同时拥有好几棵texmf树,它们有大致相同的组织结构,被委以不同的职责
  1. TEXMFMAIN:主要的树
  2. TEXMFLOCAL: 通常是对TEXMFMAIN的补充,
  3. HOMETEXMF:通常可以用来存放一些非public的(不是所有用户都可以使用的).比如只有你个人拥有许可的包, 或者你正在开发的包.

每棵树的组织结构大致如下:
.sty, .cls or .fd: $TEXMF/tex/<format>/<package>/
.mf:   $TEXMF/fonts/source/<supplier>/<font>/
.tfm:  $TEXMF/fonts/tfm/<supplier>/<font>/
.vf:   $TEXMF/fonts/vf/<supplier>/<font>/
.afm:  $TEXMF/fonts/afm/<supplier>/<font>/
.pfb:  $TEXMF/fonts/type1/<supplier>/<font>/
.ttf:  $TEXMF/fonts/truetype/<supplier>/<font>/
.otf:  $TEXMF/fonts/opentype/<supplier>/<font>/
.pool, .fmt, .base or .mem: $TEXMF/web2c


实战篇

找到你自己的${TEXMFMAIN}
kpsewhich -expand-var='$TEXMFMAIN'
在我的MacTex(基于TeX Live)上结果为/usr/local/texlive/2010/texmf

找到自己的texmf.cnf
kpsewhich texmf.cnf

metapost中使用label, 用gsview 来preview的时候报错: "undefined cmr10"
这是因为mpost 对*.mp 处理后得到的图形是 PS 格式,但是是没有嵌入字体,所以gsview无法显示

参考


[1]LaTeX之TeX系统目录结构
[2]A Directory Structure for TeX Files
[3]一个很不错的TeX笔记blog
[4]TDS in TeX Live

Saturday, October 10, 2009

[数学]The Ballot Problem

问题:在2009步步高音乐手机快乐女生的PK环节里,芒果台设定江小花得A票,喻娘娘得B票.因为芒果台是邪恶的,所以A>B.请问导演能设计出多少种投票方法能够让投票环节里,江小花一直领先?

答案:
\frac{A-B+1}{A+1}{A+B \choose A}
The Ballot Problem
http://webspace.ship.edu/msrenault/ballotproblem/
http://mathworld.wolfram.com/BallotProblem.html

Saturday, September 19, 2009

[数学]一辆需要猜测位置的车

We have a infinity road and a car whose initial position(at time t=0) is some integer coordinate which you don't know.The car is running at a fixed velocity of some other integer per second which you do not know neither. You even do not know the car is running towards +infinity or -infinity.

What you can only do is at a single integral time point you can make a query like this: Is the car at point x now? (you can choose the integer x).You can do query only once at a time and will be given the answer "yes" or "no" based on the truth.

Design a query strategy such that you can guarantee you will get a "yes"
answer in finite time.

Sol: Hint Cantor Paring Function:

Thursday, August 20, 2009

Mathematica速查

自定义函数:
In[1]:= f[x_]:=x^2+1

求解方程:
In[1]:= Solve[x^2+2x-a == b, x]

求极限:
In[1]:= Limit[Sin[x]/x, x->0]
In[2]:= Limit[1/x, x->Infinity]

求导数:
In[1]:= D[Exp[x],x]
二阶导数
In[2]:= D[Exp[x],{x,2}]

求和:
In[1]:= Sum[a^i/i, {i,1,M}]

绘图:
In[1]:= Plot[Sin[x],{x,0, Pi}]
In[1]:= Plot[{Sin[x], Cos[x]},{x,0, Pi}]

删除符号的赋值:
In[1]:= M=.

删除符号:
In[1]:= Remove[M]

导入数据:
In[1]:= Import["foo.dat","Table"]

拟合:
In[1]:= Fit[{{1,10},{2,25},{3,31},{4,40}}, {1,x}, x]
In[1]:= Fit[Import["foo.dat","Table"], {1,x}, x]

多项式展开:
In[1]:= Expand[(1 + x + x^2) (1 + x)]
Out[1]:= 1 + 2 x + 2 x^2 + x^3

分解因式:
In[1]:= Factor[1 + x^3]
Out[1]:= (1 + x) (1 - x + x^2)

多项式化简:
In[1]:= Simplify[(1 + x)^2 - (1 - x)^2]
Out[1]:=  4x