array intersection u JS

[ivanhoe]

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]

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

[dejanr]

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

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

posto ce se length racunati u svakoj iteraciji

[Dragi Tata]

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

[ivanhoe]

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]

Originalno napisao ivanhoe

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

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

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

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]

Originalno napisao dejanr

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

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

posto ce se length racunati u svakoj iteraciji

.length je atribut, ne metoda.

[Blood]

Originalno napisao dejanr

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

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]

^ 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]

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:

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:

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...