PHPor 的Blog – 第97页

PHP实现的一维关联数组序列化

下面是一个典型的k-v存储格式的PHP实现：

class db {
        public function test() {
         //.....
        }
	private function pack($arr) {
		$str = '';
		foreach($arr as $key=>$val) {
			$str .= pack("n", strlen($key)).pack("n", strlen($val)).$key.$val;
		}
		return $str;
	}
	private function unpackUserInfo($str) {
		$arrResult = array();
		$len = strlen($str);
		if ($len < 5) return $arrResult;
		$pos = 0;
		while($len - $pos >= 5) {
			$arr1 = unpack("n", substr($str, $pos, 2));
			$arr2 = unpack("n", substr($str, $pos+2, 2));

			$len_key = $arr1[1];
			$len_val = $arr2[1];
			$key = substr($str, $pos + 4, $len_key);
			$val = substr($str, $pos + 4 + $len_key, $len_val);
			$pos += 4 + $len_key + $len_val;
			$arrResult[$key] = $val;
		}
		return $arrResult;
	}

}

class db {

public function test() {

//.....

}

private function pack($arr) {

$str = '';

foreach($arr as $key=>$val) {

$str .= pack("n", strlen($key)).pack("n", strlen($val)).$key.$val;

}

return $str;

}

private function unpackUserInfo($str) {

$arrResult = array();

$len = strlen($str);

if ($len < 5) return $arrResult;

$pos = 0;

while($len - $pos >= 5) {

$arr1 = unpack("n", substr($str, $pos, 2));

$arr2 = unpack("n", substr($str, $pos+2, 2));

$len_key = $arr1[1];

$len_val = $arr2[1];

$key = substr($str, $pos + 4, $len_key);

$val = substr($str, $pos + 4 + $len_key, $len_val);

$pos += 4 + $len_key + $len_val;

$arrResult[$key] = $val;

}

return $arrResult;

}

注意：

1. pack(“n”,…) 使得key、value长度都限制在65535以内

IE6下经典的请求abort问题

摘自：http://www.cnblogs.com/shihao/archive/2012/06/22/2559042.html

IE6 a标签的请求被abort的原因

最近项目中掉进IE6 a标签abort两次坑，第一次是a标签绑定一个事件，href='javascript:;'这样a标签触发了事件，切换验证码图片，结果验证码图片总是显示不出来，通过抓包显示状态为abort。其实这个的原因可以从IE6中a标签执行顺序说起，IE6中a标签执行onclick在执行默认事件（即href跳转）之前，当触发了绑定的事件之后，那么处理完事件之后，如果不return false或者阻止默认事件，则会继续执行href跳转，IE6会认为页面跳转到其他页面或者页面重新刷新，则abort之前onclick事件中的请求。

所以当onclick时，做出的获取最新验证码图片的请求，会因为下一步href的触发而abort。同时，如果你在a绑定的事件中做ajax请求，那么也会被无情的abort。

IE6 a标签的请求被abort的解决方案

解决的方法就是在onclick或者绑定事件中return false来阻止a标签跳转的默认事件。
例如下面的代码：

&lt;a href="javascript:void(0)" onclick="fn();return false;"&gt;Test&lt;/a&gt;

1	<a href="javascript:void(0)" onclick="fn();return false;">Test</a>

或者你也可以给a标签的href写成“#”，即当前页面的锚点，这样页面就不会跳转，自然不会abort请求。

最好的方式还是两种都用，保险！

其他参考资料：

http://www.web92.net/758.html

http://www.cnblogs.com/Ren_Lei/archive/2010/09/26/1836130.html

面试题

编写算法，从10亿个浮点数当中，选出其中最大的10000个。

1、读入的头10000个数，直接创建二叉排序树。O(1)
2、对以后每个读入的数，比较是否比前10000个数中最小的大。(N次比较)如果小的话接着读下面的数。O(N)
3、如果大，查找二叉排序树，找到应当插入的位置。
4、删除当前最小的结点。
5、重复步骤2，直到10亿个数全都读完。
6、按照中序遍历输出当前二叉排序树中的所有10000个数字。
基本上算法的时间复杂度是O(N)次比较
算法的空间复杂度是10000(常数)

Bloom Filter算法及应用

1. 引言
问题：有1000瓶药，但是其中有一瓶是有毒的，小白鼠吃了24小时后就会死掉，请问，在24小时找出有毒的药物，最少需要多少只小白鼠？
答案是：10只，一只小白鼠可以表示2种状态，2^10可以表示1024种状态
分析可参考：http://lzj0470.iteye.com/blog/657579
通过二进制向量组来扩展描述的状态，Bloom Filter(BF)算法也是利用这个思想，其本质是上是一个很长的二进制向量和一系列随机映射函数

2. 概述
问题：快速判断一个元素是否在一个集合中
解决方法：一般来说，我们会用HASH表来存储集合中的数据，好处是快速准确，缺点是存储效率低，在海量数据时一般服务器无法存储。
BF是针对哈希表存储效率低的问题，而衍生出来的一种算法。
其通过利用二进制数组来描述一个集合，来判断一个元素是否属于这个集合
优点是：快速查找，并具有非常高的存储效率
缺点是：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合

3. 算法描述
BF包含：
1)一个m位的二进位数组，每一位初始化时置为0
2)k个相互独立的hash函数
算法：
针对一个n个元素的集合，通过k个hash函数，将集合中的每个元素都映射到二进位数组中，映射到的位置置为1
例如：对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1
在判断某个元素P是否在这个集合时，通过对P应用k次hash函数，判断其对应所有的位置都是1，如果是则认为P是集合中的元素，否则不是。

4. 最优位数组m大小及hash函数个数
在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合。因此，如何根据输入元素个数n，确定位数组m的大小及hash函数个数是一个非常重要的问题。
经过一些复杂的证明（可参考相关文档），可以得到：
1）当hash函数个数k=(ln2)*(m/n)时错误率最小
2）在错误率不大于E的情况下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合，但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)的1.44倍

5. 应用
有10亿个url，如何判断一个新的url是否在这个url的集合中？
一个url平均长度为52，如果用Hash表解决的话，由于Hash表的存储效率一般只有50%，因此10个url大概需要100G内存，一般服务器无法存储。
使用BF，要求错误率小于万分之一。
此时，输入元素n=10亿，最大错误率E=0.0001
可计算出：m=nlg(1/E)*1.44=57.6亿，大概需要7.2亿（57.6亿/8）个字节，即720M内存。
Hash函数个数：k=(ln2)*(m/n) 大概4个Hash函数

6.总结
BF通过牺牲一定的错误率来保证时间和空间（鱼与熊掌，不可兼得），目前被广泛应用于海量数据处理及数据库系统中。
例如，在Big table和Cassandra中，都使用BF作为索引结构。
P.S 针对BF的错误识别问题，可以通过建立白名单的方式解决。

参考文献：
paper：Network Applications of Bloom Filters: A Survey
http://blog.csdn.net/jiaomeng/article/details/1495500

迅雷面试题

1.给你10台机器，每个机器2个cpu，2g内存，现在已知在10亿条记录的数据库里执行一次查询需要5秒，问用什么方法能让90%的查询能在100毫秒以内返回结果。
2.一个长度为10000的字符串，写一个算法，找出最长的重复子串，如abczzacbca,结果是bc。最后就做出这一道题目，时间复杂度为O(n!), 空间复杂度为O(n)。

算法题：
1.连接两个单向链表，返回排序后的结果。
2.一个保存有10000个URL的文本文件，删除其中相同的URL。
3.将9个石子放在9×9的方格中，要求同行、同列、45度上无两个石子。

智力题：
1.一笔画四条直线穿过3×3的9个点。
2.国王给三个囚犯每人戴了一顶帽子，帽子不是黑色就是白色，并且告诉囚犯们谁看到其它两个人都是白帽子或者知道自己戴的是黑帽子，谁就能被释放。囚犯们能看到其它的人帽子颜色，但是看不到自己的帽子颜色。过了一段时间，三个囚犯都没有说话，其中一个聪明的囚犯立刻肯定自己戴的是黑帽子，你知道为什么吗？
3.有16个硬币，A和B轮流拿，每次拿的个数只能是1，2，4之一，谁最后拿谁就输。问可以保证赢吗？?

文件的打开方式

用法：

1. 不存在则创建之，存在则直接用之

因为w/w+ 会清空文件，故不用

2. 打开文件后可以随意改写和读取文件的任何部分

因为 a/a+ 不能随意seek到文件的任意位置，故不用

**fopen()** 中 *`mode`* 的可能值列表
`mode`	说明
‘r’	只读方式打开，将文件指针指向文件头。
‘r+’	读写方式打开，将文件指针指向文件头。
‘w’	写入方式打开，将文件指针指向文件头并将文件大小截为零。如果文件不存在则尝试创建之。
‘w+’	读写方式打开，将文件指针指向文件头并将文件大小截为零。如果文件不存在则尝试创建之。
‘a’	写入方式打开，将文件指针指向文件末尾。如果文件不存在则尝试创建之。
‘a+’	读写方式打开，将文件指针指向文件末尾。如果文件不存在则尝试创建之。
‘x’	创建并以写入方式打开，将文件指针指向文件头。如果文件已存在，则 fopen() 调用失败并返回 `FALSE`，并生成一条 `E_WARNING`级别的错误信息。如果文件不存在则尝试创建之。这和给底层的 open(2) 系统调用指定 O_EXCL\|O_CREAT 标记是等价的。
‘x+’	创建并以读写方式打开，其他的行为和 ‘x’ 一样。

注意：

1. w+ 方式总是会把原文件清空的

2. a+ 方式是不能来回fseek的

所以，或许你需要的是 r+ 方式，自己先判断一下文件是否存在，不存在则创建之即可

关于文件的最后修改时间

有这么一个现象，明明看着日志文件的最后修改时间不断地变化，但是日志内容却没有增长，看了一下是磁盘空间满了；

这里说明一个逻辑，对于已存在的文件，即使磁盘空间满了，更新文件的时候虽更新失败，依然会导致文件的最后修改时间发生变化；推测：更新文件内容时，应该是先更新文件的最后修改时间，然后再更新内容的；如果更新最后修改时间在后，似乎程序员不会让更新内容失败的情况下依然去更新最后修改时间的

fgets的第二个参数

缘起

string fgets ( resource $handle [, int $length ] );

第二个参数指定可以读取的最大长度，但是比较有意思的是，如果最终没有读取到换行，则返回的不是$length个字节，而是 $length -1 个字节，文档是这么写的，事实也是这样子的，那么为什么制造这么一个小插曲呢？说多少就是多少不是很好嘛，为什么还要少一个字节呢？

分析

因为PHP是用c写的，这可能也不是PHP故意如此的，或许C就是这样的，于是：

man fgets

…

fgets() reads in at most one less than size characters from stream and stores them into the buffer pointed to by
s. Reading stops after an EOF or a newline. If a newline is read, it is stored into the buffer. A ‘\0’ is
stored after the last character in the buffer.

…

看来这和字符串buffer的长度是有关系的，字符串总是要以”\0″（是零不是欧）结尾的，所以真正得到的长度比指定的长度是小1的。

如果一行是3个字符（带上换行），这时候，指定fgets的最大长度为3，则读不出来换行，只能读到2个字符，写一次才能读到换行

PHP版的tail -f

缘起

每天生成一个文件，用一个程序实时读文件，类似tail -f ，但是程序需要能自动切换文件

问题

脚本

<?php
$fp = fopen("a.txt", "r");
while(1) {
    $ret = fgets($fp);
    if ($ret === false){ 
        sleep(1); 
        fseek($fp, 0, SEEK_CUR);  // 如果没有fseek，则新的内容将无法读出来
    }
    echo $ret;
}

<?php

$fp = fopen("a.txt", "r");

while(1) {

$ret = fgets($fp);

if ($ret === false){

sleep(1);

fseek($fp, 0, SEEK_CUR); // 如果没有fseek，则新的内容将无法读出来

}

echo $ret;

}

具体可参考fseek的实现：main/streams/streams.c

strace: ptrace(PTRACE_CONT,1,133): Input/output error

这是strace的一个bug，已经修复：

https://bugzilla.redhat.com/show_bug.cgi?id=590172

https://bugzilla.redhat.com/show_bug.cgi?id=594616

test

How to load debug symbols with GDB

转： http://marcioandreyoliveira.blogspot.jp/2008/03/how-to-debug-striped-programs-with-gdb.html

My friend Wanderley asked me if it is possible to tell GDB to load debuging symbols from some file and use it to help debuging a program that doesn’t have them.

Yes. It is.

There are two solutions to this question.

I going to explain the first solution in this post. The other solution I will explain in the next post.

You can load debuging information from an debug enabled version of executable file.

In order to better explain the first solution, I will setup my sample environment as follows:

released.c: source code of the program we wish to debug (listing 1).
~/estudo/: Source code of our program will be put here.
~/local/bin: The stripped off version of binary program will stay here.
~/local/symbols: In this place are all files that contain debuging information.

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

int division(int a, int b);

int m;

int main(void)
{
int i;
int j;

printf("vou setar i\n");
i = 10;

printf("vou setar j\n");
j = 1;

printf ("i = %d, j = %d\n", i, j);
m = division(i, j);

printf("m = %d / %d = %d\n", i, j, m);

return 0;
}

int division(int a, int b)
{
return a / b;
}

#include <stdio.h>

#include <stdlib.h>

int division(int a, int b);

int m;

int main(void)

{

int i;

int j;

printf("vou setar i\n");

i = 10;

printf("vou setar j\n");

j = 1;

printf ("i = %d, j = %d\n", i, j);

m = division(i, j);

printf("m = %d / %d = %d\n", i, j, m);

return 0;

}

int division(int a, int b)

{

return a / b;

}

Listing 1 – sample program source code

I have two versions of the program: with and without debuging information.

1 – You compile your program with debug information. In our sample:

gcc -Wall -g -release release.c <ENTER>

2 – You make a copy of your program. In our sample:

cp release release.full <ENTER>

3 – You strip off debuging information:

strip -s release <ENTER>

As you can see on Figure 1, we have two programs. released.full has debuging symbols but release doesn’t have them.

Figure 1

4 – Move file release to ~/local/bin/:

mv release ~/local/bin <ENTER>

5 – Move file released.full to ~/local/symbols/

mv release.full ~/local/symbols <ENTER>

6 – Go to directory ~/local/bin

cd ~/local/bin <ENTER>

7 – Run GDB:

gdb ./release <ENTER>

8 – Try list command to see that release executable file doesn’t have symbols in it.

Note: if the program was already running you could get its PID then attach GDB to it.

Figure 2 shows us two windows. The first one shows that our executable file has no debug information. In the other window we can see thatrelease is not yet loaded.

Figure 2 – executable file named release is loaded by GDB but it is not yet running.

9 – Let GDB to load symbols from executable file named release.full. This binary version of our program has all symbols that we need to debug.

Please notice that GDB will not replace the release executable byrelease.full version of our program. It will just import symbols fromrelease.full into release debugging session.

But GDB needs to know in advance where it must put the symbols it will load. How can you determine the correct memory address?

It is quite simple. You issue command maint inside GDB:

maint info sections

Then you look for .text section. The address that is in the first column is what you want. In our sample, it is 0x08048320. See figure 3.

Figure 3 – looking for .text section address

10 – The next step is to instruct GDB to load debug symbols into .text section. To achieve it you do this:

add-symbol-file ~/local/symbols/release.full <.text section address>

In our sample it means to type:

add-symbol-file ~/local/symbols/release.full 0x08048320

From now on you can debug your program as usual.

Figure 4 shows us that debugging symbols where imported successfully and that now the list command (abbreviated as l) shows us the program source code.

Figure 4 – now our GDB session has debuging symbols

As you can see in figure 5, I set a break point at line 17 and I ran the program that stopped there. Then I printed i variable.

In the other terminal I issued ps command. It was done just to show you that the only program running was release executable. There is no instance of release.full program.

Figure 5 – debugging session.

I hope this post will make your life easier. In the next time I will teach you another way to import debugging symbols.