Archive for August, 2011

作者:AngryFox 分类: Uncategorized August 20th, 2011 暂无评论
<?php
/**
 * 把一个汉字转为unicode的通用函数,不依赖任何库,和别的自定义函数,但有条件
 * 条件:本文件以及函数的输入参数应该用utf-8编码,不然要加函数转换
 * 其实亦可轻易编写反向转换的函数,甚至不局限于汉字,奇怪为什么PHP没有现成函数
 * @param {string} $word 必须是一个汉字,或代表汉字的一个数组(用str_split切割过)
 * @return {string} 一个十进制unicode码,如4f60,代表汉字 “你”
 *
 * @example
    echo "你 ".getUnicodeFromOneUTF8("你");
    echo "<br />";
    echo "好 ".getUnicodeFromOneUTF8("好");
    echo "<br />";
    echo "你好 ".getUnicodeFromOneUTF8("你好");
    echo "<br />";
    echo "你好吗 ".getUnicodeFromOneUTF8("你好吗");
    你 20320
    好 22909
    你好 251503099357000
    你好吗 4.21952182258E+21
 */
function getUnicodeFromOneUTF8($word) {
    //获取其字符的内部数组表示,所以本文件应用utf-8编码!
    if (is_array( $word))
       $arr = $word;
    else
        $arr = str_split($word);
    //此时,$arr应类似array(228, 189, 160)
    //定义一个空字符串存储
    $bin_str = '';
    //转成数字再转成二进制字符串,最后联合起来。
    foreach ($arr as $value)
       $bin_str .= decbin(ord($value));
       //此时,$bin_str应类似111001001011110110100000,如果是汉字"你"
       //正则截取
    $bin_str = preg_replace('/^.{4}(.{4}).{2}(.{6}).{2}(.{6})$/','$1$2$3', $bin_str);
    //此时, $bin_str应类似0100111101100000,如果是汉字"你"
    return bindec($bin_str);
    //返回类似20320, 汉字"你"
    //return dechex(bindec($bin_str));
    //如想返回十六进制4f60,用这句
}
echo "你 ".getUnicodeFromOneUTF8("你");
echo "<br />";
echo "好 ".getUnicodeFromOneUTF8("好");
echo "<br />";
echo "你好 ".getUnicodeFromOneUTF8("你好");
echo "<br />";
echo "你好吗 ".getUnicodeFromOneUTF8("你好吗");
exit;
?>  
作者:AngryFox 分类: Uncategorized August 20th, 2011 暂无评论

1.如果一个方法可静态化,就对它做静态声明。速率可提升至 4 倍。

2.echo 比 print 快。

3.使用 echo 的多重参数(译注:指用逗号而不是句点)代替字符串连接。

4.在执行 for 循环之前确定最大循环数,不要每循环一次都计算最大值。

5.注销那些不用的变量尤其是大数组,以便释放内存。

6.尽量避免使用 __get,__set,__autoload。

7.require_once() 代价昂贵。

8.在包含文件时使用完整路径,解析操作系统路径所需的时间会更少。

9.如果你想知道脚本开始执行(译注:即服务器端收到客户端请求)的时刻,使用 $_SERVER[‘REQUEST_TIME’] 要好于 time()。

10.函数代替正则表达式完成相同功能。

11.str_replace 函数比 preg_replace 函数快,但 strtr 函数的效率是 str_replace 函数的四倍。

12.如果一个字符串替换函数,可接受数组或字符作为参数,并且参数长度不太长,那么可以考虑额外写一段替换代码,使得每次传递参数是一个字符,而不是只写一行代码接受数组作为查询和替换的参数。

13.使用选择分支语句(译注:即switch case)好于使用多个if,else if语句。

14.用@屏蔽错误消息的做法非常低效。

15.打开 apache的 mod_deflate 模块。

16.数据库连接当使用完毕时应关掉。

17.$row[‘id’] 的效率是 $row[id] 的7倍。

18.错误消息代价昂贵。

19.尽量不要在 for 循环中使用函数,比如 for ($x=0; $x < count($array); $x) 每循环一次都会调用count() 函数。

20.在方法中递增局部变量,速度是最快的。几乎与在函数中调用局部变量的速度相当。

21.递增一个全局变量要比递增一个局部变量慢2倍。

22.递增一个对象属性(如:$this->prop++)要比递增一个局部变量慢 3 倍。

23.递增一个未预定义的局部变量要比递增一个预定义的局部变量慢 9 至 10 倍。

24.仅定义一个局部变量而没在函数中调用它,同样会减慢速度(其程度相当于递增一个局部变量)。PHP 大概会检查看是否存在全局变量。

25.方法调用看来与类中定义的方法的数量无关,因为我(在测试方法之前和之后都)添加了 10 个方法,但性能上没有变化。

26.派生类中的方法运行起来要快于在基类中定义的同样的方法。

27.调用带有一个参数的空函数,其花费的时间相当于执行 7 至 8 次的局部变量递增操作。类似的方法调用所花费的时间接近于 15 次的局部变量递增操作。

28.用单引号代替双引号来包含字符串,这样做会更快一些。因为 PHP 会在双引号包围的字符串中搜寻变量,单引号则不会。当然,只有当你不需要在字符串中包含变量时才可以这么做。

29.输出多个字符串时,用逗号代替句点来分隔字符串,速度更快。注意:只有 echo 能这么做,它是一种可以把多个字符串当作参数的“函数”(译注:PHP手册中说 echo 是语言结构,不是真正的函数,故把函数加上了双引号)。

30.Apache 解析一个 PHP 脚本的时间要比解析一个静态 HTML 页面慢 2 至 10 倍。尽量多用静态 HTML 页面,少用脚本。

31.除非脚本可以缓存,否则每次调用时都会重新编译一次。引入一套PHP缓存机制通常可以提升 25% 至 100% 的性能,以免除编译开销。

32.尽量做缓存,可使用 memcached。memcached 是一款高性能的内存对象缓存系统,可用来加速动态 Web 应用程序,减轻数据库负载。对运算码 (OP code) 的缓存很有用,使得脚本不必为每个请求做重新编译。

33.当操作字符串并需要检验其长度是否满足某种要求时,你想当然地会使用 strlen() 函数。此函数执行起来相当快,因为它不做任何计算,只返回在 zval 结构(C的内置数据结构,用于存储PHP变量)中存储的已知字符串长度。但是,由于 strlen() 是函数,多多少少会有些慢,因为函数调用会经过诸多步骤,如字母小写化(译注:指函数名小写化,PHP 不区分函数名大小写)、哈希查找,会跟随被调用的函数一起执行。在某些情况下,你可以使用 isset() 技巧加速执行你的代码。

(举例如下)

if (strlen($foo) < 5) { echo “Foo is too short”$$ }(与下面的技巧做比较)

if (!isset($foo{5})) { echo “Foo is too short”$$ }调用 isset() 恰巧比 strlen() 快,因为与后者不同的是,isset() 作为一种语言结构,意味着它的执行不需要函数查找和字母小写化。也就是说,实际上在检验字符串长度的顶层代码中你没有花太多开销。

34.当执行变量 $i 的递增或递减时,$i++ 会比 ++$i 慢一些。这种差异是 PHP 特有的,并不适用于其他语言,所以请不要修改你的 C 或 Java 代码并指望它们能立即变快,没用的。++$i 更快是因为它只需要 3 条指令 (opcodes),$i++ 则需要 4 条指令。后置递增实际上会产生一个临时变量,这个临时变量随后被递增。而前置递增直接在原值上递增。这是最优化处理的一种,正如 Zend 的 PHP 优化器所作的那样。牢记这个优化处理不失为一个好主意,因为并不是所有的指令优化器都会做同样的优化处理,并且存在大量没有装配指令优化器的互联网服务提 供商(ISPs)和服务器。

35.并不是事必面向对象 (OOP),面向对象往往开销很大,每个方法和对象调用都会消耗很多内存。

36.并非要用类实现所有的数据结构,数组也很有用。

37.不要把方法细分得过多,仔细想想你真正打算重用的是哪些代码?

38.当你需要时,你总能把代码分解成方法。

39.尽量采用大量的 PHP 内置函数。

40.如果在代码中存在大量耗时的函数,你可以考虑用 C 扩展的方式实现它们。

41.评估检验 (profile) 你的代码。检验器会告诉你,代码的哪些部分消耗了多少时间。Xdebug 调试器包含了检验程序,评估检验总体上可以显示出代码的瓶颈。

42.mod_zip 可作为 Apache 模块,用来即时压缩你的数据,并可让数据传输量降低 80%。

作者:AngryFox 分类: Uncategorized August 20th, 2011 暂无评论

求个apache rewrite htaccess写法!
访问 a-123.htm 的话变成访问 a/123.htm
a/123.htm不存在的话则访问 a.php?id=123

这个htaccess要怎么写???

RewriteEngine on
RewriteRule        ([a-z]+)-([0-9]+)\.htm        /$1/$2\.htm [R]
RewriteCond        %{REQUEST_FILENAME}        !-f
RewriteRule        (.*)/(.*).htm        $1.php?id=$2
作者:AngryFox 分类: Uncategorized August 13th, 2011 暂无评论

最终编辑 andrew_crystal

参考文献:
国际权威的学术组织ICDM,于06年12月年评选出的数据挖掘领域的十大经典算法:
C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART.
==============
博主说明:
1、原文献非最新文章,只是本人向来对算法比较敏感、感兴趣,便把原文细看了下,
翻译过程中,有参考一些网友翻译的文章,但个人认为,阐述皆不够精准,且都是泛泛而谈,
故此,做了此份翻译,希望,为读者提供一个较权威而详细的文档资料。
2、同时,也可于闲余之际择其一二好好研究、剖析下此数据挖掘领域的十大经典算法。
文中,添加了一些个人自己的理解,请自行辨明。
———————————————————————

以下就是从参加评选的18种候选算法中,最终决选出来的十大经典算法:

一、C4.5
C4.5,是机器学习算法中的一个分类决策树算法,
它是决策树(决策树也就是做决策的节点间的组织方式像一棵树,其实是一个倒树)核心算法
ID3的改进算法,所以基本上了解了一半决策树构造方法就能构造它。
决策树构造方法其实就是每次选择一个好的特征以及分裂点作为当前节点的分类条件。

C4.5相比于ID3改进的地方有:
1、用信息增益率来选择属性。
ID3选择属性用的是子树的信息增益,这里可以用很多方法来定义信息,ID3使用的是熵(entropy,熵是一种不纯度度量准则),

也就是熵的变化值.

而C4.5用的是信息增益率。对,区别就在于一个是信息增益,一个是信息增益率。
一般来说率就是用来取平衡用的,就像方差起的作用差不多,
比如有两个跑步的人,一个起点是10m/s的人、其1s后为20m/s;
另一个人起速是1m/s、其1s后为2m/s。
如果紧紧算差值那么两个差距就很大了,如果使用速度增加率(加速度,即都是为1m/s^2)来衡量,2个人就是一样的加速度。

因此,C4.5克服了ID3用信息增益选择属性时偏向选择取值多的属性的不足。

2、在树构造过程中进行剪枝,在构造决策树的时候,那些挂着几个元素的节点,不考虑最好,不然容易导致overfitting。
3、对非离散数据也能处理。
4、能够对不完整数据进行处理。

二、The k-means algorithm 即K-Means算法
k-means algorithm算法是一个聚类算法,把n的对象根据他们的属性分为k个分割(k < n)。
它与处理混合正态分布的最大期望算法(本十大算法第五条)很相似,因为他们都试图找到数据中自然聚类的中心。
它假设对象属性来自于空间向量,并且目标是使各个群组内部的均方误差总和最小。

三、 Support vector machines
支持向量机,英文为Support Vector Machine,简称SV机(论文中一般简称SVM)。

它是一种监督式学习的方法,它广泛的应用于统计分类以及回归分析中。
支持向量机将向量映射到一个更高维的空间里,在这个空间里建立有一个最大间隔超平面。
在分开数据的超平面的两边建有两个互相平行的超平面,分隔超平面使两个平行超平面的距离最大化。
假定平行超平面间的距离或差距越大,分类器的总误差越小。

一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。
van der Walt 和 Barnard 将支持向量机和其他分类器进行了比较。

四、The Apriori algorithm
Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。
其核心是基于两阶段频集思想的递推算法。

该关联规则在分类上属于单维、单层、布尔关联规则。
在这里,所有支持度大于最小支持度的项集称为频繁项集,简称频集。

五、最大期望(EM)算法
在统计计算中,最大期望 (EM,Expectation–Maximization)算法是在概率
(probabilistic)模型中寻找参数最大似然估计的算法,其中概率模型依赖于无法观测的隐藏变量(Latent Variabl)。

最大期望经常用在机器学习和计算机视觉的数据集聚(Data Clustering)领域。

六、 PageRank
PageRank是Google算法的重要内容。2001年9月被授予美国专利,专利人是Google创始人之一拉里•佩奇(Larry Page)。
因此,PageRank里的page不是指网页,而是指佩奇,即这个等级方法是以佩奇来命名的。

PageRank根据网站的外部链接和内部链接的数量和质量,衡量网站的价值。
PageRank背后的概念是,每个到页面的链接都是对该页面的一次投票, 被链接的越多,就意味着被其他网站投票越多。

这个就是所谓的“链接流行度”——衡量多少人愿意将他们的网站和你的网站挂钩。
PageRank这个概念引自学术中一篇论文的被引述的频度——即被别人引述的次数越多,一般判断这篇论文的权威性就越高。

七、AdaBoost
Adaboost是一种迭代算法,其核心思想是针对同一个训练集训练不同的分类器(弱分类器),
然后把这些弱分类器集合起来,构成一个更强的最终分类器 (强分类器)。

其算法本身是通过改变数据分布来实现的,它根据每次训练集之中每个样本的分类是否正确,

以及上次的总体分类的准确率,来确定每个样本的权值。

将修改过权值的新数据集送给下层分类器进行训练,最后将每次训练得到的分类器融合起来,作为最后的决策分类器。

八、 kNN: k-nearest neighbor classification
K最近邻(k-Nearest Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。

该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的

大多数属于某一个类别,则该样本也属于这个类别。

九、 Naive Bayes
在众多的分类模型中,应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和
朴素贝叶斯模型(Naive Bayesian Model,NBC)。
朴素贝叶斯模型发源于古典数学理论,有着坚实的数学基础,以及稳定的分类效率。

同时,NBC模型所需估计的参数很少,对缺失数据不太敏感,算法也比较简单。
理论上,NBC模型与其他分类方法相比具有最小的误差率。

但是实际上并非总是如此,这是因为NBC模型假设属性之间相互独立,这个假设在实际应用中
往往是不成立的,这给NBC模型的正确分类带来了一定影响。在属性个数比较多或者属性之
间相关性较大时,NBC模型的分类效率比不上决策树模型。

而在属性相关性较小时,NBC模型的性能最为良好。

十、 CART: 分类与回归树
CART, Classification and Regression Trees。 在分类树下面有两个关键的思想:第一个
是关于递归地划分自变量空间的想法;第二个想法是用验证数据进行剪枝。

作者:AngryFox 分类: Uncategorized August 12th, 2011 暂无评论

以下这些tips,是我在实际工作中慢慢形成的,有些可能是不正确的,有些出于个人习惯,所以,千万不要把以下这些条当成什么标准,其中可能隐藏着天大的bug,代码可能正在病态的运行中,SO!请一定仔细的看过后想想,这么做的好处是什么?会产生怎样的负面影响?有问题特别欢迎你来和我讨论。这就是我写这篇文字的目的,希望能和大家多多交流,也希望不断完善自己,同时又能给大家一些帮助。

开发习惯和PHP代码:

1、准确的理解各种概念。现在的新东西层出不穷,望文生义和一知半解对开发工作有害无益;

2、代码美观,适当的空行、缩进,空格,这样能更容易理解代码段的意思;

3、一定要写注释,而且要恰当的注释,要不然后面的维护工作或者接手代码的人会痛哭不已;

4、静态方法、类访问权限、接口、抽象类应该综合起来使用,发挥各自特点;

5、不要复制粘贴,即使是要用到现成的代码,也要一行一行的审阅后,再加入到新项目,因为经验告诉我们,这太容易出错了,对于使用开源类这种大段代码更需要;

6、变量都要初始化;

7、不要只处理error,而忽略warning和notice,这可能会导致日后的莫名其妙的问题,项目在开发状态下应该是error_reporting( E_ALL ^ E_NOTICE ),等到发布的外网生产环境时,应关闭所有错误报告display_errors=Off,error_reporting(0)网友 pAUL gAO分享了他们更合理的方案,error_reporting(E_ALL | E_STRICT),并且在生产环境中记录错误日志

8、记录一些必要的错误日志,比如写文件失败、写memcache失败,socket连接失败、读写数据库失败,日志能够帮助出现问题时的快速定位,外部生产环境我个人是强烈建议关闭所有错误报告的;

9、用try、catch捕获异常,对代码的健壮有帮助,常常在API接口中碰到,这样子显得友好多了;

10、双引号中出现的变量建议加上大括号,至于是”${nider}at gmail.com”还是”{$tom}at zendstudio.net”看个人习惯,我更喜欢后面一种;

11、尽量少的if else嵌套层数,也许你要表达一个非常复杂的逻辑算法,但这样做至少能让代码逻辑更清晰

12、多阅读网上开源项目的优秀代码(不是优秀项目的开源代码),吸取其中值得借鉴的地方

13、语言包用sprintf的格式化来做是多么惬意的一件事啊!

14、写缓存并不总是要先serialize一次的

15、AJAX传数据的时候,不要将数据库查出的数组直接json_encode后传给客户端,这样做不仅有一定的安全风险(字段名暴露),而且一些不需要的数据被传出浪费带宽,这条同样适用于API接口

16、要记得处理魔术变量,我的方法是直接关闭,当然也可以获取开关状态来避免传输数据被处理两次的问题

17、用$GLOBALS['var']代替global $var

18、不能轻易的die掉程序,尤其是在方法内部

19、require、require_once、include、include_once有着略微不同的应用场景

20、为了最大限度的使得写入缓存成功,可以结合重试次数+usleep,我一般重试3次,还不行那就记下一条log了

21、PHP的常量是个非常好的东西,很多开源项目中用一整个文件来定义要用到的常量

22、尽可能的使用绝对路径寻找文件

23、autoload是个很灵活的东西

24、最好用上set_error_handler和set_exception_handler,那显得你的项目更完美

25、PHP的引用类型是很高效的,在进行复杂运算时建议使用

26、@符号抑制错误是很耗性能的,因此尽可能的找到替代方案
MYSQL部分:

1、SQL语句用双引号,其中的值都用单引号,例如”INSERT INTO gril SET money=’{$iMaxMoney}’,age=’18′”

2、用mysqli扩展代替mysql扩展

2、用mysqli_real_escape_string和mysqli_escape_string处理传出sql语句中的变量

3、用mysqli_set_charset(mysqli->set_charset)代替 query “SET NAMES”

4、联合查询(JOIN)之前,考虑下各个表的数据量,不合适的话应该分开查,尤其是有缓存可用的时候

5、很多地方需要记录发生时间,但不是每一个表都需要,同样,不是每一个表都需要一个自增量作主键

6、很多时候为integer类型加上unsigned是很好的

7、INERT DELEYED、INSERT IGNORE、SELECT DISTINCT…这种语句通常有意想不到的好效果

8、varchar类型并不是不能超过255长度,而是超过了255,这个字段就不能建立索引了,所以,看你的实际需要了

暂时就想到这么多,等再想到的继续update吧。想到什么写什么,没有什么条理性,多多包涵了,如果这些对你有点滴帮助,那我就感到非常开心了。

最后一条终极建议就是——多和别人交流能够进步更快、更大!欢迎与我交流,留下你的宝贵意见。

作者:AngryFox 分类: Uncategorized August 12th, 2011 暂无评论

腾讯笔试题:const的含义及实现机制分析:

  const的含义及实现机制,比如:const int i,是怎么做到i只可读的?

  const用来说明所定义的变量是只读的。

  这些在编译期间完成,编译器可能使用常数直接替换掉对此变量的引用。

  初探编译器static、const之实现原理

  腾讯笔试题:买200返100优惠券,实际上折扣是多少?

  到商店里买200的商品返还100优惠券(可以在本商店代替现金)。请问实际上折扣是多少?

  分析:

  由于优惠券可以代替现金,所以可以使用200元优惠券买东西,然后还可以获得100元的优惠券。

  假设开始时花了x元,那么可以买到 x + x/2 + x/4 + …的东西。所以实际上折扣是50%.(当然,大部分时候很难一直兑换下去,所以50%是折扣的上限)

  如果使用优惠券买东西不能获得新的优惠券,那么

  总过花去了200元,可以买到200+100元的商品,所以实际折扣为 200/300 = 67%.

  腾讯笔试题:tcp三次握手的过程,accept发生在三次握手哪个阶段?

  分析:

  accept发生在三次握手之后。

  第一次握手:客户端发送syn包(syn=j)到服务器。

  第二次握手:服务器收到syn包,必须确认客户的SYN(ack=j+1),同时自己也发送一个ASK包(ask=k)。

  第三次握手:客户端收到服务器的SYN+ACK包,向服务器发送确认包ACK(ack=k+1)。

  三次握手完成后,客户端和服务器就建立了tcp连接。这时可以调用accept函数获得此连接。

  腾讯笔试题:用UDP协议通讯时怎样得知目标机是否获得了数据包

  用UDP协议通讯时怎样得知目标机是否获得了数据包?

  分析:

  可以在每个数据包中插入一个唯一的ID,比如timestamp或者递增的int。

  发送方在发送数据时将此ID和发送时间记录在本地。

  接收方在收到数据后将ID再发给发送方作为回应。

  发送方如果收到回应,则知道接收方已经收到相应的数据包;如果在指定时间内没有收到回应,则数据包可能丢失,需要重复上面的过程重新发送一次,直到确定对方收到。

  腾讯笔试题:统计论坛在线人数分布

  求一个论坛的在线人数,假设有一个论坛,其注册ID有两亿个,每个ID从登陆到退出会向一个日志文件中记下登陆时间和退出时间,要求写一个算法统计一天中论坛的用户在线分布,取样粒度为秒。

  分析:

  一天总共有 3600*24 = 86400秒。

  定义一个长度为86400的整数数组int delta[86400],每个整数对应这一秒的人数变化值,可能为正也可能为负。开始时将数组元素都初始化为0。

  然后依次读入每个用户的登录时间和退出时间,将与登录时间对应的整数值加1,将与退出时间对应的整数值减1。

  这样处理一遍后数组中存储了每秒中的人数变化情况。

  定义另外一个长度为86400的整数数组int online_num[86400],每个整数对应这一秒的论坛在线人数。

  假设一天开始时论坛在线人数为0,则第1秒的人数online_num[0] = delta[0]。第n+1秒的人数online_num[n] = online_num[n-1] + delta[n]。

  这样我们就获得了一天中任意时间的在线人数。

  腾讯笔试题:从10G个数中找到中数

  在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。

  分析:

  不妨假设10G个整数是64bit的。

  2G内存可以存放256M个64bit整数。

  我们可以将64bit的整数空间平均分成256M个取值范围,用2G的内存对每个取值范围内出现整数个数进行统计。这样遍历一边10G整数后,我们便知道中数在那个范围内出现,以及这个范围内总共出现了多少个整数。

  如果中数所在范围出现的整数比较少,我们就可以对这个范围内的整数进行排序,找到中数。如果这个范围内出现的整数比较多,我们还可以采用同样的方法将此范围再次分成多个更小的范围(256M=2^28,所以最多需要3次就可以将此范围缩小到1,也就找到了中数)。

  腾讯笔试题:两个整数集合A和B,求其交集

  两个整数集合A和B,求其交集。

  分析:

  1. 读取整数集合A中的整数,将读到的整数插入到map中,并将对应的值设为1。

  2. 读取整数集合B中的整数,如果该整数在map中并且值为1,则将此数加入到交集当中,并将在map中的对应值改为2。
通过更改map中的值,避免了将同样的值输出两次。

  腾讯笔试题:找出1到10w中没有出现的两个数字

  分析:

  有1到10w这10w个数,去除2个并打乱次序,如何找出那两个数?

  申请10w个bit的空间,每个bit代表一个数字是否出现过。

  开始时将这10w个bit都初始化为0,表示所有数字都没有出现过。

  然后依次读入已经打乱循序的数字,并将对应的bit设为1。

  当处理完所有数字后,根据为0的bit得出没有出现的数字。

  首先计算1到10w的和,平方和。

  然后计算给定数字的和,平方和。

  两次的到的数字相减,可以得到这两个数字的和,平方和。

  所以我们有

  x + y = n

  x^2 + y^2 = m

  解方程可以得到x和y的值。

  腾讯笔试题:需要多少只小白鼠才能在24小时内找到毒药

  有1000瓶水,其中有一瓶有毒,小白鼠只要尝一点带毒的水24小时后就会死亡,至少要多少只小白鼠才能在24小时时鉴别出那瓶水有毒?

  分析:

  最容易想到的就是用1000只小白鼠,每只喝一瓶。但显然这不是最好答案。

  既然每只小白鼠喝一瓶不是最好答案,那就应该每只小白鼠喝多瓶。那每只应该喝多少瓶呢?

  首先让我们换种问法,如果有x只小白鼠,那么24小时内可以从多少瓶水中找出那瓶有毒的?

  由于每只小白鼠都只有死或者活这两种结果,所以x只小白鼠最大可以表示2^x种结果。如果让每种结果都对应到某瓶水有毒,那么也就可以从2^x瓶水中找到有毒的那瓶水。那如何来实现这种对应关系呢?

  第一只小白鼠喝第1到2^(x-1)瓶,第二只小白鼠喝第1到第2^(x-2)和第2^(x-1)+1到第2^(x-1) + 2^(x-2)瓶….以此类推。

  回到此题,总过1000瓶水,所以需要最少10只小白鼠。

  腾讯笔试题:根据上排的数填写下排的数,并满足要求。

  根据上排给出十个数,在其下排填出对应的十个数, 要求下排每个数都是上排对应位置的数在下排出现的次数。上排的数:0,1,2,3,4,5,6,7,8,9。

  腾讯笔试题:判断数字是否出现在40亿个数中?

  给40亿个不重复的unsigned int的整数,没排过序的,然后再给几个数,如何快速判断这几个数是否在那40亿个数当中?

  分析:

  unsigned int 的取值范围是0到2^32-1。我们可以申请连续的2^32/8=512M的内存,用每一个bit对应一个unsigned int数字。首先将512M内存都初始化为0,然后每处理一个数字就将其对应的bit设置为1。当需要查询时,直接找到对应bit,看其值是0还是1即可。

作者:AngryFox 分类: Uncategorized August 12th, 2011 暂无评论
echo <<<xxx
<a href="http://www.baidu.com">baidu</a>
xxx;

1、xxx应符合变量名的要求,可以使用中文;
2、必须存在于独立行中;
3、xxx; 必须顶格,否则出错;
4、$a,函数不被执行,有点模板的意思。

作者:AngryFox 分类: Uncategorized August 12th, 2011 暂无评论

魔术函数
1。__construct()
实例化对象时被调用,
当__construct和以类名为函数名的函数同时存在时,__construct将被调用,另一个不被调用。

2。__destruct()

当删除一个对象或对象操作终止时被调用。

3。__call()
对象调用某个方法,
若方法存在,则直接调用;
若不存在,则会去调用__call函数。

4。__get()
读取一个对象的属性时,
若属性存在,则直接返回属性值;
若不存在,则会调用__get函数。

5。__set()
设置一个对象的属性时,
若属性存在,则直接赋值;
若不存在,则会调用__set函数。

6。__toString()

打印一个对象的时被调用。如echo $obj;或print $obj;

7。__clone()

克隆对象时被调用。如:$t=new Test();$t1=clone $t;

8。__sleep()

serialize之前被调用。若对象比较大,想删减一点东东再序列化,可考虑一下此函数。

9。__wakeup()

unserialize时被调用,做些对象的初始化工作。

10。__isset()
检测一个对象的属性是否存在时被调用。如:isset($c->name)。

11。__unset()
unset一个对象的属性时被调用。如:unset($c->name)。

12。__set_state()
调用var_export时,被调用。用__set_state的返回值做为var_export的返回值。

13。__autoload()
实例化一个对象时,如果对应的类不存在,则该方法被调用。

魔术常量

1。__LINE__
返回文件中的当前行号。

2。__FILE__
返回文件的完整路径和文件名。如果用在包含文件中,则返回包含文件名。自 PHP 4.0.2 起,__FILE__ 总是包含一个绝对路径,而在此之前的版本有时会包含一个相对路径。

3。__FUNCTION__
返回函数名称(PHP 4.3.0 新加)。自 PHP 5 起本常量返回该函数被定义时的名字(区分大小写)。在 PHP 4 中该值总是小写字母的。

4。__CLASS__
返回类的名称(PHP 4.3.0 新加)。自 PHP 5 起本常量返回该类被定义时的名字(区分大小写)。在 PHP 4 中该值总是小写字母的。

5。__METHOD__
返回类的方法名(PHP 5.0.0 新加)。返回该方法被定义时的名字(区分大小写)。

(1)初识魔术方法
Php5.0发布以来为我们提供了很多面向对象的特性,尤其是为我们提供了好多易用的魔术方法,这些魔术方法可以让我们简化我们的编码,更好的设计我们的系统。今天我们就来认识下php5.0给我们提供的魔术方法。

3,__get() 当试图读取一个并不存在的属性的时候被调用。
如果试图读取一个对象并不存在的属性的时候,PHP就会给出错误信息。如果在类里添加__get方法,并且我们可以用这个函数实现类似java中反射的各种操作。
class Test
{
public function __get($key)
{
echo $key . ” 不存在”;
}
}

$t = new Test();
echo $t->name;

就会输出:
name 不存在

4,__set() 当试图向一个并不存在的属性写入值的时候被调用。
class Test
{
public function __set($key,$value)
{
echo ‘对’.$key . “附值”.$value;
}
}

$t = new Test();
$t->name = “aninggo”;

就会输出:
对 name 附值 aninggo
5,__call() 当试图调用一个对象并不存在的方法时,调用该方法。
class Test
{
public function __call($Key, $Args)
{
echo “您要调用的 {$Key} 方法不存在。你传入的参数是:” . print_r($Args, true);
}
}

$t = new Test();
$t->getName(aning,go);

程序将会输出:
您要调用的 getName 方法不存在。参数是:Array
(
[0] => aning
[1] => go
)

6,__toString() 当打印一个对象的时候被调用
这个方法类似于java的toString方法,当我们直接打印对象的时候回调用这个函数
class Test
{
public function __toString()
{
return “打印 Test”;
}
}

$t = new Test();

echo $t;

运行echo $t;的时候,就会调用$t->__toString();从而输出
打印 Test

7,__clone() 当对象被克隆时,被调用
class Test
{

public function __clone()
{
echo “我被复制了!”;
}
}

$t = new Test();
$t1 = clone $t;

程序输出:
我被复制了!

作者:AngryFox 分类: Uncategorized August 12th, 2011 暂无评论

动态应用,是相对于网站静态内容而言, 是指以c/c++、php、Java、perl、.net等 服务器端语言开发的网络应用软件,比如论坛、网络相册、交友、BLOG等常见应用。动态应用系统通 常与数据库系统、缓存系统、分布式存储系统等密不可分。

大型动态应用系统平台主要是针对于大流 量、高并发网站建立的底层系统架构。大型网站的运行需要一个可靠、安全、可扩展、易维护的应用系统平台做为支撑,以保证网站应用的平稳运行。

大型动态应用系统又可分为几个子系统:

1 Web前端系统
2 负载均衡系统
3 数据库集群系统
4 缓存系统
5 分布式存储系统
6 分布式服务器管理系统
7 代码分发系统

Web前端系统

结构图:

为了达到不同应用的服务器共享、避免单点故障、集中管理、统一配置等目的,不以应用划分服 务器,而是将所有服务器做统一使用,每台服务器都可以对多个应用提供服务,当某些应用访问量升高时,通过增加服务器节点达到整个服务器集群的性能提高,同 时使他应用也会受益。该Web前端系统 基于Apache/Lighttpd/Eginx等 的虚拟主机平台,提供PHP程序运行环境 。服务器对开发人员是透明的,不需要开发人员介入服务器管理

负载均衡系统

负载均衡系统分为硬件和软件两种。硬件负载均衡效率高,但是价格贵,比如F5等。软件负载均衡系统价格较低或者免费,效率较硬件负载均衡系统 低,不过对于流量一般或稍大些网站来讲也足够使用,比如lvs,nginx。大多数网站都是硬件、软件负载均衡系统并用。

数据库集群系统

结构图:

由于Web前端采用了负载均衡集群结构提高了服务的有效性和扩展性,因此数据库必须也是高可靠的才能保证整个服务体系的高可靠性,如何构建一个高可靠的、可以提供大规模并发处理的数据库体系?

我们可以采用如上图所示的方案:

1) 使用 MySQL 数据库,考虑到Web应用的数据库读多写少的特点,我们主要对读数据库做了优化,提供专用的读数据库和写数据库,在应用程序中实现读操作和写操作分别访问不同的数据库。

2) 使用 MySQL Replication 机制实现快速将主库(写库)的数据库复制到从库(读库)。一个主库对应多个从库,主库数据实时同步到从库。

3) 写数据库有多台,每台都可以提供多个应用共同使用,这样可以解决写库的性能瓶颈问题和单点故障问题。

4) 读数据库有多台,通过负载均衡设备实现负载均衡,从而达到读数据库的高性能、高可靠和高可扩展性。

5) 数据库服务器和应用服务器分离。

6) 从数据库使用BigIP做负载均衡。

缓存系统

缓存分为文件缓存、内存缓存、数据库缓存。在大型Web应用中使用最多且效率最高的是内存缓存。最常用的内存缓存工具是Memcachd。使用正确的缓存系统可以达到实现以下目标:

1、 使用缓存系统可以提高访问效率,提高服务器吞吐能力,改善用户体验。

2、 减轻对数据库及存储集服务器的访问压力

3、 Memcached服务器有多台,避免单点故障,提供高可靠性和可扩展性,提高性能。

分布式存储系统

结构图:

WEB系统平台中的存储需求有下面两个特点:

1) 存储量很大,经常会达到单台服务器无法提供的规模,比如相册、视频等应用。因此需要专业的大规模存储系统。

2) 负载均衡cluster中的每个节点都有可能访问任何一个数据对象,每个节点对数据的处理也能被其他节点共享,因此这些节点要操作的数据从逻辑上看只能是一个整体,不是各自独立的数据资源。

因此高性能的分布式存储系统对于大型网站应用来说是非常重要的一环。(这个地方需要加入对某个分布式存储系统的简单介绍。)

分布式服务器管理系统

结构图:

随着网站访问流量的不断增加,大多的网络服务都是以负载均衡集群的方式对外提供服务,随之集群规模的扩大,原来基于单机的服务器管理模式已经不能够满足我们的需求,新的需求必须能够集中式的、分组的、批量的、自动化的对服务器进行管理,能够批量化的执行计划任务。

在分布式服务器管理系统软件中有一些比较优秀的软件,其中比较理想的一个是 Cfengine。它可以对服务器进行分组,不同的分组可以分别定制系统配置文件、计划任务等配置。它是基于C/S 结构的,所有的服务器配置和管理脚本程序都保存在Cfengine Server上,而被管理的服务器运行着 Cfengine Client 程序,Cfengine Client通过SSL加密的连接定期的向服务器端发送请求以获取最新的配置文件和管理命令、脚本程序、补丁安装等任务。

有了Cfengine 这种集中式的服务器管理工具,我们就可以高效的实现大规模的服务器集群管理,被管理服务器和 Cfengine Server 可以分布在任何位置,只要网络可以连通就能实现快速自动化的管理。

代码发布系统

结构图:

随着网站访问流量的不断增加,大多的网络服务都是以负载均衡集群的方式对外提供服务,随之集群规模的扩大,为了满足集群环境下程序代码的批量分发和更新,我们还需要一个程序代码发布系统。

这个发布系统可以帮我们实现下面的目标:

1) 生产环境的服务器以虚拟主机方式提供服务,不需要开发人员介入维护和直接操作,提供发布系统可以实现不需要登陆服务器就能把程序分发到目标服务器。

2) 我们要实现内部开发、内部测试、生产环境测试、生产环境发布的4个开发阶段的管理,发布系统可以介入各个阶段的代码发布。

3) 我们需要实现源代码管理和版本控制,SVN可以实现该需求。

这里面可以使用常用的工具Rsync,通过开发相应的脚本工具实现服务器集群间代码同步分发

作者:AngryFox 分类: Uncategorized August 12th, 2011 暂无评论

以前在一家视频网站工作一段时间,在当时属于起步比较早的视频分享网站,尽管访问量不大,但是我们还是研究了大访问量下网站设计的一些问题,可惜网站后来关闭了,很多东西都还没来得及实践。最近又拾起这个话题,便将以前学习到的整理一下。都是些皮毛,欢迎拍砖。

要建设一个大流量网站涉及很多内容,需要Developer,SA,甚至DBA来多人协作,基本上可以分为程序设计和网络架构两个方面。相比较而言网络架构显得更为重要,因为程序性能方面的不足有些可以通过更多的服务器来弥补,但这也不是说程序设计就不重要,好的程序设计可以更有效的使用服务器资源,降低成本。

在程序设计方面需要注意的问题:

选用合适的框架

框架是个好东西,可以缩短开发周期,提高工作效率,扩展性好,适合团队开发。缺点就是学习曲线高,特别是一些非常优秀的框架,比如Zend framework,symfony等,需要一定的学习时间。当然也有一些轻量级的框架,如codeigniter等,相对来说简单一点。更重要的是不如原生的php语句快,但这不表示说就不可以用框架。

目前互联网上访问量大的网站通常可以分为两种,一种是门户网站,比如163,sina等,一种是社区网站,如人人,开心等。这两种网站的区别在于,门户网站以html静态页面为主,社区网站以动态页面为主。门户网站可以使用一个cms系统来作内容管理,生成html页面,通过squid等,将内容送至用户,用户并不会直接访问到cms控制的服务器。所以可以用框架来建设这个cms。在这些html页面中,经常会出现一些动态内容,比如点击数等,这些则可以用ajax的方式来获得,这些功能的代码则不需要使用框架了。对于评论,留言等,则可以用另外一个页面来单独进行。原则即是访问量越大,动态信息越少。对于社区网站,因为页面信息随时变化,所以一般都采用动态页面,这时则要考虑框架带来的性能影响。我个人觉得可以采用一些轻量级的框架或自己编写一些简单的框架,主要是处理输入输出,错误,路由和数据库接口(使用统一的数据库接口非常重要,当网站不断扩展时,使用数据库的方式可能会发生变化,如果不统一,将来处理起来会非常麻烦),兼顾了扩展性和性能。

所以,使用框架还是必要的,但是要选择合适的。
适当的数据冗余

所谓数据冗余就是一份数据在多个地方同时存在。在一般情况下,这是不允许的。因为这会带来数据一致性的问题,也不符合数据库设计范式。不过在大流量或者大数据量的网站中,部分的数据冗余是能接受的。

比如,通常留言和主题是分开存储的。在显示留言的过程中,需要显示留言人的名字,一般我们会使用join去用户表中获取,但是在大流量或大数据量的情况下,这样对性能会存在一定影响。如果在留言表中加入用户名的字段则不再需要去join用户表,对性能有一定提升。
程序优化

程序优化的目的主要是为了节省程序运行的时间,即使是很少的一点,在大流量的情况下,每个用户省一点,积累下来也可以省下很大的时间。常见php的调试优化工具有xdebug,xhprof,ZendServer等。这些工具都可以跟踪程序的运行状态,记录每个函数调用的次数及时间,可以非常直观的查看到哪些地方最消耗时间,从而有针对性的进行优化。至于具体怎么优化就看个人功力了,同样的功能,可能两个人写出来的效率相差N倍。
xhprof callgraph

xhprof callgraph
xdebug kcachegrind

xdebug kcachegrind
减少css/js/image文件数量

网站上一般都会有很多css,js等文件。在开发时,为了保持文件结构清晰,它们都是一个个的。但是在生产环境中,应该将它们尽量合并,并压缩大小。这样即可以减少http请求数,又可以减少带宽需求。对于小块背景图,可以合并成一个,然后用background中的位置参数来显示。

如,http://www.google.com.hk/intl/zh-CN/options/ 中的图片都在一个文件中 http://www.google.com.hk/options/i8.png 只需请求一次即可,大大的降低了服务器的负担。
谨慎选择Session和Cookie

Session和Cookie是经常使用到的。Session存储在服务端,可以存储在文件中,也可以存储在数据库中。Cookie存储在客户端,每次请求时会发送至服务器。对大流量网站而言,Session也许并不合适,因为无论是存储在文件还是数据库,在大数据量的情况下性能都不理想。要提高Session的性能可以尝试使用内存数据库来存储,这样效率会比较高。另一种方式就是把信息加密后存储在Cookie中,这样无需使用服务器资源,但是无论请求什么文件Cookie都将发送至服务器,包括图片,css,js等,这会浪费一定量的带宽,所以存放在Cookie中的数据应该尽量小,也可以通过Cookie作用域来限制Cookie发送到的域名。
合理的缓存策略

缓存主要用来减轻数据库的负担,有很多种方式,比如文件缓存,数据库缓存,内存缓存等。但是要正确的设置缓存策略,否则可能会导致各种错误结果。前段时间facebook的宕机事故就是因为缓存的处理方面出了问题。以前在做视频网站时,因为全文索引比较慢,我们对部分数据采用了文件缓存。最开始的时候只是根据文件的时间是否过期来判断是否需要更新数据,后来发现如果同时有多个页面同时更新缓存,会造成数据库长时间占用CPU100%,于是我们设置了一个标志文件,当一个页面更新时,创建此文件,这时其他页面发现有此文件就不更新,继续使用缓存,第一个页面更新完成后删除此文件,其他页面才可更新。