Сортировка огромного массива данных
 

Есть массив величиной около 100 тысяч объектов. В каждом объекте храниться текст размером примерно 60-100 символов.

Нужно удалить все одинаковые значения. Должно получится что-то вроде этого:

var a = [1, 1, 2, 3, 3, 9, 7];
myFunc(a); // return [1, 2, 3, 9, 7]

Собственный вариант
 

function uniqueData(a) {
  var cache = [];
  
  for(var x = 0; x < a.length; x++) {
    if(x == 0) {
      cache[x] = a[x];
    } else {
      for(var y = 0, alertDublicate = false; y < cache.length; y++) {
        if(cache[y] == a[x]) alertDublicate = true;
        if(y + 1 == cache.length && alertDublicate != true) cache.push(a[x]);
      };
    };
  };
  return cache;
};

uniqueData([1,2,2,3,9,9,2,5,7,8]);

Первая попытка.

вопрос -а пользователю понравиться жать каждые 30 сек на окне -сценарий не отвечает если вы хотите продолжить....no:

Не понял. Вы о чем?

для таких целей был разработан Worker но увы он не работает в старых браузерах.

Мне безразлично на старые браузеры. Честно говоря первый раз слышу.

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

о времени выполнения.
о вашем бредовом алгоритме.
берётся элемент и от него ищется и удаются такие же элемента до конца массива. Затем следующий элемент и т.д. -с каждым элементом перебор всё короче.

Так я и говорю - это я успел написать за время после создания этой темы. Я тому и написал, что бы посоветоваться, как обойтись с таким большим массивом.

UPD: Ну да. Так и буду делать. А еще предложения будут как увеличить быстродействие?

ну ,тогда вы графоман как минимум.
Вам уже devote подсказал в какую сторону рыть
чтоб было понятнее -разделить на участки и выполнить сортировку в каждом параллельно (Worker),
затем по мере прихода результатов соединять их в один и производить сортировку в нём-вариант 1
когда все будут обработаны-соединить их в один и производить сортировку в нём-вариант 2

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

Bebarr Swallow,
Делал ка то подобную задачку- оптимально создать для кажого объекта на серве MD5 сумму каждого объекта, которую ставим первым из свойств, тады чисто проверяем Перво - свойства и удаляем идентичные .. 1000 объектов менее 0.3секунды тестировалось на проце в 1-1.2Гг

а колизии?

если массив уже отсортирован, то можно проще сделать так:

var a = [ 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5 ],
    b = [],
    last,
    length = a.length;

for( var i = 0; i < length; i++ ) {
    if ( a[ i ] !== last ) {
        b[ b.length ] = last = a[ i ];
    }
}

alert( b );

Но это прокатит если массив уже отсортирован, а точнее если парные значения находятся рядом друг с другом.

dmitriymar,
Расшифруйте ?

Ну по ходу я уже справился. Странно, но скрипт проработал секунд так .. несколько. Получился массив из 585 элементов.

Окончательный скрипт был таким:

var db = [ ... ] // Array[70890]

function uniqueData(a) {
  var cache = [];
  
  for(var x = 0; x < a.length; x++) {
    if(x == 0) {
      cache[x] = a[x];
    } else {
      for(var y = 0, alertDublicate = false; y < cache.length; y++) {
        if(cache[y] == a[x]) alertDublicate = true;
        if(y + 1 == cache.length && alertDublicate != true) cache.push(a[x]);
      };
    };
  };
  return cache;
};

uniqueData(db); // return Array[585]

Конечно скрипт совсем не для всех, но для одноразового применения мне подошел (и написан за 5 минут).

Мне это нужно было все на один раз :)

это когда для различных строк md5 одинаковые.

потестируйте такой вариант:

var db = [  1, 1, 2, 10, 2, 0, 0, 9, 2, 3, 7, 3, 4, 4, 4, 5  ];
 
function uniqueData(a) {
    var result = [],
        execCache = {},
        length = a.length;
   
    for( var v, x = 0; v = a[ x ], x < length; x++ ) {
        if ( !( v in execCache ) ) {
            result[ result.length ] = execCache[ v ] = v;
        }
    }

    return result;
}

alert( uniqueData(db) );

тут используется объект, но зато проход всего один.

есть простой метод, исходные свойтва объектов переводим в бинарник и перемножаем на серве, потом от произведения берем md5 (*цифра однозначная до значений в порядка триллиона объектов

devote, у меня была аналогичная мысль, но писать влом ) Кстати,

if ( !( v in execCache ) ) {
    result[ result.length ] = execCache[ v ] = v;
}

===

if ( v in execCache ) continue;
result[ result.length ] = execCache[ v ] = v;

Кстати, кстати ^_^ если предполагается значительное "усечение" массива за счет повторов, то и времени на сортировку будет затрачено меньше.

nerv_,
да я хотел воткнуть contunue; но не люблю юзать подобные операторы, на мой взгляд читаемость кода хуже становится. Хотя кому как.

PS. И для GCC сжать его сложнее :)