The KosWu's Blog

Keep Geeking and Hacking

04
Dec

十分钟用Python创建一个Echo Server

近日想玩一下网络编程方面,但是实在不想用C去写笨重的代码,于是就使用python写了一个简单的TCP Echo Server。代码很少,标题虽然写了十分钟,但是我自己磕磕碰碰还是折腾了一天(标题党了)


什么是Echo Server

Echo Server一般是运行在7端口的一项服务,其一大特点就是会返回从客户端接收到的消息。(通俗来说就是复读机)

Echo Server能用来做什么

Echo Server是最容易实现的网络服务之一,可以用来学习Socket编程的一些基本知识,还可以用来检测客户端与服务器之间的连通性,丢包率,连接速度和传输速度。


实现思路

一开始我觉得应该挺容易的,快速的从网上找到了一些相关的代码,采用Ctrl C V大法,但是却发现有很多问题,最终还是自己动手才写出一个像样的东西。

首先第一步,我们得监听一个端口,调用python的socket模块,让其绑定在一个端口,监听TCP连接。

#使用IPV4和TCP连接,监听端口程序
tcpSocket = socket.Socket(socket.AF_INET, socket.SOCK_STREAM)
tcpSocket.bind((HOST, PORT))

第二步,我们检测是否有客户端连接上,如果连接上了,就将对这个客户的处理逻辑单独放到一个线程里跑(这是坑最多的一部,看了网上很多代码,要么就是直接一个线程,无法处理多客户,要么就是所有客户端共用一个处理线程,当数据量较大时就会出现问题)

while True:
  clientSocket, clientAddr = tcpSocket.accept()
  t = threading.Thread(target = handle, args = (clientSocket, clientAddr), daemon = True)
  t.start()

最后我们只要在线程处理逻辑中,编写相关的回显逻辑,就可以了。

while True:
  data = clientSocket.recv(BUFSIZE)
  if not data:
    break
  clientSocket.send(data)
clientSocket.close()

当然上面为了演示,对实际代码做了很多精简,完整的代码在下面(需要科学上网):

服务端
客户端
(客户端为一个类似nc的小程序)

21
Aug

关于多纳什均衡解的一点想法——由弹丸论破想到的

现实中很多东西都可以看成一场博弈,但很多时候并没有那么理想化罢了,

最近咸鱼了一把, 把PSV翻出来,稍微玩了一下《弹丸论破》系列的最新作《新弹丸论破V3:大家的自相残杀新学期》
弹丸论破

弹丸论破V3的宣传图


阅读全文»

15
May

集各家之长,异常书之著,壁即可破矣

《巴赫、埃舍尔、哥德尔——集异璧之大成》读后感

最近花了一个多月的零碎时间了读这部著作,读毕,有醍醐灌顶之势。遂记拙文一篇,以表观感。

当我看到这本书的时候,一种很怪异的心情了浮上来。巴赫、埃舍尔、哥德尔,这三个看似风牛马不相及的人物怎么能写到一本书里?并且还是一本讲人工智能的书籍里面。这本书从一个简单的形式系统逐渐深入,并且提出了许多这三个人之间的联系,虽然我觉得很多也许是作者某种意义上故意设置的同构,但是这样一种解释方式也让我对这三个人、甚至是这三门学科——音乐、美术、数学,有了新的看法。

鉴于这本书的精妙之处,我难以一一解读,就谈谈我认为的这本书最令人深刻的问题吧。那就是——什么是智能?

在写这本书的年代,人工智能对于现实生活的影响远远没有现在那么高,那个时代,国际象棋和围棋还是机器不能战胜人类的领域。但是作者已经有了如此詹前的想法,可谓一奇也。有人说机器永远不可能拥有智能,因为他只能计算。但是人的神经元也是符合各种各样的物理规则的,神经元也只能按照固定的模式运行。书中提到的一点,就是由一个无智能的复杂系统可能表现出智能。我认为不但是一个无智能的系统,即使是一个智能的系统,也会表示出一定的智能性,因为具有智能的团体,在一定程度上是可以通过将个体的智能退化而获得上层智能的。《乌合之众》中曾经这样描述过 :“群体的行为总是表现为排斥异议、极端化、情绪化和低智商。”这也许是当一个团体,表现出一定的意识所需要的,将个体的意识行为退化的一种表现。

举个例子,著名过气老婆歌姬“初音未来”,其本身是一个由创作者创作的一个虚拟形象,但是在其知名度提升之后,却能一呼百应,让众多的爱好者加入进来,创作大量的同人作品。在大家创作同人作品的时候,其实就是对这个本不存在的人物的一种形象补全,这个形象由于众多同人的加入逐渐变得丰满起来。说好的初音平胸呢??“初音未来”这个形象,从宏观来看,仿佛变得拥有了自己的意识一般,“初音未来”的演唱会,无论在哪里举办,都会有那么多人去捧场,这种现象有时候真的会让我们忘记了这个“初音未来”只是一个不具意识的创作形象罢了,是众多的粉丝和同人作者,赋予了这个形象以生命。肥宅的老婆是由众肥宅的意识组成的???

有趣的是,这种赋予生命的现象并不一定需要这些意识的联系,只要一群有着共同目标的人就会产生这种现象。其在一部21世纪初的动画《攻壳机动队:Stand Alone Complex》中也有提到,荣格所描述的集体无意识似乎在这种时候展现了出来。

在不久之前,Google的Duplex在开发者大会上向我们展示了AI与人通话的场景,其对话自然的程度,让与其对话的人都没能识别出这是一个AI,在特定场景之下,人类已经区别不出AI个真实人类的区别。就我个人认为,AI的发展目前又进入了一个新的风口,其已经具备一定的“智能”,但是距离人类的智能水平还有不少差距。我们应当抛弃那种“人类沙文主义”的包袱,正确看待其发展,并使AI的进一步智能而努力!

16
Apr

哈希表简介与其优势

在对二叉树进行学习之后,相信每个人都会对于其精妙和最坏情况下仍然能保证线性对数级别时间复杂度的增删改查赞叹不已。其用来实现符号表(存储键值对)是一种较为高效的实现。

在没有学习哈希表之前,如果我告诉你,有一种数据结构,可以做到常数时间级别的增删改查,你一定不会相信。但是哈希表做到了,有这么高效的数据结构怎么能够不对其有了解呢?这次我们就来谈谈哈希表这种数据结构的魅力所在。

要了解哈希表,首先我们得来看一看这个哈希函数是什么东西。函数,其实就是一个映射,将所有在定义域的值映射到值域范围内。有时候我们需要对任意长度的信息,提取出信息的“指纹”,这个指纹在一定程度上反映了信息的内容,但是占用空间大大缩小。此时我们就要设计一个函数,其定义域为信息可能出现的所有空间,而值域则为需要”指纹”的大小。当这个函数可以用来完成上述用途时,这个函数就被称为哈希函数,哈希函数输出的结果被称为哈系值。一些著名的哈希函数有MD5、SHA-1、SHA-2等。

有了哈希函数,我们就可以利用哈希函数的映射,将任意长度的键映射到一个合理的区间内。试想创建一个数组,数组的下标为键的哈希值。数组的内容即为键值对的值,当我们已知键,要对值进行查找时,只需要对键取哈希,就可以在常数时间内获取到值的内容。

在哈希表的实现中,我们设计的哈希函数应该考虑的重点有如下几个

  1. 尽可能让输入中的每一位都对输出结果造成影响,减少碰撞的发生
  2. 计算尽量简单,否则哈希函数的计算也会对运行时间造成极大的影响
  3. 输出范围应当尽可能的可控

因为2的原因,我们不得不抛弃MD5和SHA这些著名的哈希函数,并且这些函数也很难自己控制输出的数据范围。实现哈希函数的方法不止一种,这里介绍比较常用的一种方法——除留余数法。

这里其实可以采用一种简单的运算来实现这个哈希函数——模运算。相信学过一点编程语言的朋友都知道,对某个数取模就是除以某个数求余数。假设我们需要0-97的哈希范围,无论多大的数,只需要对97取模,就可以获得一个在0-97之间的数,但是要注意,当我们采用的基数不是素数时,就会导致输出仅仅依赖于输入的后几位数,不满足1的情况发生。所以在使用这种方法作为哈希函数的过程中,应当选择合适的基数。


哈希碰撞的解决方法

我们知道哈希函数由于对信息进行了缩短,所以导致了有可能出现碰撞的存在,这就好像出现了两个名字一样的“张三”,当我们说,张三坐在某某位置上时,并不知道到底是哪个张三真正坐在位置上。这里有两种解决方案:拉链法和线性探测法

拉链法是将具有相同哈希值的函数放到一个链表里,用一个链表的数组来存放所有键值对。而线性探测法则是采用两个数组,一个放键,一个放值,存放遇到冲突的时候,从哈希值对应的位置开始往下遍历,直到遇到一个空的位置进行插入。具体的实现中应当使用哪一种应该很据不同需求选取。

23
Mar

谈谈红黑树(二)

了解了2- 3-树的插入操作后,便可以正式开始介绍左倾红黑树了。2-3 树好是好,但是由于其是用两种不同类型的节点构成的,实现起来不方便。我们可以用一个方法巧妙的替代2-3树中的3节点,就是用两个普通的2-节点,通过一种特殊的链接——红链接来连接起来,来表示一个3-节点。

当然,要表示出这个红链接,需要给每个节点加入一个额外的属性——颜色,红黑树中每个节点都是两种颜色中的一种——黑色和红色。节点的颜色表示指向该节点的链接颜色。根节点与其他节点不同,其始终为黑色。大家应当注意到,左倾红黑树的“左倾”意味着只能够存在向左的红连接,而不能存在向右的链接。

在红黑树中,为了在保证树的平衡性的同时,还能够保证红链接的合法性,我们采用一个balance函数,其调用rotate_left(左旋)和rotate_right(右旋)以及flip_color_black方法来实现这些变换。flip_color_black和flip_color_red的作用在于将一个子节点全为红色的节点染红,并将其子节点染黑,以及上述操作的反向。其实现已经在文后的代码中给出,这里不再细说。关于树的旋转变换,参见下图。

树旋转

树的插入操作和2-3树类似,首先找到插入位置,插入,然后沿查找路径向上依次执行balance方法(参见实现中的put方法)

再来说说删除最小键,可以在向左遍历的过程中,让红黑树暂时变得“不严谨”,也就是说,暂时允许等价的4-节点出现。并且需要做一个变换,保证当前查找的位置一定是3-节点或者是4-节点,这样当查找到底部的时候,就可以保证当前节点不是2-节点,实现中使用flip_color_red和树的旋转操作来实现,此时只需要直接从树中删去最小节点,然后沿着路径向上调用balance方法恢复树的性质。这里要注意的是,如有需要,我们可以临时改变根节点的颜色为红色,这样就能保证在变换中,父节点的颜色一定是红色。
删除最大键与最小键同理,但因为子节点在右边,需要做一些额外的变换,这里留给读者去思考,实现见代码。

现在遇到了最难的操作——删除指定键,但有了前面删除最大最小键的铺垫,问题也就迎刃而解了。与删除最大最小键时类似,沿着查找路径进行4-节点变换,当找到需要删除的键时,可以分为三种情况:

  • 没有子节点

这种情况非常容易处理,由于可保证当前不是2-节点,直接删除该节点就行

  • 只有一边的子节点

这种也比较简单,只需要将子节点接上原来的链接就行

  • 同时拥有左右节点

此时需要使用类似二叉搜索树中的方法,将该节点与他的右分支中的最小节点交换,此时又将问题转换成了一个删除右分支中的最小键的问题。

最后附上我的实现代码:https://gist.github.com/Koswu/3383ec7242a997dae163c9af922b1a56