Archive

Posts Tagged ‘算法’

基础优化-最不坏的哈希表

December 8th, 2017 No comments

哈希表性能优化的方法有很多,比如:

  • 使用双 hash 检索冲突
  • 使用开放+封闭混合寻址法组织哈希表
  • 使用跳表快速定位冲突
  • 使用 LRU 缓存最近访问过的键值,不管表内数据多大,短时内访问的总是那么几个
  • 使用更好的分配器来管理 keyvaluepair 这个节点对象

上面只要随便选两条你都能得到一个比 unordered_map 快不少的哈希表,类似的方法还有很多,比如使用除以质数来归一化哈希值(x86下性能最好,整数除法非常快,但非x86就不行了,arm还没有整数除法指令,要靠软件模拟,代价很大)。

哈希表最大的问题就是过分依赖哈希函数得到一个正态分布的哈希值,特别是开放寻址法(内存更小,速度更快,但是更怕哈希冲突),一旦冲突多了,或者 load factor 上去了,性能就急剧下降。

Python 的哈希表就是开放寻址的,速度是快了,但是面对哈希碰撞攻击时,挂的也是最惨的,早先爆出的哈希碰撞漏洞,攻击者可以通过哈希碰撞来计算成千上万的键值,导致 Python / Php / Java / V8 等一大批语言写成的服务完全瘫痪。

后续 Python 推出了修正版本,解决方案是增加一个哈希种子,用随机数来初始化它,这都不彻底,开放寻址法对hash函数的好坏仍然高度敏感,碰到特殊的数据,性能下降很厉害。

经过最近几年的各种事件,让人们不得不把目光从“如何实现个更快的哈希表”转移到 “如何实现一个最不坏的哈希表”来,以这个新思路重新思考 hash 表的设计。

哈希表定位主要靠下面一个操作:

index_pos = hash(key) % index_size;

来决定一个键值到底存储在什么地方,虽然 hash(key) 返回的数值在 0-0xffffffff 之前,但是索引表是有大小限制的,在 hash 值用 index_size 取模以后,大量不同哈希值取模后可能得到相同的索引位置,所以即使哈希值不一样最终取模后还是会碰撞

第一种思路是尽量避免冲突,比如双哈希,比如让索引大小 index_size 保持质数式增长,但是他们都太过依赖于哈希函数本身;所以第二种思路是把注意力放在碰撞发生了该怎么处理上,比如多层哈希,开放+封闭混合寻址法,跳表,封闭寻址+平衡二叉树。

优化方向

今天我们就来实现一下最后一种,也是最彻底的做法:封闭寻址+平衡二叉树,看看最终性能如何?能否达到我们的要求?实现起来有哪些坑?其原理简单说起来就是,将原来封闭寻址的链表,改为平衡二叉树:

传统的封闭寻址哈希表,也是 Linux / STL 等大部分哈希表的实现,碰到碰撞时链表一长就挂掉,所谓哈希表+平衡二叉树就是:

将原来的链表(有序或者无序)换成平衡二叉树,这是复杂度最高的做法,同时也是最可靠的做法。发生碰撞时能将时间复杂度由 O(N) 降低到 O(logN),10个节点,链表的复杂度就是 10,而使用平衡二叉树的复杂度是 3;100个节点前者的时间是100,后者只有6.6 越往后差距约明显。

面临问题

树表混合结构(哈希表+平衡二叉树)的方法,Hash table – Wikipedia 上面早有说明,之所以一直没有进入各大语言/SDK的主流实现主要有四个问题:

  • 比起封闭寻址(STL,Java)来讲,节点少时,维持平衡(旋转等)会比有序链表更慢。
  • 比起开放寻址(python,v8实现)来讲,内存不紧凑,缓存不够友好。
  • 占用更多内存:一个平衡二叉树节点需要更多指针。
  • 设计比其他任何哈希表都要复杂。

所以虽然早就有人提出,但是一直都是一个边缘方法,并未进入主流实现。而最近两年随着各大语言暴露出来的各种哈希碰撞攻击,和原有设计基本无力应对坏一些的情况,于是又开始寻求这种树表混合结构是否还有优化的空间。

先来解决第一个问题,如果二叉树节点只有3-5个,那还不如使用有序链表,这是公认的事实,Java 8 最新实现的树表混合结构里,引入了一个 TREEIFY_THRESHOLD = 8 的常量,同一个索引内(或者叫同一个桶/slot/bucket内),冲突键值小于 8 的,使用链表,大于这个阈值时当前 index 内所有节点进行树化操作(treeify)。

Java 8 靠这个方法有效的解决了第一个问题和第三个问题,最终代替了原有 java4-7 一直在使用的 HashMap 老实现,那么我们要使用 Java 8 的方法么?

不用,今天我们换种实现。

Read more…

Categories: 编程技术 Tags:

AVL/RBTREE 实际比较

December 8th, 2017 No comments

网上对 AVL被批的很惨,认为性能不如 rbtree,这里给 AVL 树平反昭雪。最近优化了一下我之前的 AVL 树,总体跑的和 linux 的 rbtree 一样快了:

他们都比 std::map 快很多(即便使用动态内存分配,为每个新插入节点临时分配个新内存)。

项目代码在:skywind3000/avlmini
其他 AVL/RBTREE 评测也有类似的结论,见:STL AVL Map

谣言1:RBTREE的平均统计性能比 AVL 好

统计下来一千万个节点插入 AVL 共旋转 7053316 次(先左后右算两次),RBTREE共旋转 5887217 次,RBTREE看起来少是吧?应该很快?但是别忘了 RBTREE 再平衡的操作除了旋转外还有再着色,每次再平衡噼里啪啦的改一片颜色,父亲节点,叔叔,祖父,兄弟节点都要访问一圈,这些都是代价,再者平均树高比 AVL 高也成为各项操作的成本。

谣言2:RBTREE 一般情况只比 AVL 高一两层,这个代价忽略不计

纯粹谣言,随便随机一下,一百万个节点的 RBTREE 树高27,和一千万个节点的 AVL树相同,而一千万个节点的 RBTREE 树高 33,比 AVL 多了 6 层,这还不是最坏情况,最坏情况 AVL 只有 1.440 * log(n + 2) – 0.328, 而 RBTREE 是 2 * log(n + 1),也就是说同样100万个节点,AVL最坏情况是 28 层,rbtree 最坏可以到 39 层。

谣言3:AVL树删除节点是需要回溯到根节点

我以前也是这么写 AVL 树的,后来发现根据 AVL 的定义,可以做出两个推论,再平衡向上回溯时:

插入更新时:如当前节点的高度没有改变,则上面所有父节点的高度和平衡也不会改变。
删除更新时:如当前节点的高度没有改变且平衡值在 [-1, 1] 区间,则所有父节点的高度和平衡都不会改变。

根据这两个推论,AVL的插入和删除大部分时候只需要向上回溯一两个节点即可,范围十分紧凑。

谣言4:虽然二者插入一万个节点总时间类似,但是rbtree树更平均,avl有时很快,有时慢很多,rbtree 只需要旋转两次重新染色就行了,比 avl 平均

完全说反了,avl是公认的比rbtree平均的数据结构,插入时间更为平均,rbtree才是不均衡,有时候直接插入就返回了(上面是黑色节点),有时候插入要染色几个节点但不旋转,有时候还要两次旋转再染色然后递归到父节点。该说法最大的问题是以为 rbtree 插入节点最坏情况是两次旋转加染色,可是忘记了一条,需要向父节点递归,比如:当前节点需要旋转两次重染色,然后递归到父节点再旋转两次重染色,再递归到父节点的父节点,直到满足 rbtree 的5个条件。这种说法直接把递归给搞忘记了,翻翻看 linux 的 rbtree 代码看看,再平衡时那一堆的 while 循环是在干嘛?不就是向父节点递归么?avl和rbtree 插入和删除的最坏情况都需要递归到根节点,都可能需要一路旋转上去,否则你设想下,假设你一直再树的最左边插入1000个新节点,每次都想再局部转两次染染色,而不去调整整棵树,不动根节点,可能么?只是说整个过程avl更加平均而已。

比较结论

Read more…

Categories: 编程技术 Tags:

如何实现移动设备的通用手势识别?

April 19th, 2013 4 comments

移动设备多用手势进行输入,用户通过手指在屏幕上画出一个特定符号,计算机识别出来后给予响应的反应,要比让用户点击繁琐的按钮为直接和有趣,而如果为每种手势编写一段识别代码的话是件得不偿失的事情。如何设计一种通用的手势识别算法来完成上面的事情呢?

我们可以模仿笔记识别方法,实现一个简单的笔画识别模块,流程如下:

 

第一步:手势归一化

1. 手指按下时开始记录轨迹点,每划过一个新的点就记录到手势描述数组guesture中,直到手指离开屏幕。

2. 将gesture数组里每个点的x,y坐标最大值与最小值求出中上下左右的边缘,求出该手势路径点的覆盖面积。

3. 手势坐标归一化:以手势中心点为原点,将gesture里顶点归一化到-1<=x<=1, -1<=y<=1空间中。

4. 数组长度归一化:将手势路径按照长度均匀划分成32段,用共32个新顶点替换guestue里的老顶点。

 

第二步:手势相似度

1. 手势点乘:g1 * g2 = g1.x1*g2.x1 + g1.y1*g2.y1 + … + g1.x32*g2.x32 + g1.y32*g2.y32

2. 手势相似:相似度(g1, g2)=g1*g2/sqrt(g1*g1 + g2*g2)

 

由此我们可以根据两个手势的相似度算成一个分数score。用户输入了一个手势g,我们回合手势样本中的所有样本g1-gn打一次相似度分数,然后求出相似度最大的那个样本gm并且该分数大于某个特定阀值(比如0.8),即可以判断用户输入g相似于手势样本 gm !

Categories: 人工智能, 编程技术 Tags:

快速可靠协议-KCP

December 22nd, 2012 17 comments

KCP是一个快速可靠协议,能以比 TCP浪费10%-20%的带宽的代价,换取平均延迟降低 30%-40%,且最大延迟降低三倍的传输效果。纯算法实现,并不负责底层协议(如UDP)的收发,需要使用者自己定义下层数据包的发送方式,并以 callback的方式提供给 KCP。连时钟都需要外部传递进来,内部不会有任何一次系统调用。

整个协议只有 ikcp.h, ikcp.c两个源文件,可以方便的集成到用户自己的协议栈中。也许你实现了一个P2P,或者某个基于 UDP的协议,而缺乏一套完善的 ARQ可靠协议实现,那么简单的拷贝这两个文件到现有项目中,稍微编写两行代码,即可使用。

URL:https://github.com/skywind3000/kcp

Read more…

Categories: 编程技术, 网络编程 Tags: ,

体育竞技游戏的团队AI

August 5th, 2011 1 comment

很多人问游戏AI该怎么做?随着游戏类型的多元化,非 MMO或者卡牌的游戏越来越多,对AI的需求也越来越强了。而市面上关于 AI的书,网上找得到的文章,也都流于一些只言片语的认识,理论化的套路,和一些简单的 DEMO,离真正的项目差距甚远,无法前后衔接成一条线,更无法真正落地到编码。

国内真正做过游戏AI的少之又少,东拉西扯的人很多,真正做过项目的人很少,因为国内主要以MMO为主,RTS比较少,体育竞技类游戏更少,而从AI的难度上来看,应该是:MMO < FPS < RTS < 体育竞技。作为实际开发过AI的人,给大家科普一下,什么叫做硬派AI。

硬派游戏AI,不是虚无缥缈的神经网络,用神经网络其实是一个黑洞,把问题一脚踢给计算机,认为我只要训练它,它就能解决一切问题的懒人想法。更不是遗传算法和模糊逻辑,你想想以前8位机,16位机上就能有比较激烈对抗的足球游戏、篮球游戏,那么差的处理器能做这些计算么?

硬派游戏AI,就是状态机和行为树。状态机是基本功,行为树可选(早年AI没行为树这东西,大家都是hard code的)。大部分人说到这里也就没了,各位读完还是无法写代码。因为没有把最核心的三个问题讲清楚,即:分层状态机决策支持系统、以及团队角色分配。下面以我之前做的篮球AI为例,简单叙述一下:

 

何为分层状态机?

每个人物身上,有三层状态机:基础层状态机、行为层状态机、角色层状态机。每一层状态机解决一个层次的复杂度,并对上层提供接口,上层状态机通过设置下层状态机的目标实现更复杂的逻辑。

  • 基础状态机:直接控制角色动画和绘制、提供基础的动作实现,为上层提供支持。
  • 行为状态机:实现分解动作,躲避跑、直线移动、原地站立、要球、传球、射球、追球、打人、跳。
  • 角色状态机:实现更复杂的逻辑,比如防射球、篮板等都是由N次直线运动+跳跃或者打人完成。 image

每一层状态机都是通过为下一层状态机设定目标来实现控制(目标设定后,下层状态机将自动工作,上层不用关心动画到底播到哪了,现在到底是跑是跳),从而为上层提供更加高级拟人化的行为,所有状态机固定频率更新(如每秒10次),用于判断状态变迁和检查底层目标完成情况。最高层的角色状态机的工作由团队AI来掌控,即角色分配的工作。而行为状态机以上的状态抉择,比如回防,到底是跑到哪一点,射球,到底在哪里起跳,路径是怎样的,则由决策支持系统提供支持。

Read more…

Categories: 人工智能, 游戏开发 Tags: ,

[业余土制] 简易网络库 easenet

December 12th, 2010 3 comments

1. 跨平台网络库
2. 异步事件:kevent, iocp, epoll, poll, select封装
3. 内存管理:SlabPlus
4. 可靠协议:类tcp纯协议实现,包括重传机制,窗口管理,流量控制,拥塞处理。
5. 多种工具:缓存池,环状缓存,高性能hashmap等。

代码贴上:
Read more…

[业余土制] SlabPlus内存分配算法

March 8th, 2008 No comments

This is an enhanced SLAB algorithm implementation in application layer, which provides O(1) memory allocating and efficient memory recycling.

  • application layer slab allocator implementation
  • O(1) allocating / free: almost speed up 500% – 1200% vs malloc
  • re-implementation of page supplier: with new “SLAB-Tree” algorithm
  • memory recycle: automatic give memory back to os to avoid wasting
  • 30% – 50% memory wasting
  • platform independence

Since SUNOS has presented slab allocation theroy, many OSs have implemented slab in their kernel. But it requires kernel-layer interfaces such as page supply etc. So this library improves slab’s algorithm and brings the interfaces of slab into application layer.

项目位置:http://code.google.com/p/memslab/

原理叙述:

Read more…

Categories: 开源项目, 编程技术 Tags:

超越 STL-map/hash_map性能的DICT

November 23rd, 2007 1 comment

最近用纯C作了一个dict,根据试验,比 stl的 map快 2.3-2.5倍,比 hash_map快 1.3倍,主要用到的优化策略如下:

Read more…

Categories: 编程技术 Tags: