Zwycięzca konkursu JavaScriptowego

Wyłanianie zwycięzcy konkursu HTML5/CSS3 jeszcze trwa, natomiast już teraz mogę pogratulować niejakiemu Yanowi Kowalskyemu!

Oto najszybszy kod jego autorstwa:

/**
 * Funkcja rozwiązująca zadanie konkursowe
 *
 * @version 201103061820
 * @author Yann Kowalsky
 * @param array input Jednowymiarowa, posortowana rosnąco tablica unikalnych
 * liczb całkowitych.
 * @return array Tablica z niepowtarzającymi się liczbami dodatnimi, których
 * wartość absolutna pojawiła się w tablicy dwa razy.
 */
window.solve = function(input) {
	var output = [];
	var length = input.length;
	var a, b; // "cache"

	// iteruje tablicę input od początku i od końca, porównując kolejno
	// wartość bezwzględną elementów
	for (
		var i = 0, j = ~- length, a = - input[0];
		(a = - input[i]) > 0;
		++ i
	) {
		// mały boost - po pierwsze zatrzymaj się tu, bo i tak nie spotkasz
		// wartości równych, po drugie - j przy następnym przebiegu pętli for
		// będzie startowało od ostatniej wartości, a nie od początku
		while (a < (b = input[j])) {
			-- j;
		}
		
		// wartość bezwględna taka sama
		if (a == b) {
			output[output.length] = b;
			// output[output.length] szybsze od output.push()...
			-- j;
		}
	}

	return output;
}

Kilka słów na temat rozwiązań. Przede wszystkim należało użyć algorytmu nie korzystającego z pomocniczych struktur. Kilka algorytmów odpadło też ze względu na modyfikację tablicy z wejścia np. input.pop();. Najczęstszym rozwiązaniem z kolei była iteracja po tablicy dwa razy w celu sprawdzenia ponownego wystąpienia liczby, co nie jest najbardziej wydajnym sposobem (2n do n^2).

Warto też powiedzieć, że JavaScript ma nieco inne właściwości niż choćby C++. Tu liczy się każda operacja. Dostałem bardzo oryginalne rozwiązanie oparte na wyszukiwaniu binarnym:


    var solve = function(arr){
        /*
            performs binary search on given array
            runs in log(n) where n is amount of elements in array
            @parameters:
                val       - searched value
                arr       - array where we seach, must be sorted in ascending order
                startLow  - optional, specifies starting low index of area of array where to perform search, defaults to 0
                startHigh - optional, specifies ending index of area in array where to search for given element, 
                            defaults to arr.length - 1

            @returns: 
                if searched value is in array, returns index of searched element in given array range which is >= 0
                if searched value is not in given array, returned value is < 0, and is equal to (last checked index + 1) * (-1)
        */
        var binSearch = function(val, arr, startLow, startHigh){
            var stopFnct = function(low, high){ return low > high;};
            var foundFnct = function(arr, idx, val){ return arr[idx] == val;};
            var _newBinSearchFnct = function(val, arr, startLow, startHigh){
                return _binSearch(val, arr, startLow, startHigh, stopFnct, foundFnct);
            }
            binSearch = _newBinSearchFnct;
            return binSearch.apply(null, arguments);
        }
        
        /*
            searches for the index of oelement in sorted array so that searched element value is <= val and next element's 
            value in array is greater than val (>val)
            for example:
                >>>  diviseSearch(3, [1, 2, 3, 4, 5])
                2
                >>> diviseSearch (3, [1, 2, 4, 5])
                1

            runs in log(n) where n is amount of elements in array

            @parameters:
                val       - value that should divide array
                arr       - array where we seach, must be sorted in ascending order
                startLow  - optional, specifies starting low index of area of array where to perform search, defaults to 0
                startHigh - optional, specifies ending index of area in array where to search for given element, 
                            defaults to arr.length - 1

            @returns: 
                if searched value is in array, returns value >= 0 which represents index of searched element in given array range
                if searched value is not in given array then funciton returns -1
        */
        var diviseSearch = function(val, arr, startLow, startHigh){
            var stopFnct = function(low, high){ return low > high;};
            var foundFnct = function(arr, idx, val){ return arr[idx] <= val && arr[idx + 1]>val;};
            var _newDiviseSearch = function(val, arr, startLow, startHigh){
                //M3 return _binSearch(val, arr, startLow, startHigh, stopFnct, foundFnct);
                var res = _binSearch(val, arr, startLow, startHigh, stopFnct, foundFnct);
                if(res<0){
                    return -(++res);
                } else {
                    return -1;
                }
            }
            diviseSearch = _newDiviseSearch;
            return diviseSearch.apply(null, arguments);
        }

        /*
            It performs binary search with custom function which checks whether proper index is found.

            Searches for value of index pointing to element in given array in the way so that the minimal amount of index changes
            would be required so that given function would succeed on changed index value. Assumes that:

                IF idx1 < idx2 AND solution isn't found in idx1 THEN 
                for all idx3, so that idx3 < idx1, the solution for idx isn't found either
            AND
                IF idx1 > idx2 AND solution isn't found in idx1 THEN 
                for all idx3, so that idx3 > idx1, the solution for idx isn't found either


            @parameters:
                val       - value that will be passed to foundFnct, it's meaning depends on foundFnct
                arr       - array where we seach, must be sorted in ascending order
                startLow  - optional, specifies starting low index of area of array where to perform search, defaults to 0
                startHigh - optional, specifies ending index of area in array where to search for given element, 
                            defaults to arr.length - 1
                foundFnct - function that gets arguments: arr, idx, val. Meninng of these arguments is as follows:
                                arr - array where search is performed
                                idx - index that we ask if it may be the solution
                                val - value passed by the user
                            it should on the basis of given arguments determine whether currently checked index is solution
                            or not
                stopFnct  - function that takes two arguments: low, high. Mening of these arguments is as follows:
                                low - the lower index of the area in the searched array, 
                                high - the upper index of the area in the searched array
                            on the basis of given arguments, it should determine whether to stop for searching 
                extra_params - not used, but may be extended further for returning extra data (extra_params may be 
                               passed as reference to object, and on that object will be added extra information about search (e.g.
                               checked indexes, checked values etc.)
                        
                           
            @returns:
                if returned value is < 0, then it's absoulte value represents ((index of array where foundFnct succeed) + 1)
                if returned value is >= 0, then it represents last checked index

        */
        var _binSearch = function(val, arr, startLow, startHigh, stopFnct, foundFnct, extra_params ){
            var length = arr.length,
            low = startLow || 0,
            high = startHigh || length - 1,
            idx, last_idx;

            for(var floor = Math.floor;;){
                idx = (high + low) / 2; //calculate middle index
                idx = floor(idx);
                last_idx = idx;

                // in the if-else block below, on the first position should be checking 
                // whether foundFnct succeed, because foundFnct may succeed if arr[idx] < val or arr[idx] > val
                if(foundFnct(arr, idx, val)){
                    return -(idx + 1);
                } else if(arr[idx] > val){ 
                    high = --idx;
                } else { // arr[idx] < val
                    low = ++idx;
                }
                
                if(stopFnct(low, high))
                    return last_idx;
            }
        };

        var do_solve = function(arr){
            var swap = function(){
                var old_sLow = sLow, old_sHigh = sHigh, old_sIdx = sIdx;
                sLow = hLow, sHigh = hHigh, sIdx = hIdx;
                hLow = old_sLow, hHigh = old_sHigh, hIdx = old_sIdx;
            }

            var ret = [], 
            length = arr.length,
            divIdx = diviseSearch(0, arr),
            midEl = arr[divIdx];

            if(divIdx === -1)
                return [];

            var smaller_amount = divIdx;// calculate amount of negative and positive elements in array
            if(midEl != 0)
                smaller_amount += 1;
            var higher_amount = length - smaller_amount,
            sLow = 0, sHigh = divIdx, sIdx, 
            hLow = divIdx + 1 , hHigh = length - 1, hIdx;
            if(midEl == 0)
                sHigh--;

            if(smaller_amount == 0 || higher_amount == 0)
                return [];

            if(higher_amount < smaller_amount)
                swap();



            var searched, res, toAdd,
            ret = new Array(Math.ceil(length/2)),
            retCount = 0;
            for(var i=sLow, abs = Math.abs; i<=sHigh; i++){
                searched = -arr[i];
                res = binSearch(searched, arr, hLow, hHigh);
                if(res < 0){
                    res *= -1;
                    res -= 2;
                    ret[retCount++] = abs(searched);
                    hHigh=res;
                }else{
                    hHigh=res;
                    if(hLow == hHigh)
                        break;
                }
            }

            return ret.slice(0, retCount);
        }

        solve = do_solve;
        return solve.apply(null, arguments);
    }

Okazało się jednak, że to przerost formy nad treścią.

Z innych ciekawych rozwiązań:

function solve(i){return(i+'').match(/-(\d+)(?=.*?,\1\b)/g).map(Math.abs)}

Zamiana tablicy na stringa i potem wyszukanie powtarzających się wartości. Sprytne, niestety dość wolne.

Inny bardzo JavaScriptowy kod to:

function solve(arr) {
    return arr.filter(function(v,i,a){ return a.indexOf(-v) !== -1 && v>0; });
}

Korzysta z dobrodziejstw JS 1.6+, niestety jest dość wolny.

Warto też wkleić kod szybkich rozwiązanń: HrynKa:

/**
 * funkcja realizujaca zadanie konkursowe z http://ferrante.pl/2011/03/02/wygraj-ksiazki-o-javascript-i-html5/
 *
 * Algorytm opiera sie na iteracji tablicy z obu koncow. Pozycja w tablicy przesuwana jest na kolejna (ku liczbom o
 * mniejszych wartosciach bezwzglednych) z tej strony, z ktorej wartosc bezwzgledna liczby pod dana pozycja jest
 * wieksza. Dojscie do zera, z ktorejkolwiek strony, konczy dzialanie.
 *
 * @author Maciej "HryneK" Hryniewicz 
 * @param array data posortowane rosnaco unikalne liczby calkowite
 * @return array liczby dodatnie, ktorych wartosc absolutna pojawila sie dwukrotnie w tablicy wejsciowej
 */
window.solve = function (data) {
	var ans = [], // dane wyjsciowe
		ans_len = 0, // ilosc elementow w tablicy wyjsciowej - dla recznej realizacji .push()
		idx_a = 0, // "lewa" pozycja w tablicy
		idx_b = data.length - 1, // "prawa" pozycja w tablicy
		a, // wartosc bezwzgledna "lewej" liczby
		b; // wartosc bezwzgledna "prawej" liczby
	
	if (idx_b < 1) {
		// w tablicy wejsciowej sa mniej niz dwa elementy
		return [];
	}
	
	a = -data[idx_a], // na razie zakladamy, ze liczba jest ujemna
	b = data[idx_b]; // na razie zakladamy, ze liczba jest dodatnia

	if (a <= 0 || b <= 0) {
		// w danych wejsciowych nie ma dodatnich i ujemnych wartosci - wynik jest pusty
		return [];
	}

	while (true) {
		while (a > b) {
			if ((a = -data[++idx_a]) <= 0) {
				return ans;
			}
		}
		while (a < b) {
			if ((b = data[--idx_b]) <= 0) {
				return ans;
			}
		}
		if (a == b) {
			// @todo jak .push() przyspieszy, to podmienic i usunac komentarze
			ans[ans_len++] = b; // szybsze niz .push()

			// bierzemy kolejna "prawa" liczbe (mozna byloby brac nastepna lewa - w zaleznosci, czy
			// spodziewamy sie miec wiecej ujemnych czy dodatnich liczb w danych wejsciowych)
			if ((b = data[--idx_b]) <= 0) {
				return ans;
			}
		}
		// wartosci bezwzgledne nie sa rowne, wiec znowu "lewa" jest wieksza - zaczynamy kolejny obieg
	}
}

Piotrka Koszulińskiego:

var solve = function(input) {
 var a = 0,
	  b = input.length - 1,
	  av, bv, output = [];

 if (b < 1) return [];

 av = Math.abs(input[0]);
 bv = Math.abs(input[b]);

 while (a < b) {
  if (av > bv) {
	av = Math.abs(input[++a]);
  }
  else if (av < bv) {
	bv = Math.abs(input[--b]);
  }
  else {
	output[output.length] = av;
	av = Math.abs(input[++a]);
	bv = Math.abs(input[--b]);
  }
 }

 return output;
};

Czy Przemka Ciężkowskiego:

window.solve = function (input) {
	 var output = [], length = input.length;
	 if (length > 1){
				var l = 0, r = length - 1, abs = Math.abs, tmp1 = abs(input[l]),
tmp2 = abs(input[r]);
				do{
						  if (tmp1 > tmp2){
									 tmp1 = abs(input[++l]);
						  }else if (tmp1 < tmp2){
									 tmp2 = abs(input[--r]);
						  }else{
									 output[output.length] = tmp1;
									 tmp1 = abs(input[++l]);
									 tmp2 = abs(input[--r]);
						  }
				}while (l < r);
	 }
	 return output;
};

A oto zestaw danych, na którym testowaliśmy:

var testArr = [];
var testArr2 = [];
var testArr3 = [];
var testArr4 = [];
var testArr5 = [];
var testArr6 = [];

for (var i = -10; i < 10; i++) {
	testArr.push(i);
}


for (var i = -100; i < 100; i++) {
	 testArr2.push(i);
}


for (var i = -500; i < 100; i++) {
	testArr3.push(i);
}


for (var i = -10000; i < 10000; i++) {
	testArr4.push(i * 2);
}

for (var i = -50000; i < 50000; i++) {
	testArr5.push(i);
}

for (var i = -3000000; i < 3000000; i++) {
	if (Math.random() > 0.5) {
		testArr6.push(i);
 	}
}

Oczywiście w grę wchodziły również styl i długość kodu. Co się jednak okazało, najszybszy kod był jednym z najkrótszych i bardzo dobrze napisanych. Gratulujemy zwycięzcy!

Komentarze

1

Gratulacje dla zwycięzcy. Ładnie pokomentował kod, dzięki czemu przyjemnie się go czyta.

Za to wyszukiwanie binarne to niezłe szaleństwo, podobnie jak jednolinijkowy match ;]

2

“Najczęstszym rozwiązaniem z kolei była iteracja po tablicy dwa razy w celu sprawdzenia ponownego wystąpienia liczby, co nie jest najbardziej wydajnym sposobem (n^2).”

Dwa razy to złożoność nadal liniowa o(n) co prawda z gorszą stałą (2n).

3

Pozwolę sobie przyczepić się do kilku rzeczy w zwycięskim rozwiązaniu (i proszę się nie obrażać, robię to tylko w celach edukacyjnych).

Optymalizacja ~-length ładna (pomijając fakt, że jest faktyczną optymalizacją chyba jedynie w Fx, w pozostałych silnikach length-1 jest równie wydajne, bądź wydajniejsze), ale ma małe znaczenie (wykonywane tylko raz). Zupełnie przy tym nie widzę sensu tworzenia zmiennej lokalnej length. Podobnie z wartością początkową zmiennej a – po cą ją ustawiać, skoro zostanie napisana w warunku końcowym głównej pętli?

Poważnym problemem jest za to brak przerwania głównej pętli w momencie gdy b<=0. Na szczęście dla tego rozwiązania niemal wszystkie testowe dane wejściowe (które nawiasem mówiąc powinny były być podane wraz z treścią konkursu) są “symetryczne” (liczba wartości mniejszych od zera jest mniej więcej taka sama, jak liczba wartości większych od zera).

Poza tym oczywiście bardzo ładne rozwiązanie.

Tomasz Elendt
4

Sorry za bajzel w komentarzach – nie wiedziałem, że zamieniasz wszystkie tagi code na bloki.

Tomasz Elendt
5

pedro: fakt.

6

@ferrante, @pedro: zależy od funkcji szukania. Jeśli jest “bezstanowa” (za każdym razem iteruje po tablicy od jej początku) to złożoność pesymistyczna wynosi O(n^2).

Tomasz Elendt
7

@Tomaszu: Wyciagalem srednie czasy w wielu testach, tworzac tez asymetryczne testy. testArr6 do tego sluzylo.

Co masz na mysli z b<=0 ?

8

Jak duże były różnice w wydajności poszczególnych rozwiązań?

H
9

Kowalsky: 19op/s, Ciezkowski/Koszulinski: 11op/s, Hrynek: 12op/s na mega duzych tablicach rzedu miliona.

10

Co masz na mysli z b<=0 ?

http://jsperf.com/ferrante-quiz

Tomasz Elendt
11

Mała uwaga. Podane rozwiązanie zwraca dane posortowane malejąco.
Biorąc pod uwagę dane z przykładu algorytm miał nie zmieniać porządku!

Nie zmienia to faktu, że zapomniałem w swoim rozwiązaniu uwzględnić zero (shame on me).

Niemniej chciałbym poznać szybszą alternatywę dla Array.unshift()

12

Zauważ, że przy opisie wejścia zaznaczyliśmy, że ma być posortowane, przy wyjściu tak nie było. Sugerowanie się przykładem było trochę naiwne ;-)

13

Zauważ, że przy opisie wejścia zaznaczyliśmy, że ma być posortowane, przy wyjściu tak nie było. Sugerowanie się przykładem było trochę naiwne ;-)

Spoko podejście, może następnym razem nie dawaj przykładów w takim razie ;-)

fridek
14

Wiedziałem, że zacznie się tyrada. Jeśli czegoś nie ma, to to nie obowiązuje. Jeśli nie jesteś czegoś pewien – pytasz. Nie przewidziałem takich dylematów, wydawało mi się to jasne. Sorry Panowie.

Pozostałe szczegóły implementacji programu są mniej znaczące.

Wyjście:
Tablica z niepowtarzającymi się liczbami dodatnimi, których wartość absolutna pojawiła się w tablicy dwa razy.

15

Gdyby natomiast miało dla Ciebie znaczenie (np. ze względu na sposób porównywania tablic wyjściowych z danymi testowymi i to, że np. chciałeś zobaczyć jak ludzie sobie poradzą tym problemem) to wtedy w komentarzu bym zobaczył, że “przecież był podany przykład wyjścia, który był posortowany rosnąco”. Jak dla mnie to nie jest powód do nerwów, ale na przyszłość warto takie rzeczy doprecyzować, ponieważ we wszelkich konkursach tego typu dane wyjściowe programu muszą się pokrywać całkowicie z danymi testowymi.

16

@DrLex: Jeśli dobrze pamiętam to w komentarzach ktoś pytał się o to czy plik wyjściowy musi być posortowany, czy nie. I padła tam odpowiedź.

Więc skoro już zauważyłeś, że w tekście brakuje informacji o tym w jakiej kolejności muszą być elementy w tablicy wyjściowej, a w przykładzie są posortowane, to chyba warto było się dopytać?

Poza tym ja nie widzę problemu – czytam treść zadania i nie dodaję sobie własnych interpretacji.

17

@Piotrek, ok skoro było doprecyzowane to zwracam honor.

18

Kiedy rozwiązanie HTML5/CSS3?

Bartek
19

Dobry konkurs i ciekawe rozwiązania, liczę na kolejne edycje ;)

20

@Tomasz Elendt
~-length – takie tam bezsensowne udziwnienie kodu :)
“Zupełnie przy tym nie widzę sensu tworzenia zmiennej lokalnej” – pozostałość po tym, jak to miało znaczenie… i zapomniałem z tym wylecieć.
“po cą ją ustawiać, skoro zostanie napisana w warunku końcowym głównej pętli?” – performance boost. Czytanie elementów tablic/obiektów jest dość wolne (przeszukiwanie), spróbuj podmienić a na wartości i zobacz jak wiele tracisz.
“Poważnym problemem jest za to brak przerwania głównej pętli w momencie gdy b<=0" – hmm, nie jestem pewien, czy byłoby szybsze w ogólności ("ale Ty to sprawdź":), p. ppkt wyżej

21

@Yann: Nie zrozumiałeś mnie – deklaracja zmiennej “a” jak najbardziej. Wiem, że odwołanie do indeksu tablicy kosztuje. Ale po co ustawiasz wartość początkową na “-input[0]”, skoro nadpisujesz ją w warunku końca pętli (wykonywanym PRZED każdą iteracją). Ten fragment zwyczajnie nie ma sensu.

Jeśli chodzi o warunek b<=0 to tak, sprawdziłem to. Podałem nawet linka do testu, gdzie jako dane wejściowe użyłem 3 zbiorów o równej liczebności – jeden "symetryczny", jeden zawierający tylko wartości dodatnie i jeden zawierający tylko wartości ujemne. Twój kod zyskał znacznie na wydajności po dodaniu tego warunku.

Na szczęście "ogólność" którą zdefiniował Damian jest odmienna od "ogólności" którą zdefiniowałem ja w tym teście.

Tomasz Elendt
22

A kiedy wreszcie beda wyniki css?

dawid
23

Czekamy z niecierpliwością. Praktycznie dwa tygodnie od zakończenia minęły. Może w prima aprilis się dowiemy ;-)

Dodaj komentarz

Dozwolone tagi: <blockquote>, <code>, <strong>