xymscau-CSDN博客

原创用redis实现有优先级的"celery"

[新博客对应文章]【需求背景】对于异步任务处理，相信很多人首选celery，的确，celery处理异步任务非常强悍，使用简单，支持各种并发。但是，大家来看看我所遇到的一个应用场景：每次后台上传一个游戏母包，然后对这个母包处理（添加某种标识，比如id）生成多个游戏子包，其中有一些id号的包是要求尽快的处理的，剩下的可以闲时处理。这里就对要把一个母包分成两个任务来处理，其中一个是优先处理的，另一个

2016-01-24 01:20:20 2812

原创 meinheld为何比gevent高效？

XYM博客对应文章前言两者都是高性能的WSGI兼容的web服务器。既然是同种东西，必然有对比，网上有挺多benchmark，我也做过对应的benchmark，不过没有整理，这里推荐一下网上的一篇benchmark，能够看出meinheld的性能确实好得令人意外。那么为什么meinheld会比gevent性能高这么多呢？我们从底层实现来看看，他究竟做了一些什么。meinheld和gevent

2016-01-18 01:01:43 4234 2

原创后缀数组小结（markdown版）

这篇文章看的人还是挺多的，为了提升大家的阅读快感，特地写了这markdown版。希望大家会喜欢。还可以去我的新blog里看这篇文章【前言】后缀数组号称字符串处理神器，不过发现好多人都只会用模板，其实这不是我们学算法的本质，我们学习算法的本质应该理解其实现原理，并加以实现，特别是算法，更讲究的是一种思想。一年前的我也是只会用别人的模板，最近却静下心来，研究了一下后缀数组，自己写了一份自己的模板

2016-01-16 11:06:20 2962 2

原创 Reactor

Reactor ? Reactor设计模式在高性能I/O框架中随处可见，例如redis，tornado，gevent，libevent等。 Reactor可以翻译为反应器，是一种基于事件驱动的设计模式。那么它是如何运作的呢？其实很多设计模式都来源于生活中的一些常见的处理事情的方式。我们先来看一个例子：你和妹子去超级市场吃饭，发现很多人在排队，这时只需要让前台在电脑上填上你需

2016-01-16 10:07:35 982

原创 I/O多路复用

I/O多路复用技术系统内核缓冲I/O数据，当某个I/O准备好后，系统通知应用程序该I/O可读或可写，这样应用程序可以马上完成相应的I/O操作，而不需要等待系统完成相应I/O操作，从而应用程序不必因等待I/O操作而阻塞。select 网上很多讲解select函数的，这里围绕下图讲解一下select函数。函数构造： int select(int maxfd, fd_set

2016-01-16 10:00:59 514

原创 Meinheld 和 Gevent

XYM个人博客对应篇章 meinheld + gunicorn + flask 是神器啊，小小研究了一下。【Coroutine】 Coroutine：协程，又称微线程，纤程。协程的这种“挂起”和“唤醒”机制实质上是将一个过程切分成了若干个子过程，给了我们一种以扁平的方式来使用事件回调模型。优点：共享进程的上下文，一个进程可以创建百万，千万的coroutine。 pyth

2016-01-10 01:04:35 3074

原创 Redis

最近看了下huangz1990写的《redis设计与实现》，做一下笔记。内部数据结构【sds】struct sdshdr { int len; // buf已用长度 int free; // 剩余空间 char buf[]; // 保存字符串的char指针} 简单动态字符串：主要用于存储redis里面的字符串对象，不过只有这个对象存储的是字符串的时候，才是s

2016-01-10 00:45:39 513 1

原创 Linux 启动过程

最近安装了Arch，梳理一下linux启动流程。BIOS(MBR) 开机自检，通过通过BIOS加载CMOS，获取各种硬件信息。按照BIOS 的boot sequeuece顺序读取每一个存储设备的最前面512个字节,如果发现最后两个字节是0x55, oxAA,那么就找到了主引导扇区MBR。 MBR结构 HDD 上的位置代码用意 001-440 bytes

2016-01-10 00:41:55 516

原创 Arch

Arch原连接最近在装arch，这里记录了一些小的知识点。【分区表】 MBR(master boot record)：只能有4个主分区，一个拓展分区（也算一个主分区），展分区下可以建多个逻辑分区 GUID：只有主分区，数量不限【格式化】mkfs：mkfs.vfat -F32 /dev/sdxy #vfat32mkfs.ext4 /dev/sdxy #ext4swap:

2016-01-08 01:38:02 975

原创 GDCPC2013 总结 by SCAU_PH<7_Milk

这是我第三年省赛了，也是我acm生涯的第一块银，还是挺高兴的，比赛总会有些遗憾和惊喜，这次也不例外。先说说赛前训练吧，基本上是提前两个星期恢复整队的训练，做了6,7套题，然后就是重新对我模板上面的算法学习一遍，期间收获挺大的，温故之新啊，把一些以前只会用的模板理解了，并且自己学会了手写后缀数组。赛前试机，看到了明天在同一比赛场地的队伍，我们7楼最小的一个房间，目测我们房间就

2013-05-13 10:20:10 1517 1

原创后缀数组小结

后缀数组号称字符串处理神器，不过发现好多人都只会用模板，其实这不是我们学算法的本质，我们学习算法的本质应该理解其实现原理，并加以实现，特别是算法，更讲究的是一种思想。一年前的我也是只会用别人的模板，最近却静下心来，研究了一下后缀数组，自己写了一份自己的模板。我基本上是跟着连教的ppt来学习的，当然也少不了百度，先讲一下基本概念。(这里大量引用了连教的ppt)基本定义：子串注:串

2013-04-13 21:35:38 21949 4

原创 C#字符串梳理

1.驻留机制从老师给的资料 http://www.cnblogs.com/solan/archive/2012/08/03/CSharp07.html大概了解了C#底层对字符串的处理。字符串操作是最基本的操作之一，随便给一篇文章，里面的字符串就有很多，处理这样大量的数据，无论是空间还是时间我们都应该优化，在C#中，实现这个功能的就是驻留机制。驻留机制顾名思义，就是字符串常驻在某个地方，这个

2013-03-26 12:39:12 1164

原创算法理解-树状数组

树状数组是一种常见的计算优化方法，复杂度一般为nlog(n)，有着非常强大的功能，如统计前缀和，部分和，逆序对，dp优化等都可以解决，有人常说它是线段树的简化版，但是它也有一定的局限性，对于很多区间更新统计的问题，树状数组往往有心无力，鉴于大部分资料都以树的形式来讲解，刚开始我也是这样入门的，现在重新看一遍，发现有了更加深刻的理解，同时也感慨位运算的神奇以及对发明树状数组那个人的无比敬仰。

2013-01-17 23:33:03 1250

原创插头dp的几个模板

/*ural1519求经过所有可行点的哈密顿回路的个数括号匹配法,转移有点复杂,但是时间空间比较小*/#include#include#include#include#include#include#include#include#define LL long longusing namespace std;const int maxn=30001;int n,m,

2012-10-10 17:08:09 4508

终于切了第一道广义路径的题目，也确实感到比较复杂，最小表示法的优势也可以体现出来，因为这题，昨天的澡到现在才洗完，按照小hh的思路，用一条轮廓线记录联通状态，注意这里的轮廓线已经不是m+1啦，因为我们不需要左插头了，每个格子可以插至多4个插头，另外一条轮廓线表示当前的染色状态，这个要m+1因为还要保留左上格子的颜色，然后我们对于4个格子的颜色讨论，左，上，左上，当前，一共16中情况，8种是对称的，

2012-10-10 13:58:15 1492

原创 poj 3133 Manhattan Wiring 插头dp

这题的和上一份报告那题有点像，不过是确定了起点和终点，而且分别有两对，按照小hh的说法就是确定了起点和终点就相当于回路问题，另一边相当于虫洞连接起来，不过他说起点为左括号，终点为右括号，这还是有点问题的，昨晚思考了一下，如果，起点和终点的位置在其他位置，而不是边界，想想楼教男人8题的那题，如果位置在中间该怎么处理，左括号和右括号的设置方法肯定不可行，而是应该像上篇报告那题要独立插头，但是这个独立插

2012-10-08 18:52:32 1494

原创 zoj 3213 Beautiful Meadow 插头dp

求任意路径可以得到的最大权值和，这题和前面的题目不一样，插头的起点和结束点都不是确定的，所以要加一个插头表示单插头，表示起点或终点，接着就是恶心的转移，一直漏一个条件，后来看小hh的代码发现问题，终于过了。Run IDSubmit TimeJudge StatusProblem IDLanguageRun Time(ms)Run Memory(KB)

2012-10-07 19:00:27 1054

原创 hdu 4285 circuits

被这题卡了一整天，测试无数的数据，和对拍数据无误，几乎崩溃，后来重新敲时，发现自身写法的漏洞，果不其然，就是这个潜伏多年的bug，在ural，poj，以及我的vim下得出的数据都是一样的，我现在有些明白，为什么以前出现过在G++AC的题目，到C++是wa，应该是写法上的漏洞，编译器不同结果是不同的，改完这个bug，就AC了，rank排到第一去了。Run IDSubmit T

2012-10-05 15:54:57 822

原创 fzu 1977 Pandora adventure

这题比上题更简单，没有确定的起始点，是求回路，不过有些点是必须走的，那么这些点上必须有插头，否则不能转移，最后两个插头合并只能在所有的必须点扫描后。RunIDSubmit TimePIDLanguageTimeMemLen4665162012-10-05 12:52:391977GNU

2012-10-05 15:46:27 833

原创 hdu 3377 Plan

昨晚熬夜把它给切了，1y，这题可以相当于poj 1739+hdu 1964的加强版，我的做法是在最左边和最下边加上一层外围，权值全为0,然后就是插头dp了，不过要注意的是，题目不要求全部格子都经过，所以有一边插头的格子一定要有另一边，而没有插头的格子可以选择放两个插头，或者不放，另外要再注意下加的那两层的插头状态是确定的。Run IDSubmit TimeJudge S

2012-10-04 10:05:32 843

原创 zoj 3256 Tour in the Castle

这题是poj1739的改编版，在那份题解里我用了两种写法，这题的m很大，显然快速幂，BFS所有状态，不过矩阵也相当的大，我算了最大状态是114这么多,所以我优化了快速幂，预存幂矩阵，然后n^2快速幂，跑了600+,那个第一的200+ms是有减少状态么，还是有其他优化方法，我被他时间空间完胜了，Orz。Run IDSubmit TimeJudge StatusProb

2012-10-03 00:21:43 854

原创 hdu 1946 Pipes

这题基本上和上两题是一样的，不过这题是求所有路径权值最小，转移就直接带权转，每个可行状态取最小即可。Run IDSubmit TimeJudge StatusPro.IDExe.TimeExe.MemoryCode Len.LanguageAuthor68496812012-10-01 21:43:55Accepted19

2012-10-01 21:44:13 709

原创 poj 1739 Tony's Tour

楼教主的男人八题之一，这是我切的第一题，昨天搞定了括号表示法，今天趁热打铁，这题很容易想到把左下和右下两个格子连起来，构成一条哈密顿回路，就和上一题一样，不过这条路有一条必须经过的路径，我们需要特殊处理，做法有两种，我是添加了一层，然后特殊处理最后一层，后来发现小hh的解法说不用，又写了另一种解法，就是将最后一层的状态变成初始状态，然后从底往上dp，这种写法比较好，简单，而且状态比第一种写法少。

2012-10-01 17:33:32 1654

原创 ural 1519. Formula 1

插头dp第二题，debug了一个晚上，导致今天中秋都没有看到月亮，不过总算搞定了，思维习惯上打错个东西，找的好久，思路其实和前面轮廓线扫描差不多，但是要保证在最后一个合并最后两个插头，这样才能保证只有一条回路，单纯的二进制扫描法不能完成这个任务，所以要用括号表示法，cqd的ppt说的很明白，我就不说明啦，要用三进制表示，我们用二进制的两位来表示三进制，这样状态有2^(26)，太多啦，就算空间允许，

2012-10-01 00:24:03 885

原创 zoj 3466 The Hive II

小hh插头dp http://www.notonlysuccess.com/index.php/plug-dp-complete/ 的第二题。这题比第一题难处理一点，但是方法是一样的，用轮廓线扫一遍就好了，每个可行格子有且仅有两个插头，要分奇偶格子处理两条轮廓线就像这样，然后层层扫描即可Run IDSubmit TimeJudge Status

2012-09-28 10:53:27 908

原创 hdu 4249

一题挺恶心的dp，写了我140行，讲讲思路吧。状态：dp[len][i][j][k],表示三个数的第len位分别为i,j,k。限制条件：不能有前导0转移方程 if((i+j)%10==k)dp[len][i][j][k]+=dp[len-1][ii][jj][kk];其中ii+jj==kk||ii+jj+1==kkif((i+j+1)%10==k)dp[len][i][

2012-07-20 12:37:44 1013

原创 poj 1944

今天个人赛的一题，可惜当时不会做了，整场比赛吃蛋了，dp题都不会写，看来是太久没有切过dp了，言归正传，这题出题人是说线段树，然后山哥有个更牛b的解法，下面我就来讲讲这个解法，首先肯定要切开这个环，我们假设切开1和n那里，然后我们对于每一个要求连通的区间，有两种选择，要么顺时针，要么逆时针，假设顺时针距离为d那么逆时针距离就为n-d了，嗯，那么我们来分析几种情况，首先明确一点，先全部顺时针放在数轴

2012-07-19 23:39:31 1775 2

原创 poj 1156

这题是上午选拔赛的题目，卡了我好久，一开始暴力tle，后来用单调队列优化后就一直wa了，直到刚刚终于过了哪着别人的代码对拍的，发现题目说宽度最大100，数据中有超过100的，貌似是叫我们超过100的就不计，我打多个等号就变成101了，所以一直wa，改了之后就ac了，我是直接枚举两个边界化二维变成一维，然后用双指针O(n)扫一下，但是这里要快速找到min和max，所以要用单调队列优化，复杂度估算就是

2012-07-09 23:50:28 1539

原创 hdu 2827

这题卡了我一个晚上+一个早上，恶心的不想吐槽，一开始想法是直接高斯消元求解，但是wa了一个晚上，应该是哪里爆了int64，后来去看题目，发现了一个条件，就是m可以划分成很多个Pi相乘，100060105212012-05-28 14:14:02Accepted2827484MS704K2928 BG++Sadly_Snoopy#i

2012-05-28 14:32:20 1372

原创树DP训练专辑

No.1 hdu 2412 http://acm.hdu.edu.cn/showproblem.php?pid=2412题意：n个人形成一个关系树，每个节点代表一个人，节点的根表示这个人的唯一的直接上司，只有根没有上司。要求选取一部分人出来，使得每2个人之间不能有直接的上下级的关系，求最多能选多少个人出来，并且求出获得最大人数的选人方案是否唯一。分析：对于每一个点只有取或不去，但是有边

2012-05-23 21:36:48 1250

原创 2012SCAU校赛题

E. Prefix SumTime Limit : 6000/3000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)Total Submission(s) : 115 Accepted Submission(s) : 30Font: Times New Roman | Verdana | Georgi

2012-04-12 23:49:23 1567 2

原创 poj 3971

排位赛的一题，当时没有做出来，回来后看了大仙的代码才写出来的。大仙没有讲思路，我在这里说说吧。题意是给你个天平，你有2^0,2^1,2^2,2^3......2^n-1个砝码，问你称一个质量为m(二进制形式)的物体有多少种方法，注意天平左右两个盘都可以放砝码。状态设定：dp[i][0]表示第i个砝码不取的合法组合，dp[i][1]表示取了第i个砝码合法组合。1.如果说m中某一位为0

2012-03-20 20:11:32 817

原创 poj 1359

这题在比赛中一直wa，我的做法是把Y和N分成两个集合，然后枚举N里面的元素当成是坏的，判断剩下的条件有没有矛盾，结果一直wa。今天上课重新yy了一下这题，发现其实里面就只有三种情况。第一种情况：x y N z N，那么x一定数坏的，因为题中说了只有一个是坏的。第二种情况：N[x]>=2;表示有两个或两个以上的unit说x是坏的，那么x肯定是坏的。第三种情况：N[x]==1,N[y]==

2012-03-12 13:30:06 921

原创 hdu 2242

这题是双连通缩点，缩完点后原图会变成一棵树，这棵树的边就是割边，之后只要dfs一遍这颗树，取最小值即可，这题有个陷阱，就是有重边，显然如果有重边的话，这两个点可以构成双连通，我们只需标记一下是第几次走这条边即可，超过一次的话就是重边，要计算这条重边。Run IDSubmit TimeJudge StatusPro.IDExe.TimeExe.Memory

2012-03-06 16:29:15 1321

原创 hdu 1522

这题是一个匹配问题，一开始想用km做最佳匹配，但是图很大肯定会tle，思考无果后只能去搜搜题解，这是个经典问题吧。从http://www.cnblogs.com/drizzlecrj/archive/2008/09/12/1290176.html这里找到了相应的资料。稳定婚姻是组合数学里面的一个问题。问题大概是这样：有一个社团里有n个女生和n个男生，每位女生按照她的偏爱程度将男

2012-02-27 23:45:12 1243

原创 SCAU2011新生现场赛题解

今年新生实力很不错，一共10题有两个9题的，还有个是全1y的，极度ym，题目对于新生其实不算简单，包括一些算法题，二分，最短路，dp等，但都被一一解决了，很强悍啊，感慨之余，希望各位继续努力，你们还有时间，经过努力必有成绩。好了废话不多说，讲讲题解吧。A题数列排个序，二分搜索。B题連鎖模拟一下，用一个变量记录一下当前连锁结尾在哪一边，注意一下两边同等级大于等于小于的情

2012-02-26 11:13:42 1632

原创 hdu 3519

给你n个硬币，问你存在连续相同（正面or反面）长度>2的排列数。n很大，显然dp还要加上优化,ndp[i][j]表示前i个硬币最后j个是连续的。那么dp[i][j]只有两种转移方法：dp[i+1][j+1],dp[i+1][1];因为长度一旦超过2，我们就可以确定这个排列是符合要求的，后面的任何一位不管是正面还是反面都满足要求，所以就可以算出dp[i][3]*2^(n-i);一旦出

2012-02-06 23:03:49 972

原创 hdu 3579

蛋疼的一题啊，为了这题先去学了中国剩余定理（比较简单），然后又去学了拓展欧几里得，推了好久的公式，终于弄明白了，然后又去研究怎么求解线性方程组，终于把这题过了。拓展欧几里得我就不讲了，讲一下这题怎么解方程组的，网上只有代码，没有说明白怎么推的。我们先可以先找两个同余方程设通解为N,N=r1(mod(m1)),N=r2(mod(m2)),显然可以化为k1*m1+r1=k2*m2+r2;--->

2012-01-26 18:53:11 2150

原创 hdu 2874

今天终于遇到了tarjan算法，暑假的时候没有好好学习，今天终于弄明白了这个算法，只能感慨为什么人家的回朔用的这么完美，Tarjan可以解决强连通分量，LCA，等问题，基于dfs回朔思想，更新很巧妙，复杂度是O(n+m)，是很有效率的算法。时间是5000ms，直接vector水过。。。Run IDSubmit TimeJudge StatusPro.IDExe.

2012-01-14 15:37:48 1743 1

原创 hdu 1811

这题很考验代码能力，小弟不才，写了200+行还是wa，后来看人家的代码，vector的用法，今天学习了，写下报告记录下vector的用法，解法很简单，把集合缩成一个点，然后拓扑排序，集合用的是并查集。Run IDSubmit TimeJudge StatusPro.IDExe.TimeExe.MemoryCode Len.LanguageAuth

2012-01-08 21:31:10 1719

ACM模板byXYM

ACM竞赛与STL

空空如也