这是在工作中遇到的实际问题和解决过程。问题已经被抽象成并发任务的分配问题。
问题
如果有 n 组数据均分给 m 个处理器处理，那么每个处理器分到的数据是 \(\lceil \frac{n}{m} \rceil\) 。如果n组数据的类型有差异，其中有a组是一类数据，剩余 n-a 组是另一类数据。只有同类数据才能被一次性处理，那么该如何分配？
这个问题在现实中是存在的。比如HTTP并发请求处理一些数据。数据被批量送来，但类型不一样。为了节省耗时，我们希望并发处理这些不同的数据。并发数是确定好的。现在需要计算每个请求处理的数量，以便我们能给每一个请求打包数据。
求解
n 组数据交给 m 个处理器处理，每个处理器最多分到 \(\lceil \frac{n}{m} \rceil\) 组数据，这是毫无疑问的。如果 n 组数据中有a组是一类数据，n-a组是另一类数据。同类数据必须分配到同一个处理器。那么a类数据得到的处理器的数量是 \(\lceil \frac {a} {\lceil \frac{n}{m} \rceil} \rceil \)，b类得到的处理器的数量是 \(\lceil \frac {n-a} {\lceil \frac{n}{m} \rceil} \rceil \)。我们现在其实需要考虑它们总共需要的处理器数量和m的关系。原有的m个处理器是否满足这种需求？如果不满足，需要多少个处理器才能满足？
即，求 \(( \lceil \frac {a}{\lceil \frac{n}{m} \rceil} \rceil +\lceil \frac {n-a} {\lceil \frac{n}{m} \rceil} \rceil ) \) 和 m的关系。
对于上面的问题，我们的存在一些已知的前提条件：
- m, m 为正整数
- \(n \leq m\)
根据上面已知的条件，我们可以得出一些引理：
- \(\lceil \frac {n}{m} \rceil \geq \frac {n}{m} \)
- \( \lceil \frac {n}{m} \rceil \leq \frac {n}{m} + \frac {m-1}{m} \)
因此，容易得出\(( \lceil \frac {a}{\lceil \frac{n}{m} \rceil} \rceil +\lceil \frac {n-a} {\lceil \frac{n}{m} \rceil} \rceil ) \geq \lceil \frac {n}{\lceil \frac {n}{m} \rceil} \rceil \geq m \)
即数据类型分成两种的时候所需要的处理器数量是大于等于m的，原先的处理器个数可能不够用了。那么多少才够用？这是现在需要考虑的问题。
容易得出，\( ( \lceil \frac {a}{\lceil \frac{n}{m} \rceil} \rceil +\lceil \frac {n-a} {\lceil \frac{n}{m} \rceil} \rceil ) \leq \lceil \frac {am}{n}\rceil + \lceil \frac {(n-a)m} {n} \rceil \)
根据上面的引理可以得出 \( \lceil \frac {am}{n}\rceil + \lceil \frac {(n-a)m} {n} \rceil \leq \frac {am}{n} + \frac {n-1}{n} + \frac {(n-a)m} {n} + \frac {n-1}{n} = n+2-\frac{2}{n} \)
由已知条件可以知道，\( ( \lceil \frac {a}{\lceil \frac{n}{m} \rceil} \rceil +\lceil \frac {n-a} {\lceil \frac{n}{m} \rceil} \rceil )\) 是正整数，因此可以将 \( n+2-\frac{2}{n} \)向下取整为\(n+1\)。
即需要n+1个处理器才能满足要求。
因此遇到这种问题的时候，要么增加一个处理器，要么计算每个处理器能处理的数量的时候在原先处理器数量减一的基础上计算。
你可能还喜欢下面这些文章
最近开始研究股票了，自己一个一个的去看，几千支股票完全看不过来啊，想着自己写一个程序，让程序来看股票吧！股票接口首先我们需要得到所有的股票代码，好在已经有网页帮我们列出了所有的股票名称和代码，地址是：http://quote.eastmoney.com/stocklist.html通过这个页面，就可以抓取了。抓取之后我们就可以存入mysql中，每一个股票可以存一张表，而每一张表中则可以存入股票的动态数据。这里我们只能获取到一些最简单的数据，一些更加详细的数据还需要获取，这里需要使用一个腾讯财经的接口http://qt.gtimg.cn/q=sz000858该接口为获取五粮液的股票数据，返回结果
当我们在谈到cgi的时候，我们在讨论什么最早的Web服务器简单地响应浏览器发来的HTTP请求，并将存储在服务器上的HTML文件返回给浏览器，也就是静态html。事物总是不 断发展，网站也越来越复杂，所以出现动态技术。但是服务器并不能直接运行 php，asp这样的文件，自己不能做，外包给别人吧，但是要与第三做个约定，我给你什么，然后你给我什么，就是握把请求参数发送给你，然后我接收你的处 理结果给客户端。那这个约定就是 common gateway interface，简称cgi。这个协议可以用vb，c，php，python 来实现。cgi只是接口协议，根本不是什么语言。下面图可以看到流程WEB服
在php中，没有多线程让编程变得简单。但在一些需要并发提升性能的场景下，显得有些无能为力，比如发起一些http请求。但好在curl扩展可以让我们“并发”去请求网络资源。利用这个特点，我们能做很多有趣的事情。最基础的，并发请求网络资源，提升处理速度。并发访问代码<?phpclass ConcurrencyHTTP { private $_requests; private $_callbacks; private $_currentIndex = 0; public function get($url, $header = array(), $timeout = 3
记得第一次了解中文分词算法是在 Google 黑板报 上看到的，当初看到那个算法时我彻底被震撼住了，想不到一个看似不可能完成的任务竟然有如此神奇巧妙的算法。最近在詹卫东老师的《中文信息处理导论》课上再次学到中文分词算法，才知道这并不是中文分词算法研究的全部，前前后后还有很多故事可讲。在没有建立统计语言模型时，人们还在语言学的角度对自动分词进行研究，期间诞生了很多有意思的理论。中文分词的主要困难在于分词歧义。“结婚的和尚未结婚的”，应该分成“结婚／的／和／尚未／结婚／的”，还是“结婚／的／和尚／未／结婚／的”？人来判断很容易，要交给计算机来处理就麻烦了。问题的关键就是，“和尚未”里的“和尚”也是
来自：码农翻身（微信号：coderising）作者：IBM刘欣我是一个线程，我一出生就被编了个号： 0x3704，然后被领到一个昏暗的屋子里， 这里我发现了很多和我一模一样的同伴。我身边的同伴0x6900待的时间比较长， 他带着沧桑的口气对我说：“我们线程的宿命就是处理包裹。把包裹处理完以后还得马上回到这里，否则可能永远回不来了。”我一脸懵懂，包裹，什么包裹？“不要着急，马上你就会明白了， 我们这里是不养闲人的。”果然，没多久，屋子的门开了， 一个面貌凶恶的家伙吼道：“0x3704 ,出来！”我一出来就被塞了一个沉甸甸的包裹，上面还有附带着一个写满了操作步骤的纸。“快去，把这个包裹处理了。”“
近来项目中使用websocket，于是来研究一番。websocket传输协议有两个部分，握手和数据传输握手GET / HTTP/1.1HOST: <IP>:<PORT> Sec-Websocket-Version: 13Sec-Websocket-Key: <KEY>Connection: keep-alive, UpgradeUpgrade: websocket之后服务端会返回类似下面的数据HTTP/1.1 101 Switching ProtocolsUpgrade: websocketConnection: UpgradeSec-WebSocket-A
布隆过滤器(bloom filter)介绍以及php和redis实现布隆过滤器实现方法
引言在介绍布隆过滤器之前我们首先引入几个场景。场景一在一个高并发的计数系统中，如果一个key没有计数，此时我们应该返回0。但是访问的key不存在，相当于每次访问缓存都不起作用了。那么如何避免频繁访问数量为0的key而导致的缓存被击穿？有人说， 将这个key的值置为0存入缓存不就行了吗？这是确实是一种解决方案。当访问一个不存在的key的时候，设置一个带有过期时间的标志，然后放入缓存。不过这样做的缺点也很明显：浪费内存和无法抵御随机key攻击。场景二在一个黑名单系统中，我们需要设置很多黑名单内容。比如一个邮件系统，我们需要设置黑名单用户，当判断垃圾邮件的时候，要怎么去做。比如爬虫系统，我们要记录下
相信包括在我的绝大多数人都用jQuery的$.get()，$.post()，$.ajax()方法用的很爽了，关于其原生的请求却很少去发掘，很多时候(比如用html5开发app的时候),我并不再需要jQuery，弄明白XMLHttpRequest用原生的就能很好的处理ajax了。首先，由于我的js是通过jQuery入门的，所以才会有这篇文章。从new一个对象开始var xmlhttp = new XMLHttpRequest();之后的请求，读取，出错等等各种处理都在xmlhttp这个对象里面啦第一个GET请求get请求简单，最适合入门操作啦。之前new了一个xmlhttp对象，这次我们就要对它
在一个高并发，但是数据量不大的系统中，使用Redis做数据库再好不过，结合Swoole，只需要很少的机器就能抗住很大的量。Redis大多数的应用可能都是当做缓存，当作为一个数据库用的时候，就必须要考虑持久化的问题了。持久化的意思就是将内存中的数据写到磁盘中，当再次重启之后，数据可以从磁盘中进行恢复，不会丢失。Redis持久化有两个策略，一个是RDB快照，一个AOF日志，不管是什么策略，最终的目的都是将数据保存在磁盘上，并不高深。只需要耐心的看看这两种策略，就能明白了。RDB快照从名字上我们就能知道这是RedisDB的缩写了，Redis快照是这样生成的，到了需要生成快照的时候，通过fork当前进
这篇文章是漫话中文分词算法的续篇。在这里，我们将紧接着上一篇文章的内容继续探讨下去：如果计算机可以对一句话进行自动分词，它还能进一步整理句子的结构，甚至理解句子的意思吗？这两篇文章的关系十分紧密，因此，我把前一篇文章改名为了《漫话中文自动分词和语义识别（上）》，这篇文章自然就是它的下篇。我已经在很多不同的地方做过与这个话题有关的演讲了，在这里我想把它们写下来，和更多的人一同分享。什么叫做句法结构呢？让我们来看一些例子。“白天鹅在水中游”，这句话是有歧义的，它可能指的是“白天有一只鹅在水中游”，也可能指的是“有一只白天鹅在水中游”。不同的分词方案，产生了不同的意义。有没有什么句子，它的分词方案是
赞赏
微信赞赏
支付宝赞赏
