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

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

[{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);