Oct
13
Translated to ENGLISH VERSION
源于这两篇文章:
http://blog.csdn.net/ggggiqnypgjg/article/details/6645824
http://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-palindrome-sub-string/
这个算法看了三天,终于理解了,在这里记录一下自己的思路,免得以后忘了又要想很久- -.
首先用一个非常巧妙的方式,将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度:在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#, aba变成 #a#b#a#。 为了进一步减少编码的复杂度,可以在字符串的开始加入另一个特殊字符,这样就不用特殊处理越界问题,比如$#a#b#a#(注意,下面的代码是用C语言写就,由于C语言规范还要求字符串末尾有一个'\0'所以正好OK,但其他语言可能会导致越界)。
下面以字符串12212321为例,经过上一步,变成了 S[] = "$#1#2#2#1#2#3#2#1#";
然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度(包括S[i],也就是把该回文串“对折”以后的长度),比如S和P的对应关系:
那么怎么计算P[i]呢?该算法增加两个辅助变量(其实一个就够了,两个更清晰)id和mx,其中 id 为已知的 {右边界最大} 的回文子串的中心,mx则为id+P[id],也就是这个子串的右边界。
然后可以得到一个非常神奇的结论,这个算法的关键点就在这里了:如果mx > i,那么P[i] >= MIN(P[2 * id - i], mx - i)。就是这个串卡了我非常久。实际上如果把它写得复杂一点,理解起来会简单很多:
当然光看代码还是不够清晰,还是借助图来理解比较容易。
当 mx - i > P[j] 的时候,以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中,由于 i 和 j 对称,以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中,所以必有 P[i] = P[j],见下图。
当 P[j] >= mx - i 的时候,以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中,但是基于对称性可知,下图中两个绿框所包围的部分是相同的,也就是说以S[i]为中心的回文子串,其向右至少会扩张到mx的位置,也就是说 P[i] >= mx - i。至于mx之后的部分是否对称,就只能老老实实去匹配了。
对于 mx <= i 的情况,无法对 P[i]做更多的假设,只能P[i] = 1,然后再去匹配了。
于是代码如下:
OVER.
#UPDATE@2013-08-21 14:27
@zhengyuee 同学指出,由于 P[id] = mx,所以 S[id-mx] != S[id+mx],那么当 P[j] > mx - i 的时候,可以肯定 P[i] = mx - i ,不需要再继续匹配了。不过在具体实现的时候即使不考虑这一点,也只是多一次匹配(必然会fail),但是却要多加一个分支,所以上面的代码就不改了。
源于这两篇文章:
http://blog.csdn.net/ggggiqnypgjg/article/details/6645824
http://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-palindrome-sub-string/
这个算法看了三天,终于理解了,在这里记录一下自己的思路,免得以后忘了又要想很久- -.
首先用一个非常巧妙的方式,将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度:在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#, aba变成 #a#b#a#。 为了进一步减少编码的复杂度,可以在字符串的开始加入另一个特殊字符,这样就不用特殊处理越界问题,比如$#a#b#a#(注意,下面的代码是用C语言写就,由于C语言规范还要求字符串末尾有一个'\0'所以正好OK,但其他语言可能会导致越界)。
下面以字符串12212321为例,经过上一步,变成了 S[] = "$#1#2#2#1#2#3#2#1#";
然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度(包括S[i],也就是把该回文串“对折”以后的长度),比如S和P的对应关系:
S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
(p.s. 可以看出,P[i]-1正好是原字符串中回文串的总长度)
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
(p.s. 可以看出,P[i]-1正好是原字符串中回文串的总长度)
那么怎么计算P[i]呢?该算法增加两个辅助变量(其实一个就够了,两个更清晰)id和mx,其中 id 为已知的 {右边界最大} 的回文子串的中心,mx则为id+P[id],也就是这个子串的右边界。
然后可以得到一个非常神奇的结论,这个算法的关键点就在这里了:如果mx > i,那么P[i] >= MIN(P[2 * id - i], mx - i)。就是这个串卡了我非常久。实际上如果把它写得复杂一点,理解起来会简单很多:
//记j = 2 * id - i,也就是说 j 是 i 关于 id 的对称点(j = id - (i - id))
if (mx - i > P[j])
P[i] = P[j];
else /* P[j] >= mx - i */
P[i] = mx - i; // P[i] >= mx - i,取最小值,之后再匹配更新。
if (mx - i > P[j])
P[i] = P[j];
else /* P[j] >= mx - i */
P[i] = mx - i; // P[i] >= mx - i,取最小值,之后再匹配更新。
当然光看代码还是不够清晰,还是借助图来理解比较容易。
当 mx - i > P[j] 的时候,以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中,由于 i 和 j 对称,以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中,所以必有 P[i] = P[j],见下图。
当 P[j] >= mx - i 的时候,以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中,但是基于对称性可知,下图中两个绿框所包围的部分是相同的,也就是说以S[i]为中心的回文子串,其向右至少会扩张到mx的位置,也就是说 P[i] >= mx - i。至于mx之后的部分是否对称,就只能老老实实去匹配了。
对于 mx <= i 的情况,无法对 P[i]做更多的假设,只能P[i] = 1,然后再去匹配了。
于是代码如下:
//输入,并处理得到字符串s
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++) {
p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
while (s[i + p[i]] == s[i - p[i]]) p[i]++;
if (i + p[i] > mx) {
mx = i + p[i];
id = i;
}
}
//找出p[i]中最大的
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++) {
p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
while (s[i + p[i]] == s[i - p[i]]) p[i]++;
if (i + p[i] > mx) {
mx = i + p[i];
id = i;
}
}
//找出p[i]中最大的
OVER.
#UPDATE@2013-08-21 14:27
@zhengyuee 同学指出,由于 P[id] = mx,所以 S[id-mx] != S[id+mx],那么当 P[j] > mx - i 的时候,可以肯定 P[i] = mx - i ,不需要再继续匹配了。不过在具体实现的时候即使不考虑这一点,也只是多一次匹配(必然会fail),但是却要多加一个分支,所以上面的代码就不改了。
Jul
22
#include <stdio.h>
int main()
{
int a, b;
scanf("%d%*[, ]%d", &a, &b);
printf("%d + %d = %d\n", a, b, a + b);
return 0;
}
int main()
{
int a, b;
scanf("%d%*[, ]%d", &a, &b);
printf("%d + %d = %d\n", a, b, a + b);
return 0;
}
<= 1 2
=> 1 + 2 = 3
<= 1,2
=> 1 + 2 = 3
<= 1 , 2
=> 1 + 2 = 3
Jun
20
=> How to call a php function in a php extension
详细的说明参见:
[php-5.2.17]
/Zend/zend_execute_API.c +623 & +636 call_user_function_ex
/ext/standard/basic_functions.c +5174 PHP_FUNCTION(call_user_func_array)
/ext/pcre/pcre.c +833 (in function "preg_do_repl_func")
http://man.chinaunix.net/develop/php/php_manual_zh/html/zend.calling-user-functions.html
http://www.phpfreaks.com/forums/index.php?topic=10272.0
详细的说明参见:
[php-5.2.17]
/Zend/zend_execute_API.c +623 & +636 call_user_function_ex
/ext/standard/basic_functions.c +5174 PHP_FUNCTION(call_user_func_array)
/ext/pcre/pcre.c +833 (in function "preg_do_repl_func")
http://man.chinaunix.net/develop/php/php_manual_zh/html/zend.calling-user-functions.html
http://www.phpfreaks.com/forums/index.php?topic=10272.0
PHP_FUNCTION (caller)
{
//call_user_function_ex
zval *function, *str, *arr;
zval **params[10];
MAKE_STD_ZVAL(function);
ZVAL_STRING(function, "var_dump", 1); //I wanna call var_dump
/* //pass a string as its param
MAKE_STD_ZVAL(str);
ZVAL_STRING(str, "Hello, world!", 1);
params[0] = &str;
*/
//pass an array as its param
MAKE_STD_ZVAL(arr);
array_init(arr);
add_assoc_string(arr, "name", "felix021", 1);
params[0] = &arr;
zval *ret;
if (call_user_function_ex(CG(function_table), NULL,
function, &ret, 2, params, 0, NULL TSRMLS_CC) != FAILURE)
{
*return_value = *ret;
zval_copy_ctor(return_value);
zval_ptr_dtor(&ret);
return;
}
else {
RETURN_FALSE;
}
}
{
//call_user_function_ex
zval *function, *str, *arr;
zval **params[10];
MAKE_STD_ZVAL(function);
ZVAL_STRING(function, "var_dump", 1); //I wanna call var_dump
/* //pass a string as its param
MAKE_STD_ZVAL(str);
ZVAL_STRING(str, "Hello, world!", 1);
params[0] = &str;
*/
//pass an array as its param
MAKE_STD_ZVAL(arr);
array_init(arr);
add_assoc_string(arr, "name", "felix021", 1);
params[0] = &arr;
zval *ret;
if (call_user_function_ex(CG(function_table), NULL,
function, &ret, 2, params, 0, NULL TSRMLS_CC) != FAILURE)
{
*return_value = *ret;
zval_copy_ctor(return_value);
zval_ptr_dtor(&ret);
return;
}
else {
RETURN_FALSE;
}
}
Jun
18
网上摘下来的代码,没什么好说的了(因为那一堆 mcrypt_* 函数太乱了,用就是了):
<?php
class DES
{
public static function pkcs5_pad ($text, $blocksize) {
$pad = $blocksize - (strlen($text) % $blocksize);
return $text . str_repeat(chr($pad), $pad);
}
public static function pkcs5_unpad($text) {
$pad = ord($text{strlen($text)-1});
if ($pad > strlen($text)) {
return false;
}
if (strspn($text, chr($pad), strlen($text) - $pad) != $pad) {
return false;
}
return substr($text, 0, -1 * $pad);
}
public static function encrypt($key, $data) {
$size = mcrypt_get_block_size('des', 'ecb');
$data = DES::pkcs5_pad($data, $size);
$td = mcrypt_module_open('des', '', 'ecb', '');
$iv = @mcrypt_create_iv(mcrypt_enc_get_iv_size($td), MCRYPT_RAND);
@mcrypt_generic_init($td, $key, $iv);
$data = mcrypt_generic($td, $data);
mcrypt_generic_deinit($td);
mcrypt_module_close($td);
return $data;
}
public static function decrypt($key, $data) {
$td = mcrypt_module_open('des','','ecb','');
$iv = @mcrypt_create_iv(mcrypt_enc_get_iv_size($td), MCRYPT_RAND);
$ks = mcrypt_enc_get_key_size($td);
@mcrypt_generic_init($td, $key, $iv);
$decrypted = mdecrypt_generic($td, $data);
mcrypt_generic_deinit($td);
mcrypt_module_close($td);
$result = DES::pkcs5_unpad($decrypted);
return $result;
}
}
/* test code
$in = "04fMaWegkH1/BL9CNYxgusFpYK8wdraBX06mPiRmxJP+uVm31GQvyw==";
$des = base64_decode($in);
echo DES::decrypt("12345678", $des);
echo "\n";
$in = "cea3e8e1659582206e0be32539729e9f";
$des = DES::encrypt("12345678", $in);
$out = base64_encode($des);
echo $out;
echo "\n";
// */
?>
class DES
{
public static function pkcs5_pad ($text, $blocksize) {
$pad = $blocksize - (strlen($text) % $blocksize);
return $text . str_repeat(chr($pad), $pad);
}
public static function pkcs5_unpad($text) {
$pad = ord($text{strlen($text)-1});
if ($pad > strlen($text)) {
return false;
}
if (strspn($text, chr($pad), strlen($text) - $pad) != $pad) {
return false;
}
return substr($text, 0, -1 * $pad);
}
public static function encrypt($key, $data) {
$size = mcrypt_get_block_size('des', 'ecb');
$data = DES::pkcs5_pad($data, $size);
$td = mcrypt_module_open('des', '', 'ecb', '');
$iv = @mcrypt_create_iv(mcrypt_enc_get_iv_size($td), MCRYPT_RAND);
@mcrypt_generic_init($td, $key, $iv);
$data = mcrypt_generic($td, $data);
mcrypt_generic_deinit($td);
mcrypt_module_close($td);
return $data;
}
public static function decrypt($key, $data) {
$td = mcrypt_module_open('des','','ecb','');
$iv = @mcrypt_create_iv(mcrypt_enc_get_iv_size($td), MCRYPT_RAND);
$ks = mcrypt_enc_get_key_size($td);
@mcrypt_generic_init($td, $key, $iv);
$decrypted = mdecrypt_generic($td, $data);
mcrypt_generic_deinit($td);
mcrypt_module_close($td);
$result = DES::pkcs5_unpad($decrypted);
return $result;
}
}
/* test code
$in = "04fMaWegkH1/BL9CNYxgusFpYK8wdraBX06mPiRmxJP+uVm31GQvyw==";
$des = base64_decode($in);
echo DES::decrypt("12345678", $des);
echo "\n";
$in = "cea3e8e1659582206e0be32539729e9f";
$des = DES::encrypt("12345678", $in);
$out = base64_encode($des);
echo $out;
echo "\n";
// */
?>
Jun
18
在"libc 4.6.27 and later, and glibc 2.1 and later"中,提供了 rpc/des_crypt.h这个头文件,其中有几个函数,比如:
这个函数可以用于DES的加密/解密。详情可以看 man des_crypt ,以下说 ecb_crypt() 函数几个比较坑爹的地方:
1. 虽然提供给DES的密钥(key)是8个字节,但是实际上只用到了其中的56个bit,另外8个bit是用于奇偶校验的(从用户处取得一个64位长的密码key ,去除64位密码中作为奇偶校验位的第8、16、24、32、40、48、56、64位,剩下的56位作为有效输入密钥)。所以需要调用 des_setparity(key) 来处理key。
2. 必须在data后面补上1~8个 "\x8",以将datalen补齐到8的倍数。对,是1~8个。假设要加密的data是32个字节,需要先补齐到40个字节。
3. 传给des_setparity()的key和给ecb_crypt的data会被直接改写。
以下是样例代码:
void des_setparity(char *key);
int ecb_crypt(char *key, char *data, unsigned datalen, unsigned mode);
int ecb_crypt(char *key, char *data, unsigned datalen, unsigned mode);
这个函数可以用于DES的加密/解密。详情可以看 man des_crypt ,以下说 ecb_crypt() 函数几个比较坑爹的地方:
1. 虽然提供给DES的密钥(key)是8个字节,但是实际上只用到了其中的56个bit,另外8个bit是用于奇偶校验的(从用户处取得一个64位长的密码key ,去除64位密码中作为奇偶校验位的第8、16、24、32、40、48、56、64位,剩下的56位作为有效输入密钥)。所以需要调用 des_setparity(key) 来处理key。
2. 必须在data后面补上1~8个 "\x8",以将datalen补齐到8的倍数。对,是1~8个。假设要加密的data是32个字节,需要先补齐到40个字节。
3. 传给des_setparity()的key和给ecb_crypt的data会被直接改写。
以下是样例代码:
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <rpc/des_crypt.h>
//注意:这里有个坑,需要保证 data 可以存放的字符串在后面补了\8 不会越界。否则结果是不确定的。
void des_encrypt(const char *key, char *data, int len)
{
char pkey[8];
strncpy(pkey, key, 8);
des_setparity(pkey);
do {
data[len++] = '\x8';
} while (len % 8 != 0);
ecb_crypt(pkey, data, len, DES_ENCRYPT);
}
void des_decrypt(const char *key, char *data, int len)
{
char pkey[8];
strncpy(pkey, key, 8);
des_setparity(pkey);
ecb_crypt(pkey, data, len, DES_DECRYPT);
}
int main(int argc, char *argv[])
{
/*
* char data[4096] = "cea3e8e1659582206e0be32539729e9f";
* des_encrypt("12345678", data, strlen(data));
* printf("%s\n", data);
* //should be "04fMaWegkH1/BL9CNYxgusFpYK8wdraBX06mPiRmxJP+uVm31GQvyw=="
*/
char data[4096];
int i = 0;
while (EOF != (data[i] = fgetc(stdin))) {
i++;
}
data[i] = '\0';
des_decrypt("12345678", data, strlen(data));
printf("%s\n", data);
/*
* echo -n 04fMaWegkH1/BL9CNYxgusFpYK8wdraBX06mPiRmxJP+uVm31GQvyw== | base64 -d | ./des
* should be "cea3e8e1659582206e0be32539729e9f"
*/
return 0;
}
#include <unistd.h>
#include <string.h>
#include <rpc/des_crypt.h>
//注意:这里有个坑,需要保证 data 可以存放的字符串在后面补了\8 不会越界。否则结果是不确定的。
void des_encrypt(const char *key, char *data, int len)
{
char pkey[8];
strncpy(pkey, key, 8);
des_setparity(pkey);
do {
data[len++] = '\x8';
} while (len % 8 != 0);
ecb_crypt(pkey, data, len, DES_ENCRYPT);
}
void des_decrypt(const char *key, char *data, int len)
{
char pkey[8];
strncpy(pkey, key, 8);
des_setparity(pkey);
ecb_crypt(pkey, data, len, DES_DECRYPT);
}
int main(int argc, char *argv[])
{
/*
* char data[4096] = "cea3e8e1659582206e0be32539729e9f";
* des_encrypt("12345678", data, strlen(data));
* printf("%s\n", data);
* //should be "04fMaWegkH1/BL9CNYxgusFpYK8wdraBX06mPiRmxJP+uVm31GQvyw=="
*/
char data[4096];
int i = 0;
while (EOF != (data[i] = fgetc(stdin))) {
i++;
}
data[i] = '\0';
des_decrypt("12345678", data, strlen(data));
printf("%s\n", data);
/*
* echo -n 04fMaWegkH1/BL9CNYxgusFpYK8wdraBX06mPiRmxJP+uVm31GQvyw== | base64 -d | ./des
* should be "cea3e8e1659582206e0be32539729e9f"
*/
return 0;
}
May
27
前些天写的程序在上线的时候出现BUG了,错误提示就是call_user_func_array无法调用指定的函数。
代码大概是这样的
追了一下发现是PHP版本的问题,开发环境使用的是php 5.2.17,而线上环境是旧版本的5.1.6。5.1版的php的call_user_func / call_user_func_array函数没法调用类的静态函数,所以出现了这个问题。
没有很好的解决方法,大致就是
1. 升级PHP(最后我们是这么做的)
2. 使用字符串拼出一段php代码,然后用eval来执行。很挫,但是也能用。
代码大概是这样的
class foo {
public static function bar($arg1, $arg2) {
//do sth.
}
}
call_user_func_array("foo:bar", array(1, 2));
public static function bar($arg1, $arg2) {
//do sth.
}
}
call_user_func_array("foo:bar", array(1, 2));
追了一下发现是PHP版本的问题,开发环境使用的是php 5.2.17,而线上环境是旧版本的5.1.6。5.1版的php的call_user_func / call_user_func_array函数没法调用类的静态函数,所以出现了这个问题。
没有很好的解决方法,大致就是
1. 升级PHP(最后我们是这么做的)
2. 使用字符串拼出一段php代码,然后用eval来执行。很挫,但是也能用。
Mar
29
本文转自 酷壳(Coolshell.cn) http://coolshell.cn/articles/4102.html 酷壳这个网站非常不错,推荐大家订阅。
-----------------
有人在酷壳的留言版上询问下面的问题
keep_walker :
今天晚上我看到这篇文章。
http://programmers.stackexchange.com/questions/62502/small-c-projects
我也遇到了和提问的老外一样的问题。。能给像遇到这样烦恼的程序员一点建议嘛?谢谢!
我相信,这可能是很多朋友的问题,我以前也有这样的感觉,编程编到一定的时候,发现能力到了瓶颈,既不深,也不扎实,半吊子。比如:你长期地使用Java和.NET ,这些有虚拟机的语言对于开发便利是便利,但是对于程序员来说可能并不太好,原因有两个:
1. 虚拟机屏蔽了操作系统的系统调用,以及很多底层机制。
2. 大量的封装好的类库也屏蔽了很多实现细节。
一段时间后,你会发现你知其然,不知所以然。。我以前在CSDN上写过一篇《Java NIO类库Selector机制解析(上,下,续)》,在那篇文章中我说提到过(有讥讽的语气)Java的程序员不懂底层实现,所以很难把技术学得更扎实。此时,一部分程序员会不自然地想学学底层的技术,很自然的,C语言就被提了上来。
下面是我给这位朋友的一些建议:
· 鼓励并为你叫好。我鼓励你想要去学C语言的想法和精神,很多人都觉得C语言好学,其实并不然,现在的这个社会更多地去关注那些时髦的技术,而忽略了这个流行了40+年的C语言。一门技术如果能够流行40多年,这才是你需要去关注和学习的技术,而不是那些刚出来的技术(过度炒作的技术,Windows编程史)。这才是踏踏实实的精神。
· 不要找借口。这一条路走下来并不容易,不要给自己找借口。我最不喜欢听到的就是“很忙,没有时间”这样的借口。我以前在银行做项目,早9点到晚10点,周一到周六,我一样可以每天抽1个小时来看书和专研,一年下来也能精读5、6本书。我现在的工作项目和招聘任务很紧张,刚生的小孩只有自己和老婆两人带,还需要准备讲课,但是我还是能够找到时间看文章写文章维护酷壳。所以,我可以告诉你,“时间就像乳沟,只要你肯挤,就一定会有”。
· 学好C语言和系统编程。我认为,学好编程有四个方面:语言、算法和数据结构、系统调用和设计。
·· 语言。我可以告诉你C语言有两大主题你要好好学,一个是内存管理,一个是指针!这个世界上90%以上的C/C++出的严重性错误全是和这两个有关。不要看谭浩强的那本书,那本是本烂书。推荐这本书给你《C程序设计语言(第2版·新版)》
·· 算法和数据结构。我认为,用C语言实现算法和数据结构莫过于最爽的事情。推荐你看这本书——算法:C语言实现(第1~4部分)基础知识、数据结构、排序及搜索(原书第3版)
·· 系统编程。Windows下推荐两本书——《Windows 程序设计 》和《Windows核心编程》,Unix/Linux下推荐两本书——《Unix高级环境编程》和《Unix网络编程卷1,套接字》《Unix网络编程卷2,进程间通信》尤其是《Unix网络编程》这本书,一通百通,无论Windows还是Unix/Linux,都是一样的。
·· 系统设计。关于设计方面,我全力推荐《Unix编程艺术》,看完以后,你就明白什么是真正的编程文化了。然后,当你看到Windows的Fans的某些言论时,你就知道什么叫一笑了之了。
如果你能在2-3年内精读完这些书,并全部融会贯通,那么你就明白什么是一览众山小的感觉了!我足足花了5年时间才算是真正全部读完这些书的。最后,祝你好运!努力!
-----------------
有人在酷壳的留言版上询问下面的问题
keep_walker :
今天晚上我看到这篇文章。
http://programmers.stackexchange.com/questions/62502/small-c-projects
我也遇到了和提问的老外一样的问题。。能给像遇到这样烦恼的程序员一点建议嘛?谢谢!
我相信,这可能是很多朋友的问题,我以前也有这样的感觉,编程编到一定的时候,发现能力到了瓶颈,既不深,也不扎实,半吊子。比如:你长期地使用Java和.NET ,这些有虚拟机的语言对于开发便利是便利,但是对于程序员来说可能并不太好,原因有两个:
1. 虚拟机屏蔽了操作系统的系统调用,以及很多底层机制。
2. 大量的封装好的类库也屏蔽了很多实现细节。
一段时间后,你会发现你知其然,不知所以然。。我以前在CSDN上写过一篇《Java NIO类库Selector机制解析(上,下,续)》,在那篇文章中我说提到过(有讥讽的语气)Java的程序员不懂底层实现,所以很难把技术学得更扎实。此时,一部分程序员会不自然地想学学底层的技术,很自然的,C语言就被提了上来。
下面是我给这位朋友的一些建议:
· 鼓励并为你叫好。我鼓励你想要去学C语言的想法和精神,很多人都觉得C语言好学,其实并不然,现在的这个社会更多地去关注那些时髦的技术,而忽略了这个流行了40+年的C语言。一门技术如果能够流行40多年,这才是你需要去关注和学习的技术,而不是那些刚出来的技术(过度炒作的技术,Windows编程史)。这才是踏踏实实的精神。
· 不要找借口。这一条路走下来并不容易,不要给自己找借口。我最不喜欢听到的就是“很忙,没有时间”这样的借口。我以前在银行做项目,早9点到晚10点,周一到周六,我一样可以每天抽1个小时来看书和专研,一年下来也能精读5、6本书。我现在的工作项目和招聘任务很紧张,刚生的小孩只有自己和老婆两人带,还需要准备讲课,但是我还是能够找到时间看文章写文章维护酷壳。所以,我可以告诉你,“时间就像乳沟,只要你肯挤,就一定会有”。
· 学好C语言和系统编程。我认为,学好编程有四个方面:语言、算法和数据结构、系统调用和设计。
·· 语言。我可以告诉你C语言有两大主题你要好好学,一个是内存管理,一个是指针!这个世界上90%以上的C/C++出的严重性错误全是和这两个有关。不要看谭浩强的那本书,那本是本烂书。推荐这本书给你《C程序设计语言(第2版·新版)》
·· 算法和数据结构。我认为,用C语言实现算法和数据结构莫过于最爽的事情。推荐你看这本书——算法:C语言实现(第1~4部分)基础知识、数据结构、排序及搜索(原书第3版)
·· 系统编程。Windows下推荐两本书——《Windows 程序设计 》和《Windows核心编程》,Unix/Linux下推荐两本书——《Unix高级环境编程》和《Unix网络编程卷1,套接字》《Unix网络编程卷2,进程间通信》尤其是《Unix网络编程》这本书,一通百通,无论Windows还是Unix/Linux,都是一样的。
·· 系统设计。关于设计方面,我全力推荐《Unix编程艺术》,看完以后,你就明白什么是真正的编程文化了。然后,当你看到Windows的Fans的某些言论时,你就知道什么叫一笑了之了。
如果你能在2-3年内精读完这些书,并全部融会贯通,那么你就明白什么是一览众山小的感觉了!我足足花了5年时间才算是真正全部读完这些书的。最后,祝你好运!努力!
Jan
12
今天跟Sandy讨论的时候发现的这两个trick。其中第一个trick以前曾经知道,不过太久没用,忘了;第二个trick一直就没发现。
1. make_heap、push_heap、pop_heap默认与其他STL算法一样使用 operator < 进行比较,但是建立的是大根堆,也就是说,pop_heap取出的是heap中的最大值。
2. 在调用sort_heap(begin, end, comparor) 之前,需要保证 [begin, end) 之间是使用同一个 comparor 建立的heap。默认的排序也是使用 operator < ,效果与调用sort是一致的(即默认从小到大排序):【不要以为】make_heap默认是大根堆,sort_heap就会从大到小排序。可参见源码:
-----
以下是sandy整理的
1. make_heap、push_heap、pop_heap默认与其他STL算法一样使用 operator < 进行比较,但是建立的是大根堆,也就是说,pop_heap取出的是heap中的最大值。
2. 在调用sort_heap(begin, end, comparor) 之前,需要保证 [begin, end) 之间是使用同一个 comparor 建立的heap。默认的排序也是使用 operator < ,效果与调用sort是一致的(即默认从小到大排序):【不要以为】make_heap默认是大根堆,sort_heap就会从大到小排序。可参见源码:
sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_heap_pred(__first, __last, __comp);
while (__last - __first > 1)
std::pop_heap(__first, __last--, __comp);
}
_Compare __comp)
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_heap_pred(__first, __last, __comp);
while (__last - __first > 1)
std::pop_heap(__first, __last--, __comp);
}
-----
以下是sandy整理的
引用
1、heap算法虽然默认都使用的是operator <,但是建立的却是大根堆
2、sort_heap,是对已经成为heap的序列进行sort。本质上就是不断循环pop_heap而已。
3、sort_heap默认使用的也是operator <,排序出来的结果是从小到大的序列。
4、sort_heap算法使用的判别式,必须和之前建立heap的时候使用的判别式一致,比如都是operator <,或者都是operator > 。否则不能保证排序出来的结果是正确的。
5、简而言之,对大根堆进行sort_heap,必须使用operator <,对于小根堆进行sort_heap,必须使用operator >。
6、如果想让大根堆变成一个从大到小的序列,或者想让小根堆变成一个从小到大的序列,不能简单的改变判别式(原因如上所述),而应该保持原有判别式排序,然后调用std::reverse。
7、如果仅仅是想要用堆排序,这样自己封装一个heap_sort函数会更安全:
void heap_sort(RAIterator begin, RAIterator end , Comp op) {
make_heap(begin, end, op);
sort_heap(begin, end, op);
}
这样就可以保证建堆的时候和排序的时候用的都是同样的判别式。
8、n次push_heap的算法貌似是O(nlogn)的。。
2、sort_heap,是对已经成为heap的序列进行sort。本质上就是不断循环pop_heap而已。
3、sort_heap默认使用的也是operator <,排序出来的结果是从小到大的序列。
4、sort_heap算法使用的判别式,必须和之前建立heap的时候使用的判别式一致,比如都是operator <,或者都是operator > 。否则不能保证排序出来的结果是正确的。
5、简而言之,对大根堆进行sort_heap,必须使用operator <,对于小根堆进行sort_heap,必须使用operator >。
6、如果想让大根堆变成一个从大到小的序列,或者想让小根堆变成一个从小到大的序列,不能简单的改变判别式(原因如上所述),而应该保持原有判别式排序,然后调用std::reverse。
7、如果仅仅是想要用堆排序,这样自己封装一个heap_sort函数会更安全:
void heap_sort(RAIterator begin, RAIterator end , Comp op) {
make_heap(begin, end, op);
sort_heap(begin, end, op);
}
这样就可以保证建堆的时候和排序的时候用的都是同样的判别式。
8、n次push_heap的算法貌似是O(nlogn)的。。