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

[Deff]

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

[dmitriymar]

а колизии?

[devote]

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

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

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

[Deff]

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

[Bebarr Swallow]

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

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

Ну по ходу я уже справился. Странно, но скрипт проработал секунд так .. несколько. Получился массив из 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 минут).

[Bebarr Swallow]

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

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

[dmitriymar]

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

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

[devote]

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

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

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

[Deff]

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

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

[nerv_]

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

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

===

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

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