牛牛C | Qmsheng Blog

直观的表现 PRNG 周期性

无图无真相。真的真，真出声

我在前面的一些文章中介绍过：Lua 随机数算法用的是 LCG（32位的随机数，周期最多为232）; LuaJIT 用的是 LFSR，周期达到 2223。下面是我分别用 Lua 和 LuaJIT 的随机数填充一个位图，代码： #!/usr/bin/env lua -- Draws the B/W image with lua-gd local gd = require "gd" loca...

Posted by qmsheng on December 13, 2017

重新认识 randomseed

原生 Lua 的 randomseed 是不支持浮点数的

在之前的文章中，我写过这样的测试用例： local seed = 123456 for i=1,2 do math.randomseed(seed + (i-1)/10) local num = {} for j=1,10 do table.insert(num, math.random(100)) end print(table.c...

Posted by qmsheng on October 27, 2017

Lua 中的随机数

随机数生成对我们太重要了，我们不能让它随机生成

Lua 随机数算法用的是 libc 中的 rand, 也就是 LCG。然而这个算法的随机性一般。尤其是在一些平台上，当随机种子变化非常小的时候，产生的随机数变化也非常小。这样再经过 Lua 的精度取舍之后，产生的随机序列仍然很相似（伪随机的结果变成可预知性）。 lua-l 上也讨论过这个问题 msg00564，lua 的作者之一 lhf 给出的解决方案是先弹出前面几个看起来「不怎么随机」的...

Posted by qmsheng on October 26, 2017

正确认识随机数

北京车牌摇号的算法是公平的

前一阵子我去参加了 OpenResty Con 2017, 来自 KONG 的 Thibault Charbonnier 分享了他们在 OpenResty 上关于随机数应用的一些 Tips. 这才知道 LuaJIT 使用的随机算法和原生 Lua 的算法是不同的。我在自己的项目中也常常有使用随机数，但基本上只是直接使用，没有探寻背后的一些原理。刚好利用这个机会来好好补充下这方面的知识。引言...

Posted by qmsheng on October 24, 2017

警惕系统中那些异常的 RST

认真学习协议栈很重要

我们的系统有一个应用启用了连接池来连接后端的应用，最近我却发现这个连接池貌似并不能正常工作。理论上来说，当启用了连接池，应用到后端的连接应该稳定才对，而我通过 ss 观察到的现象却是应用不断的建立连接，断开连接。更为奇怪的是，应用方并没有出现 TIME_WAIT。起初我怀疑是服务端主动关闭了连接，但是在服务端也并没有发现 TIME_WAIT，所以可以基本排除这个问题。之后抓了下包才发现，...

Posted by qmsheng on July 23, 2017

OpenResty 中的安全隐患

在 OR 的官方 GitHub 中，介绍了这么一种简单的「路由」写法 # use nginx var in code path # CAUTION: contents in nginx var must be carefully filtered, # otherwise there'll be great security risk! location ~ ^/app/([-_a-zA-Z...

Posted by qmsheng on June 5, 2017

Lua 汉字拼音首字母提取

计算机内部只存储和处理字节，字符只是人类理解的概念。

最近项目上有个需求，需要将一些联系人数据按照拼音首字母排序。google 了一番，竟然没有找到一个合适的 Lua 解决方案。倒是找到一个 lua-pinyin，粗略翻了下源码发现其是将所有的中文返回全部完整的拼音，原理是将所有汉字对应拼音创建好数据字典，载入 Lua，之后查询这个字典，返回对应的拼音。但是这对于我这个需求来说显然是太臃肿了，我只需要返回首字母就可以了，却载入一个巨大的字典，感...

Posted by qmsheng on June 5, 2017

理解 timeout，这一篇就够了

对 TCP 协议栈的理解总是需要慢慢积累

PS. 最近比较忙，原先的 Lua 排序算法系列暂时搁置一段时间，以后还是会接着更新的。要是我精力足够，将来可能还会出 Lua 搜索算法系列，尽请期待。嗯，好吧，有些标题党了。不过这个问题我在 google 了大量中文的资料后，都没能解释清楚我的疑惑。索性深入研究了几天，自己来总结下学习成果。如果你的 Nginx 服务器流量足够大，足够繁忙。可能你会在 Nginx 的 error...

Posted by qmsheng on April 14, 2017

Lua 排序算法 - 插入排序

Insertion Sort

设有一组关键字｛K1， K2，…， Kn｝；排序开始就认为 K1 是一个有序序列；让 K2 插入上述表长为 1 的有序序列，使之成为一个表长为 2 的有序序列；然后让 K3 插入上述表长为 2 的有序序列，使之成为一个表长为 3 的有序序列；依次类推，最后让 Kn 插入上述表长为 n-1 的有序序列，得一个表长为 n 的有序序列。算法步骤从第一个元素开始，该元素可以认为已经被排...

Posted by qmsheng on March 23, 2017

Lua 排序算法 - 选择排序

Selection Sort

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理如下，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被...

Posted by qmsheng on March 19, 2017

Qmsheng Blog