python - 在python中过滤json对象的json数组的有效方法

Question

我有一个像这样的 json 样本:

{"ratings": [{

    "TERM": "movie1",       
    "Rating": "3.5",
    "source": "15786"

},
{
    "TERM": "movie2",       
    "Rating": "3.5",
    "source": "15786"
},
{
    "TERM": "Movie1",       
    "Rating": "3.0",
    "source": "15781"
}

]}

现在我想从中创建一个新的 json 文件，过滤逻辑是如果 TERM 已经存在一次则忽略 json 对象。因此，对于这个示例，输出将是

{"ratings": [{

"TERM": "movie1",       
"Rating": "3.5",
"source": "15786"

},
{
"TERM": "movie2",       
"Rating": "3.5",
"source": "15786"
}
]}

由于 movie1 已经存在于索引 0 中，我们希望忽略索引 2。

我想出了下面的逻辑，它适用于小样本。我有一个 json 数组大小为 10 milliion 的示例，下面的代码需要 2 天以上的时间才能完成。我想知道是否有更有效的方法来做到这一点:

import json
import io
input1 = "movies.json"
res=[]
resTerms = []
with io.open(input1, encoding="utf8") as json_data:
    d = json.load(json_data)
    print(len(d['ratings']))
    for x in d['ratings']:
        if x['TERM'].lower() not in resTerms:
            res.append(x)
            resTerms.append(x['TERM'].lower())


final ={}
final["ratings"] = res
output =  "myFileSelected.json"
with io.open(output, 'w') as outfile:
    json.dump(final, outfile)

Answer 1

这里的问题是当您检查术语是否已经存在时(即当您检查 if x['TERM'].lower() not in resTerms: 时)。这是因为 resTerms 是一个 list 并且查找复杂度为 O(n) 因此整个算法变为 O(n^2)

解决这个问题的方法是使用 set 而不是 list，后者的查找复杂度为 O(1)。然后你的循环看起来像这样(你也不需要保持 json 文件打开)

import json
import io
input1 = "movies.json"
res=[]
resTerms = set()
with io.open(input1, encoding="utf8") as json_data:
    d = json.load(json_data)
    print(len(d['ratings']))

for x in d['ratings']:
    if x['TERM'].lower() not in resTerms:
        res.append(x)
        resTerms.add(x['TERM'].lower())

可在此处找到有关 Python 数据结构和时间复杂度的便捷指南: https://wiki.python.org/moin/TimeComplexity