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

[FINoM]

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

[{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, но это замечание сути дела не меняет

[9xakep]

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)

[FINoM]

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

[Gvozd]

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

[FINoM]

O(N*lg N)

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

[FINoM]

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

var someOne = newArr.some(function(el2){return el['id'] === el2['id']});

indexOf (из моего варианта) побыстрее будет.

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

[nerv_]

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

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

пихать уникальные объекты в новый массив

[B@rmaley.e><e]

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

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

[melky]

про новые методы все забыли ? 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);

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

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

[melky]

но это так криво выглядит что я сделал обычный перебор.

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

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

Пример: Gvozd

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, только у последнего исп-ся быстрые функции, реализованные в движке. (или я по диагонали его код прочитал?)

Пример: 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);

Пример: melky

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