» »

Digitalna evolucija

strani: « 1 2 3 ... 29

Thomas ::

Da ne bi obremenjeval PROTOKOLa, kjer pa smo s tem začeli, odpiram tole temo:

A kdo mogoče pozna tale sort:

o=0;
p=1;
n=29;
k=1;
while (k>=i) {
    k=-1;
    while (n>k) {
      k++;
      l=TAB[k];
      if (j>l) {
        TAB[i]=l;
        i++;
        TAB[k]=j;
      }
      if (l>j) {
        i=k;
        j=TAB[k];
      }
    }
    j=0;
    n=i-p;
}

Zadeva gre skozi tabelo tolikokrat, kolikor je različnih elementov tabele, kar je v nekaterih (čestih) primerih bolje od Quick sorta.

Algoritem/program se je zevoluiral danes popoldne, ko sem kosil travo.

8-)

Če tega algoritma nobeden nikjer ne najde - potem je nov. Grem iskat!
Man muss immer generalisieren - Carl Jacobi

Brane2 ::

A bi lahko tole malo bolj dokumantiral, recimo dal smiselna imena spremenljivkam, pa definiral i ? :8)

Thomas ::

Vse spremenkjivke ki se pojavijo, so pred programom deklarirane kot:

int var=0;

V TAB[] je pa 30 slučajnih števil. Naprimer od 4 do 7.

Lahko bi jih bilo pa kakšno drugo število.
Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

  • spremenil: Thomas ()

Fury ::

cist hudo :) jest bi tut to evolucijo drku mal :) bomo pocakal do pocitnc.. sicer bi pa reku da je tole vse skup mal prerobustno za mojo glavco :)

OwcA ::

@Thomas: Hudo! :D
Kateri sort je bil osnova?
Otroška radovednost - gonilo napredka.

Thomas ::

Bubble --> tisti ki sem ga pastal v "P temo" skupaj z (nevoninim) tolmačenjem --> tale sort.

:)
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Tkole gre:

prehod : 1 n= 29
j=0 3i,k02030131323123213032301302210
j=3 3i0k2030131323123213032301302210
j=3 03i2k030131323123213032301302210
j=3 023i0k30131323123213032301302210
j=3 0203i3k0131323123213032301302210
j=3 0203i30k131323123213032301302210
j=3 02003i31k31323123213032301302210
j=3 020013i33k1323123213032301302210
j=3 020013i331k323123213032301302210
j=3 0200113i333k23123213032301302210
j=3 0200113i3332k3123213032301302210
j=3 02001123i3333k123213032301302210
j=3 02001123i33331k23213032301302210
j=3 020011213i33332k3213032301302210
j=3 0200112123i33333k213032301302210
j=3 0200112123i333332k13032301302210
j=3 02001121223i333331k3032301302210
j=3 020011212213i333333k032301302210
j=3 020011212213i3333330k32301302210
j=3 0200112122103i3333333k2301302210
j=3 0200112122103i33333332k301302210
j=3 02001121221023i33333333k01302210
j=3 02001121221023i333333330k1302210
j=3 020011212210203i333333331k302210
j=3 0200112122102013i333333333k02210
j=3 0200112122102013i3333333330k2210
j=3 02001121221020103i3333333332k210
j=3 020011212210201023i3333333332k10
j=3 0200112122102010223i3333333331k0
j=3 02001121221020102213i3333333330k
prehod : 2 n= 19
j=0 0k20011212210201022103i333333333
j=0 02k0011212210201022103i333333333
j=2 02i0k011212210201022103333333333
j=2 002i0k11212210201022103333333333
j=2 0002i1k1212210201022103333333333
j=2 00012i1k212210201022103333333333
j=2 000112i2k12210201022103333333333
j=2 000112i21k2210201022103333333333
j=2 0001112i22k210201022103333333333
j=2 0001112i222k10201022103333333333
j=2 0001112i2221k0201022103333333333
j=2 00011112i2220k201022103333333333
j=2 000111102i2222k01022103333333333
j=2 000111102i22220k1022103333333333
j=2 0001111002i22221k022103333333333
j=2 00011110012i22220k22103333333333
j=2 000111100102i22222k2103333333333
j=2 000111100102i222222k103333333333
j=2 000111100102i2222221k03333333333
j=2 0001111001012i2222220k3333333333
prehod : 3 n= 12
j=0 0k0011110010102i2222223333333333
j=0 00k011110010102i2222223333333333
j=0 000k11110010102i2222223333333333
j=0 0001k1110010102i2222223333333333
j=1 0001i1k1100101022222223333333333
j=1 0001i11k100101022222223333333333
j=1 0001i111k00101022222223333333333
j=1 0001i1110k0101022222223333333333
j=1 00001i1110k101022222223333333333
j=1 000001i1111k01022222223333333333
j=1 000001i11110k1022222223333333333
j=1 0000001i11111k022222223333333333
j=1 0000001i111110k22222223333333333
prehod : 4 n= 6
j=0 0k0000001i1111122222223333333333
j=0 00k000001i1111122222223333333333
j=0 000k00001i1111122222223333333333
j=0 0000k0001i1111122222223333333333
j=0 00000k001i1111122222223333333333
j=0 000000k01i1111122222223333333333
j=0 0000000k1i1111122222223333333333

;)
Man muss immer generalisieren - Carl Jacobi

Thomas ::

> in mislš da je ta algo bolši od štetja bitov?

Seveda, da mislim. Da je tole boljši algoritem od štetja bitov.

Pri štetju bitov greš najprej enkrat skoz da prešteješ, potem pa še enkrat, da napišeš toliko 0 in toliko 1.

Če pa imaš recimo za sortat recorde po spolu ... naprimer ... spola ne moreš kar napisati, pač pa moraš premakniti cel record - ane?

Seveda, da je algoritemsko precej bolje takole!

8-)
Man muss immer generalisieren - Carl Jacobi

Valentin ::

Thomas, ali ni zadnji prehod odveč ?

Prehodov bi bilo dovolj (število_različnih_elementov - 1), v tem primeru.

:\

Zgodovina sprememb…

  • spremenil: Valentin ()

Thomas ::

Ne vem če. Tazadnji prehod, ko se nič ne zgodi, zagotovi izhod iz tazunanje zanke.

Bom zvečer dal zadevo še malček kuhat na 2G, pa da vidmo do jutri zjutraj, če se še kaj bistvenega postori.

;)
Man muss immer generalisieren - Carl Jacobi

Valentin ::

Ja, samo v primeru, ko bilo elementov zadnjega prehoda veliko, bi bil tale izhod zelo potraten.

Samo ti verjetno hočeš, da ti program to sam ugotovi.

Me zanima, če bo.

OwcA ::

@Thomas: bi bil tako dober in objavil še dejansko (v C-ju, ne metajeziku) impelemtacijo "mehurčkov" iz katere je tole nastalo. Hvala! :)



P.S. moj 1000. odgovor >:D
Otroška radovednost - gonilo napredka.

Thomas ::

Navaden bubble:

int TAB[31]
int i=0;int j=0;int k=0;int l=0;int m=0;
int n=31;int o=0;int p=1;
//FILL TAB[] random(0,1)
o=0;
p=1;
n=31;
while (p>o) {
    k=0;
    p=0;
    while (n>k) {
      i=k;
      l=TAB[k];
      k++;
      m=TAB[k]
      if (l>m) {
        TAB[i]=m;
        TAB[k]=l;
        p=1;
      }
    }
}


smo naterali, da je iskal optimalni algoritem za sortiranje samih 0 in 1.

Prišel je z enoprehodno rešitvijo.

Potem smo pognali to enoprehodno rešitev za 0 in 1 na nekoliko bolj bogatem nizu.

To tako, da smo okoli tega segmenta dodali zanko, ki naj se izvaja dokler ni naletel na prehod, v katerem ni bilo nobene zamenjave.

Potem smo vrgli zadevo še enkrat v Critticall, da je poštudiral, da mu ni treba delati zank do konca, pač pa gre lahko prej ven.

S tem je dobil še skoraj 50% prihranka na izvedenih vrsticah.


------

Biološka primera:

Morske ribe, ki so šle v reke, so razvile kosti, ko so v hrustancih začele kopičiti minerale. Morska riba hrustančnica ima okoli sebe v morju dovolj raztopljenih mineralov. Rečna pa ne.

V drugi fazi, so se tako trde kosti (mineraliziran hrustanec) izkazale za dovolj trdno oporo na kopnem.

Evolucija v dveh fazah.
-----


Bi šlo tole s sortom v eni fazi? Nedvomno, samo ni bilo še dovolj CPU_časa, da bi probali. Bomo morda preko vikenda.

Pričakujem še več čudnih algoritmov. Po več za vsako nišo.

Pa seveda ne samo sortnih. Šele začeli smo se resno poigravati.

8-)
Man muss immer generalisieren - Carl Jacobi

Vesoljc ::

kaj pa kakšni "vmesni" algo? se ga da vidt al dobiš ven samo končni rezultat?
Abnormal behavior of abnormal brain makes me normal...

Thomas ::

Vsak člen je vmesni. Evolucija pač.

Trenutno najboljši je vedno na disku, v output datoteki. Če pa preide do izboljšave se stari prekrije z novim. Zelo evolucijsko! :D

Tole je ena 100. genracija od bubi.c naprej.

Kadar minute (ali celo ure) ni pojavitve novih generacij, imaš čas trenutno nekam skopirat.

Cela filogenija se mogoče zdi zanimiva, ampak kaj se češ ubadat s stotimi ali tisočimi zaguljenimi algoritmi. Kvečjemu z najboljšim doslej.

Paradigm shift! Neha nas brigati, kako zadeva dela. Tako ali tako, postaja prezapletena.

Ampak kdor želi, lahko program kadarkoli zaustavi, preuči (shrani) algoritem - in požene od tam naprej.

Ni pa nobene garancije, da bo naslednji sledil ravno iz trenutnega. Evolucija je nekako 2D - kot vsi rodovniki. Vedno se lahko povzpne nek neprestolonaslednik iz daljne stričeve loze in prevzame prvenstvo.

:)
Man muss immer generalisieren - Carl Jacobi

snow ::

Thomas lahko malo opisno(nisem programer, približno razumem stvari) predstaviš princip delovanja Critticalla.

Kdaj bo Critticall dobil v roke samega sebe?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Thomas ::

Bom se razpisal o tem - zvečer predvidoma.

Kmalu se bo dobil v roke. V nekaj letih celo ... zelo resno.

:)
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Evolucijski algoritem (EA) je dovolj močan, da z njim lahko naredimo praktično karkoli.

Kaj je v tem Vesolju večji čudež kot mi, s svojo inteligenco, zavestjo, civilizacijo ... ?

In "vsakemu" je jasno, da je vse to nastalo zgolj z evolucijo.

Tisti, ki nimajo antievolucijskih predsodkov, so poskusili (tudi uspešno) implementirati evolucijo kot tehnologijo. O tem smo že veliko govorili na tem forumu. Od bolj odpornih paradižnikov, do turbin in do reaktivnih motorjev za potniška letala.

Enkrat smo se tukaj šli tudi eno igrico z imenom "Thomasov problem". Šlo je za to, kako postaviti šahovske figure tako, da se bodo kar največkrat pokrivale drug drugo.

Najboljši človeški rezultat za en komplet figur je bil 51 (Mici).

Toda evolucijski reševalec je našel 53 krat pokrivajoče se konfiguracije. Brez posebnih težav.

Ultimatni izziv (pa se je meni vedno zdel) kako tej tehnologiji podvreči programske algoritme.

To je zdaj realizirana zadeva. Program, ki k zadanemu algoritmu (postopkovnim navodilom) z metodo evolucijskega spreminjanja in pritiska - priredi učinkovitejši algoritem, ki naredi isto kot originalni - samo v manj korakih.

Vsak kos programske kode je pravzaprav algoritem, ki ene vrednosti spremenljivk spremeni v druge.

Dva operatorja na takem segmentu, ga lahko optimizirata. Eden je naša inteligenca s svojim znanjem - drugi je evolucijski algoritem.

Nekako sta si ekvivalentna. Ali je svet nastal po inteligentnem božjem načrtu - ali pa ga je izoblikovala evolucija. Rezultat je očitno isti.

Pa kaj je ta EA - v svojem bistvu?

Neskončna zanka, ki neperfektno kopira (algoritme) in preizkuša na nastalih njihovo učinkovitost. Rahlo boljše od originalov, ustoličuje kot nove kralje in plemstvo. Čedalje bolj žlahtni so.

Problem je samo v podrobnostih, tehniki, kako to narediti. Začeli smo z inteligenco, naprej se zadeva lahko sama sebe izboljšuje po evolucijskem algoritmu. Vendar čisto tam še nismo.

Bistveno je, da je evolucija nerazločljiva od inteligence. Bo kmalu tudi od tehnologije?

Bomo videli!

8-)
Man muss immer generalisieren - Carl Jacobi

Vesoljc ::

kot štekam se ta EA izvaja na v biti source file-u bubi.c? se pravi, modificirano kodo recompilaš in preveriš če ustreza pogojem? če ja, daš overwrite, če ne, gremo še enkrat...
tko nekak?
Abnormal behavior of abnormal brain makes me normal...

blabla ::

Cool! :)

A imaš v mislih še kakšne (zahtevnejše) algoritme, ki jih boš podvrgel evolucijo. Ali pa so današnji računalniki še prepočasni za kaj zahtevnejšega.
Lahko bi naredil distribucijski program. Vsakemu računalniku pošlješ nek vmesni algoritem in naročiš par tisoč evolucij.

Drugače pa me moti predvsem to, da je potrebno vmesni program stestirati na čimveč različnih vhodnih parametrih, najraje pa na vseh. To pa je v mnogih primerih nemogoče. Tako program v nekaterih primerih dela, v drugih pa ne.
Pri sortu recimo... Ali vsako vmesno različico testiraš na večih vhodnih datotekah ali samo na eni in se do "konca" evolucije tiste različice, ki ne delajo pri določenih vhodih, same eliminirajo.

Keep up the good work!

p.s.: Ali bo tole kdaj na voljo za dolpoteg ali moram počakati na piratsko verzijo. :D

Thomas ::

Ne. Brute force algoritem je pa procesorsko prezahteven, da bi prišli do pametnega rezultata v realnem času. Mogoče bo drugače, ko bomo imeli kvantne računalnike, zdaj pa zagotovo ne.

Je pa to neločevanje med EA in BF večkrat vidno.

Naprimer Darwinovi nasprotniki dostikrat rečejo, kako da je majhna verjetnost, da "izmed vseh možnosti pride ravno do slona ali človeka."

Preprosto nerazumevanje.

Če bi graf, na dveh točkah obešene verige, 50% daljše od razdalje med njima, iskali na navadnem PC računalniku v resoluciji 1024*1024, z brute force ... bi porabili ogromno starosti Vesolja časa za to nalogo.

Po EA - je naloga narejena v minuti.

EA != BF

:)

p.s.

Je kdo kje našel tale rezultatni algoritem? Ga je kdo primerjal s Quick sort?
Man muss immer generalisieren - Carl Jacobi

Thomas ::

> Cool!

Hvala.

> A imaš v mislih še kakšne (zahtevnejše) algoritme, ki jih boš podvrgel evolucijo.

Sieve od Eratostena sem že.

Samo večino drugih (segmentov kode) bodo drugi. Vse, zaradi mene.

> Ali pa so današnji računalniki še prepočasni za kaj zahtevnejšega.

Ne, mislim da niso.

> Lahko bi naredil distribucijski program. Vsakemu računalniku pošlješ nek vmesni algoritem in naročiš par tisoč evolucij.

Hja ... skoraj že lahko.


> Drugače pa me moti predvsem to, da je potrebno vmesni program stestirati na čimveč različnih vhodnih parametrih, najraje pa na vseh.

Ne, ne. Program sam naredi inpute. Naredi jih za nekajkrat toliko, kot je Kolmogorova kompleksnost algoritma. Povsem zadostuje. LAHKO pa sam definiraš inpute za algoritem. Poleg tistih, ki jih naredi sam program.


> Pri sortu recimo... Ali vsako vmesno različico testiraš na večih vhodnih datotekah ali samo na eni in se do "konca" evolucije tiste različice, ki ne delajo pri določenih vhodih, same eliminirajo.

Sproti. Vse sproti, sicer na precej zvit način, tako da ni preveč dela - ampak vse sproti. Če ne deluje na eni dati, je primerek algoritma uničen.

> Keep up the good work!

Thanx.


> p.s.: Ali bo tole kdaj na voljo za dolpoteg ali moram počakati na piratsko verzijo.

Se še testira, ker nočem preveč debatirati o razsulih sistema in podobnih rečeh. Je treba prej dobro stestirati, preden ga spustim v divjino.

:)
Man muss immer generalisieren - Carl Jacobi

Vesoljc ::

sounds as if it(he,she?) was alive...
Abnormal behavior of abnormal brain makes me normal...

Thomas ::

If ver was alive. :D
Man muss immer generalisieren - Carl Jacobi

Vesoljc ::

nisi še potrdil mojga razmišljanja... :\
se dogaja recompile ali ne? kwa pa če bi to počel "dinamično" na strojni kodi?
Abnormal behavior of abnormal brain makes me normal...

Thomas ::

O algoritmih se ne razmišlja v strojni kodi. Smatra se, da v strojno kodo bomo že prevedli. Pa bodi x86 ali kakšna druga strojna koda. Z malo manj ali malo več cacheja.

Jest sem zadevo sicer začel z nekim assemblerjem - ampak sem videl, da ga je potem treba prevajati v C.

Algoritemski koraki so edino merilo. Če narediš v čimmanj korakih, bo implementacija v assembler v splošnem lažja.

Tole konkretno, se da kompilirati kar v C++ compilerju. Direktno.

:)
Man muss immer generalisieren - Carl Jacobi

Vesoljc ::

the light just hit me...
Abnormal behavior of abnormal brain makes me normal...

Thomas ::

A je to dobr, a je to slabo? :D
Man muss immer generalisieren - Carl Jacobi

Vesoljc ::

odlično...
Abnormal behavior of abnormal brain makes me normal...

SmartOne ::

A ta EA je v bistvu genetsko programiranje?
Pa še nekaj. Naprimer imaš datoteko v kateri so podatki o npr. gibanju delnic. Vsak dan je podan v svoji vrstici. Zanima me kako "Generator Programov" črpa podatke iz te datoteke, ko testira generirani program. A ima dostop do vseh podatkov, ali samo ene vrstice? A so podatki predstavljeni kot funkcija ene spremenljivke ali več spremenljivk?
Npr. v eni vrstici imamo podatke: 23, 56, 78, 41
A si to lahko predstavljamo kot f(1) = 23, f(2) = 56, f(3) = 78, f(4) = 41 ?
Ali to predstavimo kako drugace?

Lepo prosim za obširno in razumljivo obrazložitev...

Thomas ::

Do gornjega sorta smo prišli (pridemo) po kakih 1014 floating point operations. Približno ena cela noč na spodobnem PCu.

Kar sploh ni veliko, če se je toliko programerjev, informatikov, matematikov in podobnih ukvarjalo s sortnimi algoritmi - cela desetletja.

Kaj bi to zdaj pomenilo pa pri prevajanju neke tabele dogodkov (BTW - dovolj dobro si zadel, kako bi morali narediti input funcijo!) - je pa vprašanje. Real time gotovo ne bi mogli biti. Tudi le nekaj več, kot a priori random predictor, bi to bil.


> A ima dostop do vseh podatkov, ali samo ene vrstice?

Do vseh. Lahko pa (seveda) samo do vseh preteklih. Nti se računa iz vseh od prvega do N-1. Odvisno od tega, če funkcija prireja vektorju skalar, ali pa vektorju vektor.

Upam, da ti kaj pomaga. Če ne, še vprašaj!


:)
Man muss immer generalisieren - Carl Jacobi

SmartOne ::

Obrazloži še malo: odvisno od tega, če funkcija prireja vektorju skalar, ali pa vektorju vektor.
Mene mučijo predvsem problemi, kjer je potrebno napovedati več stvari in ne samo ene. Output programa je namreč ENA sama vrednost. A to pomeni, da program vsebuje več podprogramov (ki jih je toliko kolikor je stvari ki jih moramo napovedati)?
Sicer sem na tem področju začetnik, zato prosim za obrazložitev, ker me področje zelo zanima in se mi zdi posebno obetavno (predvsem za razvoj umetne inteligence).

Thomas ::

> Obrazloži še malo: odvisno od tega, če funkcija prireja vektorju skalar, ali pa vektorju vektor.

Critticall ima metastatemente, ki niso C, pač pa jih ver razume, C jih pa ignorira, ker so zakomentirani.

Eden teh metaukazov je $retvar. Ta pove, katero spremenljivko je treba vrniti. Če je to array (vektor) je to vektor, niz večih števil. Čeje to število je pa to pač eno število. Poleg tega obstajata metaukaza $invar in $rinvar. Spet je lahko vhod za programski segment več nizov in/ali več vektorjev.

Če bi hotel na podlagi niza prejšnjih izidov napovedati današnje stanje, bi vektorju prirejal skalar.

Ali pa bi hotel algoritem, ki k danemu nizu sprememb napove nov niz sprememb. Kar je pa praktično utopija. Da bi daljši čas kak algoritem deloval.

Vsak dan, uro, minuto drugi - to pa že. Pa še ta bi bil verjetno le kakšno malenkost boljši od čistega ugibanja. Včasih morda dovolj.

Kolikor vem, je to trenutno popularna zadeva. Iskati zakonitosti iz navideznega kaosa.

Meni pa je bolj všeč EA na področju povsem determinističnih (programskih) algoritmov.

Ravnokar sem gledal eno Eratostenovo rešeto s strange twistom ... ga bom jutri dal sem.

:)
Man muss immer generalisieren - Carl Jacobi

Simko ::

Ker smo že pri Evroviziji v eni drugi temi, pa ker Thomas trdi, da je vsako razmišljanje imitacije evolucije v spet tretji temi (mogoče ste tam celo to, kar bom povedal, omenili), me zanima - kaj če bi napisali EA za generiranje melodije oz. pesmi, ki bo nato zagotovo postala svetovna uspešnica?

Do

*generiraj melodijo
*modificiraj melodijo
*povezuj melodije
*vrednoti melodije (shrani najboljše)
*vrednoti povezave (shrani najboljše)
If kvaliteta>minimum - objavi!

Loop

Zgornji algoritem je delno skopiran iz ABC teme ;)

A bi to šlo? Problem je le kako vrednotiti melodije....kako povedati računalniku, katera pesem je "lepa" in katera ne...
A bi se rač. znal naučiti na vseh mega uspešnicah do zdaj, kaj je dobra pesem?


Glede tistega iskalnega algoritma pa....ja fajn. Jaz še ga nisem nikjer zasledil. Lahko pa kakšega profesorja povprašam. :)

snow ::

> Ravnokar sem gledal eno Eratostenovo rešeto s strange twistom ... ga bom jutri dal sem.

Sliši se zanimivo. Sem si šel pogledat princip tega rešeta, da bom potem približno vedel, kaj je digitalni stvor pogruntal.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Thomas ::

Simko,

Vse kar si povedal drži kot pribito.

Na žalost drži tudi to, da mora človek povedati, kaj mu je všeč, kaj mu pa ni. Moral bi torej dobiti feed back od človeka. Milijone feedbackov, kot kriterijsko funkcijo, da program ve katere mutacije zavreči in katere sprejeti.

To bi lahko tudi rahlo avtomatiziral, da ti računalnik sam meri tvoj odziv na EEG.

Seveda človek ne bi mogel biti en sam, pač pa njih ogromno. Vsak svoj player na ušesih in EEG čelado in sprejemnik/oddajnik ...

Rezultat bi bil zagotovo breath taking.

O Eratostenes sieve twistu pa mejčkn kasneje.

:)

:)
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Dobr ... tale twist, ki ga izumi.

Enostavno Eratostenovo rešeto deluje tako, da prekrižamo vse dvo in več kratnike od 2, 3, 4, 5, 6, 7, 8 ... -

Če mu to damo, kamlu ugotovi, da je dovolj, če prečrta dvo in več kratnike od 2, 3, 5, 7, 9, 11 ...

Se pravi od 2 in lihih števil.

Ta spremenljivka mu je slučajno i.

Povečuje jo takole:

i++;i|=1;

iz 2 na 3, s 3 pa najprej na 4 (i++) in takoj zatem na 5. Itd.

Kasneje se spomni še nekaj trikov. Recimo da preveri če je TAB[i]==0. Če ne, kar izpusti. Torej samo po dvo in več kratnike praštevil prekrižuje.

Samo nifty se mi zdi tole povečevanje:

i++;i|=1;

Tega še nisem videl v nobeni izvedenki sita.

:)
Man muss immer generalisieren - Carl Jacobi

Fury ::

a i|=1 ... to pomen da i OR-a z 1 vsakic?

Thomas ::

Ja. Vsakič se "zORa" z 1. Po i++;!

Iz začetne vrednosti 2 tako dobi 3.

Potem pa iz 3 dobi 5. Iz 5 pa 7, iz 7 9 ...

Na ta način se izogne

if (i==2) i++; else i+=2;.

:)
Man muss immer generalisieren - Carl Jacobi

snow ::

Impresivno.

Thomas kdaj bo critticall@home? :)
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Thomas ::

Vhod:

//$DIMENSION tab[962]
//$RETVAR tab[]
//$SOUND ON
j=961;
l=1;
//$BES
m=4;
while (j >= m) {
    tab[m]=l;
    m+=2;
}
i=3;
while (j > i) {
    m=i+i;
    while (j >= m ) {
      tab[m]=l;
      m=m+i;
    }
    i++;
}
//$EES



Izhod:



// The algorithm has been enhanced for 81.2984%

//$DIMENSION tab[962]
//$RETVAR tab[]
//$SOUND ON

// int tab[1]; int arr256[256];int j=0;int l=0;int m=0;int i=0;int cri1=0;int cri2=0;int cri3=0;

j=961;
l=1;
//$BES
i=3;
m=4;
tab[m]=l;
m+=2;
while (m!=j) {
    tab[m]=l;
    m+=2;
}
tab[j]=j;
while (j > l) {
    m=i*i;
    tab[m]=l;
    m=m+i;
    m=m+i;
    while (j>=m ) {
      tab[m]=l;
      m=m+i;
      m=m+i;
    }
    j=tab[j];
    i++;
    i++;
}
//$EES



Kot vidite, je drugi program (spet eden od vmesnih členov, ki je že doživel 2 spremembi odkar tole pišem - ampak nekje je treba potegnit črto) precej večji od prvega, ki je dokaj neoptimalen.

:)
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Tole bo shareware, ne distributed computing.

Power to the people!

:D
Man muss immer generalisieren - Carl Jacobi

svit ::

Thomas: impresivno... zares dobra zadeva. Me pa zanima še nekaj. Kolikor se jaz dobro spomnim časovne zahtevnosti algoritmov, je tako originalni kot modificirani algoritem časovne zahtevnosti n^2. Tako da v splošnem gledanju, je ista pašta...

Sicer pa vsaka ti čast, ker si to napisal in da ti stvar deluje. A si mogoče dobil kakšen izboljšan (v smislu časovnosti) algoritem ven iz Critticala? Recimo da bi mu dal input program z n^3, ven pa bi dobil program recimo n^2 * logn...?

Zgodovina sprememb…

  • spremenilo: svit ()

Thomas ::

Ja pri sortu je odvisnost O(n^2) zmanjšal na O(kn). Pri čemer je k število unikatnih polj.

Tale O(f(n)) ... bi blo dobro zmerej zračunat ... :|
Man muss immer generalisieren - Carl Jacobi

svit ::

Kako pa določa program modifikacije? A ima v kakšni datoteki vse vrstice programa in jih potem zamenjuje med seboj, ali pa ima nek centralni seznam splošnih stavkov (recimo prireditveni stavek, do stavek...) katere potem na slepo meče notri? Ali lahko Crittical spreminja pogoje v zankah? Kot sem videl v zadnjem primeru, ki si ga objavil, zgleda da lahko. Tako je spremenil iz >= v !=. Ali lahko program dodaja nove zanke v zanke? Lepo bi te prosil da malo bolj objasniš vso to zadevo. Zanima me tudi, kako se program rešuje pred "segmentation error" in podobno...

Thomas ::

Vsak C program se prevede (na začetku) v bitni string, dolg milijon bitov če je treba, lahko pa še več!

Ta bitni string je potem podvržen bitnim mutacijam, random bombardiranju z biti.

Če gre tako mutirani bitni string skozi naslednje teste:

- predstavlja sintaktično pravilen C segment

- njegov output, je (za isti input) enak outputu nemutirane verzije

- izvede se v manj korakih, kot original

... potem zavzeme svoje mesto v Panteonu! ;)

V okviru (striktne) sintakse, se lahko programskemu segmentu lahko zgodi vse. Nove zanke in ukinitve starih. Nove spremenljivke in novi pogoji ...

:)
Man muss immer generalisieren - Carl Jacobi

Vesoljc ::

tko bi lahko že takoj na začetku razložu...
Abnormal behavior of abnormal brain makes me normal...

Fury ::

thomas to je pa totalno prevec hudo :) jest sem nekako tak: 8-O 8-O 8-O ti pa najbrz tak: 8-) :D >:D

seprav u bistvu se to cist nakljuco use dela in pol pac 1 od miljonov verzij dejansko enako deluje, 1 od miljon delujocih je pa hitrejsa od originala al kaksna je tuki statistika?

pa se to procesorsko vse obnese? al mas kaksne dirty hacke not? ;)

Marjan ::

Jest sem bil tud fasciniran nad Critticall-om, ko mi je Thomas povedal kaj zmore.

Programerji bi "ubijal" za tak optimizator!

Res 8-O

Thomas ::

Takole se Eratostenovo rešeto še naprej kuha.



$DIMENSION tab[962]
$RETVAR tab[]
$SOUND ON
$INVAR j(121)
$INVAR j(961)
$INVAR j(400)
$INVAR j(300)

// int tab[1]; int arr256[256];int l=0;int m=0;int j=0;int i=0;int cri2=0;int cri1=0;

l=1;
m=4;
while (j >= m) {
    tab[m]=l;
    m+=2;
}
m=9;
while (j >= m) {
    tab[m]=l;
    m+=3;
}
$BES
i=4;
i++; //ni (še) optimizirano na i=5;
m=i*i; // ugotovil je, da je dovolj, če gre od kvadrata naprej
while (j >= m) {
    cri1=i+i; // uvedel je prvo novo spremenljivko
    tab[m]=l;
    m=m+cri1; // da bo šel samo po mjih lihih naprej
    while (j > m) {
      tab[m]=l;
      m=m+cri1;
    }
    i++;
    i++;
    m=i*i;
}
$EES

Stay tuned! Samo še help napišemo ... pa gre zadeva v lajf.

:)
Man muss immer generalisieren - Carl Jacobi
strani: « 1 2 3 ... 29


Vredno ogleda ...

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

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

Oddelek: Programiranje
754114 (1934) Senitel
»

Petaflopsu naproti (strani: 1 2 3 )

Oddelek: Novice / Procesorji
1053818 (3818) Marjan
»

cene permutacij help please

Oddelek: Programiranje
261032 (639) Sergio
»

Object packing - kakšne ideje?

Oddelek: Programiranje
16758 (537) Thomas
»

Išče se hiter algoritem za izračun ene čudne matrične operacije.

Oddelek: Znanost in tehnologija
171277 (768) Thomas

Več podobnih tem