11

给定：连接是安全的=真所以更新的返回将包含更新信息。

假设我有一个看起来像这样的文件：

[{'a': [1]}, {'a': [2]}, {'a': [1,2]}]

我发出：

coll.update({}, {'$addToSet': {'a':1}}, multi=True)

结果将是：

{u'connectionId': 28,
 u'err': None,
 u'n': 3,
 u'ok': 1.0,
 u'updatedExisting': True
}

即使来的文件已经具有这种价值。为了避免这种情况，我可以发出命令。

coll.update({'a': {'$ne': 1}}, {'$push': {'a':1}}, multi=True)

$addToSet 与 $push 与 $ne check 的时间复杂度比较是多少？

4

3 回答 3

18

看起来$addToSet正在做与您的命令相同的事情：$push 和 $ne check。两者都是 O(N)

https://github.com/mongodb/mongo/blob/master/src/mongo/db/ops/update_internal.cpp

如果速度真的很重要，那么为什么不使用哈希：

代替：

{'$addToSet': {'a':1}}
{'$addToSet': {'a':10}}

利用：

{$set: {'a.1': 1}
{$set: {'a.10': 1}
于 2012-12-04T10:58:10.500 回答
2

编辑

好的，因为我一直都错误地阅读了您的问题，事实证明实际上您正在查看两个不同的查询并判断它们之间的时间复杂度。

第一个查询是：

coll.update({}, {'$addToSet': {'a':1}}, multi=True)

第二个是：

coll.update({'a': {'$ne': 1}}, {'$push': {'a':1}}, multi=True)

这里想到的第一个问题，没有索引。$addToSet，作为更新修饰符，我不相信它使用索引，因为您正在执行全表扫描来完成您需要的操作。

实际上，您正在查找尚未包含的所有文档1并a查看该数组$push的值。1a

所以 2 甚至在我们进入时间复杂度之前就指向了第二个查询，因为第一个查询：

  • 不使用索引
  • 将是全表扫描
  • 然后会做一个完整的数组扫描（没有索引）到$addToSet

因此，我在这里几乎已经下定决心，第二个查询是您在使用任何大 O 表示法之前要查找的内容。

这里使用大 O 表示法来解释每个查询的时间复杂度是有问题的：

  • 我不确定您想要什么视角，无论是每个文档还是整个集合。
  • 我不确定索引本身。使用索引实际上会创建一个 Log 算法，a但不使用索引则不会。

然而，第一个查询看起来像：每个文档 O(n)，因为：

  • $addToSet 需要遍历每个元素
  • 然后 $addToSet 需要执行 O(1) 操作来插入该集合（如果它不存在）。我应该注意我不确定 O(1) 是否被取消（轻微阅读表明我的版本），我在这里取消了它。

每个集合，如果没有索引，它将是：O(2n2)，因为迭代的复杂性a将随着每个新文档呈指数级增加。

没有索引的第二个查询看起来像： O(2n2) (O(n) per document) 我相信因为会出现与没有索引$ne相同的问题。$addToSet但是，对于索引，我相信这实际上是 O(log n log n) （每个文档 O(log n)），因为它会首先根据 b-tree找到所有包含在其中的文档a，然后是所有不在其集合中的文档。1

因此，根据时间复杂度和开头的注释，我会说查询 2 更好。

老实说，我不习惯用“Big O”表示法解释，所以这是实验性的。

希望能帮助到你，

于 2012-09-01T18:35:22.947 回答
2

添加我对 addToSet 和从 100k 文档的批量更新推送之间的差异的观察。

当您进行批量更新时。addToSet 将单独执行。

例如，

bulkInsert.find({x:y}).upsert().update({"$set":{..},"$push":{ "a":"b" } , "$setOnInsert":  {} })

将首先插入并设置文档。然后它执行 addToSet 查询。

我看到了 10k 之间的明显差异

db.collection_name.count() #gives around 40k 

db.collection_name.count({"a":{$in:["b"]}}) # it gives only around 30k

但是当用 $push 替换 $addToSet 时。两个计数查询都返回相同的值。

注意：当您不关心数组中的重复条目时。您可以使用 $push。

于 2015-12-10T07:14:23.847 回答