ITeye博客

知知为知知

home198979 · 共 152 篇文章

[置顶] Dijkstra算法(最短距离)

该算法由荷兰的一个牛人计算机科学家Edsger Wybe Dijkstra在1956年发现。 这套算法主要解决计算从一个点到其它的点的最短距离,而不是Floyd-Warshall算法的任意两点距离。 如图,现要计算出,从1号点到其它各点的最短距离,首先我还是转化成矩阵 由此可见1号点到其它点的初始距离为: 0 1 12 ∞ ∞ ∞ 很明显2号点是离1号点最近的点,那么1号点到2号点的最短距离肯定就是直达了。那我就将2号点作为“换乘点”,来计算下距离: 0 1 10 4 ∞ ∞ 这个过程有个专业术语“松弛”。2号点我也已经用了,那么4号点是离1号最近的点了,那再用它来松弛下: 0 1 8 4 …

2016-08-05 16:57 · 算法编程 · 评论(0)

[置顶] Floyd-Warshall算法(最短距离)

Robert W.Floyd和Stephen Warshall在1962年发表了Floyd-Warshall算法 如图,有1234,四个点,每个点都有一定的距离,比如1和2有2的距离,现在我想知道任意两个点的最短距离。 我先用“邻接矩阵存储法”将这个图转化为矩阵 竖坐标是出发点,横坐标是目的地,∞表示无穷大,也就是到不了,例如2到不1。有了这个矩阵,就可以用一个两维数组来存储。 现在切入重点:Floyd-Warshall算法。 拿从4到3来看,4到3直达为12,要想缩短,只有“换乘”。 我发现4还可以直达1,1换乘到3,这时距离为11,比直达要短。那有什么比这个还短的?到1时再换乘!不要走直…

2016-08-05 16:13 · 算法编程 · 评论(0)

[置顶] 玩转深度优先搜索算法

小时候玩游戏,有个BOMB人的游戏,把BOMB放在一个空地上,将怪兽炸死,如图: BOMB的威力只要不碰到墙壁,可以无限延长。那么我们应该把BOMB放哪里可以炸死最多的怪兽呢? 这个问题貌似很简单,一个一个地方试下不就知道了吗?是啊,那我们用代码来试下。 将图象转成字符,用#表示墙,用G表示怪兽,用.表示空地,最后得到的字符为: ############# #GG.GGG#GGG.# ###.#G#G#G#G# #.......#..G# #G#.###.#G#G# #GG.GGG.#.GG# #G#.#G#.#.#.# ##G...G.....# #G#.#G###.#G# #...G#G…

2016-08-01 17:32 · 算法编程 · 评论(2)

[置顶] 如何正确防御xss攻击

XSS:Cross Site Script,本来简写是css,但为了区别样式表的css,因此在安全领域叫做“XSS”。 XSS攻击通常是指黑客通过"HTML注入"篡改了网页,插入了恶意的脚本,从而在用户浏览网页时,控制用户浏览器的一种攻击。 一、HttpOnly防止劫取Cookie HttpOnly最早由微软提出,至今已经成为一个标准。浏览器将禁止页面的Javascript访问带有HttpOnly属性的Cookie。目前主流浏览器都支持,HttpOnly解决是XSS后的Cookie支持攻击。 我们来看下百度有没有使用。 未登录时的Cookie信息 可以看到,所有Cookie都没有设置Http…

2014-12-10 10:54 · web安全 · 评论(2)

[置顶] 构建WEB数据库扩展

已文大神可以略过。 当一台服务器已不能满足日益膨胀的站点时,就应该对数据库进行扩展。 一、主从复制 几乎所有的主流数据都支持复制,在mysql中,配置如下 1、开户服务器上的二进制日志(log-bin) 2、在主服务器和从服务器上分别进行简单的配置和授权。 具体可参看官方手册。 MySQL支持单向、异步复制,复制过程中一个服务器充当主服务器,而一个或多个其它服务器充当从服务器。主服务器将更新写入二进制日志文件,并维护文件的一个索引以跟踪日志循环。这些日志可以记录发送到从服务器的更新。当一个从服务器连接主服务器时,它通知主服务器从服务器在日志中读取的最后一次成功更新的位置。从服务器接收从那时起…

2014-12-05 09:42 · 分布式 · 评论(1)

[置顶] 六大Web负载均衡原理与实现

开头先理解一下所谓的“均衡” 不能狭义地理解为分配给所有实际服务器一样多的工作量,因为多台服务器的承载能力各不相同,这可能体现在硬件配置、网络带宽的差异,也可能因为某台服务器身兼多职,我们所说的“均衡”,也就是希望所有服务器都不要过载,并且能够最大程序地发挥作用。 一、http重定向 当http代理(比如浏览器)向web服务器请求某个URL后,web服务器可以通过http响应头信息中的Location标记来返回一个新的URL。这意味着HTTP代理需要继续请求这个新的URL,完成自动跳转。 性能缺陷: 1、吞吐率限制 主站点服务器的吞吐率平均分配到了被转移的服务器。现假设使用RR(Round …

2014-11-25 09:38 · 分布式 · 评论(3)

[置顶] 代码实现任意容量倒水问题

形象化设计模式实战 HELLO!架构 redis命令源码解析 倒水问题:有两个杯子,一个A升,一个B升,水有无限多,现要求利用这两杯子装C升的水。 想必很多人都可能被问到过这个问题,问题虽然简单的,但是要费些脑子。这个问题显然是个逻辑问题,那么就肯定能够用程序来实现。 现在我假设A=3,B=5,C=4。 大脑的运算过程: 第一步、把3装满,或把5装满(只有这两种选择吧)。 第二步、把装满的杯子的水倒入空杯子(没有人会把第二个杯子也装满吧)。 第三步、两个杯子的水做运算得出一个D(D不能和A、B相等,如果D等于C就成功啦) 第四步、跟第一步相同 第五步、跟第三步相同 。 。 。 直到D等于C就…

2014-11-05 11:49 · 算法编程 · 评论(1)

[置顶] python实现数据的多维缩放(集体智慧编程)

多维缩放 可以为数据集找到一种二维表达形式。算法根据每对数据项之间的差距情况,尝试绘制出一幅图来,图中的各数据项之间的距离远近,对应于它们彼此间的差异程度。 以 分类聚集算法 中的数据为例 第一步:计算所有数据项两两间的实际距离(可参考 皮尔逊算法 或 欧几里德算法 ) 第二步:将数据项随机放置在二维图上。 第三步:针对每两两构成的一对数据项,将它们的实际距离与当前在二维图上的距离进行比较,求出一个误差值 第四步:根据误差的情况,按照比例将每个数据项的所在位置移近或移远少许量。(每一个节点的移动,都是所有其它节点施加在该节点上的推或拉的结合效应。) 第五步:重复第三步、第四步(节点每移动一次…

2014-03-27 17:26 · 算法编程 · python · 评论(0)

使用nginx部署django应用

1、通过pip安装uwsgi $sudo yum install python-devel $sudo yum install python-pip $sudo pip install pip --upgrade $sudo yum install libpcre3 libpcre3-dev $sudo yum install zlib1g-dev 如果安装版本错误,先卸载: $pip uninstall uwsgi $sudo yum remove uwsgi python 版本最好是python 2.7.* pip的版本应该是最新版本。 查看pip 版本: $ pip --version…

2016-02-25 11:05 · python · 评论(0)

redis之列表命令源码解析

形象化设计模式实战 HELLO!架构 redis命令源码解析 一、Lpush,Rpush t_list.c void lpushCommand(redisClient *c) { pushGenericCommand(c,REDIS_HEAD); } void rpushCommand(redisClient *c) { pushGenericCommand(c,REDIS_TAIL); } lpush插入列表头部,rpush插入列表尾部 void pushGenericCommand(redisClient *c, int where) { int j, waiting = 0, push…

2014-11-18 09:42 · redis/memcache · 评论(0)

redis之哈希命令源码解析

形象化设计模式实战 HELLO!架构 redis命令源码解析 前面讲过了字典和压缩列表的实现,redis的哈希数据就是存储在这两种结构之中的,如果对这两种结构都非常清楚了,那么对哈希命令的实现的理解将会非常简单。 一、hset void hsetCommand(redisClient *c) { int update; robj *o; // 取出或新创建哈希对象 if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return; // 如果需要的话,转换哈希对象的编码 hashTypeTryConversion(o,c-…

2014-11-14 10:07 · redis/memcache · 评论(2)

redis之压缩列表源码剖析

形象化设计模式实战 HELLO!架构 redis命令源码解析 用过Redis的应该对其哈希命令不陌生,在探索其实现之前,先得了解Redis的一个内部映射数据结构——压缩列表。 1、zipList的结构 找到ziplist.c文件,在代码注释中: * The general layout of the ziplist is as follows: * <zlbytes><zltail><zllen><entry><entry><zlend> //注意这三个定义,新建时会使用。 #define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl))) //32位unsigne…

2014-11-04 09:59 · redis/memcache · 评论(0)

redis之字符串命令源码解析(三)

形象化设计模式实战 HELLO!架构 redis之字符串命令源码解析(一) redis之字符串命令源码解析(二) 前面已经将set get命令的原理与过程作了详细的解析,下面对一些常用的命令做一些简单讲解,前提是前面的已经明白。 1、append方法解析 t_string.c中的appendCommand方法: void appendCommand(redisClient *c) { size_t totlen; robj *o, *append; // 取出键相应的值对象 o = lookupKeyWrite(c->db,c->argv[1]); // 如果键值对不存在 if (o == …

2014-10-31 09:40 · redis/memcache · 评论(0)

redis之字符串命令源码解析(二)

形象化设计模式实战 HELLO!架构 在redis之字符串命令源码解析(一)中讲了get的简单实现,并没有对如何取到数据做深入分析,这里将深入。 1、redisObject 数据结构,以及Redis 的数据类型 (一)中说set test "hello redis",“hello redis”会最终保存在robj中,redisObject是Redis的核心,数据库的每个键、值,以及Redis本身处理的参数都表示为这种数据类型,其结构如下: /* The actual Redis Object */ /* * Redis 对象 */ #define REDIS_LRU_BITS 24 #def…

2014-10-30 09:32 · redis/memcache · 评论(0)

redis之字符串命令源码解析(一)

形象化设计模式实战 HELLO!架构 在redis的使用中,set/get无疑是使用最普遍的命令,我先telnet连接运行看看 先看get命令,获取一个key服务器返回了两行内容,是"$3\r\n123\r\n"(\r\n为换行符),不难发现3就是“123”的长度,redis的官方文档get返回值为: Bulk string reply : the value of key , or nil when key does not exist. 可以点击超链接看里面的解释,发现确实如此,那现在就从源码看看get是如何获取数据的。 1、内部数据结构之sds(Simple Dynamic Strin…

2014-10-28 09:47 · redis/memcache · 评论(0)