3

JSON を言語間シリアライゼーションとして使用してデータを渡すプロジェクトがあります。最近、データのサイズが少し大きくなっています (10k の長さのオブジェクトのリスト)。データをシリアル化するのに約 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

最初の列: リストの長さ。2 列目: シリアル化の時間。プロット (xmgrace などを使用) により、理想的な線形関係が明らかになります。

于 2012-05-21T15:08:50.720 に答える