Вопрос по mongodb – Сложность времени $ addToset против $ push, когда элемент не существует в массиве

10

Дано: Соединение безопасно = Истинно, поэтому возвращение обновления будет содержать информацию об обновлении.

Скажем, у меня есть документы, которые выглядят так:

[{'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?

Да. Если $ push с $ ne будет проходить через каждый элемент, что, как я предполагаю, делает и $ addToSet. Какой из двух вариантов оптимален для использования? meson10
Что вы подразумеваете под «сложностью времени»? Вы имеете в виду количество времени, затраченное на сравнение по отношению к$push? Sammaye
$ push легко, так как хотя $ push должен извлекать массив (вложенный документ), его не нужно сравнивать с установленным. Sammaye

Ваш Ответ

3   ответа
2

Edit

Хорошо, поскольку я все время неправильно читаю ваш вопрос, получается, что вы на самом деле смотрите на два разных запроса и судите о сложности времени между ними.

Первый запрос:

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

И второе существо:

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

Здесь на ум приходит первая проблема, никаких индексов.$addToSetБудучи модификатором обновления, я не верю, что он использует индекс как таковой, поэтому вы выполняете полное сканирование таблицы, чтобы выполнить то, что вам нужно.

На самом деле вы ищете все документы, которые не имеют1 вa уже и с нетерпением$push Значение1 к этомуa массив.

Таким образом, 2 указывают на второй запрос еще до того, как мы столкнемся с временной сложностью, поскольку первый запрос:

  • Does not use indexes
  • Would be a full table scan
  • Would then do a full array scan (with no index) to $addToSet

Итак, я в значительной степени решил, что второй запрос - это то, что вы ищете, прежде чем что-либо из обозначений Big O.

Существует проблема с использованием большой нотации O для объяснения временной сложности каждого запроса здесь:

  • I am unsure of what perspective you want, whether it is per document or for the whole collection.
  • I am unsure of indexes as such. Using indexes will actually create a Log algorithm on a however not using indexes does not.

Однако первый запрос будет выглядеть примерно так: O (n) для каждого документа, поскольку:

  • The $addToSet would need to iterate over each element
  • The $addToSet would then need to do an O(1) op to insert the set if it does not exist. I should note I am unsure whether the O(1) is cancelled out or not (light reading suggests my version), I have cancelled it out here.

Для каждой коллекции без индекса это будет: O (2n2), поскольку сложность итерацииa будет экспоненциально увеличиваться с каждым новым документом.

Второй запрос без индексов будет выглядеть примерно так: O (2n2) (O (n) на документ)$ne будет иметь те же проблемы, что и$addToSet без индексов. Однако с индексами я считаю, что на самом деле это будет O (log n log n) (O (log n) на документ), так как он сначала найдет все документы сa тогда все документы без1 в их наборе, основанном на b-дереве.

Исходя из сложности времени и заметок в начале, я бы сказал, что запрос 2 лучше.

Если честно, я не привыкла объяснять в «Большой О» Обозначения, так что это экспериментально.

Надеюсь, поможет,

@ meson10 Хорошо, я не привык биться вокруг куста с математическим синтаксисом, вместо этого я привык объяснять это простым английским языком, однако я, после 50 минут чтения в формате Big O, думаю, что смог перевести свой английский в математику , Я буду редактировать, если я увижу ошибки.
Я думаю, что вы неправильно поняли мой вопрос. Я не сравниваю $ addToSet с толчком $ ne против $. Я имею в виду сравнить $ addToSet с ($ push + $ ne). ПРИМЕЧАНИЕ: помните, что нет $ ne поиска, пока я делаю $ addToSet. Во-вторых, "математика" синтаксис является более стандартным способом обозначения метрик. Пример: Автомобиль A намного быстрее, чем B, или Автомобиль A на 80 км / ч быстрее, чем B :-) meson10
@ meson10 Вы продолжаете использовать сленг, а я не понимаю, потому что я не использую тот же сленг, что и вы, что такое "Big O"? Также я утверждаю, что $ push быстрее для «временной сложности».
Ну, твоя последняя строчка - мой вопрос. Его ($ addToSet) против ($ push + $ ne). Они оба сработали бы, но если бы мне пришлось оценивать их с точки зрения Big O, как бы оценил каждый из них? meson10
В компьютерных науках временная сложность алгоритма определяет количество времени, затрачиваемого алгоритмом на выполнение, как функцию размера входных данных для задачи. Временная сложность алгоритма обычно выражается с использованием больших обозначений O, которые подавляют мультипликативные константы и члены более низкого порядка. Когда выражено таким образом, говорят, что временная сложность описывается асимптотически, то есть размер входного сигнала стремится к бесконечности. Например, если время, требуемое алгоритмом на всех входах размера n, составляет не более 5n3 + 3n, асимптотическая сложность времени составляет O (n3)smnr.me/TNAp7n meson10
16

Похоже$addToSet делает то же самое, что и ваша команда:$push with a $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}
Хм, я говорю, что addtoset был O (n), но я получил отрицательный голос ... должен быть не прав
2

Добавлю свое наблюдение в разницу между addToSet и push от массового обновления 100к документов.

когда вы делаете массовое обновление. addToSet будет выполнен отдельно.

например,

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

сначала вставит и установит документ. И тогда он выполняет запрос addToSet.

Я видел четкую разницу в 10К между

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

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

Но при замене $ addToSet на $ push. оба запроса на счет вернули одинаковое значение.

примечание: когда вас не беспокоит повторяющаяся запись в массиве. Вы можете пойти с $ push.

Похожие вопросы