《Ruby太慢了》PHP实现,两种算法

http://www.oschina.com 之前 有一篇文章 http://www.oschina.net/translate/ruby-is-too-slow-for-programming-competitions
一下子掀起了各语言实现这个算法的狂潮

转帖呢,首先看看题目要求:给定数字X和Y,返回其中包括多少个数字,数字本身是回文数,同时也是另一个回文数的平方。

这里有一个PHP 实现,是仿照的 JAVA 算法:http://www.oschina.net/code/snippet_1023425_20741
实际上这样没有完全利用PHP本身的特点,运算速度颇慢,我本地大概27s
我以这个算法为基础,优化如下:

<?php
set_time_limit(0);
$t1 = microtime(true);
$min = 1;
$max = 100000000000000;
$i = (int) sqrt($min);
$end = (int) sqrt($max) + 1;
for (; $i < $end; $i++) {
if (($i % 10) > 0 && $i == strrev($i)) {
$n = $i * $i;
if ($n == strrev($n)) {
echo "$n ($i)<br>";
}
}
}
echo 'Time:', (microtime(true) - $t1), 's';

1、使用 strrev 可以让对回文的判断快非常多,本地测试减少了10s
2、去掉了独立的 isPlalindrome 函数。第一,调用纯PHP写的函数花费时间很多,这个修改可以节省了大约4s;第二,上一步修改后的 $i == strrev($i) 已经足够简洁
3、$min 和 $max,sqrt 后手动转成 int,否则 for 时PHP会有自动类型转换,浪费 2s 左右
4、增加了 ($i % 10) > 0,还是能快几百毫秒吧,聊胜于无
5、拆成了两个,经过测试,拆开要比写成一个 if 快一点
6、去掉了 showPlalindrome,简单到底,没必要封装,反正肯定会快那么无法察觉的一点
7、$end + 1,如果 $max 是 4000008000004 这样的符合条件的回文数,不这么写会漏掉

经过以上修改,执行大概需要 8.1s

然后,正戏来了,参考:http://www.oschina.net/code/snippet_169326_20803,中的算法:

<?php
set_time_limit(0);
$t1 = microtime(true);
$min = 1;
$max = 0xffffffffffffffff;
$palindromes = array();
$s = (string) sqrt($min);
$l = strlen($s);
$i = (int) substr($s, 0, $l / 2 + $l % 2); 
while (true)
{
$s1 = (string) $i;
$s2 = strrev($s1);
$p = (int) ($s1 . substr($s2, 1));
$pp = $p * $p;
if ($pp > $max)
{
break;
}
if ($pp >= $min and $pp == strrev($pp))
{
$palindromes[$p] = $pp;
}
$p = (int) ($s1 . $s2);
$pp = $p * $p;
if ($pp >= $min and $pp <= $max and $pp == strrev($pp))
{
$palindromes[$p] = $pp;
}
++$i;
}
ksort($palindromes);
foreach($palindromes as $p => $pp)
{
echo $pp, ' (', $p, ')<br />';
}
echo 'Time:', (microtime(true) - $t1), 's';

1 ~ 0xffffffffffffffff 只需要 0.4s
上一个算法中,那个 1 ~ 100000000000000 只需要 0.04s

这就是算法的力量….

PHP5.4

总结一下有点意思的 PHP5.4 更新:

<?= is now always available regardless of the short_tags setting
<?= 不管php.ini里面 short_tags 怎么设置都将一直能用

Added multibyte support by default
终于直接支持多字节了,应该是不需要再用mbstring了吧

Added support for Traits
新的语法结构,trait,用法看这里:https://wiki.php.net/rfc/traits

Added array dereferencing support
就是说可以这么玩了:

function fruit()
{
return array('a' => 'apple', 'b' => 'banana');
}
echo fruit()['a'];

Array shortcuts
可以用 JSON 那种结构定义 PHP ,看:https://wiki.php.net/rfc/shortsyntaxforarrays
alpha1里面还没有,在 TODO Items For Discussion 中,也就是还不确定是否会有

Built-in web server
目前主要还是为了更简单的调试,不过我想有这个东东,php未来就有可能模拟一些单纯的应用出来,详见:https://wiki.php.net/rfc/builtinwebserver

生成 main/config.w32.h

准备好PHP源代码,假设解压到 D:\php-src

下载2个必要的包
http://www.php.net/extra/bindlib_w32.zip
http://www.php.net/extra/win32build.zip
把这2个包的内容放一起,例如解压缩到 D:\win32build

请使用 Visual Studio Tools 下的 Visual Studio 命令提示 操作
进入D:\php-src\
执行buildconf.bat
建立一个临时环境变量,执行set path=%path%;D:\win32build\bin

执行 cscript /nologo configure.js –with-php-build=”../win32build” –without-libxml  –disable-odbc
如果想要No Thread Safe 模式就在上面的命令最后加上参数 –disable-zts

然后看看是不是main下面多了一个 config.w32.h~
还有一点,config.w32.h 里面 #define PHP_COMPILER_ID 改成和你正在用的 PHP 编译版本相同的编译器ID,例如VC6或者VC9,不然编译出来的扩展没法载入,说实话,这个ID的判断真的很傻很天真….

注:以上过程在PHP5.3.5 + VS2010 下测试通过

Migrating from PHP 5.2.x to PHP 5.3.x

PHP5.3已经正式发布了…打算抽点时间把 Migrating from PHP 5.2.x to PHP 5.3.x(从PHP5.2.x迁移到PHP5.3.x)翻译成中文,慢慢写咯…因个人能力限制…难免有错误,欢迎指正

未向下兼容的变化
大部分现有的PHP5代码是不需要改变的,不过请注意下面这些变化:
  • 新的内部参数解析 API 已经被应用在 PHP 5.3.x 绑定的所有扩展上。这个 API 使得函数在传入不兼容的参数时返回 NULL。这条规则也有一些例外,例如函数 get_class(),在出错的时候将继续返回 FALSE。
  • clearstatcache() 默认不再清除真实路径缓存(realpath cache)。(PS:函数增加了两个有关的参数,具体请看手册)
  • realpath() 现在已经是与平台完全无关的了。
  • call_user_func() 这一系的函数现在可以使用 $this ,即使是在父类中执行也可以这样使用。
  • 以下数组函数 natsort(), natcasesort(), usort(), uasort(), uksort(), array_flip()array_unique() 不再支持对象(object)参数 如果要将这些函数应用于一个对象(object),首先需要将这个对象强制转换成数组。
  • 使用引用参数(by-reference parameters)的函数传入值的行为被改变了。之前函数可以接受值参数(by-value argument),现在将会触发一个警告(warning),同时所有应用参数被设置为 NULL
  • 新的 mysqlnd 库(PS:此为PHP 5.3 新加入的原生 MySQL 驱动,用于代替之前使用的 MySQL Client,全称 MySQL Native Driver) 需要使用 MySQL 4.1 之后引入的新的 41字节(41-byte) 密码格式。继续mysql_connect() 和类似的函数中使用老的 16字节(16-byte)密码将会触发错误 “mysqlnd cannot connect to MySQL 4.1+ using old authentication.”(mysqlnd 无法使用过时的验证方式连接 MySQL 4.1+
  • 路径 / 已经从 SplFileInfo 类和其他有关目录的类中移除。
  • 魔术方法(magic method__toString 不再接收参数。
  • 以下魔术方法(magic method __get, __set, __isset, __unset__call 必须总是公开的(public)而且不允许是静态方法(static)。这些方法的标签从现在开始是强制性的。
  • 魔术方法(magic method __call 现在可以被调用来访问私有(private)或者受保护的(protected)方法。

下面的关键字已经被保留,不允许用在函数、类等的名字内。

新功能
PHP 5.3.0 提供了多方面的新功能:
  • 新增:支持 namespaces (名字空间)。
  • 新增:支持 Late Static Bindings (延迟静态绑定)。
  • 新增:支持 jump labels (跳转标签,有限制的 goto) 。
  • 新增:支持原生的 Closures (闭包,表达式函数/匿名函数)。
  • 两个新的魔术方法(magic methods),__callStatic__invoke.
  • 现在支持 Nowdoc 语法,类似于 Heredoc 语法,但是名字上加上单引号。
  • 现在可以将 Heredocs 用来初始化静态变量(static variables)和类的属性/常量(class members/constants).
  • Heredocs 现在可以在声明的时候名字两边使用双引号,以作为新增的 Nowdoc 语法的补充。
  • Constants (常量)现在可以在类以外的地方使用 const 关键字进行声明。
  • ternary operator(三元运算符)现在可以使用简写形式:?:(PS:expr1 ?: expr3, expr1 true 的时候返回 expr1,否则返回 expr3
  • The HTTP stream wrapper(HTTP 数据流封装?)现在认为从 200 到 399 之间的状态代码(status codes)都是表示成功。
  • 现在可以动态的访问静态方法(static methods)。(PS:大概指的就是 __callStatic)
  • Exceptions (异常处理)现在可以嵌套使用。
  • 新增了一个垃圾回收器(garbage collector),默认是开启的。
为支持 Windows 所做的修改
PHP 发布的 Windows 版的修改:
  • 最低的 Windows 版本是 Windows 2000; Windows 98, ME 和 NT4 不再支持。
  • Windows 二进制包现在指定为 i586 或更高。 i386 和 i486 不再支持。
  • 在 Windows 平台上 PHP 提供对 x64 实验性的支持。
  • 现在编译器支持 Visual C++ 9 (VC9),可以使用 Visual Studio 2008。快照和发布版现在同样可以支持 VC9。对以前那样使用 VC6 编译的二进制包依然提供支持,将随着 VC9 产品线一起发布。
  • PDO_OCI php_pdo_oci8.dll 库 (使用 Oracle 8 客户端库) 不再构建。 取而代之,使用基于 Oracle 10 或 11 客户端库的 php_pdo_oci.dll (注意没有 ‘8’) 。 连接其他数据库版本的功能依然是被支持的
  • 为了 OCI8 扩展,一个新的库 php_oci8_11g.dll 可以用作 php_oci8.dll 的补充。任何时候这两个库都只能开启其中的一个。php_oci8.dll 使用 Oracle 10.2 客户端库。php_oci8_11g.dll 使用 Oracle 11 客户端库。 连接其他数据库版本的功能依然是被支持的

对 Windows 的支持已经被加入到如下函数中:

其他改变:

  • 改良了 stat(), touch(), filemtime(), filesize() 和其他有关函数的可移植性 (对有效数据 (the available data)具有 100% 的可移植性).
  • 现在可以在 Windows 下使用 link() 函数建立硬连接(hard links),使用 symlink() 建立符号连接(symbolic links)。硬链接用于 Windows 2000,符号连接用于 Windows Vista.
  • Windows 版 PHP 现在公布了一组新的常量,使用前缀 PHP_WINDOWS_*。有关的常量列表和用途请查阅 Predefined Constants(预定义常量)。
警告
ISAPI 模块支持已经被放弃。可以使用改进的 FastCGI SAPI 模块来代替。

提示: 现在已经创建了一个全新的专注于 Wiudows 下 PHP 的网站, 包含各种版本的下载, 发布候选, 和快照 (thread-safe/not-thread-safe (线程安全/非线程安全), VC6/VC9, x86/x64)。网站的 URL » http://windows.php.net/

SAPI 模块的改变
  • 一个成名于 litespeed 的新 SAPI 模块被启用。
  • FastCGI 现在总是开启的,而且不能被关闭。请查看 sapi/cgi/CHANGES 获得更多的信息。
  • 增加了一个新的 CGI SAPI 选项 -T,用来测量脚本的重复执行时间。
  • CGI/FastCGI 现在支持 .htaccess-style user-defined php.ini files。( .htaccess 风格 用户定义的 php.ini文件?
  • dl() 函数当前默认是关闭的,并且只能用于 CLI, CGI 和嵌入式 SAPIs (embed SAPIs)。
PHP 5.3.x 中不建议使用的功能

PHP 5.3.0 引入了两个新的错误标示: E_DEPRECATEDE_USER_DEPRECATEDE_DEPRECATED 用来表明一个函数或者功能不建议使用。E_USER_DEPRECATED 表示不建议使用的功能是用户代码,类似 E_USER_ERRORE_USER_WARNING

下面的列表是不建议使用的 INI 指令(PS:就是 php.ini 中的参数)。使用这些中的任何一个指令都会在启动的时候抛出一个 E_DEPRECATED 错误。

不建议使用的函数:

不建议使用的功能:

  • new 的返回值指定为引用现在不推荐。(PS:大概是 $object = &new stdClass; 这种形式)
  • Call-time pass-by-reference (执行时传递引用?PS:可能是指 func(&$param) 这样)不推荐。
  • 使用 {} 访问字符串坐标(string offsets)不推荐。使用 [] 代替。(PS:似乎这三条从 PHP5.0 开始就不建议使用了,这次可能是把错误类型从 E_STRICT 改成了新的 E_DEPRECATED
PHP 5.3.x 不再反对的功能

基于对 is_a() 函数的广泛需求,不再反对它的使用;使用这个函数不会再产生 E_STRICT 错误。

新的参数

在 PHP 5.3 中部分函数提供了新的可选参数:

PHP 核心:

  • clearstatcache()增加了 clear_realpath_cachefilename .
  • copy() – 增加数据流环境参数(stream context parameter), context .
  • fgetcsv() – 增加 escape .
  • ini_get_all()增加 details .
  • mail() 函数现在支持记录发送的邮件。(注:只有通过这个函数发送邮件时才有效)
  • nl2br() – 增加 is_xhtml .
  • parse_ini_file() – 增加 scanner_mode .
  • round() – 增加 mode .(PS:现在不光是四舍五入这一种形式了)
  • stream_context_create() – 增加 params .
  • strstr()stristr() – 增加 before_needle .(PS:可以取指定字符前面的部分了)

json:

Streams:

sybase_ct:

PHP 5.3.0 中新的方法参数:

PHP 参数:

Exception::__construct – 增加 previous .

新的函数

PHP 5.3 引入了一些新的函数:

PHP 核心:

Date/Time:

GMP:

Hash:

IMAP:

  • imap_gc() – Clears IMAP cache.
  • imap_utf8_to_mutf7() – Encode a UTF-8 string to modified UTF-7.
  • imap_mutf7_to_utf8() – Decode a modified UTF-7 string to UTF-8.

JSON:

MySQL Improved:

OpenSSL:

PCNTL:

PCRE:

  • preg_filter() – Perform a regular expression search and replace, reutrning only results which matched the pattern.

Semaphore:

The following functions are now natively implemented, making them available on all operating systems which can run PHP:

今天遇到有史以来最囧的bug

今天开新服,结果在开服前20分钟测出一个巨囧的bug…经过一个下午调试终于知道原因并解决了…其实也不用多说什么,说一下解决方法就知道为什么囧了…

某函数xxx需要参数$a(数组)

形如:xxx($a)

程序形如:

$a = array();

$a[] = 1;

$a[] = 2;

echo xxx($a);

结果错误 = =

解决方法如下:

$a = array();

$a[] = 1;

$a[] = 2;

eval(‘$a = ‘ . var_export($a, true) , ‘;’);

echo xxx($a);

结果正确…..这一刻你也囧住了吧….

强大的动网…

今天看了动网PHP版2.0++的宣传词,实在受不了了…好一堆什么首创什么第一,只一句话:做人不能WC到这种地步。

PS:小装了一下 2.0++…恩,不支持FireFox,安装成功第一次访问直接 syntax error,很好,很强大

再PS:原来是必须要打开short_tag_open(顺便说下DZ也有这个问题)…看来我是无福消受了…

Blitz Templates 最快的 PHP 模板引擎

这个最快的模板引擎可不像网上那些自我吹嘘的模板引擎那样,最起码一个很大的不同是这个模板引擎是一个 PHP 扩展,从这一点就可以看出它比用 PHP 写出来的模板引擎要快不是难以理解的。
官方网址:http://alexeyrybak.com/blitz/blitz_en.html
官方提供的测试数据:

从这个数据看比 php include都要快,咳咳….

当然也可以看出来 php include其实也是很快的,至少比一般的模板引擎快很多,特别是 ZPS(Zend Performance Suite) on 的情况下,虽然还是比Blits略慢,可见装一个PHP内存cache扩展加速是很有必要的,我个人推荐xcache,这个扩展以后再说了^^

在ZPS off的情况下即使 include 速度下降的也令人吃惊…跟不用说smarty这种模板引擎了…这种状态Blitz下比传统模板引擎至少快3倍,即使是和php include比也要快1倍多,那个仅次于Blitz的php_templates也是一个PHP扩展模板引擎,可见扩展形式的模板引擎在没有加速扩展的时候 是最好的选择,不过话说回来,既然这个模板引擎扩展你都装了…那么再装一个xcache似乎也不是什么难事吧= =b

Blitz 引擎的语法架构和 phplib 那一类的模板引擎有点类似,是基于block的,模板用到的变量需要注册,所以安全性来说会高一些,而且它的速度对于那些速度极致追求者来说会有不小的诱惑

先简单介绍这么多,更详细的以后有时间再说^^

同时发布于:http://bbs.phpso.com/viewthread.php?tid=4415&extra=page%3D1

一些经典字符串哈希函数算法的 PHP 实现

恩…或许还有朋友不清楚字符串的哈希函数到底有什么用,这个用处呢,就是将字符串转换成数字,同时让所得数字尽量平均的分布在容器中,换句话说就是让字符串得到相同数字这种情况尽可能少的出现。当然咯…容器太小,内容太多那么再好的算法也没法避免出现冲突 = =b

从网上找到的哈希函数基本上都是C算法的…最后只好从C and Java 算法中整理 and 测试了这些 PHP中的实现方法。有几个经典的算法在 PHP 下会有问题,字符串一长就会全部取 0,那些我就没有再列出来了。代码就看下面咯:
继续阅读“一些经典字符串哈希函数算法的 PHP 实现”

All in One SEO 中文环境下的一个 Bug

All in One SEO 是一个进行 Wordprss SEO 优化的插件,它能够重写 Wordprss 页面的 title 以利于搜索引擎收录,但是这个插件有一个 bug 当你使用的 Tag 是中文时,title中显示的第一个字符会是乱码,检查后发现是插件会试图将英文单词第一个字符转成大写,本身中文就是多字节字符,substr再 strtoupper,了解 php 中文处理的人就应该知道肯定会出问题了…

为了解决这个问题我将插件中的 capitalize 方法(function capitalize)修改如下:

function capitalize($s)
{
$s = trim($s);
$tokens = explode(' ', $s);
for ($i = 0, $n = count($tokens); $i < $n; $i++)
{
$matches = array();
preg_match('/^(.{1})(.*)$/us', $tokens[$i], $matches);
$tokens[$i] = strtr($matches[1], 'abcdefghijklmnopqrstuvwxyz', 'ABCDEFGHIJKLMNOPQRSTUVWXYZ') . $matches[2];
}
$s = implode(' ', $tokens);
return $s;
}

这样 title 就不会出现乱码了。

2007.11.12更新:
我光注意到Tag中文有错误,没注意到分类的title中文也会乱码,感谢 funyfan 提醒。

搜索all_in_one_seo_pack.php中全部的ucwords替换为$this->capitalize,如此即可避免上述问题,其实ucwords做的事情和capitalize方法是一样的,不过ucwords是php原生函数,同样的不支持多字节字符处理。All in One SEO在这个地方的处理思路看起来还是够不统一啊,虽然说一样都有问题,呵呵。

2009.04.17:

新版的 All in One SEO 已经解决了这个问题,我直接升级使用没发现还有乱码了

刚刚看到WordPress MU1.0和bbPress发布

WordPress MU就是WordPress Multi-user,WordPress多用户版。bbPress是一个使用了WordPress的架构编写的论坛。

MU的话可能国人不会用的太多,第一是没有一个足够强大的门户页面,这个东西似乎在国内都很看重;第二是数据库的结构是新建一个用户就新建一批表,这个对于国内一般意义的多用户来说是不能承受的。

bbPress让我想起了另外一个论坛Vanilla,感觉这两个论坛在颇有一些相似之处,比较简洁清爽的论坛,不过是否能为国人接受就不得而知了。