nizovi &amp; nizovi

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*

+6 Profil

^{11.02.2002. u 16:30 - pre 279 meseci}

Auuu, dobar, dobar! Na "prvu loptu" rešenje bi moglo da bude sledeće:

za svaki "par" koji želiš da proveriš, napravi jednu malu for petlju. U okviru petlje, "zamaskiraj" gornjih 8 bitova u A, pa uporedi sa B. Onda "šiftuj" A udesno, pa tako redom.

Pseudo-kod primer:

Code:

short tempA = A[k];
for (j = 0; j < 8; j++)
{
  short masked = tempA & 0x00ff; // maskiraj gornje bitove
  if (masked == B[k])
  {
   //uslov ispunjen
   ...
   break;
  }
  tempA >> 1;
}

Nego, evo dok čekam da se opere veš (znam šta mislite mangupi, ali pitaću vas kad se oženite) sastavio sam ceo primer (uploadovan uz poruku)

[Ovu poruku je menjao Dragi Tata dana 10.09.2002 u 10:55 AM GMT]

[Ovu poruku je menjao Dragi Tata dana 10.09.2002 u 10:56 AM GMT]

Prikačeni fajlovi

zez.cpp - 0.44k

jc denton

Član broj: 2358
Poruke: 1705
*.ptt.yu

Profil

^{17.02.2002. u 06:35 - pre 279 meseci}

mozda se butam de ne treba jer radim u VB-u, ali evo ideje pa je prebudzite na C++ :

dim c (n) as long ' to je zeljeni novodobijeni niz
for i =1 to n
if Instr(trim(str(a(i))), trim(str(b(i))), 1) >0 then c(i)=a(i)
next

jebem li ga sta je ekvivalent za Instr u C++ ...

fire, walk with me

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*

+6 Profil

^{18.02.2002. u 21:05 - pre 279 meseci}

Citat:

jc denton:
jebem li ga sta je ekvivalent za Instr u C++ ...

Ekvivalent je string::find(). Ali čini mi se da je postavka zadatka bila takva da se na ulazu traži broj, a ne string koji sadrži nule i jedinice. Naravno, uvek možeš iz broja da dobiješ takav niz, ali to je malo "izokola".

jc denton

Član broj: 2358
Poruke: 1705
*.ptt.yu

Profil

^{19.02.2002. u 01:21 - pre 279 meseci}

Dobro, uzmimo da je string.

Koja bi metoda bila brza ?

fire, walk with me

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
..ndg-pm4-1.dialup.nethere.net

+6 Profil

^{19.02.2002. u 01:38 - pre 279 meseci}

Citat:

jc denton:
Dobro, uzmimo da je string.

Koja bi metoda bila brza ?

Ako je string, onda je tvoja metoda "prava". Ona koju sam ja naveo gore, radi samo za brojeve.

A inače, šta je brže a šta ne, retko može da se uspešno proceni na osnovu koda. Treba probati pa izmeriti.

jc denton

Član broj: 2358
Poruke: 1705
*.ptt.yu

Profil

^{19.02.2002. u 01:50 - pre 279 meseci}

Postavio sam pitanje oko brzine zato sto sam svojevremeno pisao neki SW za tombolu, pa je tu neku pretrazivanje listica itd.

Naguram ti ja sve listice (po 15 dvocifrenih brojeva po listicu) u string, pa tom kverujem preko Instr.

Znas za koliko je nalazio listic na nekih 50 000 * 15 pretrazenih karaktera ?

Na tadasnjem Intel Pentium 133 MHz , cirka 11 sec. !!!

Koliko bi to bilo brzo u C++??

fire, walk with me

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
..ndg-pm4-1.dialup.nethere.net

+6 Profil

^{19.02.2002. u 02:00 - pre 279 meseci}

Citat:

jc denton:

Koliko bi to bilo brzo u C++??

Verovatno bi bilo brže, ali koliko ne bih znao. Treba probati pa videti.

Sa optimizacijom je jedino sigurno to da nikad nisi siguran šta ćeš da dobiješ.

deda Miloje
NBG

Član broj: 2246
Poruke: 56
*.ppp-bg.sezampro.yu

Profil

^{22.02.2002. u 22:09 - pre 279 meseci}

ljudi , thanks

voli deda baba_devojke

sportbili

Član broj: 5083
Poruke: 16
*.dial.InfoSky.Net

Profil

^{10.09.2002. u 19:43 - pre 272 meseci}

Citat:

Dragi Tata:

za svaki "par" koji želiš da proveriš, napravi jednu malu for petlju. U okviru petlje, "zamaskiraj" gornjih 8 bitova u A, pa uporedi sa B. Onda "šiftuj" A udesno, pa tako redom.
Pseudo-kod primer:

Code:

short tempA = A;
for (j = 0; j < 8; j++)
{
short masked = tempA & 0x00ff; // maskiraj gornje bitove
if (masked == B)
{
//uslov ispunjen
...
break;
}
tempA >> 1;
}

Stara je tema ali me interesuje samo jedna stvar. Cemu siftovanje A u desno nakon maskiranja? Da li zbog sledeceg:

0011001101011101 (prviniz[0] naprimer) & 0000000011111111 ('A')
i dobijemo 0000000001011101 koji je eventualno druginiz[0].

Onda siftujemo prviniz[0] za 1 u desno i dobijamo
0001100110101110.

OK, ali zasto siftujemo? Da bi smo proverili da li se u njemu (dakle stringu 0001100110101110) sadrzi druginiz[0]? To je pitanje. :-)

Mada ako posmatramo brojeve a ne stringove onda nam ne treba to vec samo prvi slucaj sa maskiranjem?

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
199.171.112.*

+6 Profil

^{10.09.2002. u 20:05 - pre 272 meseci}

Recimo da imamo 16-bitni broj 0011011011011001 i da treba da proverimo da li je niz bitova 01101100 sadržan u njemu.

Najpre zamaskiramo gornjih 8 bitova i dobijemo 0000000011011001. Kad to uporedimo sa 01101100, videćemo da nije isto. Onda šiftujemo gornji broj za jedan udesno i dobijemo 0001101101101100; kad zamaskiramo gornje bitove, to je 0000000001101100 a to jeste jednako 01101100.

Znači, da nismo šiftovali, mi bismo proverili samo da li je 01101100 prvih 8 bitova sa desne strane, a ne bismo znali da li ta kombinacija bitova postoji negde drugde unutar broja.