最新 | 最热门 | 最高评价
^..^

+0  局部敏感哈希介绍

Tag: 算法
鸟窝 发于 2018年08月16日 19:56 | 点击: 165 | 展开摘要
传统的Hash当源数据有些许的变化的时候生成的哈希值差异也非常的大， 比如：

1
2
3
4
5
6
7
8
9
10

func main() {
s1 := []byte("你好世界")
s2 := []byte("你好,世界")

hash1 := md5.Sum(s1)
hash2 := md5.Sum(s2)

fmt.Println(hex.EncodeToString(hash1[:]))
fmt.Println(hex.EncodeToStrin

查看全文: http://www.udpwork.com/item/17005.html
---

+0  数学运算的实时编译及 Lua 中的一点奇技淫巧

Tag: lua与虚拟机 | 算法 | 优化与技巧
云风 发于 2018年07月12日 11:24 | 点击: 391 | 展开摘要
我为 3d engine 项目设计的向量运算库 已经用了一段时间了。在使用过程中也一直在改进 。从一开始，我就考虑过，这个库的设计主要考量是减少 lua 和 C 交互间的开销，提高内聚性。而易用性方面，计划再上面再做封装。这段时间继续在想怎样从更自然的表达形式转换到这个库的逆波兰指令流上。

大致的方向有两个：

其一，实现一个小语言，用字符串输入表达式组。

其二，利用 Lua 已有的语法解析设施，把 lua 的一个函数翻译成对应的数学运算指令流。

两者都可以看成是一种

查看全文: http://www.udpwork.com/item/16947.html
---

+0  Ericsson Texture 压缩贴图 EAC 的编码器

Tag: 技术 | 算法 | 优化与技巧
云风 发于 2018年05月22日 15:13 | 点击: 459 | 展开摘要
最近在做新引擎 UI 模块的工作。汉字字体纹理需要占比较大的一张贴图，考虑到这张贴图只需要用一个通道就够了，所以我决定使用压缩贴图。在手机设备上，GL_COMPRESSED_R11_EAC 是一个不错的选择。

EAC 是 Ericsson 提出的对单通道贴图的压缩方案，现已进入 OpenGL 的官方标准。它通常会结合 ETC2 一起使用。ETC2 负责 RGB 部分，EAC 负责 Alpha 通道。偶尔也可以单独使用。它会将每个像素解码为 [0,2047] 的整数，有 11

查看全文: http://www.udpwork.com/item/16856.html
^..^

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

Tag: 编程技术 | 算法
skywind 发于 2017年12月08日 19:14 | 点击: 824 | 展开摘要
哈希表性能优化的方法有很多，比如：

使用双 hash 检索冲突

使用开放+封闭混合寻址法组织哈希表

使用跳表快速定位冲突

使用 LRU 缓存最近访问过的键值，不管表内数据多大，短时内访问的总是那么几个

使用更好的分配器来管理 keyvaluepair 这个节点对象

上面只要随便选两条你都能得到一个比 unordered_map 快不少的哈希表，类似的方法还有很多，比如使用除以质数来归一化哈希值（x86下性能最好，整数除法非常快，但非x86就不行了，arm还没有整数

查看全文: http://www.udpwork.com/item/16530.html
---

+0  AVL/RBTREE 实际比较

Tag: 编程技术 | 算法
skywind 发于 2017年12月08日 18:37 | 点击: 595 | 展开摘要
网上对 AVL被批的很惨，认为性能不如 rbtree，这里给 AVL 树平反昭雪。最近优化了一下我之前的 AVL 树，总体跑的和 linux 的 rbtree 一样快了：

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

项目代码在：skywind3000/avlmini

其他 AVL/RBTREE 评测也有类似的结论，见：STL AVL Map

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

统计下来一千万个节点插入

查看全文: http://www.udpwork.com/item/16529.html
^..^

+0  functor applicative 和 monad

Tag: 算法
鸟窝 发于 2017年10月05日 22:30 | 点击: 1061 | 展开摘要
Monad 函数式编程中的一个概念， 在 Haskell 和 Scala 语言中用的比较多。

这个概念来源于数学中的范畴学，过于学术化，我看国内的文章介绍的很多，但是准确、清晰而简要的介绍的文章却没有看到。

我也不准备介绍，因为我对它的理解也不够深，这里引用 Functors, Applicatives, And Monads In Pictures一文中的图片和总结，来加深一下自己的理解。

functors: you apply a function to a wra

查看全文: http://www.udpwork.com/item/16443.html
---

+0  支持部分共享的树结构

Tag: 算法 | 优化与技巧
云风 发于 2017年06月18日 16:23 | 点击: 696 | 展开摘要
因为图形引擎中的对象天然适合用树 (n-ary tree) 表达，所以它在图形引擎中被广泛使用。通常，子节点会继承父节点的一些状态，比如变换矩阵，在渲染或更新的时候，可以通过先序遍历逐级相乘。

在 PC 内存充裕的条件下，我们通常不必考虑树结构储存的开销，所以大多数图形引擎通常会为每个渲染对象独立生成一个树结构，比如 Unity 中的 GameObject 就是这么一个东西。在 Ejoy2D 中，从节约内存的角度考虑，把树节点上的一部分可共享的状态信息（不变的矩阵、纹理坐标

查看全文: http://www.udpwork.com/item/16307.html
^..^

+0  浅谈 WHR 全历史排名

Tag: 算法
云风 发于 2016年03月16日 21:25 | 点击: 965 | 展开摘要
这几天 AlphaGo 4:1 战胜了李世石，围棋积分网站 给了 AlphaGo 一个世界排名。在 3:1 的时候是世界第四，4:1 后上升到了世界第二。

我很好奇这个网站是如何给棋手打分的，便顺着链接指引翻了下 wikipedia 读了几篇 paper 。

下面是我的一些理解，由于我的数学基本功不太扎实，难免有错误，所以有兴趣的同学最好自己读论文 。

首先，如何定义等级分这个东西？

在一对一竞技类游戏中，假设规则是公平的，对战双方如果都能给出最优策略，那么胜负概率是

查看全文: http://www.udpwork.com/item/15333.html
---

+0  “残酷”的事实

Tag: Commentary | code review | 吐槽 | 学校 | 工作 | 算法 | 编程 | 面试
四火 发于 2015年10月21日 14:21 | 点击: 1409 | 展开摘要
下面这些文字来自我在知乎的回答：“在真实工作中的编程是怎么样的，与学校里有什么不同？”。

入行愉快。

首先，一言以蔽之，用两个字来概括，就是“残酷”，但是，好在是加引号的。有的不但残酷，还很无奈；有的则是在残酷的同时，还很有趣。搞工程和学校里的象牙塔大不相同，这也许老早就知道，但是绝对不是七八年前我想象的模样。你可以把它当成我没睡醒的呓语，也可以当成我喝多的胡话，或者是心情太差的时候写的吐槽檄文。反正，它们就在那里，事实就在那里。

总的来说，学校里面编程，或者在工作之余

查看全文: http://www.udpwork.com/item/14694.html
---

+0  lua 分配器的一些想法及实践

Tag: lua与虚拟机 | skynet | 算法
云风 发于 2015年07月28日 14:33 | 点击: 949 | 展开摘要
从周末开始, 我一直在忙一个想法。我希望给 skynet 中的 lua 服务定制一个内存分配器。

倒不是为了提升性能。如果可以单独为每个 lua vm 配置一个内存分配器，自己调用 mmap 映射虚拟内存，就可以为独立的服务制作快照了。这样可以随时 fork 出子进程，只保留关心的 vm 的内存快照。主要可以有三个用途：

可以在快照上做序列化，并把结果返还父进程。通常做序列化有一定的时间代价，如果想定期保存的话，这个代码很可能导致服务暂停。

可以利用快照监控检查泄露。定

查看全文: http://www.udpwork.com/item/14443.html
^..^

+0  对象到数字 ID 的映射

Tag: skynet | 算法
云风 发于 2015年04月10日 14:37 | 点击: 987 | 展开摘要
skynet 中使用了一个 hash 表结构来保存服务和 32bit 数字地址的映射关系。

一个 skynet 的服务，其实是一个 C 对象。在有沙盒的系统中，尤其是并行构架，我们很少直接用 C 对象指针来标识一个 C 对象，而是采用数字 id 。用数字做 handle 可以让系统更健壮，更容易校验一个对象是否还有效，还可以减少悬空指针，多次释放对象等潜在问题。比如，操作系统为了把用户程序隔离在用户态，像文件对象就是用数字 id 的形式交给用户程序去用的。

和操作系统通常

查看全文: http://www.udpwork.com/item/14082.html
---

+0  如何拼接 PVR 压缩贴图

Tag: 算法 | 优化与技巧
云风 发于 2015年01月08日 18:41 | 点击: 1231 | 展开摘要
2d 游戏通常都用到很多图素，由于显卡硬件特性，我们又不会把单个图素放在独立贴图中。这样会导致渲染批次过多。在移动设备上，非常影响渲染效率。

所以，游戏运行时，这些图素一般都会合并在很少几张贴图上。要么采用离线合并的方式（利用 texture packer 这样的工具），或者在运行时使用装箱算法。

最近，朱光同学一直在为 ejoy2d 编写运行时合并图素的模块。今天我们讨论了一下他做的诸多尝试。

为了提高贴图利用率，我们可以把大的不规则图素先拆分成小块，然后再组合起来。

查看全文: http://www.udpwork.com/item/13756.html
|<<<1234567>>>| 一共11页, 132条记录