要弄清楚Thread的层次结构，必须先弄清楚它的参照系。看看“The Futures of Ruby Threading”这段话：“Current stable releases of Ruby use user space threads (also called "green threads"), which means that the Ruby interpreter takes care of everything to do with threads. This is in contrast to kernel threads, where the creation, schedu ...
- 10:36
- 浏览 (496)
- 评论 (0)
- 分类: Concurrency
既然Thread质疑声一片，为什么它仍能够存在呢？原因有：（1）某些应用程序天生就具有并发特性，而且需要共享地址空间和各种资源，比如数据库服务器。（2）进程方案开销大。（3）Java语言大行其道，使得绝大部分程序员认为并发编程唯一也是最好的方式就是采用多线程，而且在Java语言中创建一个线程非常简单。对于第二点，只有线程创建，线程同步，线程加锁等开销比进程方案开销小，才会真正获益。只是来个线程创建和进程创建开销的比较，那也太天真了。此处，我认为还要包括开发，维护进程并发程序和线程并发程序两种方式之间的开销对比。毕竟，除了机器时间，人的时间也很宝贵。对于第三点，Java是不是会在以后考虑另外的并 ...
- 08:16
- 浏览 (472)
- 评论 (0)
- 分类: Concurrency
在Ruby实现中，Ruby1.8采用的是Green thread，JRuby和XRuby采用的是Native thread，Rubinius既支持Green thread，也支持Native thread。Ruby1.9将由Green thread转向Native thread。Green thread有哪些不足呢？在“Ruby Userspace Threads vs GUI tookits Roundup”中重点强调了Green Thread的一个不足：Blocking syscall将阻塞所有其余的线程，而且这个问题在GUI和网络开发中将随处碰到。另外，Green Thread不能有效挖 ...
- 06:10
- 浏览 (470)
- 评论 (0)
- 分类: Concurrency
过去，提升CPU性能的方法有：时钟速度执行优化缓存此时用户程序无须修改，就可以获得CPU性能提升所带来的好处。现在，提升CPU性能的方法：超线程多核缓存此时虽然缓存能，但超线程和多核CPU对现在的绝大多数应用，几乎不会有任何影响。多核还说不定会降慢程序的运行，因为多核带来的是更强的并行处理能力、更高的计算密度和更低的时钟频率。如果不采用并发好好利用硬件资源，多核CPU真的是浪费。另外，还有一些问题需要注意。有了多核，有时候还是感觉应用程序慢，此时问题可能就不是出在CPU上。要知道就算是单核，在日常工作中，CPU的利用率远没有达到100%。有时候，应用程序的瓶颈可能是在I/O，可能在网络，或者数 ...
- 06:10
- 浏览 (475)
- 评论 (0)
- 分类: Concurrency
整体结构：在IPC包中，最重要的3个类是Server，Client和RPC，它们具有层次化的结构。RPC类是对Server、Client的具体化。在RPC类中规定，客户程序发出请求调用时，参数类型必须是Invocation；从服务器返回的值类型必须是ObjectWritable。为了加强理解，可以查看测试类TestIPC。在那里，规定的参数类型与返回值类型都是LongWritable。RPC类是对Server、Client的包装，简化用户的使用。如果一个类需充当服务器，只需通过RPC类的静态方法getServer获得Server实例，然后start。同时此类提供协议接口的实现。如果一个类充当客 ...
在此包中，最重要的是FileSystem抽象类。它定义了文件系统中涉及的一些基本操作，如：create，rename，delete...另外包括 一些分布式文件系统具有的操作：copyFromLocalFile,copyToLocalFile,...类似于Ftp中put和get操作。 LocalFileSystem和DistributedFileSystem，继承于此类，分别实现了本地文件系统和分布式文件系统。了解了最重要的类之后，看一看它的一系列stream类：FSOutputStream在原有OutputStream基础之上添加了获得文件指针偏移量的getPos方法。可以通过FileSys ...
实现拥有多个不同的MapReduce接口的实现是可能的。具体选择取决于环境。比如，一种实现适合于共享内存的机器，一种适合于NUMA(Non-Uniform Memory Access )多处理器，另外一种适合于大量的网络机器。这节将描述在Google内部大量使用，适合于大量PC构成的集群系统这种计算环境的实现。在这个环境中：双CPUx86机器，运行Linux，具有2-4G内存。网络采用的是100M/s或1G/s的配置硬件，然实际的平均使用值大概为它们的一半。采用由成百上千PC构成的集群系统，机器故障很经常。存储采用的是直连每个机器的IDE硬盘。通过我们自己开发的GFS来管理磁盘上的数据。此文件 ...
看了基于Google File System思想实现的Hadoop代码，重读了Google的这篇论文《The Google File System》。Paper挺长，网上已经有热心的人把翻译版奉献了出来。在这里，只是把其中的部分内容抽取出来，与大家一起分享。性能，可扩展性，可靠性，可用性仍然是GFS的目标，但它还有一些与传统分布式文件系统与众不同的东西：（1）对于大规模的集群系统，机器出现故障很正常，因此系统容错必须十分重视。文件系统必须具有高可用性，数据完整性和相应的诊断工具。通过快速恢复，chunk复制，master复制达到高可用性；通过checksum检查数据完整性；通过log记录系统中 ...
OpenMP和MPI是并行编程的两个手段，对比如下： OpenMP:线程级（并行粒度）；共享存储；隐式（数据分配方式）；可扩展性差； MPI：进程级；分布式存储；显式；可扩展性好。OpenMP采用共享存储，意味着它只适应于SMP,DSM机器，不适合于集群。MPI虽适合于各种机器，但它的编程模型复杂：需要分析及划分应用程序问题，并将问题映射到分布式进程集合；需要解决通信延迟大和负载不平衡两个主要问题；调试MPI程序麻烦；MPI程序可靠性差，一个进程出问题，整个程序将错误； 其中第2个问题感受深刻。每次听我们部门并行组的人做报告，总是听到他们在攻克通信延迟大和负载不平衡的问题。一种并行算法的好坏就 ...
IPC 实现RPC的一种方法，具有快速、简单的特点。 它不像Sun公司提供的标准RPC包，基于Java序列化。 IPC无需创建网络stubs和skeletons。 IPC中的方法调用要求参数和返回值的数据类型必须是Java的基本类型，String和Writable接口的实现类，以及元素为以上类型的数组。接口方法应该只抛出IOException异常。 使用模型 采用客户/服务器模型 Server：它把Java接口暴露给客户端。指定好监听端口和接受远程调用的对象实例后，通过RPC.getServer()可以得到Server实例。 Client：连接Server，调用它所暴露的方法。Clie ...
反向索引是一种索引结构，它存储了单词与单词自身在一个或多个文档中所在位置之间的映射。反向索引通常利用关联数组实现。它拥有两种表现形式：inverted file index，其表现形式为 {单词，单词所在文档的ID}full inverted index，其表现形式为{单词，（单词所在文档的ID，在具体文档中的位置）}具体实例，假设有三个文档：T0 = "it is what it is"T1 = "what is it" T2 = "it is a banana"那么，采用inverted file index方式，结果是： "a": {2} "banana": { ...
在Google 的论文《MapReduce：Simplified Data Processing on Large Clusters》中提到“Our abstraction is inspired by the map and reduce primitives present in Lisp and many other functional lanuages.”。对于大部分不熟悉函数语言的程序员来说，可能并不能够彻底理解Map和Reduce的具体含义。在这篇文章中，将采用C语言实现函数语言中的Map和Reduce操作。简单来说，Map是对一组数据中的每个元素进行操作，产生一组全新的数据；R ...
想从事与搜索相关的研发工作，需要哪些知识。带着这个疑问，我查看了包括Google，Baidu，Yahoo，腾讯，Sohu，Sina，阿里巴巴等公司的招聘信息。自我总结如下：为什么要从事研发工作？ 在公司处于核心地位；把研究和开发紧密而完美的结合在一起；研发职责是什么？ 负责搜索引擎系统的架构设计以及核心模块的系统设计； 进行搜索引擎系统核心模块的编码和技术研发； 重点技术难题的攻关；想从事研发工作，需要什么？ 强烈责任心，开放的性格，良好的沟通能力；拥有极强的发现问题、分析问题、解决问题的能力； Fluency in English(Reading and ...
顺序搜索Programmer每天都碰到顺序搜索，其code snippet：/** 顺序遍历数组，搜索v值是否存在。如果存在，返回相应的位置索引，* 否则返回-1*/int sequentialSearch(int a[],int v,int l,int r){int i;for(i = l;i <= r;i++){if(v == a[i])return i;}return -1;}分析：假设数组拥有N个元素，对于不成功的搜索，总是搜索N个元素；对于成功的搜索，平均搜索次数为N/2。假设每个数组元素被搜索到的概率相等，那么平均搜索次数可以这样计算：(1+2+...+N)/N = (N+1 ...
KMP算法，在《数据结构》课上听过，似是非懂，读完大学后全忘光了。Brute-Force算法，简单，谁都知道。从主串S的第pos个字符起与模式串进行比较，匹配不成功时，从主串S的第pos+1个字符重新与模式串进行比较。如果主串S的长度是n，模式串长度是m，那么Brute-Force的时间复杂度是o(m*n)。最坏情况出现在模式串的子串频繁出现在主串S中。虽然它的时间复杂度为o(m*n)，但在一般情况下匹配时间为o(m+n)，因此在实际中它被大量使用。前几日，重新拾起了KMP算法，然后向MM讲解之。KMP的主要思想是：每当一趟匹配过程中出现字符比较不等时，不需回溯主串S的指针，而是利用已经得到的 ...
周末两天被BM算法折磨的要死。《a fast string search algorithm》论文中提到的算法思想倒是理解的差不多，但网上（http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140）给出的实现可就是看不懂。通过Baidu，Google一搜，可以看到很多Boyer-Moore的实现。但绝大部分实现都是简化版本，只考虑了bad-character shift，而忽略了good-suffix shift。它思想的源泉是从右向左匹配字符串将获得更多有用的信息。The algorithm precomputes ...
题目 You have been given 2 special, extremely rugged Xboxes. You are in an office building that is 100 stories high. Using the fewest possible number of drops from windows in your office building, determine the highest floor you can drop an Xbox from and have it survive: for example, they might be abl ...
题目村子中有50个人，每人有一条狗。在这50条狗中有病狗（这种病不会传染）。于是人们就要找出病狗。 每个人可以观察其他的49条狗，以 判断它们是否生病（如果有病一定能看出来），只是自己的狗不能看。观察后得到的结果不得交流，也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要枪 毙自己的狗（发现后必须在一天内枪毙），而且每个人只有权利枪毙自己的狗，没有权利打死其他人的狗。 第一天大家全看完了，但枪没有响，第二天仍没有枪响。到了第三天传来一阵枪声，问村里共有几条病狗，如何推算得出？答案3条病狗分析 假设有n条病狗，那么就有50-n个人的狗不是病狗。第一天大家枪都没有响， 那么n必然大 ...
Skip List号称性能与BST（Binary Sort Tree）树有得一拼，于是把它翻了个底朝天。代码是阐述其思想的最好方式，那我们还是看看它的具体实现（采用Java语言）public class SkipList { public static final int NOT_FOUND = -1; public static final int HEADER_KEY = -2; public static final int NIL_KEY = Integer.MAX_VALUE; // optimum probability public static final float OP ...
特色：Library sort优于传统的插入排序（时间复杂度为O(n^2))，它的时间复杂度为O（nlogn），采用了空间换时间的策略。 思想：一个图书管理员需要按照字母顺序放置书本，当在书本之间留有一定空隙时，一本新书上架将无需移动随后的书本，可以直接插空隙。Library sort的思想就源于此。 实现：有n个元素待排序，这些元素被插入到拥有(1+e)n个元素的数组中。每次插入2^(i-1)个元素，总共需要插logn趟。这2^(i-1)个元 素将被折半插入到已有的2^(i-1)个元素中。因此，插入i趟之后，已有2^i个元素插入数组中。此时，执行rebalance操作，原有处在(1+ e)2 ...
插入实现（传指针地址的地址）： void InsertNode(struct node **node_ptr, struct node *newNode) { struct node *node = *node_ptr; if (node == NULL) *node_ptr = newNode; else if (newNode->value <= node->value) InsertNode(&node->left, newNode); else InsertNode(&node-> ...
用堆栈实现递归其实并没有消除递归，只不过人工做了本来由编译器做的事情。真正的非递归是指运算时所需要的空间是常数，即所需空间与问题的输入规模无关。并非所有递归都可以转换成非递归，比如著名的Ackmann函数。递归转非递归方法：（1）用一般公式直接代替。象经常看到的斐波那契数列，它就存在通项公式，而无需采用递归实现。（2）使用栈来实现（3）通过Cooper变换、反演变换将一些递归转化为尾递归，从而迭代求出结果至于什么是Cooper变换，反演变换，这可得好好研究数学。这里贴两个变换实例。计算阶乘的递归实现（用Haskell实现的，谁都看得懂）：f x ＝ if x = 0 then 1 else f ...
顺序表的实现，天下人都知道，最最简单的一种，不过我还是贴出两个实现，大家看看：int search(int a[],int key,int length){int i;for(i=length-1;i>=0;i--){if(a[i]==key) return i;}return -1;}/** 实际数组元素是从1号位置起开始存储，0号位置存储key*/int search(int a[],int key,int length){int i;a[0] = key;for(i=length;!(a[i]==key);i--);return i;}由此，想到了字符串的拷贝实现： for(i ...
性质1：一颗二叉树（严格的二叉树，即没有度为1的节点），有N个内部节点，那么它将有N＋1个外部节点。 采用归纳法证明： 如果只有一个外部节点，即单独的一个根节点，那么内部节点数为0，结论显然成立。 假设有N－1个内部节点时，结论成立。那么二叉树拥有N个内部节点时，左子树有k个内部节点，右子树有N－k－1个内部节点，此外包括一个根节点。由于左 右子树的节点数都小于N，所以由前面假设可得左子树有k＋1个外部节点，右子树有N－k个节点，总共有k＋1＋(N-k)个节点，即N＋1个节点。 由性质1可得，一颗有N个外部节点的二叉树需要用数组存储，那么需要申请一个拥有2N－1个元素的数组。性质2：在一个已排 ...
评论排行榜