3

我有一个项目使用 JSON 作为跨语言序列化来传递数据。最近数据的大小变得有点庞大（10k 长度的对象列表）。序列化数据需要 python 标准 json 库大约 20 秒。

我正在努力优化时间。虽然切换到其他 json 序列化程序（cjson、simplejson、ujson）可以加快速度，但我开始怀疑 JSON 序列化的时间复杂度。如果关系不是线性的（比如说如果它是 n^2），我可以轻松地将数据分成块并显着减少时间。

从我的猜测来看，复杂性应该真的取决于输入数据。但是是否有最坏情况/平均估计可用？参考链接也将受到高度赞赏。

谢谢。

4

1 回答 1

3

我用这段代码对时间复杂度进行了基准测试：

import json
import random
import time

Ns = 10, 100, 1000, 10000, 100000, 200000, 300000, 600000, 1000000
for N in Ns:
    l = [random.random() for i in xrange(N)]
    t0 = time.time()
    s = json.dumps(l)
    t1 = time.time()
    dt = t1-t0
    print "%s %s" % (N, dt)

在我的机器上，结果是：

10 7.20024108887e-05
100 0.000385999679565
1000 0.00362801551819
10000 0.036504983902
100000 0.366562128067
200000 0.73614192009
300000 1.09785795212
600000 2.20272803307
1000000 3.6590487957

第一列：列表长度；第二列：序列化时间。绘图（例如 xmgrace）揭示了理想的线性关系。

于 2012-05-21T15:08:50.720 回答