Удаление дубликатов в массиве объектов по уникальному ключу

[Gvozd]

melky,
Да, твой пример самый быстрый, и в отличии от моего не пересортировывает массив.
Для конкретно данной задачи подходит лучше всех.
Но труднее масштабируется для фильтрации произвольных объектов - полная сериализация объекта может занять существенно больше времени, чем сравнение объектов, и не всегда возможна.

[melky]

melky,
Да, твой пример самый быстрый, и в отличии от моего не пересортировывает массив.
Для конкретно данной задачи подходит лучше всех.
Но труднее масштабируется для фильтрации произвольных объектов - полная сериализация объекта может занять существенно больше времени, чем сравнение объектов, и не всегда возможна.

я его для конкретной задачи и писал. я даже и не думал, что он будет перебирать объекты - только примитивы. деревянный код

[FINoM]

O(N lg N) + O(N) = O(N lg N)

В универе оценку алгоритмов не проходили, только во время диплома препод объяснил, что всё нужно сокращать. Но, не ради спора, почему O(N lg N) + O(N) != O(N + N lg N)?

melky, отлично, всего N итераций.

[Gvozd]

Но, не ради спора, почему O(N lg N) + O(N) != O(N + N lg N)?

O (читается как "О большое от") - означает оценку сверху.
http://ru.wikipedia.org/wiki/%C2%ABO...%D0% BE%D0%B5
Читаем с фразы "является «O» большим от при" (я бы процитировал, но там картинки в формулах)

При сложении двух O(), остается тот их них, который быстрее растет
O(N lg N) + O(N) <= C * O(N lg N)
Если мы выберем C>1, то рано или поздно наступит момент, когда это неравенство будет выполнятся, и при дальнейшем стремелении к бесконечности, C * O(N lg N) будет всегда больше, чем O(N lg N) + O(N)
соответсвенно
O( O(N lg N) + O(N) ) = O(N lg N)

[melky]

melky, отлично, всего N итераций.

у меня всегда хорошо получается решать мелкие задачи, но вот большие задачи даются с трудом... я почти решил эту проблему функциональной декомпозицией, но тогда становится очень много кода... к счастью, эту проблему отлично решает Google Closure Compiler и режиме продвинутой оптимизации.

но вот идеальный алгоритм решения больших задач я ещё для себя не разработал
пока что следую совету "если в функции решается несколько подзадач, то их решение нужно вынести в отдельную функцию".

PS немного мимо кассы, но всё равно, на вопрос уже ответили

[Gvozd]

melky, отлично, всего N итераций.

Отлично, но сложность его алгоритма также как и у моего - O(N* lg N)
Он делает N итераций, и в каждой из них он обращается к объекту по ключу.
Самый эффективные алгоритмы хранения данных ключ-значение имеют сложность обращения к элементу по ключу - O(lg N)
Поэтому итоговая сложность - O(N) * O(lg N) = O(N*lg N)
PS его алгоритм работает быстрее моего в разы, из-за внутренних оптимизаций браузера для данной операции
но сложность одинакова

[FINoM]

Отлично, но сложность его алгоритма также как и у моего - O(N* lg N)
Он делает N итераций, и в каждой из них он обращается к объекту по ключу.

Теоретически эти два алгоритма эквивалентны. Практически — нет. key in obj можно не брать в расчет, как и 5 > 1.

но вот идеальный алгоритм решения больших задач я ещё для себя не разработал

Алгоритм решения больших задач? Квинтэссенция программирования?

[Gvozd]

key in obj можно не брать в расчет, как и 5 > 1.

Почему key in obj можно не брать в расчет?
ведь с ростом размера объекта он начинает работать медленнее
И при чем тут 5>1?
а главное почему его не брать в расчет также можно? ведь это неоспоримый факт, и игнорировать его как-то не очень

[FINoM]

Почему key in obj можно не брать в расчет?

Потому что он чересчур быстрый.

ведь с ростом размера объекта он начинает работать медленнее

Да, ты прав, но эта разница заметна лишь при чудовищных объектах: http://jsfiddle.net/pQYZw/