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.
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!
Jakiś czas temu uruchomiliśmy specjalną kategorię biletów za 250zł, które dają przepustkę na dzień konferencji Falsy Values w piątek 20 maja. Informujemy, że dzięki tej specjalnej promocji możecie na własne oczy zobaczyć sławy takie jak Douglas Crockford czy Tantek Çelik. Bilet na konferencję oznacza też wolny wstęp na imprezę towarzyszącą eventowi. No i oczywiście zapewniony jest pyszny obiad i przerwy kawowe. Zapraszamy wszystkich! Koniecznie powiedzcie o tym znajomym. Ceny nie mogą być już niższe! :-)
Tymczasem zostały ostatnie w ogóle bilety na workshop Tanteka Çelika czy ostatnie promocyjne bilety na workshop node.js. Lepiej się pospieszcie!