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. 23: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. 23:56

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

dejanr 25. 02. 2010. 00: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 25. 02. 2010. 00:34

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

ivanhoe 25. 02. 2010. 00: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 25. 02. 2010. 00: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. 01: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. 03: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. 12: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. 16: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...


Vreme je GMT +2. Trenutno vreme je 00:59.

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.