牛牛C | Qmsheng Blog

Lua 排序算法 - 归并排序

Merge Sort

归并排序（Merge Sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并操作(Merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。归并排序有多路归并排序、两路归并排序, 可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨...

Posted by qmsheng on March 17, 2017

Lua 排序算法 - 快速排序

Quick Sort

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。算法步骤从数列中挑出一个元素，称为 “基准”（pivot）重新排序数列，所有元素比基准值小的摆放在基准前面，所有...

Posted by qmsheng on March 16, 2017

Lua 排序算法 - 冒泡排序

Bubble Sort

冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。算法步骤有一个长度为n的序列，一共需要n次外循环在一次外循环里，...

Posted by qmsheng on March 15, 2017

Lua 的标准输出与缓存

最近我遇到了个奇怪的问题，我的一个Lua脚本需要通过shell的重定向将输出追加到一个日志文件中。但是那个Lua脚本的输出在日志文件里看来却不是实时的，输出的文本直到脚本结束时才能看到。在shell下运行这个程序，是可以看到实时输出的： -- buffer_test.lua local socket = require "socket" local const = 100 for ...

Posted by qmsheng on December 20, 2016

cjson 的抢占问题

默认的 cjson 其实是 “共享” 的

我说的 cjson 抢占问题可不是 lua 的非抢占式协程，更准确的理解应该是：由于 lua 的协程切换，可能会导致 cjson 上下文不一致的情况。例如： -- json.lua local json = require("cjson") local _M = {} function _M.encode(data, empty_table_as_object) if j...

Posted by qmsheng on November 28, 2016

Lua 正确处理可变参数

一定要注意 table 中的 hole

为了在 Lua 里处理可变参数，我们可能会写下面这样的代码： local function args(...) if next({...}) then for _, v in ipairs{...} do print(v) end else print("empty var") end end ...

Posted by qmsheng on October 9, 2016

Lua string.find 中的 “坑”

我们的线上环境，ngx_lua api 都是以模块形式加载到 lua 级别的 vm 中，已达到最大性能。而且我们并没有使用传统的 “包” 的形式来加载(也就是 require "xx.xx.xx" )，而是直接以模块名为加载( require "xx" )，这就意味着我们需要不断的来动态设置 package.path 来配合 require 的机制。于是我们写了下面这个方法，来实现我们的需求...

Posted by qmsheng on September 23, 2016

OpenResty 中写日志的套路

记录日志很重要，套路同样更重要

在 OR 中为了方便调试，我们可能会用这样的方式来记录日志： local f = io.open("test.log", "a+") f:write(message .. "\n") f:close() 然而这种写法在大多数情况下，都是可以正常工作的。但是在高并发的系统上，尤其还是多 worker 的环境下，这样写日志是会串的，原因就是 io.open 自身的缓存机制(本质是 libc...

Posted by qmsheng on September 21, 2016

Goto in LuaJIT

吊炸天的 LuaJIT

Lua 在 5.2 之后的版本，加入了 goto 这个关键字，用来控制程序跳转到指定 label。我们可以利用这个特性，来模拟 continue 的实现。需要注意的是 goto 只能跳转到 label，而 ::name:: 的格式就可以设置一个 label。 for i=1,5 do if i == 3 then goto continue end ...

Posted by qmsheng on September 20, 2016

tail call 到底有啥用？

来体验下 proper tail call 强大的威力

在聊今天这个话题之前，我们需要知道什么叫 tail call。先来看下，lua 程序设计是怎么定义的：尾调用是一种类似在函数结尾的 goto 调用，当函数最后一个动作是调用另外一个函数时，我们称这种调用尾调用。例如： function f(x) return g(x) end g 的调用是尾调用。例子中 f 调用 g 后不会再做任何事情，这种情况下当被调用函数 g ...

Posted by qmsheng on September 9, 2016

Qmsheng Blog