Strona gナづウwna - poczytaj o JavaScript, jQuery, CSS i HTML5

RSSSubscribe RSS

Zwycięzca konkursu CSS

Panie i Panowie. Brawa dla Krzysztofa Urbasa za zwycięstwo w konkursie CSS.

Powiem szczerze, że miałem duży dylemat pomiędzy jeszcze jedną pracą. Generalnie, co zadecydowało to mała wielkość kodu, brak nadmiarowych klas czy tagów i jeden szczegół – obecność wrappera na wszelki wypadek. Ten css jest po prostu dobrze napisany i działa. A propos – na stronie Opery możecie przetestować go pod Operą Mini.

Punktowaliśmy przede wszystkim to, czy używacie najświeższych ficzerów CSS3. Tak więc można było użyć przede wszystkim dwóch rzeczy: display: box oraz calc. Potem było działanie na urządzeniach mobilnych – wiele przysłanych rozwiązań tego nie wspierało. Liczyła się też schludność kodu. Jeśli ktoś dodawał mnóstwo niepotrzebnych id to był oceniany niżej (to musiało być jednym z kryteriów z powodu wąskiej tematyki, mimo że identyfikatory nic nie robiły). Było też jedno rozwiązanie na table-cell oraz różne kombinowanie z marginesami czy z position.

Jeszcze raz przepraszam za opóźnienie. Ostatnio wróciłem do szkoleń z JS, pracuje też nad wieloma rzeczami naraz, co w połączeniu dało taki a nie inny efekt. Niemniej, chciałbym podziękować za kilkanaście rozwiązań. Większość z nich była na wysokim poziomie, chociaż pojawiło się kilka na podstawie float – zachęcam ich autorów do sprawdzenia nowości.

Wyszedł Firefox 4

Nowy, o wiele szybszy, bardziej bezpieczny. Jest już nowy Firefox 4, do pobrania którego gorąco zapraszam. Nowe ficzery HTML5 teraz w zasięgu ręki dla o wiele szerszej publiczności! Yay!

Tutaj dowiesz się, co nowego w czwartej wersji. M.in. o wiele szybszy JavaScript, zmodyfikowany interfejs i wiele innych!

Polecam też zobaczyć jak szybko i w jakich ilościach jest pobierana nowa wersja Firefoksa. Jest też bardzo ciekawe Twitter Party – efekt „wow” murowany.

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!

Konferencja Falsy Values za 250zł!

Konkurs z Autentika.pl – zakończenie

Ludzie Front-Endu: Marek „marcoos” Stępień

Podstawy JavaScript ze mną na Falsy Values

Falsy Values – JavaScriptowa konferencja 18-20 maja w Warszawie!

Warszawski meet.js w PJWSTK 19. marca o 12:00

Ludzie Front-Endu: Piotr Zalewa

Wygraj książki o JavaScript i HTML5

Ludzie Front-Endu: Kornel „porneL” Lesiński

Ludzie Front-Endu w Polsce

To dzisiaj

Poszukiwani prelegenci na meet.js w Warszawie

meet.js::after

meet.js – spotkajmy się by pomówić o webdev

JavaScript – podstawowe błędy #1

Rok 2010

JSNews Meetup – Poznań

Pages: newer posts 1 2 3 4 5 6 7 8 ... 12 13 14 older posts