The fork() System Call

System call fork() is used to create processes. It takes no arguments and returns a process ID. The purpose of fork() is to create a new process, which becomes the child process of the caller. After a new child process is created, both processes will execute the next instruction following the fork() system call. Therefore, we have to distinguish the parent from the child. This can be done by testing the returned value of fork():

• If fork() returns a negative value, the creation of a child process was unsuccessful.
• fork() returns a zero to the newly created child process.
• fork() returns a positive value, the process ID of the child process, to the parent. The returned process ID is of type pid_t defined in sys/types.h. Normally, the process ID is an integer. Moreover, a process can use function getpid() to retrieve the process ID assigned to this process.

25个让人惊叹的HTML5应用实验

今，很多Web技术爱好者都在尝试使用HTML5来制作各种丰富的应用，本文就列出了25个让人惊叹的HTML5应用实验，让你体验下一代Web技术的魅力。相信你看完这些例子后会对未来的Web发展充满无限期待。(博客园)

Bomomo

Design Iterative Algorithms

If you are designing describing and proving correct an algorithm using loop invariants, the following is the list the things must consider.

Specification: Define the problem (pre and post conditions): likely defined by the problem.

Define Loop Invariant: It needs to be a picture of what is true every time the algorithm is at the top of the loop. 

Establishing the Loop Invariant:

  <pre-cond> & code_pre-loop => <Loop Invariant>

·      state what you know about the input instance because of <pre-cond>

·      state the effect of the code before the loop

·      State how it then follows that <loop invariant> has been established.

Different types of Iterative Algorithms

Here are a few classic types of iterative algorithms to help you design a measure of progress and a loop invariant.

More of the Output:  if the solution is a structure composed of many pieces (e.g., an array of integers, a set, or a path), a natural thing to try is to construct the solution one piece at a time.

·      Measure of Progress:  The amount of the output constructed.

·      Loop Invariant: The output constructed so far is correct

More of the Input:  Suppose the input consists of n objects ( e.g., an array of n integers or a graph with n nodes). It would be reasonable for the algorithm to read them in one at time.

·      Measure of Progress:  The amount of the input considered.

·      Loop Invariant: Pretending that this prefix of the input is the entire input, I have a complete solution.

Narrowing the Search Space: If you are searching for something, try narrowing the search space, maybe decreasing it by one or, even better, cutting it in half.

·      Measure of Progress: the size of the space in which you have narrowed the search.

·      Loop Invariant: If the thing be searched for is anywhere, then it is in this narrowed sublist.

GCD LIKE: substitute the input with other instance much easier or smaller.

·      Measure of Progress: the new instance replacing the original input has smaller size or easier.

·      Loop Invariant:  if the new instance has been constructed whose solution is the same as the original instance, then I have the solution

算法总结系列之八:复读机的故事 - 散列表.NET应用的研究(下集)

估计写这么个题目会被扔鸡蛋, 因为实在是太大了. 各位不要期望太高啊,我写这东西,就是为了给自己个备忘. 你们要是把它当垃圾看, 说不定还能发现点什么东西.

言归正题. 说实话, .NET Framework的实现可能比我们认为的要好一些, 比如线程安全, 代码效率, 甚至以及代码风格方面. 比如HashTable 的实现就是一个比较好的佐证.

上文说到, .NET Framework 中的哈希表, 使用了双重散列的方式来计算散列值. 那么到底精确的来说, 是采用了什么关系式呢? 实际上很简单, 这个关系式就是:

h(key, n) = h1(key) + n*h2(key)

算法总结系列之八:复读机的故事-散列表及其在.NET中的应用浅析(上集)

记得3年前还在上一家公司的时候, 一天下午一个哥们很激动的在偶旁边念叨"散列表真是个好东西,散列表真是个好东西...."绵绵不绝, 偶石化继而抓狂,奋起曰:"你复读机啊你复读机啊你复读机啊...".

散列表不是复读机, 散列表更像是一个大池子(但是不是所有的大池子都可以认为是散列表). 这个特殊的大池子有这样的特点, 它的容量总是要比你想要存储的元素数量大, 它能利用大出一部分容量的特点, 让你能更加快速的查找定位某一元素.

牺牲一点点内存,换取更高效的表现, 有人问值不值得?  大哥,现在1G的内存都100多块钱了...

第一部分: 散列表的基本知识

散列表是这样一种数据结构: 它利用散列函数(通常称为函数h(k))计算元素关键字(标记k)的散列值, 并根据该散列值, 直接确定(或者通过简单数学计算)该元素在散列表中的存储位置(散列表中的存储位置我们称为槽Slot). 如果两个元素关键字通过散列函数的计算获得了同样的散列值, 从而指向散列表中的同一个槽, 我们称这种现象为"碰撞(Collision)".由于元素关键字域U的容量大于散列表T的容量m, 所以完全避免碰撞是不可能的. 这就引申出了散列表最为重要的两个问题:

算法总结系列之七:选择问题(Randomized Select)

"能否以O(n)的时间复杂度, 从一个未排序的整数数组中选取第i大的整数出来?"

你面试的时候,有人问过你这样的问题吗?

这类有关大小排序选取的选择问题是极容易出现在面试题目中的问题,在算法学上,我们把这类问题统称为"选择问题", 也称之为"中位数问题".

选择问题的解决, 不一定要先排序然后遍历(事实上这是比较慢的做法,排序的时间复杂度决定了它不可能比O(nlgn)快). 通常选择问题只是要求知道第i大/小的元素, 所以我们可以将它当作排序算法的简化. 我们以快速排序为例, 我们以划分的区间判断,选择问题我们只追究可能出现问题解的一个区间,而快速排序要处理两个区间.

当待选择元素足够均匀时, 本文的RandomizedSelect算法可以达到O(n)的时间复杂度, 而最坏情况下,它的时间复杂度可能是O(n * n).这里有必要着重说明一下, O(n*n)的算法复杂度是RandomizedSelect算法的上限, 而不是它的平均复杂度, 除非是特别设计(样本间元素满足特定关系多项式)的样本, RandomizedSelect算法一般可以认为它的平均时间复杂度是O(n).