关于C/C++的标准

没有什么语言能够像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)去搜索一下咯。

 

参考资料:

Share "关于C/C++的标准"

Share on: FacebookTwitter

快速排序

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

下面是 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;
}

Share "快速排序"

Share on: FacebookTwitter

堆排序

堆排序的是经典的排序方法,而堆的存储也非常的巧妙,用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; // 最后的位置保存初始时在堆顶的数据
}

Share "堆排序"

Share on: FacebookTwitter

败者树

很多时候看起来很简单,但是最好自己写一写,这样理解才会更加深刻一些。下面是今天练手写的败者树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;
}

Share "败者树"

Share on: FacebookTwitter

关于php中的中文字符截取

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 四字节情形
0x81308130到0xFE39FE39。四字节字符的第一个字节的编码为0x81至0xFE;第二个字节的编码范围为0x30至0x39;第三个字节编码范围为0x81至0xFE;第四个字节编码范围为0x30至0x39

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

 

参考资料:

 

Share "关于php中的中文字符截取"

Share on: FacebookTwitter

mac中的top命令

我相信很多开发人员选择mac除了它有很酷的界面外,它还是unix系统,在系统内置了很多unix的程序。

top就是很常用的一个程序,使用top的原因有以下:

  1. 虽然mac中有活动监视器,但top命令来的快
  2. gui程序不一定任何时刻都能正常运行,我亲身经历过强制退出没有效果,但可以在命令行 kill -9 <pid>(当然qq视频那个现象就无语了,直接将整个屏幕占满,任何操作都无效,只能眼睁睁的看着鼠标可以移动,但干不了任何事情)

之前一直依着linux的习惯在top运行时按M(按使用内存排序)、P(按CPU占用率排序)以及h(帮助),但在mac下却没有效果。我想可能mac下的top不支持这些吧,每次用完就不管了,也懒的google和man,今天忽然想到了在top运行时按?键,结果真出现了帮助菜单。

o<key>         Set primary sort key to <key>: [+-]{command|cpu|pid|prt|reg|rprvt|rshrd|rsize|th|time|uid|username|vprvt|vsize}.

按CPU排序是ocpu,按内存排序是ovsize。

人是懒惰的,是有惯性的。

Share "mac中的top命令"

Share on: FacebookTwitter

别了,摩托罗拉

惊闻摩托罗拉移动被google收购,虽是情理之中,但事实真的发生后还是让我吃了一惊。

摩托罗拉是无线电话的鼻祖,早在二战时期,美国大兵就使用moto的无线通讯设备,moto的大哥大,bp机更是一个时代的标志。

在数字通讯到来的时候,moto的行动迟缓,结果败给了诺基亚等新兴的通讯公司(当然,诺基亚的行动迟缓又使他目前在智能机市场处于劣势)。

moto还制造、生产芯片,mac当年的芯片就是摩托罗拉的,因为摩托罗拉当时cpu的性能是超过intel的,但他也没有抓住这一次机会,如果当年在芯片上面能够奋力一搏,也不会有今天的intel和AMD的存在了,我们用的电脑也许更快,更省电。

 

历史没有如果,时光永远不会倒流。同类的电话发明者美国电话电报公司陨落了,如今轮到无线通讯的摩托罗拉败走麦城。

如此看来,还真是很佩服ibm这样的公司,能够跟随历史的潮流,百年仍然昌盛。

 

推荐阅读《浪潮之巅》,可以帮自己了解很多过去科技界的辉煌和衰落的过程,从中提高自己的判断力。

附:浪潮之巅在线阅读

第一章 帝国的余辉(AT&T)

  1. 百年帝国
  2. 几度繁荣
  3. 利令智昏
  4. 外来冲击

第二章 蓝色巨人(IBM)

  1. 赶上机械革命的最后一次浪潮
  2. 领导电子技术革命的浪潮
  3. 错过全球信息化的大潮
  4. 他也是做(芯)片的
  5. 保守的创新者
  6. 内部的优胜劣汰

第三章 “水果”公司的复兴(乔布斯和苹果公司)

  1. 传奇小子
  2. 迷失方向
  3. 再创辉煌
  4. 大难不死

第四章 计算机工业的生态链

  1. 摩尔定理(Moore’s Law)
  2. 安迪-比尔定理(Andy and Bill’s Law)
  3. 反摩尔定理 (Reverse Moore’s Law)

第五章 奔腾的芯(英特尔——Intel)

  1. 时势造英雄
  2. 英特尔摩托罗拉之战
  3. 指令集之争
  4. 英特尔和 AMD 的关系
  5. 天步艰难

第六章 互联网的金门大桥(思科)

  1. 好风凭借力
  2. 好风凭借力(续)
  3. 持续发展的绝招
  4. 竞争者

第七章 硅谷的见证人(惠普公司)

  1. 昔日硅谷之星
  2. 争议的生死抉择
  3. 最有争议的CEO
  4. 亚洲制造的冲击
  5. 峰回路转

第八章 没落的贵族(摩托罗拉)

  1. 二战的品牌
  2. 黄金时代
  3. 基因决定定理
  4. 铱星计划
  5. 全线溃败
  6. 回天乏力

第九章 硅谷的另一面

  1. 成王败寇
  2. 嗜血的地方
  3. 机会均等
  4. 硅含量不断降低
  5. 亘古而常青

第十章 短暂的春秋——与机会失之交臂的公司

  1. 昔日的辉煌(Sun Microsystems)
  2. 错失良机(Sun Microsystems)
  3. 历史的回放(Sun Microsystems)
  4. 局域网的微软(Novell)
  5. 网景公司(Netscape)
  6. Real Networks

第十一章 幕后的英雄——风险投资(Venture Capital)

  1. 风投的起源
  2. 风投的结构
  3. 风投的过程
  4. 投资的决策和公司的估价
  5. 风投的角色
  6. 著名的风投公司

第十二章 信息产业的规律性

  1. 70-20-10律
  2. 诺威格定理
  3. 基因决定定理

第十三章 高科技公司的摇篮 — 斯坦福大学

  1. 充满传奇的大学
  2. 硅谷的支柱
  3. 纽曼+洪堡的教育模式
  4. 创业的孵化器

第十四章 科技公司的吹鼓手:投资银行

  1. 前言 有幸见证历史
  2. 华尔街和美国的金融体系
  3. 著名的投资公司
  4. 科技公司的上市过程
  5. 成也萧何、败也萧何
  6. 华尔街与微软、雅虎和 Google 的三国演义

第十五章 成功的转基因

  1. 从木工厂到手机之王(诺基亚 Nokia)
  2. 道琼斯的常青树(3M)
  3. 世界最大的联合体(GE)
  4. 百年扩张,从有线电到无线电
  5. 从实体经济到金融
  6. 领袖的重要性

浪潮之巅第十六章

  1. 印钞机——最佳的商业模式(一)
  2. 印钞机——最佳的商业模式(二)
  3. 印钞机——最佳的商业模式(三)
  4. 印钞机——最佳的商业模式(四)

 

 

Share "别了,摩托罗拉"

Share on: FacebookTwitter

java中HashMap和HashTable的比较

1 HashMap 和 HashTable 都是通过链接法解决碰撞

通过链接法解决碰撞,点击放大图片

链接解决碰撞,摘自算法导论第二版135页


2 HashMap 的hash函数更加牛一些,另外支持null的key(这其实是一个支不支持的问题)

3 javadoc中写道:除了不同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。从具体代码来看,HashMap代码的方法前面没有加synchronized,而HashTable的方法前面加了synchronized;另外,HashTable不支持null是“全面”的,key 和 value都不能为null

4 HashMap计算key对应的bucket(桶)所使用取模算法中,HashMap是二进制的 & (table.length - 1),而HashTable 是 % table.length,显然HashMap更加牛些

5 HashMap的查找,插入性能更加好,因为它中间会对key的hashCode再做一次hash,使其尽量均匀分布,而HashTable基本依赖于key的hashCode()

选择的原则:尽量使用HashMap,如果有同步方面的需求,自己可以在外面做控制。

Share "java中HashMap和HashTable的比较"

Share on: FacebookTwitter

悲惨的mac输入法更新经历

江湖盛传,最近mac输入法风生水起,各家已经做的非常nb了。

我本不想再折腾这些软件了,实在没有意思;再说了,当年google出的mac输入法beta版害死一大堆人的情景历历在目(注销后登录无法输入密码),但考虑目前使用的sunpinyin和FIT在词汇量方面太少,经常影响打字的速度,故想试试新的输入法;怎么说也有两大公司推出了mac下的输入法,也都推出了正式版,应该比较稳定可靠吧。

一开始就卸载了FIT,因为我用它不是很爽。再比较一下两大输入法公司的产品:qq mac输入法和搜狗mac输入法

通过网站对比发现,qq的应该更加好点,说明详细,更新频繁,应该有保证;而搜狗的mac输入法更新不是很及时,另外说明文档没有qq那边多。这么想想,应该qq的输入法比较有保证,下载下来安装。

安装一切顺利,只是最后安装uninstaller时失败,我想想不是什么大事,就在自定义安装时,去掉了uninstaller。安装后,切换到qq拼音,系统巨卡无比,我想,初始化可能会慢点,结果后面还是巨卡,输入法设置没有出现,无法正常输入。打开活动监视器看,发现ReportCrash飘过,也就是说程序出现异常了。难道需要重启?重启了看看,结果现象依旧。我无语了,准备卸掉,结果卸载程序无法运行(应该是只能10.6以上的版本运行,从程序的异常log中也发现了一句 unknown required load command 0x80000022 ),最后只好通过命令行卸载了。

那接着只能看看搜狗的怎么样了,下载下来,兴冲冲的安装,结果提示我该输入法只支持10.6以上的系统。我还能说什么呢?唯有放弃。

虽然是两家大公司,但好像都没有打算支持10.5 leopard系统的意思,在网站上面也没有看到说明仅支持10.6以上的系统,不得不说这是个很大的遗憾。

对了,还有sunpinyin可以更新看看,抱着一丝希望,更新至2.0.3版本,结果还是挂了,现象和qq拼音一样。

sunpinyin crash

 

正如你上面看到的那样,配置面板一直无法载入;而活动监视器里面也有ReportCrash的进程。虽然网站上写的支持10.5/6,但我的确无法使用,有可能是我安装不对,也有可能没在10.5(leopard) 上面好好测试过。

再找找QIM看看了,QIM之前是mac下最好的输入法,最近听说免费了。找了很久,有新闻,有链接,但无法下载,我很无奈和绝望。

难道只能安装FIT了吗?对于这个输入法,我今天一开始就卸了它,为什么?因为我对它很有成见,之前不好好做核心功能,反而在状态栏上面多增加一个图标,被大家狠狠一顿批;还做什么截屏功能,要知道,截屏是mac自带的功能(最简单的是按 shift+cmd+4);另外给我的感觉是反应较慢,耗内存较多。

但现在是没有选择了,只好硬着头皮去下载FIT了,最后通过下载FIT,奇迹般的找到了一个网站,可以下载QIM。这个网站(http://mac.brothersoft.com/)很赞,有很多mac下的软件,而且可以直接wget下(为什么直接wget下,你懂的),如果你是10.5的系统,可以用这个链接下载(http://macfiles.brothersoft.com/business/word_processing/QIM_Sogou_2_0_0_Leopard.dmg.zip)。

最后,终于用上了QIM,QIM的确不错,安装后不需要设置就能很方便的使用了,词汇量大,反应速度也很快;这篇blog就是用QIM写的。

结论是:如果你是mac os 10.5的系统,我建议你使用QIM,其次是FIT2.2.1(2.3.0后无法使用,情况和sunpinyin一样,无法载入配置面板),再者是sunpinyin 2.0.2 (更新到2.0.3后无法使用了,不知道是个人特例还是普遍情况)。

非常感谢这么多个人开发了这么好的免费的软件供大家使用。

Share "悲惨的mac输入法更新经历"

Share on: FacebookTwitter

update使用group_contact

以下讨论针对mysql。

想要达到的目的:

UPDATE users AS u
LEFT JOIN orders AS o ON o.user_id = u.user_id
SET u.orders = GROUP_CONCAT(DISTINCT o.order_id)

上面的sql无法运行,即使加上GROUP BY也是不行的

UPDATE users AS u
LEFT JOIN orders AS o ON o.user_id = u.user_id
SET u.orders = GROUP_CONCAT(DISTINCT o.order_id)
GROUP BY u.user_id

一种的不用临时表的解决方法为:
UPDATE users AS u
SET u.orders = (
SELECT GROUP_CONCAT(DISTINCT o.order_id)
FROM orders o
WHERE o.user_id = u.user_id
)

Share "update使用group_contact"

Share on: FacebookTwitter

blog built using the cayman-theme by Jason Long. LICENSE