Lua表存储优化

用Python脚本实现对 Lua表的压缩



一览

问题

在研发过程中,通常会定义一些Excel表格,规定行列值让策划填写,然后,转成lua的table文件,直接使用。

但是,随着研发进行,项目迭代,表格将越来越大。

如果表格中存在大量重复数据,或者表格中很多列数值重复,则可以通过数据压缩给表减减肥。

解决

利用python实现lua表的数据压缩

  • excel表内存在大量 同列不同行 内容一致
  • excel表内存在大量 复合型 单元格内容一致

具体代码,均在github中: ltree98’s github -> CompressLua




参照方案

这是我在网上看到的文章:

Lua配置表存储优化方案

总结的来说,就是

  • 利用lua的元表机制。如果在table中取的值不存在,会去它的元表中查找(如果元表存在)。
  • 将重复的table,提取出来,将所有使用的地方引用过去。




问题

在参照方案的文章中,也提供了解决方法,但是在使用过程中遇见一些问题。

对同一文件压缩后文件MD5可能不一致

对同一个lua文件,进行减肥,在减肥后,虽然最终体重一样,但是可能这次瘦了肚子,下次瘦了腿。

主要原因就是参照方案使用lua处理,对同一个table遍历顺序是不稳定的,即table中存在 A B C 元素,可能这次遍历顺序是 A-B-C,下次遍历顺序可能就是 B-A-C;稳定性得不到保证。

lua的官网对于table的遍历描述一直是:

The order in which the indices are enumerated is not specified, even for numeric indices. (To traverse a table in numeric order, use a numerical for or the ipairs function.)

就是 索引在遍历过程中的次序是不固定的,即使是数字索引也不固定。

因为,项目中使用热更机制是比较两个文件的MD5,决定是否更新该文件。

所以,这个问题就显得很严重,每次热更要更新所有的表。当然,这个问题也可以通过做备份等方式来弥补,但是毕竟治标不治本。

但是用不同的lua版本发现:

使用 lua5.1 版本 生成的压缩文件是一致的

使用 lua5.3版本 生成的压缩文件是不一致的



复杂度高

虽然是现成的,但是也没法直接拿来用;

还是要根据项目现状进行修改。

在整合过程中,发现逻辑比较复杂,而且工具集与我们现有的python不符。(如果用其他工具集,又要去配置相应环境等,比较麻烦)。




修改方案

简介

目的

  • 解决 Excel表 内存在大量 同列不同行 内容一致
  • 解决 Excel表内存在大量 复合型单元格 内容一致

设计

  • 对于重复table,只存一份,其他引用过去
  • 设计一个基础元表,存储Excel每列 最频繁的值;其他表缺省 最频繁的值
  • 设置 只读属性

注意

  • Lua作用域内存放最大的local变量个数为 200个,超过的需要放入临时数组
  • 输出到lua文件,key值不可存在特殊字符($、- 等)

缺点

  • Lua表的可读性变差,需要跳转获取最终值
  • 使用元表实现,若后续处理(比如 加密,修改操作 等)也存在使用元表,增加处理的复杂度



方案

名词解释

  • Excel表:Excel转换成Lua的表,一般结构为

    1
    2
    3
    4
    5
    6
    -- tableName.lua

    local tableName = {
    ...
    }
    return tableName
  • 默认表:未来的元表,存储Excel中每列最频繁的元素

  • 重复表:Excel表中各单元格重复的 复合型元素(array/table)


流程

  1. 遍历表,进行统计

    • 统计Excel表中各列元素出现次数

    • 统计Excel表中 单元格复合型元素 出现次数

  2. 构造 重复表

    • 筛选 单元格复合型元素 次数大于1的元素,构建重复表
  3. 构造 默认表

    • 根据各列最频繁元素,构造默认表
  4. 整理 Excel表

    • 根据默认表,将重复的字段忽略
  5. 输出 各表

    • 根据 重复表,替换并输出 重复表
    • 根据 重复表,替换并输出 Excel表
    • 根据 重复表,替换并输出 默认表
  6. 设置 元表 及 只读属性


关键代码

最新代码请移步 lt-tree的github

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
###################################################################
##
## tools
##

def count_dict_deep(dict_temp):
"""Count dictionary's deep

Args:
dict_temp: dict

Returns:
int : deep
"""

deep = 0
for item in dict_temp.values():
if isinstance(item, dict):
temp_deep = count_dict_deep(item)
if temp_deep > deep:
deep = temp_deep

return deep+1

def calc_weight(obj1):
"""Calculate obj's weight

Args:
obj1: tuple[dict's string, dict's frequency]

Returns:
int : weight
"""

dict1 = eval(obj1[0])
times1 = obj1[1]

deep1 = count_dict_deep(dict1)
ans = deep1 + 1/times1

return ans

def count_table_frequency(unit_dict, dict_frequency):
"""Count table frequency

Count table frequency and record as {table string: times}

Args:
unit_dict: dict, need analyse data
dict_frequency: dict, the record's set
"""

unit_str = str(unit_dict)
if unit_str in dict_frequency:
dict_frequency[unit_str] = dict_frequency[unit_str] + 1
else:
dict_frequency[unit_str] = 1

# traversing sub dict
for item in unit_dict.values():
if isinstance(item, dict):
count_table_frequency(item, dict_frequency)


def count_table_value_frequency(key, value, item_frequency):
"""Count table value frequency

Count every excel column element appear times.
Record as {
key1 : {element1 : times, element2: times, ...}
key2 : {element1 : times, element2: times, ...}
...
}

Args:
key: string
value: string or dict
item_frequency: dict, the record's set
"""

if isinstance(value, dict):
value = str(value)

if key in item_frequency.keys():
if value in item_frequency[key].keys():
item_frequency[key][value] = item_frequency[key][value] + 1
else:
item_frequency[key][value] = 1
else:
item_frequency[key] = {}
item_frequency[key][value] = 1


def traverse_table(excel_dict, dict_frequency, item_frequency):
"""Traverse table.

Analyse lua table.

Args:
excel_dict: dict
dict_frequency: dict
item_frequency: dict
"""

for key in sorted(excel_dict):
if isinstance(excel_dict[key], dict):
count_table_frequency(excel_dict[key], dict_frequency)

for k, v in excel_dict[key].items():
count_table_value_frequency(k, v, item_frequency)


def check_repeat_dict(item_dict, repeat_dict):
"""Check repeat dict

Check repeat dict and return the repeat index, if not exist in repeat dict return -1.

Args:
item_dict: dict
repeat_dict: dict

Returns:
int
"""

dict_str = str(item_dict)
if dict_str in repeat_dict.keys():
return repeat_dict[dict_str]
else:
return -1

def replace_repeat_dict(item_dict, repeat_dict, cur_index = -1):
"""Replace repeat dict

Check if element exist in repeat dict and replace by designation string.

Args:
item_dict: dict
repeat_dict: dict
"""

cur_index = -1

for key, value in item_dict.items():
if isinstance(value, dict):
index = check_repeat_dict(value, repeat_dict)
if index != -1 and (index < cur_index or cur_index == -1):
if index > 190:
item_dict[key] = REPEAT_KEY_PREFIX + '[' + str(index - LOCAL_TABLE_MAX) + ']'
else:
item_dict[key] = REPEAT_KEY_PREFIX + str(index)
else:
replace_repeat_dict(value, repeat_dict, cur_index)



def output_file(table_name, file_path, repeat_dict, final_dict, default_dict):
"""Output file

Args:
table_name: string
file_path: path
repeat_dict: dict
final_dict: dict
default_dict: dict
"""

file_handler = codecs.open(file_path, 'a', encoding='utf-8')

# output repeat dict
for dictStr, index in sorted(repeat_dict.items(), key=lambda item:item[1]):

# replace repeat item by repeat_dict
repeat_dict_item = eval(dictStr)
replace_repeat_dict(repeat_dict_item, repeat_dict, index)

if index <= LOCAL_TABLE_MAX:
# file_handler.write("local %s = {\n" % (REPEAT_KEY_PREFIX + str(index)))
file_handler.write("local %s = {\n" % (REPEAT_KEY_PREFIX + str(index)))
convert.convert_dict_lua_file(file_handler, repeat_dict_item, 1)
file_handler.write("}\n")
else:
if index == (LOCAL_TABLE_MAX + 1):
file_handler.write("\nlocal __rt = createtable and createtable(%d, 0) or {}\n" % (len(repeat_dict)-LOCAL_TABLE_MAX))

file_handler.write("__rt[%d] = {\n" % (index - LOCAL_TABLE_MAX))
convert.convert_dict_lua_file(file_handler, repeat_dict_item, 1)
file_handler.write("}\n")

# output final dict
replace_repeat_dict(final_dict, repeat_dict)
file_handler.write("\nlocal %s = {\n" % (table_name))
convert.convert_dict_lua_file(file_handler, final_dict, 1)
file_handler.write("}\n")

# output default dict
replace_repeat_dict(default_dict, repeat_dict)
file_handler.write("\nlocal %s = {\n" % (DEFAULT_TABLE_NAME))
convert.convert_dict_lua_file(file_handler, default_dict, 1)
file_handler.write("}\n")

# set metatable and read-only
file_handler.write("\ndo\n")
file_handler.write("\tlocal base = {__index = %s, __newindex = function() error(\"Attempt to modify read-only table\") end}\n" % (DEFAULT_TABLE_NAME))
file_handler.write("\tfor k, v in pairs(%s) do\n" % (table_name))
file_handler.write("\t\tsetmetatable(v, base)\n")
file_handler.write("\tend\n")
file_handler.write("\tbase.__metatable = false\n")
file_handler.write("end\n")

file_handler.write("\nreturn %s\n" % (table_name))
file_handler.close()


###################################################################
##
## structure method
##

def structure_repeat_dict(dict_frequency):
"""Structure frequency dict

Select frequency > 1 element to structure dict.

Args:
dict_frequency: dict

Returns:
dict; {dict's string : repeat index}
"""

repeat_dict = {}
repeat_index = 1

for key, value in sorted(dict_frequency.items(), key=lambda x:calc_weight(x)):
if value > 1:
repeat_dict[key] = repeat_index
repeat_index = repeat_index + 1

return repeat_dict


def structure_default_dict(excel_dict, all_item_frequency):
"""Structure default dict

Args:
excel_dict: dict
all_item_frequency: dict

Returns:
dict; {key : most frequently value}
"""

excel_item = {}
for item in excel_dict.values():
excel_item = item
break

default_dict = {}
for key, value in excel_item.items():
for k, v in sorted(all_item_frequency[key].items(), key=lambda item:item[1], reverse=True):
if isinstance(value, dict):
default_dict[key] = eval(k)
else:
default_dict[key] = k
break

return default_dict


def structure_final_dict(excel_dict, default_dict):
"""Structure final dict

Structure final dict by default_dict and excel_dict.

Args:
excel_dict: dict
default_dict: dict

Returns:
dict
"""

final_dict = {}
for key, value in excel_dict.items():
final_dict[key] = {}

if isinstance(value, dict):
for k, v in value.items():
if default_dict[k] != v:
final_dict[key][k] = v
else:
final_dict[key] = value

return final_dict



def process_file(src_path, dst_path, file_name):
dict_frequency_statistics = {}
all_item_frequency_statistics = {}

# conver lua table to python dict
file_dict = convert.convert_lua_table_dict(src_path)

# analyse dict
traverse_table(file_dict, dict_frequency_statistics, all_item_frequency_statistics)

# get repeat dict
repeat_dict = structure_repeat_dict(dict_frequency_statistics)

# get default dict
default_dict = structure_default_dict(file_dict, all_item_frequency_statistics)

# structure final dict
final_dict = structure_final_dict(file_dict, default_dict)

output_file(file_name, dst_path, repeat_dict, final_dict, default_dict)

文件结构


其他

为什么 lua5.1 有序, lua5.3 无序

最开始使用lua5.3来执行 参照方案,所以出现了压缩后的文件不一致问题;

一开始也没有想是lua版本的问题,只是单纯觉得用lua实现太不方便了,就直接用python重写了。

后来在实现完python版本,然后进行整理的时候,

发现lua5.1版本其实还是固定顺序的(虽然官方文档写的不保证),

但是lua5.3版本的确是无序,而且这个无序是载入无序,

也就是说,对同一个table,载入时会安排好顺序,后面遍历就固定顺序了,但是下次载入可能就换了个顺序。

为什么lua5.3会载入无序呢?

lua中table的 for pairs 遍历是通过next来实现的,next的实现在不同lua版本没有变化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int luaH_next (lua_State *L, Table *t, StkId key) {
int i = findindex(L, t, key); /* find original element */
for (i++; i < t->sizearray; i++) { /* try first array part */
if (!ttisnil(&t->array[i])) { /* a non-nil value? */
setnvalue(key, cast_num(i+1));
setobj2s(L, key+1, &t->array[i]);
return 1;
}
}
for (i -= t->sizearray; i < sizenode(t); i++) { /* then hash part */
if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */
setobj2s(L, key, key2tval(gnode(t, i)));
setobj2s(L, key+1, gval(gnode(t, i)));
return 1;
}
}
return 0; /* no more elements */
}

都是先查数组部分,再查哈希部分。

所以,key值的设置就是关键。

lua关于table中加入新key值解释是:

/
inserts a new key into a hash table; first, check whether key’s main position is free. If not, check whether colliding node is in its main
position or not: if it is not, move colliding node to an empty place and put new key in its main position; otherwise (colliding node is in its main
** position), new key goes to an empty position.
/

向哈希表插入新key值,

  • 先检查key的 mainposition(哈希值) 是否空着
    • 是:key值放在 mainposition
    • 否:查看占据位置的 值 的 mainposition 是否是该位置
      • 是:找到 空位置,然后把 key值放在该位置
      • 否:将占据位置的值 移动到空位置,然后将key值放在 该位置

核心就是,

当发生哈希碰撞的时候,会在碰撞位置 物理向上查找到空位置,然后作为 后加入值 的位置。

因此,出现发生碰撞的时候,需要先去判断 占据位置的值 的哈希值是否是 该位置。

由于,对同一个 哈希值 的不同值,是有链关系的,所以,后来的兄弟被移到别的位置了,还是能被找到,并不会因为后来兄弟把它扔别的地方就丢了。

最后,当没有空位置的时候,就要进行 rehash操作,这个设计到lua表的具体实现,等以后有空再整理一下吧。

mainposition的值是怎么来的呢?

这里先只讨论string类型的值,

对于 lua5.1 来说:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {

...

unsigned int h = cast(unsigned int, l); /* seed */
size_t step = (l>>5)+1; /* if string is too long, don't hash all its chars */
size_t l1;
for (l1=l; l1>=step; l1-=step) /* compute hash */
h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));

...

return newlstr(L, str, l, h); /* not found */
}

此处,h的取值即为该string的hash key,可以发现它是将 string长度作为种子,计算出来的,所以 lua5.1 是固定顺序的。

对于 lua5.3 来说:

1
2
3
4
5
TString *luaS_createlngstrobj (lua_State *L, size_t l) {
TString *ts = createstrobj(L, l, LUA_TLNGSTR, G(L)->seed);
ts->u.lnglen = l;
return ts;
}

此处,h取值是一个随机种子,在创建的时候随机生成的:

1
2
3
4
5
6
7
8
/*
** a macro to help the creation of a unique random seed when a state is
** created; the seed is used to randomize hashes.
*/
#if !defined(luai_makeseed)
#include <time.h>
#define luai_makeseed() cast(unsigned int, time(NULL))
#endif

至此,破案。

关于 repeat_dict 的嵌套问题(v0.0.2更新)

问题

最终输出的lua会存在以下结构:

1
2
3
4
5
6
local __rt1 = {
[1] = __rt2,
}
local __rt2 = {
[1] = 0,
}

这样在lua使用时,由于定义__rt1时,__rt2未被声明定义,所以输出出来的结果是:

1
2
3
4
5
6
__rt1 = {

}
__rt2 = {
[1] = 0,
}

这是由于,repeat_dict只是单纯根据出现频繁次数排序的,所以可能存在上面的去引用下面的情况。

解决

方案一

这种方案是比较正规的方法,

  1. 将repeat_dict内所有序号都看作一个节点,然后通过引用关系相连,可以生成多条链结构。

  2. 根据链的长度进行遍历,共同维护将要输出的最终链结构

    • 每遍历一个节点,都先去最终结构遍历位置关系及是否已经输出

    • 找到合适的位置,将结点插入进去

  3. 将最终链结构按顺序赋值输出

方案二

这种方案比较投机取巧一些。

因为存在嵌套关系,那肯定是递归深度高的table嵌套了递归深度低的table。

所以先输出递归深度低的table,再输出递归深度高的table,那就不会出现这种问题。

但是,为了更好查找,同样深度的table,根据出现频率要再排序。

针对不同python版本打表不一致问题(v0.0.3更新 & v0.0.4更新)

经使用发现,不同python版本会导致,输出的表内容不一致。(暂时只试验了 Python 3.4 及 Python 3.7)

经过试验查询,发现是Python在存到字典后读取的顺序是不同的,导致sorted排序会有所差异(Python3.7没有问题,Python3.4会有所差异)。

查了相关资料发现,在python3.6开始 普通字典可以记住元素添加顺序,之前并没有,所以会导致之前的字典遍历顺序有问题。

  • PS:注意,此处排序的稳定性 和 添加顺序一致 是两个概念。
    • 排序的稳定性:对于待排序数列 1,1,2,3, 经历稳定排序,则不会进行交换操作,第一个位置的1 和 第二个位置的1 不会交换位置(虽然两者值相同)
    • 添加顺序的一致:输入 age, sex, sex, age;如果添加顺序一致,那么 sex永远会优先遍历到第二次,从而顺序会是 {sex: 2, age: 2};如果添加顺序不一致,就可能出现 {age: 2, sex: 2}

原因查明白了,该想怎么解决了。就是对同样频率的再根据key排个序。(没有什么顺序是排序解决不了的,如果不行,多排几遍…)

基于同样的问题,v0.0.4进一步修改,字典转字符串,要先对字典排序再转,否则将出现根据存储顺序不一致问题,然后比较是否重复元素,也由原来比较字符串相同改为比较字典相同。