DevProTalk - array intersection u JS

DevProTalk

DevProTalk (http://www.devprotalk.com/index.php)

- (X)HTML, JavaScript, DHTML, XML, CSS (http://www.devprotalk.com/forumdisplay.php?f=8)

- - array intersection u JS (http://www.devprotalk.com/showthread.php?t=8479)

ivanhoe

24. 02. 2010. 22:25

array intersection u JS

Treba mi presek 2 niza (lista elemenata koji se pojavljuju i u jednom i u drugom). E sad, naravno to mogu da uradim seljacki sa 2 petlje, ali posto ima jako puno elemenata n^2 efikasnost mi je prespora, zakuca se browser. Jel postoji neki efikasniji algoritam?

BluesRocker

24. 02. 2010. 22:56

Ovi su isto uradili seljacki. :) Mozda je njihov algoritam brzi.
http://phpjs.org/functions/array_intersect:318

dejanr

24. 02. 2010. 23:12

Kad smo vec kod optimizacije js-a ovo ne treba nikad raditi :

Kôd:

for (i=1; i < arguments.length; i++) {

posto ce se length racunati u svakoj iteraciji :)

Dragi Tata

24. 02. 2010. 23:34

Можеш ли да обезбедиш да низови буду сортирани пре него што тражиш интерсекцију?

ivanhoe

24. 02. 2010. 23:37

bilo bi mi cudno da se length racuna (da se broji svaki put), verovatno niz objekat to cuva kao interni podatak koji samo prikaze?

@tata: mogu, nizove punim na pocetku, pa nije previse skupo da ih izsortiram

Dragi Tata

24. 02. 2010. 23:44

Citat:

Originalno napisao ivanhoe (Napišite 80219)

@tata: mogu, nizove punim na pocetku, pa nije previse skupo da ih izsortiram

Онда можеш да нађеш пресек у линеарном времену, тј у једној петљи.

Ево ти и код (нађох га негде на интернету, изгледа ок на први поглед):

Kôd:

int[] a = {0,2,3,2,2,7,2,5,5,5,5,5,5};   

int[] b = {0,0,0,0,3,7,3,2,2,2,4,5};   

  

Arrays.sort(a);   

Arrays.sort(b);   

           

int i=0,j=0;   

while (i<a.length && j<b.length) {   

    if (a[i]==b[j]) { // equal   

        int n=a[i];   

        System.out.println(n);   

        while (i<a.length && a[i]==n) i++; // skip equal   

        while (j<b.length && b[j]==n) j++; // skip equal   

    } else if (a[i]<b[j]) i++; // one is less   

    else j++; // the other is less   

}

skaarj

25. 02. 2010. 00:14

Citat:

Originalno napisao dejanr (Napišite 80217)

Kad smo vec kod optimizacije js-a ovo ne treba nikad raditi :

Kôd:

for (i=1; i < arguments.length; i++) {

posto ce se length racunati u svakoj iteraciji :)

.length je atribut, ne metoda.

Blood

25. 02. 2010. 02:30

Citat:

Originalno napisao dejanr (Napišite 80217)

Kad smo vec kod optimizacije js-a ovo ne treba nikad raditi :

Kôd:

for (i=1; i < arguments.length; i++) {

posto ce se length racunati u svakoj iteraciji :)

Off Topic: Ovo sam i ja procitao negde, cak sta vise, procitao sam da to vazi za bilo koji jezik koji nema kompajler..

jablan

25. 02. 2010. 11:52

^ Logično je da važi za svaki jezik koji ima c-ovski for, nebitno "imao kompajler" ili ne, na čelu sa c-om... :)

ivanhoe

25. 02. 2010. 15:48

nije sporno da se to sto pise u uslovu svaki put poziva, ali ovde se radi o propertiju, koji se samo procita iz objekta, ne izracunava mu se vrednost svaki put (niz zna koliko je dugacak), pa je zato razlika minimalna...

Evo probajte i sami u firebugu:

Kôd:

var a = [];

var b = [];

var start = new Date();

for(var i=0; i<1000000; i++)

    a.push(i);

var end = new Date();



console.log( (end-start) /1000)



var start = new Date();

for(var i=0; i<a.length; i++)

    b.push(i);

var end = new Date();



console.log( (end-start) /1000)

Dobije se, iz nekoliko pokretanja:

Citat:

const .length
------------------
0.866 1.063
0.862 1.064
0.866 1.067
0.852 1.056
0.866 1.066

znaci jeste malo sporiji pristup propertiju nego varijabli, ali razlika je smesna, ~0.2 mikrosekunde po iteraciji, po meni je to nebitno, i sto je najbitnije ne degradira se povecanjem broja elemenata, nego zavisi od js kompajlera..

Ali zato u php-u nikako ne treba raditi for($i=0; $i<count($nesto); $i++) jer to zaista broji elemente niza svaki put...

ivanhoe

25. 02. 2010. 16:07

zapravo mala ispravka prethodnom testu, ovako ce biti jos realnija situacija, jer obicno ne znamo unapred koliko ima elemenata niza, pa u prvom slucaju mora da se uradi dodela vrednosti prvo:

Kôd:

var a = [];

for(var i=0; i<1000000; i++)

    a.push(i);



var dummy;

var start = new Date();

var tmp = a.length;

for(var i=0; i<tmp; i++)

    dummy=1;

var end = new Date();



console.log( (end.getTime() - start.getTime()) /1000)



var start = new Date();

for(var i=0; i<a.length; i++)

    dummy=1;

var end = new Date();



console.log( (end.getTime() - start.getTime()) /1000)

kad se ovo pokrene, rezultati su prakticno identicni (ispadne prvi metod nekad i sporiji, znaci radi se o gresci merenja), tako da mozemo slobodno da tvrdimo da nema apsolutno nikakve razlike.

noviKorisnik

25. 02. 2010. 16:16

Valja i da se izbegne brlja poput sledeće:

Kôd:

var a = [];

for (var i = 0; i <= a.length; i++)

    a.push(i);

:-D

Dragi Tata

26. 02. 2010. 17:30

Citat:

Originalno napisao jablan (Napišite 80292)

^ Logično je da važi za svaki jezik koji ima c-ovski for, nebitno "imao kompajler" ili ne, na čelu sa c-om... :)

Сваки иоле нормалан компајлер ће да генерише потпуно идентичан машински код у оба случаја. Сад, шта раде ови "модерни", JIT-овани компајлери, то већ не знам. Пар пута сам се запрепастио гледајући шта JVM и CLR не оптимизују, али може бити да је у тим ситуацијама JIT компајлер једноставно закључио да нема сврхе оптимизовати даље.

jablan

26. 02. 2010. 18:44

Misliš smestiće rezultat funkcije u neku internu promenljivu, pa uvek porediti s njom, bez obzira što bi pri nekom od sledećih poziva funkcije dobio različit rezultat?

Dragi Tata

26. 02. 2010. 19:17

Citat:

Originalno napisao jablan (Napišite 80511)

Misliš smestiće rezultat funkcije u neku internu promenljivu, pa uvek porediti s njom, bez obzira što bi pri nekom od sledećih poziva funkcije dobio različit rezultat?

Не, једноставно ће да "инлајнује" (каква реч!) функцију. Рецимо, метод као што је length обично изгледа некако овако:

Kôd:

int length { return l; }

У пракси ће компајлер код позива метода length једноставно да уклони цеопозив те функције и уместо тога ће директно да приступи интерној променљивој. На пример:

Kôd:

n = arr.length();

ће у ствари да се замени еквивалентом овога:

Kôd:

n = arr.l;

Vreme je GMT +2. Trenutno vreme je 09:01.

Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright © DevProTalk. All Rights Reserved.

Mišljenja, saveti, izjave, ponude ili druge informacije ili sadržaji nastali na Sajtu su vlasništvo onoga ko ih je kreirao, a ne DevProTalk.com, tako da ne morate da se oslanjate na njih.
Autori poruka su jedini odgovorni za ovakve sadržaje. DevProTalk.com ne garantuje tačnost, kompletnost ili upotrebnu vrednost informacija, stavova, saveta ili datih izjava. Ne postoje uslovi pod kojima bi mi bili odgovorni za štetu ili gubitak koji je posledica bilo čijeg oslanjanja na nepouzdane informacije, ili bilo kakve informacije nastale kroz komunikaciju između registrovanih članova.
Web sajt može sadržavati linkove na druge web sajtove na Internetu ili neke druge sadržaje. Ne kontrolišemo niti podržavamo te druge web sajtove, niti smo pregledali bilo kakve sadržaje na takvim sajtovima. Mi nećemo biti odgovorni za legalnost, tačnost ili prikladnost bilo kog sadržaja, oglasa, proizvoda, usluga ili informacije lociranim na ili distribuiranih kroz druge web sajtove, niti za bilo kakvu štetu nastalu kao posledica takvih informacija. DevProTalk.com drži i čuva druga prava vlasništva na web sajtu. Web sajt sadrže materijale zaštićene copyright-om, zaštitne znakove i druge informacije o pravu vlasništva ili softver. Članovi mogu poslatu informacije zaštićene pravima vlasništva njihovih nosilaca i ona ostaju zaštićena bez obzira da li su oni koji prenose te informacije to naveli ili ne. Osim informacija koje su u javnom vlasništvu ili za koje dobijete dozvolu, nemate pravo da kopirate, modifikujete ili na bilo koji način menjate, objavljujete, prenosite, distribuirate, izvršavate, prikazujete ili prodajte bilo koju informaciju zaštićenu pravima vlasništva. Slanjem informacija ili sadržaja na bilo koji deo DevProTalk.com, Vi automatski dozvoljavate i predstavljate garanciju da imate pravo da dozvolite DevProTalk.com ili članovima DevProTalk.com bespovratnu, kontinualnu, neograničenu, globalnu dozvolu da koriste, kopiraju, izvršavaju, prikazuju i distribuiraju takve informacije i sadržaje i da iz takvih sadžaja koriste bilo koji deo u bilo koje svrhe, kao i pravo i dozvolu da koriste gore navedene sadržaje. Svi zaštitni znakovi (trademarks), logotipi, oznake usluga, firme ili imena proizvoda koji se pominju na ovom web sajtu su vlasništvo kojim raspolažu njihovi vlasnici.