There is a need to remove all duplicate elements from the array, but do not sort it. I implemented it in the forehead and simply rewrite each element of the array from the end to a new array and check the old one for the presence of the same element.

It seems everything works, but I thought about speed because This method should be very expensive and decided to check it on jsperf. To my surprise, the tests showed that my method wins the method I found in jquery (first sort the array, and then delete all the repetitions, walking the entire array).

But it seems to me that jsperf is somewhere wrong and for this I want to ask more experienced colleagues why such strange results are obtained:

http://jsperf.com/unique-test

    2 answers 2

    @MrFranke , you have an array

    var arr = [2,3,1,3,4,2,7,92,4];

    very small.

    In fact, when you search for a duplicate in an array, you make a simple match (with quadratic complexity). It is widely known that for small (dozens of elements) arrays, this type of sorting is faster than any "serious" (quicksort, mergesort (all types, including timsort), etc.) sorting (due to the simplicity of the algorithm, little teams).

    Moreover, in all serious implementations of such sortings at a certain point (when you need to sort the next small segment of data), switching to quadratic (D. Knut advises using sorting inserts) sorting occurs. But in any case, usually before that you have to perform a “mass of gestures”, which, naturally, you don’t have in your particular case.

    Here, in fact, is the explanation of the observed effect. You can see that O (n * n) <O (n * log n)

    • Many thanks for the explanation! Maybe you then tell me how best to organize the removal of identical elements in the array without sorting it? Those. so that the elements remain in their original places. - MrFranke
    • In the sense that arr = [2,3,1,3,4,2,7,92,4]; it turns out arr2 = [2,3,1,4,7,92]; So? On С int j = 0, k; arr2 [j ++] = arr [0]; for (int i = 1; i <n_arr; i ++) {for (k = 0; k <j; k ++) if (arr [i] == arr2 [k]) break; if (k == j) arr2 [j ++] = arr [i]; } now j is the number of elements in arr2. - avp
    • @MrFranke, without sorting (well, or without creating a hash set) faster square will not work. - dzhioev

    The fastest method will be using an auxiliary object:

     function returnUnique(arr) { var obj = new Object; for (var i = 0, i_max = arr.length; i < i_max; i++) { obj[arr[i]] = ''; // запоминаем элемент как свойство объекта } return Object.keys(obj); }

    But this method works correctly only with arrays of simple homogeneous elements.

    • Using an object as a dictionary with keys? Not bad) - Mi Ke Bu