» »

Loopy problem

Loopy problem

StratOS ::

Saša je postavila en primer glede iskanja datotek/direktoriju po disku,no jaz pa sem se spomnil enega problema, ki mi dela preglavice na enem siteu.

Prosil bi za manjšo pomoč, kajti moj proggy v VB-u dela namrec zelo (BERI :ZELO počasi).Poleg tega pa postane nestabilen čez čas !

O čem je reč :
Gre so o tejle datoteki.

Gre se o sequenci stringa "ABCD".
Fajl vsebuje 100 robno kocko (100 x 100 x 100) (100 layerje-v po 100 x 100 kvadrata).
Iskani string ("ABCD") mora biti v takem zaporedju nahajan v tem fajlu v tej kocki v vseh možnih smereh in diagonalah ( Se pravi max. 26 smeri v enih točkah - notranjih).

Ja in kaj je tvoja naloga ?
Narediti program (ni važno v katerem jeziku), ki bo skalkuliral število nastopov tega stringa v celotni kocki.

Moj proggy najprej eliminira stringe črk, ki jih je največ, torej izbere črko ki je najmanj pojavljena v kocki, potem pa išče pare ...
Ampak počasi ...(kaj morem VB pač :()
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."
  • spremenila: StratOS ()

kopernik ::

Kaj zate pomeni počasi? (koliko sekund traja ena obdelava take datoteke)

Thomas ::

Hu hu hu ... madona, upam da bom čez vikend, no.

Mislim, probal tole.

:|
Man muss immer generalisieren - Carl Jacobi

StratOS ::

Odvisno kako dober si in kaj uporabljaš. VB is too slow, al pa morem neko drugo pot izbrati
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Thomas ::

Čaka tale tvoja zadeva pri meni na vrsto - že en mesec.

Pa ne pri meni pravzaprav - pri programu ...

Sej bo ... kmalu!

:)
Man muss immer generalisieren - Carl Jacobi

kopernik ::

si meril čase za različne operacije?
Torej:
- koliko časa potrebuje za branje datoteke (braz kakršnih koli računanj in drugih operacij)
- koliko časa potrebujeza operacije

Jaz sem se takrat, ko si dal tvoj post, malce poigral (v Javi) in stvar
ne bi smela biti tako huda. Ne vem. Sicer nisem implementiral
celotnega algoritma (ker nisem imel časa in volje), zato ti tudi
nisem odgovoril. Moji časi:
- branje te datoteke (1MB): cca 0.5 s
- obdelava v eno smer (le naprej), torej le v max. 13 smereh: cca. 0.2 s

Tale moj algoritem ni bil nič posebnega (tudi ni obravnaval robnih izjem),
ampak iz računskega stališče ti ne bi smelo vzeti preveč časa.
In s stabilnostjo tudi nisem imel problemov, ker sem v 5 threadih zagnal
10x zaporedoma.

lp

BigWhale ::

> si meril čase za različne operacije?
> Torej:
> - koliko časa potrebuje za branje datoteke (braz kakršnih koli računanj in drugih
> operacij)

Bleeh, to je zanemarljivo... 1MB dolg file preberes in a blink of an eye... :)

> - koliko časa potrebujeza operacije

Obdelava vodoravno, bi morala biti precej trivialna, pac isces stringa abcd in dcba.
Diagonale bi bile tezje.

Hm, zadevo bistveno pohitris, da ne isces stringov ampak kar binary data. To bo malo hitreje...

kopernik ::

Odvisno kako ga bereš, kje se nahaja, kakšen disk.
IO operacije so ponavadi vedno najdaljše. Ker računanja
tu sploh ni. Le zaponmiti si moraš pozicije A,B,C,D znakov.
In ja, logično je, da ne smeš delati s stringi...
Drugače pa, če se komu da, naj sprogramira. Bomo vidli,
koliko časa bo trajala obdelava. In kaj bo dlje trajalo, IO ali obdelava.
Grem stavit, da IO...

lp

BigWhale ::

Hmm, problem so tisti minusi v datoteki.... Ako bi jih ne bilo, bi lahko kar rezerviral 1MB pomnilnika in celo datoteko prebral ter zalimal kot 3D array na tisti del spomina. Tako preberes vse v enem prehodu...

Toje precej hitro... Obdelava diagonal bi bila najbolj zamudna...

Thomas ::

Sem vzel, da tekmujemo. Še kdo?

:) :\
Man muss immer generalisieren - Carl Jacobi

kopernik ::

Kakor jaz vidim tale problem, je magično število je 4. End of the story.
Vse ostalo je le način, kako si boš zapomnil pozicije. In tle je sranje.
Ko bom imel čas (enkrat poleti :) ), bom poskusil dokončati. Če me
ne bo že kdo prehitel :) .

lp

kopernik ::

Thomas:
>Sem vzel, da tekmujemo. Še kdo?

hehehe. Kaj naredi ena taka nalogica ?
Z veseljem bi, ampak res nimam časa. Lahko pa kasneje (po poletju),
primerjamo algoritme.

lp

StratOS ::

algoritem gor al pa dol, rad bi videl se kaksno razmišljanje (dobro) v smeri rešitve te naloge.
VB je pre pre prepocasen in nestabilen ...
v c-ju bi to moglo švigat ...

lp
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Thomas ::

Ne uspe mi ga pastat sem. Why is that?

:\
Man muss immer generalisieren - Carl Jacobi

StratOS ::

Men pa progy (v VB) zablokira zaradi preveč dodatnih podatkov zaradi dupliranja in pregleda inverznih parov istih parov štirih točk ( ABCD=DCBA ) !

Hja, kot sem povedal se pari z istimi 4 parami sosednih koordinat in smermi ne smejo ponoviti 2x , to je samo en par kot rešitev.
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Zgodovina sprememb…

  • spremenila: StratOS ()

Thomas ::

Pošlji mi mail, pa ti vrnem program v C.

Moj mail je viden, če me klikneš.

:)
Man muss immer generalisieren - Carl Jacobi

StratOS ::

za ostale : Mail
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

StratOS ::

lahko *.exe oblika z printom številke ?
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Thomas ::

Tele dni enkrat. OK?

:)
Man muss immer generalisieren - Carl Jacobi

StratOS ::

OK, ni blema :)
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

OwcA ::

@Thomas: če se forum pritoži, da mu HTML ni všeč, skoraj gotovo kje uporabljaš znak <, ki mu sledi nepresledkast znak. Ali naredi presledke ali pa uporabi HTML kodo < .

Bi bilo zanimivo videt Critticalov algoritem ... :D
Otroška radovednost - gonilo napredka.

Zgodovina sprememb…

  • spremenilo: OwcA ()

snow ::

Ne stejemo a,b,c,d-je:
Load file time: 0,187s
A:0 B:0 C:0 D:0 SUMA:0
ABCD stringov: 97099
Total time: 0,671s

Stejemo:
Load file time: 0,203s
A:249691 B:250409 C:250016 D:249884 SUMA:1000000
ABCD stringov: 97099
Total time: 0,687s

Source:

#include < iostream.h>
#include < fstream.h>
#include < time.h>

char cube[100][100][100];

int ABCDcheck(int x, int y, int z){
int pp=0, ax, ay, az;
//variacije stringov
for(az=-1;az< 2;az++){
for(ay=-1;ay< 2;ay++){
for(ax=-1;ax< 2;ax++){
//pogleda če sploh obstaja string v tisto smer
if ((3*ax+x> =0) && (3*ay+y> =0) && (3*az+z> =0)){
if ((cube[1*ax+x][1*ay+y][1*az+z]=='B') && (cube[2*ax+x][2*ay+y][2*az+z]=='C') && (cube[3*ax+x][3*ay+y][3*az+z]=='D')){
pp++;
}
}
}
}
}

return pp;
}

int main(){
//load the file
int i,x,y,z,a=0,b=0,c=0,d=0,found=0,test=0;
char string[100];
ifstream reader;
reader.open("cube.txt", ios::in);
for(z=0;z< 100;z++){
for(y=0;y< 100;y++){
reader> > string;
for(x=0;x< 100;x++){
cube[x][y][z]=string[x];
switch(string[x]){
case 'A':
a++;
break;
case 'B':
b++;
break;
case 'C':
c++;
break;
case 'D':
d++;
break;
}

}
}
reader> > string;
}
reader.close();
cout< < "Load file time: "< < clock()/CLOCKS_PER_SEC< < ","< < clock()%CLOCKS_PER_SEC< < "s"< < endl;



//check for 'ABCD'

for(z=0;z< 100;z++){
for(y=0;y< 100;y++){
for(x=0;x< 100;x++){
if(cube[x][y][z]=='A'){
found+=ABCDcheck(x,y,z);
}
}
}
}
cout< < "A:"< < a< < " B:"< < b< < " C:"< < c< < " D:"< < d< < " SUMA:"< < a+b+c+d< < endl;
cout< < "ABCD stringov: "< < found< < endl;
cout< < "Total time: "< < clock()/CLOCKS_PER_SEC< < ","< < clock()%CLOCKS_PER_SEC< < "s"< < endl;

return 0;
}


Za vseh 27 (ja 26, nisem izločil 0,0,0) si narediš vektorsko smer, in potem jo prišteješ 1x, 2x, 3x. Še dodatna optimizacija bi bila, če bi takoj nehal gledat, ko bi prišel v stringu na napačno zaporedje. Ampak 0,600 ali 0,560... nima smisla.

Procesor AMD 1800+.
Če se komu da, naj skompila in pove kakšne čase ma.

Aja pa prosil bi vse, da pokomentirate strukturo programa, sem namreč začetnik.
Pa če ma kdo še kak podobno zabaven primer, naj kar pove... včasih je zabavno kaj gruntat.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

snow ::

Hm.. po moje ma kocka 3 strani. Mojim robnim pogojem manjkajo omejitve za 100 oz 99...

Pa še ena zanimiva stvar.
Če skompilam z minigw, ki sem ga downloadal pred kratkim, je čas dela za 150ms manjši, kot pa če compilam z dev c++ ki ima najbrž malo starejši minigw.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

StratOS ::

Hja, sam ne vem kje bi bil še kak haklc.
Rezultat je namreč nepravilen.

The truth is somewhere out there
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

snow ::

Hmph.. bom preveril.. ko bo čas.
Kako zelo nepravilen je rezultat? Mogoče je on robni pogoj problem, to lahko probam zdele.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

snow ::

Load file time: 0,187s
A:249691 B:250409 C:250016 D:249884 SUMA:1000000
ABCD stringov: 95157
Total time: 0,562s

Malo drugače je ja. Se mi je zdelo da je lahko tole problem, probal pa kje pa da bi.
Sedaj je ok?

Pa povej kaj je to >kajti moj proggy v VB-u dela namrec zelo (BERI :ZELO počasi)
Sekundo? 10? 100?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Zgodovina sprememb…

  • spremenilo: snow ()

StratOS ::

Hja to bo bolje in prav.

Kar se tiče rutin v VB par ur
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Thomas ::

V C je pod sekundo ...
Man muss immer generalisieren - Carl Jacobi

snow ::

Par ur? To bi na roke v tem času. :)

Saj moja kocka je prej imela 3 stranice.

Offtopic:
Podobna bedarija kot sem danes pri matematiki rekel da v zaporedju vedno obstaja natančna zgornja meja. Pa ta matematična neskončnost. :)
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Algoritmi za urejanje tabel

Oddelek: Programiranje
51145 (882) lebdim
»

Time.h v c-ju.

Oddelek: Programiranje
6960 (763) Wrop
»

Najhitrejši programski jezik? (strani: 1 2 )

Oddelek: Programiranje
757379 (5199) Senitel
»

Časovna zahtevnost programa

Oddelek: Programiranje
61501 (1380) CaqKa
»

domači benchmark program

Oddelek: Programiranje
71033 (887) ruph

Več podobnih tem