从svn迁移到git

On 九月 26, 2011, in 技术记录, by pensz

最近需要从svn迁移到git了,之前虽然有简单的用过的git,但那远远不够,最近先花了点时间来看看git的使用。

git和svn的最大区别是git是分布式的,而svn仅仅是一个svn服务器,实际的来说,git有本地的代码库,可以离线提交自己的修改至本地的代码库。通过下面这个图可以有一个直观的印象。

若要修改代码,从一个版本库开始的方法:

  • git是git clone
  • svn是svn checkout

提交代码至远程服务器的方法:

  • git是git commit -am ‘comment’ 提交至本地的代码库,若要提交至远程服务器,再执行git push
  • svn 则很简单,svn commit即可

从中央服务器更新到本地代码的方法:

  • git是git fetch到本地代码库,然后再git merge,简单的办法是 git pull
  • svn很简单 svn update

撤销本地修改:

  • git是git checkout . (该命令就是将本地的workspace修改撤销至本地代码库)
  • svn是删除掉修改的文件,然后svn update

比较差异:

  • git是 git diff (获得当前workspace还没有计划提交的差异,若计划提交后但仍未提交至本地代码库则用git diff –cached)。 git diff  <remote_branch> <branch> (比较本地代码库和服务端的差异),一般的命令就是 git origin/master master
  • svn 则是svn diff即可

 

其他一些问题:

git 的本地代码库commit的撤销:

  • git revert 这个会撤销本地代码库的修改,但这个动作本身会创建一个版本,因此很容易搞混。
  • git reset –hard HEAD 这个会撤销本地代码库的修改。

git push 目标分支:

git push 可以将local的分支push到远程不同的分支上(non-fast-forwording),但是最好不要这么做。

合并本地分支:

git merge  和 git rebase, 这两个的动作都可以合并,但最终得到的分支线路会不太一样。

最简单的类似svn的工作流程:

git workflow

有用的参考:

  • http://progit.org/book/zh/
  • http://book.git-scm.com/index.html
  • http://schacon.github.com/git/everyday.html
Tagged with:  

关于C/C++的标准

On 九月 18, 2011, in 技术记录, by pensz

没有什么语言能够像C/C++这么NB了吧,这么多平台,这么多家大公司支持,拥有N多编译器,开发出来的产品大到操作系统,小到网页,C/C++无所不在;正是因为如此,弄清楚相关标准尤为重要,切不能道听途说。

这两个语言标准的情况如下:

C的标准是 ISO/IEC 9899:1999(也就是常说的C99)。

而C++较为稳定的标准是 ISO/IEC 14882:2003(C++03) ,wiki和blog上早在8月份就说ISO/IEC 14882:2011 (C++11或者C++0x) 已经在ISO通过了,而后在C++标准委员会的网站上也得到了证实(News 2011-09-11: The new C++ standard – C++11 – is published!)。

制定标准的是ISO/IEC C/C++标准委员会制定,要找标准,自然去找ISO(“黑心”的ISO组织,这两个标准都要卖钱的)。

关于C的标准可以参考以下pdf http://www.open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf

而至于C++嘛,要自己根据标准名(ISO/IEC 14882:2003)去搜索一下咯。

 

参考资料:

Tagged with:  

快速排序

On 九月 12, 2011, in 技术记录, 数据结构和算法, by pensz

快速排序是分治法的思想,先设定一个标志,保证左边的数据不大于该标志,右边的数据都不小于该标志。然后分别对左右区域使用同样的处理方法,最终得到的序列即为有序序列。

下面是 c++ 的快速排序。

#include <iostream>
using namespace std;

/**
 * 调整数据,使得在一个位置左边的数据均小于 pivotkey, 右边的数据均大于 pivotkey
 */
int Partition(int *p, int low, int high) {
 int pivotkey = p[low];
 while (low < high) {
 while (low < high && p[high] > pivotkey) --high;
 p[low] = p[high];

 while (low < high && p[low] <= pivotkey) ++low;
 p[high] = p[low];
 }

 p[low] = pivotkey;

 return low;
}

/**
 * 快速排序
 */
void QuickSort(int *p, int begin,  int end) {
 if (begin < end) {
 int pivot;

 pivot = Partition(p, begin, end); // 进行一次分区
 QuickSort(p, begin, pivot-1); // 对左边的进行快速排序
 QuickSort(p, pivot+1, end); // 对右边进行快速排序
 }
}

int main() {
 int i, length, *p;
 cin >> length;
 p = (int *) malloc (length * sizeof(int));
 for (i=0; i<length; ++i) {
 cin >> p[i];
 }

 cout << "original" << endl;
 for (i=0; i<length; ++i) {
 cout << p[i] << endl;
 }    

 QuickSort(p, 0, length-1);

 cout << "sorted" << endl;
 for (i=0; i<length; ++i) {
 cout << p[i] << endl;
 }

 return 0;
}
Tagged with:  

堆排序

On 九月 12, 2011, in 技术记录, 数据结构和算法, by pensz

堆排序的是经典的排序方法,而堆的存储也非常的巧妙,用n个数据只需要n个结点存储,即采用长度为n+1(+1是为了下标处理的方便)的数组即可。

下面是php的实现。


// 示例数据
$data_input = array(
    null, 34, 10, 23, 58, 20, 49, 11,
);

$data_input = array(
    null, 1, 2, 3, 4, 5, 6, 7,
);

$data_input = array(
    null, 7, 6, 6, 4, 3, 2, 1, 9, 8,
);

// 排序前
var_dump($data_input);

// 堆排序,建大顶堆用来达到从小到大排序的目的
heap_sort($data_input);

// 排序后
var_dump($data_input);

/**
 * 堆排序
 */
function heap_sort(&$heap) {
    $total = count($heap) - 1; // 需要减1,原因是最大下标为 count - 1
    $half = intval($total / 2);

    // 初始化大顶堆
    for ($i=$half; $i>0; $i--) {
        heap_adjust($heap, $i, $total);
    }

    // 取出堆顶,放入最后,然后不断调整保证新的结构为堆
    for ($i = $total; $i > 1; $i--) {
        $temp = $heap[1];
        $heap[1] = $heap[$i];
        $heap[$i] = $temp;
        heap_adjust($heap, 1, $i-1);
    }
}

/**
 * 调整为大顶堆
 */
function heap_adjust(&$heap, $begin, $end) {
    $top_value = $heap[$begin];
    for ($i=2*$begin; $i<=$end; $i*=2) {
        if ($i < $end && $heap[$i] < $heap[$i+1]) $i++; // 右边的结点更加大,选择右边的结点和他们的父结点比较
        if ($top_value >= $heap[$i]) break; //找到了合适的位置,即 topvalue 大于左右的孩子, 为 $i 的父结点很合适
        $heap[$begin] = $heap[$i]; $begin = $i; // 否则,父结点的值为最大值,将$beign处的值设置为$i 结点上的数值,从$i接着调整堆
    }
    $heap[$begin] = $top_value; // 最后的位置保存初始时在堆顶的数据
}
Tagged with:  

败者树

On 九月 10, 2011, in 技术记录, 数据结构和算法, by pensz

很多时候看起来很简单,但是最好自己写一写,这样理解才会更加深刻一些。下面是今天练手写的败者树php实现。


// 测试数据
$data_input = array(
    array(2, 5, 10, 14, 20, 21, 23, 25, 30),
    array(1, 6, 9,  13, 17),
    array(3, 8, 12, 16, 19),
    array(4, 7, 11, 15, 18),
);

// 调用代码示例
k_merge($data_input);
find_x($data_input, 10);

global $b, $k; // $b 为败者树上的叶子结点值, $k为归并的路数量
define('MINVALUE', -65535); // 定义最小值
define('MAXVALUE', 65536); // 定义最大值

/**
 * k 路归并排序
 */
function k_merge($data_input) {
    global $b, $k;
    $k = count($data_input);

    for ($i = 0; $i< $k; $i++) {
        $b[$i] = array_shift($data_input[$i]);
    }

    $loser_tree = array();
    create_loser_tree($loser_tree);

    while ($b[$loser_tree[0]] !== MAXVALUE){
        $key = $loser_tree[0];
        $value = $b[$key];
        print "\n " . $value . " from $key" ;
        $b[$key] = array_shift($data_input[$key]);
        $b[$key] = $b[$key] === null ? MAXVALUE : $b[$key];
        adjust_loser_tree($loser_tree, $key);
    }
}

/**
 * 从 k 段有序序列中找到 第 x 小的数据
 */
function find_x($data_input, $x) {
    global $b, $k;
    $k = count($data_input);

    for ($i = 0; $i< $k; $i++) {
        $b[$i] = array_shift($data_input[$i]);
    }

    $loser_tree = array();
    create_loser_tree($loser_tree);

    for ($x_i = 1; $x_i <= $x - 1; $x_i++) {
        $key = $loser_tree[0];
        $value = $b[$key];
        // print "\n -- $key " . $value ;
        $b[$key] = array_shift($data_input[$key]);
        $b[$key] = $b[$key] === null ? MAXVALUE : $b[$key];
        adjust_loser_tree($loser_tree, $key);
    }

    $key = $loser_tree[0];
    $value = $b[$key];
    print "\n" . $value . "\n";
}

/**
 * 创建败者树
 */
function create_loser_tree(&$loser_tree) {
    global $b, $k;
    $b[$k] = MINVALUE; //下面初始化调整败者树会用到

    for ($i = 0; $i<$k; $i++) {
        $loser_tree[$i] = $k;
    }

    for ($i = $k - 1; $i >=0; $i--) {
        adjust_loser_tree($loser_tree, $i);
        // var_dump(" adjusted $i", $loser_tree);
    }
}

/**
 * 重新调整败者树
 */
function adjust_loser_tree(&$loser_tree, $s) {
    global $b, $k;
    $t = intval(($s + $k) / 2);

    while ($t > 0) {
        if ($b[$s] > $b[$loser_tree[$t]]) {
            $temp = $s;
            $s = $loser_tree[$t];
            $loser_tree[$t] = $temp;
        }
        $t = intval($t / 2);
    }

    $loser_tree[0] = $s;
}
Tagged with:  

php没有原生unicode支持,若没有mb(Multibyte String) 扩展,需要自己写截取中文字符串的代码。保证无乱码的关键在于保证截取的字节数正确,而这个参考编码规则即可。

如 utf8的编码规则:

Char. number range | UTF-8 octet sequence
(hexadecimal) | (binary)
--------------------+---------------------------------------------
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
110xxxxx 意味着 >= 2^7 + 2^6 即 ASCLL值 >= 192 时为两个字节
1110xxxx 意味着 >= 2^7 + 2^6 + 2 ^ 5 即 ASCLL值 >= 224 时为三个字节,以此类推。

按上面的编码规则,可以先取一个字节,通过ASCLL值来判断应该截取字节的字节数。算法如下:

初始化相关数据
while(已经截取的长度 < 要截取的长度) {
临时字符 = 取当前位置后面的1个字节
根据临时字符的ASCLL值判断本次截取的字节长度
最终的字符串 += 从当前位置截取指定长度的字节
当前位置 += 本次截取的字节长度
已经截取的长度 += 本次截取的字节长度
}

返回 最终的字符串

于是有了下面这段经典的代码:

function SubUtf8String($String,$Length) {
    $pos = 0;
    $lenCutted = 0;
    $stringCutted = "";
    $strlen = strlen($String);
    $Length = min($strlen, $Length);

    while ($lenCutted > $Length){
        $StringTMP = substr($String,$pos,1);

        $ascllvalue = ord($StringTMP);

        if ( $ascllvalue >= 224 ){
            $StringTMP = substr($String,$pos,3);
            $pos = $pos + 3;
            $lenCutted = $lenCutted + 3;
        } elseif ( $ascllvalue >= 192 ){
            $StringTMP = substr($String,$pos,2);
            $pos = $pos + 2;
            $lenCutted = $lenCutted + 2;
        } else {
            $pos = $pos + 1;
            $lenCutted = $lenCutted + 1;
        }
        $stringCutted .= $StringTMP;
    }

    if ($stringCutted){
        $stringCutted .= "...";
    }
    return $stringCutted;
}

gbk编码规则:
00-7F 单字节情形
81-FE 40-FE 双字节情形
gb 18030的扩展部分
81-FE 30-39 81-FE 30-39 四字节情形
0×81308130到0xFE39FE39。四字节字符的第一个字节的编码为0×81至0xFE;第二个字节的编码范围为0×30至0×39;第三个字节编码范围为0×81至0xFE;第四个字节编码范围为0×30至0×39

根据上述规则,写出截取gbk编码的函数应该较为简单了。

 

参考资料:

 

Tagged with: