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

У меня есть массив объектов:

[{id:3}, {id:5}, {id:3}]

Нужно из этого массива убрать дубликаты. Как это вижу я:

ids = [];
array.forEach(function( object ){
  if( ~ids.indexOf(object.id) ) {
    // удаляем сплайсом этот object из массива
  } else {
     ids.push(object.id);
  }
});

Я не уверен, что алгоритм оптимален. Есть ли более оптимальные пути удалять объекты с дублирующимся значением ключа?

UPD Здесь forEach неуместен, нужно юзать обычный for, но это замечание сути дела не меняет

FINoM,
конечно через жопу сделан, но если выложишь свой код, то можно проверить по скорости:

<script>
var arr = [{id:3}, {id:5}, {id:3}]
var arr2 = []
for(i=0;i<arr.length;i++) {
  for(k=0;k<arr.length;k++) {
    if(k!=i) {
      if(arr[i].id==arr[k].id) arr[k]=''
    }
  }
}
for(i=0;i<arr.length;i++) {
  if(arr[i]=='') continue
  else arr2.push(arr[i])
}
console.log(arr2)

9xakep, ужас. Это в несколько раз хуже моего варианта.

Maxmaxmахimus,
у вас сложность O(N*N)
есть гораздо более быстрый вариант - O(N*lg N) - сперва отстортировать, а затем перенести в новый массив оставив только один из подряд идущих одинаковых

var arr = [1, 2, 3, 1, 2, 3, 5];

var newArr = arr.sort().reduce(function(arr, el){
	if(!arr.length || arr.length && arr[arr.length - 1] != el) {
		arr.push(el);
	}
	return arr;
}, []);

console.log( newArr );

var arr = [{id:3}, {id:5}, {id:3}];

var newArr = arr.sort(function(a,b){return a.id < b.id ? -1 : 1;}).reduce(function(arr, el){
	if(!arr.length || arr[arr.length - 1].id != el.id) {
		arr.push(el);
	}
	return arr;
}, []);

console.log( newArr );

Откуда такая оценка? Только сортировка (исходя из списка алгоритмов на википедии) занимает столько.

Gvozd, сортировка, к сожалению, не подходит. Я подгружаю данные порциями из элементов с произвольными айдишниками и вывожу их. Сортировка потребует перерисовывать каждый раз интерфейс, вместо обычного дописывания ниже. Это не приемлемо в задаче.indexOf (из моего варианта) побыстрее будет.

Другой вопрос. Что быстрее: удалять совпадения (сплайсом) или пихать уникальные объекты в новый массив?

на первый взгляд ответ очевиден -

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

про новые методы все забыли ? Array.prototype.filter легко реализуется в IE, а сама проверка существование через in - самая быстрая операция в JS (на хабрэ читал исследование)
нужна проверка по ID, а это примитив... как раз сюда подойдет оператор in.

var used = {};

var arr = [{id:3}, {id:5}, {id:3}, {id:3}, {id:3}, {id:7}, {id:7}];

var filtered = arr.filter(function(obj) {
    return obj.id in used ? 0:(used[obj.id]=1);
    /*
    var res = !(obj.id in used);
    used[obj.id] = null;
    return res;
    */
});

console.log(filtered);

сплайс будет сдвигать все последующие значения, заполняя просвет. очень медленно :)

что там кривого?

FINoM свой код не написал. (запускаемый пример)

var arr, i, c, st;
for(i = 0, c = 1e4, arr = []; i < c; i += 1) arr.push({ id: i > c/2 ? i:c-i }); 
st = Date.now();

var newArr = arr.sort(function(a,b){return a.id < b.id ? -1 : 1;}).reduce(function(arr, el){
	if(!arr.length || arr[arr.length - 1].id != el.id) {
		arr.push(el);
	}
	return arr;
}, []);

console.log("Gvozd", Date.now() - st);

у кода 9xakep тот же принцип, что и у кода Maxmaxmахimus, только у последнего исп-ся быстрые функции, реализованные в движке. (или я по диагонали его код прочитал?)

var arr, i, c, st;
for(i = 0, c = 1e4, arr = []; i < c; i += 1) arr.push({ id: i > c/2 ? i:c-i }); 
st = Date.now();

var newArr = [];
arr.forEach(function(el){
  var someOne = newArr.some(function(el2){return el['id'] === el2['id']});
  if( !someOne ) {
    newArr.push(el);
  }
});

console.log("Maxmaxmахimus", Date.now() - st);

var arr, i, c, st;
for(i = 0, c = 1e4, arr = []; i < c; i += 1) arr.push({ id: i > c/2 ? i:c-i }); 
st = Date.now();

var used = {};
var filtered = arr.filter(function(obj) {
    return obj.id in used ? 0:(used[obj.id]=1);
});

console.log("melky", Date.now() - st);

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

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

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

melky, отлично, всего 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)

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

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

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

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

Теоретически эти два алгоритма эквивалентны. Практически — нет. key in obj можно не брать в расчет, как и 5 > 1.Алгоритм решения больших задач? Квинтэссенция программирования? :D

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

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