xiaobaoqiu Blog

Think More, Code Less

Sublime Markdown 预览

Sublime Text 2 终于迎来了一个 Markdown 预览插件:Sublime Text 2 Markdown Preview.

1. 安装Package Control

ctrl + `,出现控制台,输入:

1
import urllib2,os; pf='Package Control.sublime-package'; ipp = sublime.installed_packages_path(); os.makedirs( ipp ) if not os.path.exists(ipp) else None; urllib2.install_opener( urllib2.build_opener( urllib2.ProxyHandler( ))); open( os.path.join( ipp, pf), 'wb' ).write( urllib2.urlopen( 'http://sublime.wbond.net/' +pf.replace( ' ','%20' )).read()); print( 'Please restart Sublime Text to finish installation')

重启sublime,可在Preferences -> Package Settings看到Package Control。

2. 安装markdown preview

按下键ctrl+shift+p调出命令面板,找到Package Control: install Pakage(输入pci可以快速找到)这一项。搜索markdown preview,点击安装。

Markdown Preview较常用的功能是preview in browser和Export HTML in Sublime Text,前者可以在浏览器看到预览效果,后者可将markdown保存为html文件。

3. 快捷键

markdown preview默认没有快捷键,我们可以自己为preview in browser设置快捷键。方法是在Preferences -> Key Bindings User打开的文件的中括号中添加以下代码(可在Key Bindings Default找到格式):

1
2
3
[
    { "keys": ["ctrl+shift+b"], "command": "markdown_preview", "args": { "target": "browser"} }
]

快捷键自己选择,这里使用的是ctrl+shift+b,注意尽可能少的和Key Bindings Default定义的快捷键重复.

Java Concurrency in Practice 3 : 共享对象

第三章:共享对象 编写正确的并发程序关键在于对共享的可变状态进行管理

1. 可见性

没用同步的情况下共享变量的例子,不能保证主线程写入的值对于读线程是可见的,读线程可能会一致等待,也可能读出0(因为主线程在写入number之前已经写入ready,重排序现象)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class NoVisibility {
    public static int number = 0;
    public static boolean ready = false;

    /**
     * 负责读的线程
     */
    private static class ReadThread implements Runnable {
        @Override
        public void run() {
            while(!ready){
                System.out.println("Waiting...");
                Thread.yield();
            }
            System.out.println("Number = " + number);
        }
    }

    /**
     * 主线程, 写
     * @param args
     */
    public static void main(String[] args){
        new Thread(new ReadThread()).start();
        number = 100;
        ready = true;
    }
}

结论:只要数据被跨线程共享,就需要进行恰当的同步.

上面例子的一种情况是,读线程读取的是一个过期数据.但更坏的情况是:过期即不是发生在全部变量上,也不是不过期,而是部分变量过期.

最低限的安全性(out-of-thin-air safety):当线程在没有同步的情况下读取变量,它可能会的得到过期值.但是它至少看到的是某个线程设置的真实值,而不是凭空而来的值.

最低限安全性应用于所有的变量,除了:没有声明为volatile的64位的数值变量(long,double),JVM允许将64位的读或写划分为两个32位的操作.

为了保证所有的线程能够看到共享的可变变量的最新值,读取和写入都必须使用公共的锁进行同步.

Volatile提供了同步的一种弱形式.

当一个变量声明为volatile类型后,编译与运行时候会见识这个变量,而且对它的操作不会被重排序.

volatile变量不会缓存在缓存器或者缓存在对其他处理器隐藏的地方.所以,读一个volatile类型变量时候总会返回由某一个线程写入的最新值.

访问volatile变量的操作不会加锁,也就不会引起执行线程的阻塞,这使得volatile变量相对于sychronized而言,只是轻量级的同步机制.通常被当作标记完成,中断或某个状态的标记使用.

注意:加锁可以保证可见性和原子性,volatile变量只能保证可见性.比如volatile不足以保证自增操作(count++)原子化.

2. 发布和逸出

发布(publish)一个对象的意思是使它能够被当前范围之外的代码锁使用.

逸出(Escape):一个对象尚未准备号时候就将它发布.

下面是一个发布的例子,init()声明了一个HashSet,并将它存储到公共的静态域中.

1
2
3
4
5
6
7
public class Publish {
    public static Set<Secret> knownSecret;

    public void init(){
        knownSecret = new HashSet<Secret>();
    }
}

类似的,非私有的方法中返回引用,也能发布返回的对象,如:

1
2
3
4
5
6
7
public class Publish {
    private String[] country = {"USA", "China"};

    public String[] getCountry() {
        return country;
    }
}

这种发布会有问题,任何一个调用者都能修改它的内容.

3. 线程封闭

实现线程安全最简单的方式之一就是线程封闭.

一种维护线程限制的方式是使用ThradLocal,它提供了get和set访问器,为每个使用它的线程维护了一份单独的拷贝,所有get总是返回当前执行线程通过set方法设置的最新值.简单示例如下:

1
2
3
4
5
6
7
8
9
10
private static ThreadLocal<Connection> connectionHolder = new ThreadLocal<Connection>(){
    @Override
    protected Connection initialValue() {
        return super.initialValue();
    }
};

public static Connection getConnection(){
    return connectionHolder.get();
}

4. 不可变性

为例满足同步的需要,另外一种方法是使用不可变对象.不可变对象即创建后状态不能被修改的对象.

不可变对象并不适简单的等于将对象的所有域都声明为final类型,所有域都是final类型的对象仍然可以是可变的,因为final域可以获得一个可变对象的引用.

5. 安全发布

在并发程序中,使用和共享对象的一些最有效的策略如下:

  1. 线程限制:一个线程限制对象,通过限制在线程中,而被线程独占,且只能被占有它的线程修改.
  2. 共享只读:一个共享的只读对象,在没有额外同步的情况下啊,可以被多个线程并发的访问,但是任何线程都不能修改它.
  3. 共享线程安全:一个线程安全的对象在内部进行同步,所以其他线程无需额外的同步,就可以通过公共接口随意访问它.
  4. 被守护的:一个被守护的对象只能通过特定的锁来访问.

Java Concurrency in Practice 2 : 线程安全

第二章:线程安全

1.什么是线程安全

当多个线程并发的访问一个类,如果不用考虑多个线程运行时的调度执行顺序,且不需要做额外的同步及代码调用时候的限制,这个类的结果依然是正确的,则可以称之为线程安全.

无状态的类是线程安全的,无状态指不包含域也没有引用其他类的域.如下面这个类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class StateLess extends HttpServlet {

    /**
     * 从请求中获取两个数字,并计算两个数字的最大公约数,返回
     *
     * @param req
     * @param resp
     * @throws ServletException
     * @throws IOException
     */
    @Override
    protected void service(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        Pair<Integer, Integer> number = extract(req);

        int result = computer(number.getLeft(), number.getRight());

        setToResponse(resp, result);
    }
}

2.原子性

常见的竞争条件1:检查再运行(check_then_act).检查再运行指使用潜在的过期值来做决策或者执行计算.如下面的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Account {

    /**
     * 余额
     */
    private float balance;

    /**
     * 取款
     * @param count
     */
    public void withdrawing(float count) {
        if(balance > count){         //check
            doWithdrawing(count);     //act
        }
    }

    private void doWithdrawing(float count){
        balance -= count;
    }
}

常见的竞争条件2:读-改-写.如count++ 这种非原子的操作,其实包含三个原子操作

1
2
3
Read
Add
Write

什么是原子操作:

假设有操作A,在其他线程来看,执行操作A的线程执行时,要么操作A执行完成,要么一点都没有执行.则称之为原子操作.

如果前面的例子是原子的,则不会出现检查再运行和读-改-写的竞争条件.

为例保证线程安全,操作必须原子的执行.

比如count++,我们可以使用AtomicInteger:

1
count.getAndIncrement();

3.锁

java提供了强制原子性的内置锁机制:synchronized块.一个synchronized块包含两部分:1.锁对象的引用;2.锁对象保护的代码块;

1
2
3
synchronized(lock){
  // code
}

每个java对象都代表一个互斥锁(称之为内部锁或者监视器锁),因此每个java对象都可以扮演lock的角色.对于方法级别的synchronized,获取的是方法所在对象的锁.对于静态方法,从Class对象上获取锁.

当一个线程请求另外一个线程持有的锁时候,请求线程将会被阻塞.但是,内部锁是可以重入(Reentrancy)的,即线程请求它自己占有的锁的时候,是会成功的.这表示锁的请求是基于每个线程(per-thread)的,而不是基于每个调用(per-invocation)的.

4.用锁来保护状态

对于可以被多个线程访问的可变状态变量,如果所有访问它的线程在执行时都占有同一个锁,则称这个变量是由这个锁保护的.

并不是所有数据都需要锁的保护,只有哪些被多个线程访问的可变数据.

如果类的不变约束涉及到多个变量,则需要用同一个锁来保护这多个变量.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Account {

    /**
     * 余额
     */
    private float balance;

    /**
     * 操作次数
     */
    private int count = 0;

    /**
     * 取款
     * @param value
     */
    public void withdrawing(float value) {
        synchronized (this){    //同一个锁保护多个可变变量
            if(balance > value){
                doWithdrawing(value);
            }

            count++;
        }
    }
}

5.活跃度和性能

为了达到安全的目的,我们完全可以将方法设置为synchronized,但是这样带来的问题是:我们期房方法能提供并发访问,但是为了安全,实际上变成的串行访问.

因此在使用synchronized的时候需要考虑安全(不能妥协),简单性和性能.

比如网络或者IO这种耗时的操作器件,不应该占用锁.

Sublime输入中文

环境:Ubuntu 13.04

1.保存下述代码为 sublime-imfix.c 文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/* C
sublime-imfix.c
Use LD_PRELOAD to interpose some function to fix sublime input method support for linux.
By Cjacker Huang <jianzhong.huang at i-soft.com.cn>

gcc -shared -o libsublime-imfix.so sublime_imfix.c  `pkg-config --libs --cflags gtk+-2.0` -fPIC
LD_PRELOAD=./libsublime-imfix.so sublime_text
*/
#include <gtk/gtk.h>
#include <gdk/gdkx.h>
typedef GdkSegment GdkRegionBox;

struct _GdkRegion
{
  long size;
  long numRects;
  GdkRegionBox *rects;
  GdkRegionBox extents;
};

GtkIMContext *local_context;

void
gdk_region_get_clipbox (const GdkRegion *region,
            GdkRectangle    *rectangle)
{
  g_return_if_fail (region != NULL);
  g_return_if_fail (rectangle != NULL);

  rectangle->x = region->extents.x1;
  rectangle->y = region->extents.y1;
  rectangle->width = region->extents.x2 - region->extents.x1;
  rectangle->height = region->extents.y2 - region->extents.y1;
  GdkRectangle rect;
  rect.x = rectangle->x;
  rect.y = rectangle->y;
  rect.width = 0;
  rect.height = rectangle->height; 
  //The caret width is 2; 
  //Maybe sometimes we will make a mistake, but for most of the time, it should be the caret.
  if(rectangle->width == 2 && GTK_IS_IM_CONTEXT(local_context)) {
        gtk_im_context_set_cursor_location(local_context, rectangle);
  }
}

//this is needed, for example, if you input something in file dialog and return back the edit area
//context will lost, so here we set it again.

static GdkFilterReturn event_filter (GdkXEvent *xevent, GdkEvent *event, gpointer im_context)
{
    XEvent *xev = (XEvent *)xevent;
    if(xev->type == KeyRelease && GTK_IS_IM_CONTEXT(im_context)) {
       GdkWindow * win = g_object_get_data(G_OBJECT(im_context),"window");
       if(GDK_IS_WINDOW(win))
         gtk_im_context_set_client_window(im_context, win);
    }
    return GDK_FILTER_CONTINUE;
}

void gtk_im_context_set_client_window (GtkIMContext *context,
          GdkWindow    *window)
{
  GtkIMContextClass *klass;
  g_return_if_fail (GTK_IS_IM_CONTEXT (context));
  klass = GTK_IM_CONTEXT_GET_CLASS (context);
  if (klass->set_client_window)
    klass->set_client_window (context, window);

  if(!GDK_IS_WINDOW (window))
    return;
  g_object_set_data(G_OBJECT(context),"window",window);
  int width = gdk_window_get_width(window);
  int height = gdk_window_get_height(window);
  if(width != 0 && height !=0) {
    gtk_im_context_focus_in(context);
    local_context = context;
  }
  gdk_window_add_filter (window, event_filter, context); 
}

2.安装C/C++的编译环境和gtk libgtk2.0-dev

1
2
sudo apt-get install build-essential
sudo apt-get install libgtk2.0-dev

3.编译共享内库

1
gcc -shared -o libsublime-imfix.so sublime_imfix.c  `pkg-config --libs --cflags gtk+-2.0` -fPIC

4.启动 Sublime Text 2

1
LD_PRELOAD=./libsublime-imfix.so sublime_text

现在就可以输入中文了.

5.别名

每次这样启动sublime,很是别扭,我们取个别名就可以了.同时libsublime-imfix.so放在~目录下很是别扭,哪天可能不小心删除了,也把它移个位置:

1
2
3
4
5
6
7
8
xiaobaoqiu@xiaobaoqiu:~$ whereis sublime
sublime: /usr/local/bin/sublime

xiaobaoqiu@xiaobaoqiu:~$ cd /usr/local/bin/

xiaobaoqiu@xiaobaoqiu:/usr/local/bin$ sudo cp ~/libsublime-imfix.so .

xiaobaoqiu@xiaobaoqiu:~$ vim ~/.bashrc

在.bashrc文件中加一个别名:

1
2
#sublime
alias sublime='LD_PRELOAD=/usr/local/bin/libsublime-imfix.so sublime_text'

退出之后:

1
xiaobaoqiu@xiaobaoqiu:~$ source ~/.bashrc

现在,在命令行下直接输入sublime就可以开启可以输入中文的sublime了.

附上截图

两个已序数组的第k小元素

Problem:

两个已序数组(从小到大)的第k小元素.数组分别记为A(长度m)和B(长度n).

Solutions

方法1

将两个数组merge成一个有序数组(m+n大小),再直接取第k个元素.

时间复杂度:O(m+n).

空间复杂度:O(m+n).

方法2

两个指针i和j分别从小到大遍历两个数组,代码大致如下:

1
2
3
4
5
i=0, j=0
while((i+j)<k && (i<m || j<n)){
    if(A[i] < B[j]) i++;
    else j++;
}

时间复杂度:O(k).

空间复杂度:O(1).

方法3

利用方法2,我们发现,如果

1
B[j-1] < A[i] < B[j]

则,A[i]为第i+j+1小的元素,同理,如果

1
A[i-1] < B[j] < A[i]

则B[j]是第i+j+1小的元素.令

1
2
3
i+j+1 = k
i+j=k-1

则找到了我们需要的第k小元素.

下面是我们的方法:

  1. 二分搜索数组A,i的初值: i = (int)((double)m / (m+n) * (k-1)); 令j = k-1-i;

  2. 比较,如果 B[j-1] < A[i] < B[j] 则返回A[i]. 如果 A[i-1] < B[j] < A[i] 则返回B[j];

  3. 步骤2未结束,则比较A[i]和B[j]

    如果A[i]<B[j],则我们可以排除比A[i]小的元素和比B[j]大的元素,即

    在A[i+1, m]和B[0, j]中查找第k-i小的元素

    否在,可以排除比B[j]小的元素和比A[i]大的元素,即

    在A[0, i]和B[j+1, n]中查找第k-j小的元素

简单示例代码(不完整):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int kthSmallest(int A[], int m, int B[], int n, int k) {
  
  int i = (int)((double)m / (m+n) * (k-1));
  int j = (k-1) - i;

  int Ai_1 = ((i == 0) ? INT_MIN : A[i-1]);
  int Bj_1 = ((j == 0) ? INT_MIN : B[j-1]);
  int Ai   = ((i == m) ? INT_MAX : A[i]);
  int Bj   = ((j == n) ? INT_MAX : B[j]);
 
  if (Bj_1 < Ai && Ai < Bj)
    return Ai;
  else if (Ai_1 < Bj && Bj < Ai)
    return Bj;
 
  if (Ai < Bj)
    return kthSmallest(A+i+1, m-i-1, B, j, k-i);
  else
    return kthSmallest(A, i, B+j+1, n-j-1, k-j);
}

时间复杂度:O(logm + logn)

空间复杂度:O(1)