Forum » Znanost in tehnologija » Digitalna evolucija
Digitalna evolucija
Thomas ::
To traja malo več.
Ampak a Critticall al njegovi produkti?
Critticall nikoli, njegovi produkti (kot Several Unique Sort) pa ja.
Ampak a Critticall al njegovi produkti?
Critticall nikoli, njegovi produkti (kot Several Unique Sort) pa ja.
Man muss immer generalisieren - Carl Jacobi
Zgodovina sprememb…
- spremenil: Thomas ()
Thomas ::
Hja ... nimam linka. Mam nekej pošte, ampak kaj bi s tem.
Ko link bo, ga bom seveda dal.
Nekako se ne morem iznebiti vtisa, da nisi ravno prepričan, da ta zadeva sploh dela? Kot da hočeš izpeljavo matemetičnega dokaza za to.
No ja, mislim da bo kdo ta dokaz pa že naredil, saj ni pretežak.
Ko link bo, ga bom seveda dal.
Nekako se ne morem iznebiti vtisa, da nisi ravno prepričan, da ta zadeva sploh dela? Kot da hočeš izpeljavo matemetičnega dokaza za to.
No ja, mislim da bo kdo ta dokaz pa že naredil, saj ni pretežak.
Man muss immer generalisieren - Carl Jacobi
Gandalfar ::
pri velikem stevilu ponovitev iste stevke
ma q-sort o(n^2) njegov pa O(kn) torej ce on izbere k ki je manjsi od logn potem ja, bo hiter.
sicer bo pa n^2 bubble.
zanic stvar, ki je specializirana.
-------
Tole se je prej pojavilo na netu. Komentar?
ma q-sort o(n^2) njegov pa O(kn) torej ce on izbere k ki je manjsi od logn potem ja, bo hiter.
sicer bo pa n^2 bubble.
zanic stvar, ki je specializirana.
-------
Tole se je prej pojavilo na netu. Komentar?
Thomas ::
Several Unique Sort je to, kar pove ime. Algoritem specializiran za malo različnih elementov med mnogim.
Naprimer za posortanje mesecev rojstva milijona ljudi, za posortanje dni v tednu milijarde zapisov, za posortanje prebivalcev EU po spolu ....
Tukaj je bistveno hitrejši tudi od QuickSorta.
V primerih, ki mu pa niso pisani na kožo, pa poklekne. Tako kot poklekne tudi QuickSort za nekatere primere vhodnih podatkov. V svojem slabem ekstremu tako Quick kot Several postaneta ENAKA Bubblu.
Avtor navedenega citata je to "pozabil" omeniti. Zakaj, lahko samo špekuliram:
- ker se ne spozna prav dobro na zadeve
- foušija
- način za downplay Critticalla, ker ne mara delujoče AI
Jest sem na ta dosežek ponosen in sploh ne poznam Slovenca, ki bi pogruntal kakšen nov sort. Critticall seveda ni Slovenec, ampak vendarle je Slovenskih staršev. Torej kateri Slovenski programer ali matematik je izumil kakšen algoritem, primerljiv z izumom SU sorta? Ne bi omenjal tega, ampak ko se ravno piše v Slovenščini neprijazno o Critticallu - vračamo udarec.
p.s.
Kaj pomeni neprijazno? To niso upravičene kritike, četudi ostre. Recimo na račun odzivnosti, oblikovanja, nujnosti zunanjega editorja ... to je vse prijazno. To gre vse na račun Critticalla.
Da pa nekdo udriha po algoritmu ki ga ne razume, da bi zadal nekakšen rikoše udarec, je pa pobalinstvo.
Naprimer za posortanje mesecev rojstva milijona ljudi, za posortanje dni v tednu milijarde zapisov, za posortanje prebivalcev EU po spolu ....
Tukaj je bistveno hitrejši tudi od QuickSorta.
V primerih, ki mu pa niso pisani na kožo, pa poklekne. Tako kot poklekne tudi QuickSort za nekatere primere vhodnih podatkov. V svojem slabem ekstremu tako Quick kot Several postaneta ENAKA Bubblu.
Avtor navedenega citata je to "pozabil" omeniti. Zakaj, lahko samo špekuliram:
- ker se ne spozna prav dobro na zadeve
- foušija
- način za downplay Critticalla, ker ne mara delujoče AI
Jest sem na ta dosežek ponosen in sploh ne poznam Slovenca, ki bi pogruntal kakšen nov sort. Critticall seveda ni Slovenec, ampak vendarle je Slovenskih staršev. Torej kateri Slovenski programer ali matematik je izumil kakšen algoritem, primerljiv z izumom SU sorta? Ne bi omenjal tega, ampak ko se ravno piše v Slovenščini neprijazno o Critticallu - vračamo udarec.
p.s.
Kaj pomeni neprijazno? To niso upravičene kritike, četudi ostre. Recimo na račun odzivnosti, oblikovanja, nujnosti zunanjega editorja ... to je vse prijazno. To gre vse na račun Critticalla.
Da pa nekdo udriha po algoritmu ki ga ne razume, da bi zadal nekakšen rikoše udarec, je pa pobalinstvo.
Man muss immer generalisieren - Carl Jacobi
Sergio ::
Naredis kopico. Levo poravnano uravnotezeno binarno drevo. Elementi tega drevesa so distinktni kljuci, ki vsebujejo array pointerjev na elemente s tem kljucem (predstavljaj si heap, ki ima za elemente stack).
Distinkntne kljuce drzis se v rdece-crnem drevesu, ki nekako zagotavlja minimalno izrojenost. V drevesu torej pogledas, ce je element z danim kljucem ze notri. Ce ga ni, ga dodas v drevo in v kopico. Ce je, v RC drevesu dobis pointer do stacka, in dodas element v stack.
Ko vse elemente dodas, deleteMin()as kopico in izpises elemente.
Analiza:
Recimo da imas 500.000 elementov, 10 distinktnih.
Elemente imas v RC drevesu, teh 10 distinktnih, precej hitro (entropija, jebiga). Iskanje po RC drevesu zahteva log(2)10 korakov (torej 3, amortizirano). Vstavljanje ima konstanten cas. Izpis ima O(n).
Evo, Several Unique Sort, ki sem si ga izmislil v 5 minutah prostega casa. Prostorska zahtevnost je zelo majhna (RC drevo hrani samo distinktne elemente, kar je zelo malo).
Plus, stvar dela pasje hitro. Ali se motim?
Sem za debato :)
Distinkntne kljuce drzis se v rdece-crnem drevesu, ki nekako zagotavlja minimalno izrojenost. V drevesu torej pogledas, ce je element z danim kljucem ze notri. Ce ga ni, ga dodas v drevo in v kopico. Ce je, v RC drevesu dobis pointer do stacka, in dodas element v stack.
Ko vse elemente dodas, deleteMin()as kopico in izpises elemente.
Analiza:
Recimo da imas 500.000 elementov, 10 distinktnih.
Elemente imas v RC drevesu, teh 10 distinktnih, precej hitro (entropija, jebiga). Iskanje po RC drevesu zahteva log(2)10 korakov (torej 3, amortizirano). Vstavljanje ima konstanten cas. Izpis ima O(n).
Evo, Several Unique Sort, ki sem si ga izmislil v 5 minutah prostega casa. Prostorska zahtevnost je zelo majhna (RC drevo hrani samo distinktne elemente, kar je zelo malo).
Plus, stvar dela pasje hitro. Ali se motim?
Sem za debato :)
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Thomas ::
Kaj je tvoja teza? Da si si tudi ti v petih minutah izmislil nekaj novega?
Tole ni novo.
Sem za debato.
Tole ni novo.
Sem za debato.
Man muss immer generalisieren - Carl Jacobi
Sergio ::
Moja teza je, da Several Unique Sort _ni_ nekaj novega. Too much fuss.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Thomas ::
Ni nekaj novega?
A - si ga že kje zasledil?
B - je preveč podoben nekemu drugemu, kateremu?
C - ne deluje
D - drugo
p.s.
D je možen samo z _jasno_ razlago. Ne kr neki ali pa "sicer se ne spoznam, ampak yada yada ..."
A - si ga že kje zasledil?
B - je preveč podoben nekemu drugemu, kateremu?
C - ne deluje
D - drugo
p.s.
D je možen samo z _jasno_ razlago. Ne kr neki ali pa "sicer se ne spoznam, ampak yada yada ..."
Man muss immer generalisieren - Carl Jacobi
Thomas ::
Sicer pa to ni stvar debate. To je stvar meritve.
Vzemi niz deset milijonov dolg, v katerem so random izmešana števila med 87 in 95. Posortaj ga s SU in pa s katerimkoli drugim sortom po svoji izbiri.
Razlika v času med SU in QS bo nekajkratna, v korist prvega. Dovolj, da se bodo posebnosti kompilerja kompajlerja ki ga uporabljaš in procesorja popolnoma zakrile.
Pot, da poiščeš še kaj boljšega kot je SU za take primere, je seveda odprta. Toda nisi še tam, nihče še ni. Nihče še ni niti blizu - vsaj brez velike dodatne potošnje memorije ne.
Bo kdo vprašal, kakšno praktično korist pa to prinaša. Seveda jo prinaša. V praksi primer, za katerega vnaprej vemo, da je pisan na kožo SU, ni tako redek. Sploh ne.
Vzemi niz deset milijonov dolg, v katerem so random izmešana števila med 87 in 95. Posortaj ga s SU in pa s katerimkoli drugim sortom po svoji izbiri.
Razlika v času med SU in QS bo nekajkratna, v korist prvega. Dovolj, da se bodo posebnosti kompilerja kompajlerja ki ga uporabljaš in procesorja popolnoma zakrile.
Pot, da poiščeš še kaj boljšega kot je SU za take primere, je seveda odprta. Toda nisi še tam, nihče še ni. Nihče še ni niti blizu - vsaj brez velike dodatne potošnje memorije ne.
Bo kdo vprašal, kakšno praktično korist pa to prinaša. Seveda jo prinaša. V praksi primer, za katerega vnaprej vemo, da je pisan na kožo SU, ni tako redek. Sploh ne.
Man muss immer generalisieren - Carl Jacobi
kopernik ::
Meni se zdi ta sort precej uporabna zadeva. Ni izključeno, da ga bom kje tudi uporabil :-) Sploh ne ...
Zgodovina sprememb…
- spremenil: kopernik ()
nevone ::
Critticall je izjemno inovativen, kadar gre za specializirane probleme. Sicer pa problemi so specializirani. To da z enim zamahom opraviš vse, preprosto ne gre, oz. nekaj stane. To ve vsak, ki je kdaj resno delal na kakšnem projektu. Zato je Critticall dober tudi za izboljševanje osnovnih gradnikov večjih sistemov.
o+ nevone
o+ nevone
noraguta ::
jaz iama pa eno vprašanje , če se several realizira z generičnim komparatorjem , kjer nimamo eksplicitno dolčenega low bounda, ali velja za worst case korekcija kn+n ?
Pust' ot pobyedy k pobyedye vyedyot!
Zgodovina sprememb…
- spremenilo: noraguta ()
Thomas ::
Nisem prepričan, da sem povsem dobro razumel vprašanje. Ampak se bom potrudu pojasnt.
Vsi sorti so computing equivalent. Pomeni, da delajo isto zadevo - uredijo vrstni niz elementov niza. V tem smislu je pač samo eden.
Lahko jih pa razlikujemo recimo po tem, v kakšnem redu menjavajo člene niza in pod kakšnimi pogoji. V tem smislu jih je pa milijarde in milijarde. Večina je prekompleksnih in prenerodnih, da bi sploh prišli v poštev.
Ljudje so jih izmed teoretično možnih našli kakšnih 10 ali 15 takih, ki so vredni omembe. Bodisi zaradi preprostosti, bodisi ker so tako dobri (=hitri).
V to prgišče zdaj lahko sodi SUS. Najboljši je v neki pomembni niši, kar za večino ne moremo reči.
Kako je prišlo do njega? Critticall simulira sorte (ali druge algoritme) in hkrati izvaja (nastavljiv) evolucijski pritisk. V nišnih primerih potem to da za to okolje optimum.
Če bi pogruntali hyper quantum computer (ako je sploh mogoče), bi lahko preverili kar vse sorte zaporedoma.
Critticall pa skače med njimi kot koza. In kakorkoli zanimive lahko ujame. Ne samo sorte, digitalne algoritme.
Vsi sorti so computing equivalent. Pomeni, da delajo isto zadevo - uredijo vrstni niz elementov niza. V tem smislu je pač samo eden.
Lahko jih pa razlikujemo recimo po tem, v kakšnem redu menjavajo člene niza in pod kakšnimi pogoji. V tem smislu jih je pa milijarde in milijarde. Večina je prekompleksnih in prenerodnih, da bi sploh prišli v poštev.
Ljudje so jih izmed teoretično možnih našli kakšnih 10 ali 15 takih, ki so vredni omembe. Bodisi zaradi preprostosti, bodisi ker so tako dobri (=hitri).
V to prgišče zdaj lahko sodi SUS. Najboljši je v neki pomembni niši, kar za večino ne moremo reči.
Kako je prišlo do njega? Critticall simulira sorte (ali druge algoritme) in hkrati izvaja (nastavljiv) evolucijski pritisk. V nišnih primerih potem to da za to okolje optimum.
Če bi pogruntali hyper quantum computer (ako je sploh mogoče), bi lahko preverili kar vse sorte zaporedoma.
Critticall pa skače med njimi kot koza. In kakorkoli zanimive lahko ujame. Ne samo sorte, digitalne algoritme.
Man muss immer generalisieren - Carl Jacobi
noraguta ::
ma dobro saj sem sedaj dokaj siguren o svoji proksimaciji .
sus lahko uvrščamo nekje malo nad pinholeta. ni ravno treba da smo gotovi o preiskovancih moramo biti pa gotovi o preiskovanem prostoru preiskovancev. tu se potem pojavi dilema ali izrabiti susovo determinirano hitrost pri iskanju majhne variabilnosti podatkov ali iti v iskanje mediane pri quick sortu z podobno zahtevnim algoritmom o(n). se pravi ce nam prostor sortiranja ni zan je skoraj gotovo favorit qs(ako je distribucija nakjucna). ako je prostor determiniran ,variabilnost sortirancev majhna a vendar so vrednosti same po sebi nedeterminirne tedaj ima sus celo nekaj moznosti. v ostalem za determiniran set sortirancev je pinhole mojster nad mojstri.
ali se pac motim ?
kritični se mi je zdel do sedaj najbolj fascinanten pri komprešnu, iz stališča golega komuting funkcionalizma pa no ja mogoce kdaj ... pa brez zamere.
sus lahko uvrščamo nekje malo nad pinholeta. ni ravno treba da smo gotovi o preiskovancih moramo biti pa gotovi o preiskovanem prostoru preiskovancev. tu se potem pojavi dilema ali izrabiti susovo determinirano hitrost pri iskanju majhne variabilnosti podatkov ali iti v iskanje mediane pri quick sortu z podobno zahtevnim algoritmom o(n). se pravi ce nam prostor sortiranja ni zan je skoraj gotovo favorit qs(ako je distribucija nakjucna). ako je prostor determiniran ,variabilnost sortirancev majhna a vendar so vrednosti same po sebi nedeterminirne tedaj ima sus celo nekaj moznosti. v ostalem za determiniran set sortirancev je pinhole mojster nad mojstri.
ali se pac motim ?
kritični se mi je zdel do sedaj najbolj fascinanten pri komprešnu, iz stališča golega komuting funkcionalizma pa no ja mogoce kdaj ... pa brez zamere.
Pust' ot pobyedy k pobyedye vyedyot!
Thomas ::
Radix, Postman, Bucket, Pigeon hole - če hočeš, so matematični sorti, ki ne temeljijo na primerjanju, pač pa na preštevanju in grupiranju in zahtevajo dodatno memorijo.
Several Unique je logični sort ki temelji na primerjanju in zamenjevanju. V svoji domeni je pač najboljši, ne vem zakaj je nekaterim to tako težko sprejet. Ker je zadaj Thomas, al ker je zadaj Critticall?
Several Unique je logični sort ki temelji na primerjanju in zamenjevanju. V svoji domeni je pač najboljši, ne vem zakaj je nekaterim to tako težko sprejet. Ker je zadaj Thomas, al ker je zadaj Critticall?
Man muss immer generalisieren - Carl Jacobi
Thomas ::
> kritični se mi je zdel do sedaj najbolj fascinanten pri komprešnu
Ja ... hvala za to. Ampak nehumano je zvit pri vseh algoritmih.
Ja ... hvala za to. Ampak nehumano je zvit pri vseh algoritmih.
Man muss immer generalisieren - Carl Jacobi
_marko ::
Thomas:
Kako je sploh nastal SUS?
Si dal kak že prej znan sort Critticallu?
In če ja, kaj se zgodi, če probaš enako z vsemi ostalimi najbolšimi na svojem področju?
Drugače pa vse čestitke.
Kako je sploh nastal SUS?
Si dal kak že prej znan sort Critticallu?
In če ja, kaj se zgodi, če probaš enako z vsemi ostalimi najbolšimi na svojem področju?
Drugače pa vse čestitke.
The saddest aspect of life right now is that science
gathers knowledge faster than society gathers wisdom.
gathers knowledge faster than society gathers wisdom.
Thomas ::
Dal sem mu Bubble na samo 0 in 1 recordih. Me je zanimalo, kdaj bo poštudiral, da je dovolj, če samo prešteje nule, jih zapiše od začetka, do konca pa potem enice.
Na moje začudenje je pogruntal, da mu jih še prešteti ni treba! Wow ... hehe!
Potem sem pa dal na začetku programa ta algoritem, pod njim pa še Bubble, da posorta kar pride iz tazgornjega, na vec unique recordih. Zmergal (zdruznil) je oba v nekaj, kar sem potem poimenoval SUS.
Na moje začudenje je pogruntal, da mu jih še prešteti ni treba! Wow ... hehe!
Potem sem pa dal na začetku programa ta algoritem, pod njim pa še Bubble, da posorta kar pride iz tazgornjega, na vec unique recordih. Zmergal (zdruznil) je oba v nekaj, kar sem potem poimenoval SUS.
Man muss immer generalisieren - Carl Jacobi
_marko ::
Kaj pa je še drugega Critticall pogruntal, oz. na čem se dela trenutno?
Kaj lahko v bližnji prihodnosti od njega pričakujemo?
Kaj lahko v bližnji prihodnosti od njega pričakujemo?
The saddest aspect of life right now is that science
gathers knowledge faster than society gathers wisdom.
gathers knowledge faster than society gathers wisdom.
Thomas ::
Next lexical je že. To kar si je zamislil Dijkstra in objavil v učbeniku 1976, je Critticallu uspelo zmanjšati za povprečno en korak. To ni tako razumljiv primer, je pa istega ooomph ranga.
Precej smo se igrali recimo s popravljanjem sortov. Izdelavo nišnih sortov za recimo 9 elementov. Kako jih najboljš posortat. Čudna koda pride!
Ena druga zadeva so sesije. To so matrične operacije za urnike. Prestavi enega učenca iz dveh "istih" skupin tako, da je manj sesij. Se reče, da se več poukov lahko odvija hkrati. Iz "normalnih" 17 pride na 14!
Včeraj sem bil v knežjem mestu da vidim, če so ravnatelji pripravljeni ubijati za to. Zdej grem spet na službeno potovanje.
Precej smo se igrali recimo s popravljanjem sortov. Izdelavo nišnih sortov za recimo 9 elementov. Kako jih najboljš posortat. Čudna koda pride!
Ena druga zadeva so sesije. To so matrične operacije za urnike. Prestavi enega učenca iz dveh "istih" skupin tako, da je manj sesij. Se reče, da se več poukov lahko odvija hkrati. Iz "normalnih" 17 pride na 14!
Včeraj sem bil v knežjem mestu da vidim, če so ravnatelji pripravljeni ubijati za to. Zdej grem spet na službeno potovanje.
Man muss immer generalisieren - Carl Jacobi
Thomas ::
critticall2=array[critticall1];
k=1;
critticall1=1;
if (k>critticall2) {
____l+=1;
}
critticall2=array[critticall1];
if (k>critticall2) {
____array[l]=critticall2;
____l+=1;
}
critticall1+=1;
critticall2=array[critticall1];
if (k>critticall2) {
____array[l]=critticall2;
____l+=1;
}
critticall1+=1;
critticall2=array[critticall1];
if (k>critticall2) {
____array[l]=critticall2;
____l+=1;
____critticall2=63;
____critticall1+=1;
____critticall2=array[critticall1];
____if (k>critticall2) {
________array[l]=critticall2;
________l+=1;
____}
____critticall1+=1;
____critticall2=array[critticall1];
____if (k!=critticall2) {
________array[l]=critticall2;
________l+=1;
____}
____critticall1+=1;
____critticall2=array[critticall1];
____if (k>critticall2) {
________array[l]=critticall2;
________l+=1;
________labelcritticall5:;
________if (critticall1<l) {
________} else {
________}
____}
____critticall1+=1;
____critticall2=array[critticall1];
____if (k>critticall2) {
________array[l]=critticall2;
________l+=1;
____}
____critticall1+=1;
____critticall2=array[critticall1];
____if (k>critticall2) {
________array[l]=-critticall2;
________l+=1;
____}
____critticall1+=1;
____critticall2=array[critticall1];
____if (k>critticall2) {
________array[l]=critticall2;
________l+=1;
____}
}
critticall2=63;
while (critticall2>critticall1) {
____critticall1+=1;
____critticall2=array[critticall1];
____if (k>critticall2) {
________array[critticall1]=k;
________array[l]=critticall2;
________l+=1;
____}
____critticall1+=1;
____critticall2=array[critticall1];
____if (k!=critticall2) {
________array[critticall1]=k;
________array[l]=critticall2;
________l+=1;
____}
____critticall1+=1;
____critticall2=array[critticall1];
____if (k>critticall2) {
________array[critticall1]=k;
________array[l]=critticall2;
________l+=1;
____}
____critticall1+=1;
____critticall2=array[critticall1];
____if (k>critticall2) {
________array[critticall1]=k;
________array[l]=critticall2;
________l+=1;
____}
____critticall1+=1;
____critticall2=array[critticall1];
____if (k>critticall2) {
________array[critticall1]=k;
________array[l]=-critticall2;
________l+=1;
____}
____critticall1+=1;
____critticall2=array[critticall1];
____if (k>critticall2) {
________array[critticall1]=k;
________array[l]=critticall2;
________l+=1;
____}
____critticall2=63;
}
Tole je že en tak primer. Koda optimizirana za sortanje arraya 64 elementov z dvema različnima vrednostma - 0 in 1.
Popolnoma nerazumljivo za človeka - vsaj celotne slike po mojem ćlovek ne more zaobjeti - pa zelo učinkovito, tudi v primeri s Several Unique. Tudi s COMPEXI!
Man muss immer generalisieren - Carl Jacobi
snow ::
Do kolk compex korakov je prišel critticalla pri sortiranju arraya velikega 16?
Tisto ko je ful oh in sploh nekaj.. tam okol 60? 61 menda en prišel z neko podobno zadevo pred dost časa..
Tisto ko je ful oh in sploh nekaj.. tam okol 60? 61 menda en prišel z neko podobno zadevo pred dost časa..
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Thomas ::
COMPEXe razbija, v tem je "problem". Sem se ravno danes ukvarjal z mislijo, kako naj mu to preprečim, to razbijanje.
Krucialno skoraj! S tem bi zdrmal marsikoga.
Krucialno skoraj! S tem bi zdrmal marsikoga.
Man muss immer generalisieren - Carl Jacobi
snow ::
Za to bi bilo najboljše kar kak specialen program - spet kak derivat ;)
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Thomas ::
Ravno mam enega v paci. Sem mislil, da ga bom spacal v eni uri, ampak ... ga bom pa in bo zanimiv.
Man muss immer generalisieren - Carl Jacobi
snow ::
In si že kaj spacal? :)
Bo critticall tudi distributed kdaj? Pa gremo lahko kaj bolj hudega računat/izumljat..
Bo critticall tudi distributed kdaj? Pa gremo lahko kaj bolj hudega računat/izumljat..
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Thomas ::
Sem spacal, ja. Zdej vrednotim rezultate. Moram bit prepričan, preden začnem s samohvalo. Ker to je nerodno, če jo moraš potem vleči nazaj.
Distributed pa je. Sicer so agenti brez komunikacije, tako da morda podvajajo delo. Samo po moje se zaradi tega ne zgubi prav dosti.
Da citiram Cirila Zlobca:
mnogo ciljev je pred nami,
mnoge so poti ki k njim drže ..
Distributed pa je. Sicer so agenti brez komunikacije, tako da morda podvajajo delo. Samo po moje se zaradi tega ne zgubi prav dosti.
Da citiram Cirila Zlobca:
mnogo ciljev je pred nami,
mnoge so poti ki k njim drže ..
Man muss immer generalisieren - Carl Jacobi
snow ::
1.36 verzija je shujšala za ene 150kb glede na 1.35.. kako to?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Thomas ::
Optimizacije se stalno delajo, potem se pa nenadoma začne poznati.
Man muss immer generalisieren - Carl Jacobi
ciki57 ::
Si že probal da bi Critticall (algoritme v njem) izboljševal z Critticalom?
Kakšni bodo pa kaj novi fičerji ki se bodo pojavili v naslednjih verzijah?
Kakšni bodo pa kaj novi fičerji ki se bodo pojavili v naslednjih verzijah?
Thomas ::
Ja, smo probal in nekaj zank je že optimiziranih.
V bodoče se načrtuje specializirane vezije za razna področja in optimiziranje.
V bodoče se načrtuje specializirane vezije za razna področja in optimiziranje.
Man muss immer generalisieren - Carl Jacobi
hash ::
Kaj pa recimo ce das v critticall kaksen NP-complete problem - recimo problem trgovskega potnika(the travelling salesman problem)? A lahko kej izboljsa probleme, ki naj bi bili resljivi le z brute-forcom?
snow ::
Izboljša glede na končni rezultat ne. Brute force pač preveri vse rešitve.
Moral bi pa izboljšat glede na kak količnik dolžina poti/čas... alpa na število preiskanih možnosti.
Je pa seveda problem karkoli iz bruteforce razvijat, ker poje ogromno CPU ;) Need more CPU power!
Moral bi pa izboljšat glede na kak količnik dolžina poti/čas... alpa na število preiskanih možnosti.
Je pa seveda problem karkoli iz bruteforce razvijat, ker poje ogromno CPU ;) Need more CPU power!
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
hash ::
Ja koncnega rezultata ne more izboljsati, saj brute-force proba use moznosti se pravi najde tudi najbolso resitev.
Ampak a niso NP-complete pravilno resljivi le z brute-forcom - torej a bi znal critticall to izboljsati? Obstajajo sicer hitrejsi algoritmi, ki pa dajo le delno pravilne rezultate, oziroma jih ne dajo zmeraj in pa seveda optimizacije(npr. pri knapsacku dinamicno programiranje).
A lahko napise kdo malo vec na temp NP-complete algoritmov?
Ampak a niso NP-complete pravilno resljivi le z brute-forcom - torej a bi znal critticall to izboljsati? Obstajajo sicer hitrejsi algoritmi, ki pa dajo le delno pravilne rezultate, oziroma jih ne dajo zmeraj in pa seveda optimizacije(npr. pri knapsacku dinamicno programiranje).
A lahko napise kdo malo vec na temp NP-complete algoritmov?
Thomas ::
Evo. TSP za 4 mesta: Iz Bruta forca po nekaj urah.
// The algorithm has been enhanced For 15.9523%
$DECLAREINT x1 x2 x3 y0 y1 y3 d02 d03 dw acritticall1 acritticall2 acritticall3 acritticall4 critticall2 critticall5
$DIMENSION x[4] y[4] di[3]
$RINVAR x[](0,100) y[](0,100)
$RETVAR di[]
// int x[4]; int y[4]; int di[3]; int x1=0;int x2=0;int x3=0;int y0=0;int y1=0;int y3=0;int d02=0;int d03=0;int dw=0;int acritticall1=0;int acritticall2=0;int acritticall3=0;int acritticall4=0;int critticall2=0;int critticall5=0;
$BES
acritticall1=1;
y1=y[acritticall1];
y0=y[x3];
x1=x[acritticall1];
dw=x[d02];
acritticall1=2;
x2=x[acritticall1];
acritticall3=y0-y1;
acritticall3=acritticall3*acritticall3;
acritticall2=y[acritticall1];
acritticall1=3;
critticall5=dw-x1;
critticall5=critticall5*critticall5;
critticall5=critticall5+acritticall3;
y3=y[acritticall1];
x3=sqrt(critticall5);
acritticall3=y0-acritticall2;
acritticall3=acritticall3*acritticall3;
critticall5=dw-x2;
critticall5=critticall5*critticall5;
critticall5=critticall5+acritticall3;
d02=sqrt(critticall5);
acritticall3=y3-y0;
acritticall3=acritticall3*acritticall3;
acritticall4=x[acritticall1];
critticall5=dw-acritticall4;
critticall5=critticall5*critticall5;
critticall5=critticall5+acritticall3;
d03=sqrt(critticall5);
acritticall3=y1-acritticall2;
acritticall3=acritticall3*acritticall3;
critticall5=x1-x2;
critticall5=critticall5*critticall5;
critticall5=critticall5+acritticall3;
acritticall1=1;
y0=sqrt(critticall5);
acritticall3=y1-y3;
acritticall3=acritticall3*acritticall3;
dw=x3+y0;
critticall5=x1-acritticall4;
critticall5=critticall5*critticall5;
critticall5=critticall5+acritticall3;
x1=sqrt(critticall5);
critticall5=x2-acritticall4;
critticall5=critticall5*critticall5;
acritticall3=acritticall2-y3;
acritticall3=acritticall3*acritticall3;
critticall5=critticall5+acritticall3;
acritticall2=3;
acritticall4=sqrt(critticall5);
critticall5=d02+y0;
di[acritticall1]=acritticall2;
critticall5=critticall5+x1;
acritticall1=2;
if (critticall5<dw) {
y1=4;
acritticall2=0;
di[acritticall1]=y1;
y1=1;
di[acritticall2]=y1;
goto labelcritticall16;
}
critticall5=d03+x1;
critticall5=critticall5+y0;
if (critticall5<dw) {
acritticall2=2;
y1=4;
di[acritticall2]=y1;
x3=-acritticall3;
y1=1;
di[critticall2]=y1;
goto labelcritticall16;
}
critticall5=x3+x1;
critticall5=critticall5+acritticall4;
acritticall2=5;
y1=dw;
di[acritticall1]=acritticall2;
if (critticall5<dw) {
dw=critticall5;
critticall5=x3+d02;
critticall5=critticall5+acritticall4;
if (critticall5<dw) {
goto labelcritticall10;
}
y1=4;
acritticall2=1;
di[acritticall2]=y1;
y1=1;
di[critticall2]=y1;
goto labelcritticall10;
labelcritticall16:;
dw=critticall5;
}
critticall5=y0+d02;
critticall5=d03+critticall5;
if (critticall5<dw) {
acritticall2=acritticall1;
di[acritticall2]=acritticall2;
y1=3;
dw=critticall5;
di[critticall2]=y1;
acritticall2=1;
di[acritticall2]=acritticall2;
}
if (y1<x3) {
critticall5=x3+d02;
critticall5=critticall5+acritticall4;
if (critticall5<dw) {
di[acritticall2]=y1;
di[critticall2]=critticall2;
y1=5;
di[acritticall1]=y1;
}
}
labelcritticall10:;
$EES
//$RINVAR x[](0,100) y[](0,100)
$INVAR x[](49,57,23,73) y[](61,66,7,68)
$INVAR x[](99,16,71,69) y[](14,81,16,89)
$INVAR x[](46,99,77,66) y[](46,78,66,59)
$INVAR x[](77,53,76,24) y[](12,31,15,7)
$INVAR x[](11,84,15,55) y[](53,24,47,75)
$INVAR x[](57,63,63,73) y[](0,41,68,45)
$INVAR x[](50,10,69,41) y[](47,55,50,61)
$INVAR x[](75,99,43,71) y[](0,25,75,49)
$INVAR x[](8,57,33,36) y[](92,77,49,85)
$INVAR x[](32,98,28,39) y[](89,25,95,57)
$INVAR x[](69,3,64,36) y[](47,37,75,39)
$INVAR x[](4,62,42,24) y[](47,6,18,35)
$INVAR x[](58,9,73,65) y[](66,91,78,55)
$INVAR x[](57,85,39,22) y[](94,10,89,33)
$INVAR x[](16,96,9,80) y[](93,10,22,39)
$INVAR x[](17,64,49,37) y[](46,13,56,58)
$INVAR x[](63,13,86,67) y[](42,67,45,53)
$INVAR x[](68,100,46,64) y[](23,91,19,25)
$INVAR x[](6,23,55,28) y[](81,89,53,87)
$INVAR x[](76,58,3,57) y[](85,97,29,8)
$INVAR x[](89,47,92,57) y[](57,50,10,41)
$INVAR x[](90,7,94,74) y[](77,81,100,94)
$INVAR x[](20,93,3,43) y[](95,100,42,75)
$INVAR x[](27,2,68,57) y[](25,9,96,76)
$INVAR x[](75,17,73,68) y[](0,97,77,16)
$INVAR x[](32,67,2,59) y[](29,65,53,56)
$INVAR x[](42,44,88,46) y[](83,30,20,55)
$INVAR x[](76,74,66,87) y[](15,93,38,76)
$INVAR x[](26,86,79,38) y[](51,24,54,55)
$INVAR x[](32,22,97,81) y[](53,76,50,57)
$INVAR x[](88,62,70,96) y[](89,2,44,15)
$INVAR x[](44,88,31,68) y[](57,29,64,56)
$INVAR x[](47,6,47,53) y[](37,61,49,39)
$INVAR x[](51,31,84,69) y[](53,61,3,14)
$INVAR x[](49,98,94,57) y[](35,65,49,42)
$INVAR x[](61,22,80,40) y[](0,90,93,34)
$INVAR x[](34,46,53,85) y[](59,26,85,41)
$INVAR x[](82,31,74,98) y[](71,11,73,55)
$INVAR x[](90,89,90,77) y[](23,85,83,83)
$INVAR x[](37,96,7,63) y[](60,24,80,40)
$INVAR x[](60,95,49,59) y[](56,20,56,70)
$INVAR x[](63,10,49,28) y[](54,13,56,26)
$INVAR x[](70,89,37,0) y[](42,90,4,37)
$INVAR x[](93,48,81,63) y[](65,10,9,28)
$INVAR x[](58,28,31,0) y[](10,32,91,10)
$INVAR x[](77,43,100,69) y[](83,34,52,41)
$INVAR x[](99,14,93,70) y[](52,95,93,84)
$INVAR x[](7,73,0,46) y[](59,90,60,32)
$INVAR x[](10,99,32,0) y[](91,84,88,37)
$INVAR x[](62,56,0,78) y[](41,67,29,21)
$INVAR x[](58,0,66,32) y[](21,2,70,58)
$INVAR x[](98,39,0,92) y[](93,53,65,86)
$INVAR x[](68,0,90,52) y[](65,51,52,96)
$INVAR x[](48,2,11,3) y[](77,45,95,39)
$INVAR x[](100,22,65,38) y[](3,18,18,55)
Man muss immer generalisieren - Carl Jacobi
Thomas ::
Pogrunta, da lahko nekoliko skače ven iz zank. Težko mu je slediti, kaj hoče povedat, le da dela 15% hitreje od BF.
Zaenkrat.
Z zadost CPU ...
Zaenkrat.
Z zadost CPU ...
Man muss immer generalisieren - Carl Jacobi
OwcA ::
Ker sem dober kot marmorni kolač, prestavljam sem v drugi temi začeto debato (ako sem kakšen odgovor preskočil, me naj prizadeti avtor pocuka za šop dlake). Radujte se!
---
snow
Thomas
snow
Thomas
Thomas
Thomas
Thomas
snow
snow
snow
Thomas
snow
snow
Thomas
Thomas
snow
Vesoljc
---
snow
Thomas kak kaj trikotniki? Si najdel osnovno kodo.. oziroma princip?
Ono najboljižje potence 2 me je minilo ker sem potem šel tam brat pa je bilo 5 korakov asm kode.. kaj hitreje pa res težko da gre ;)
Thomas
Ravno zdej mi gleda najblizjo potenco. A lahko daš tistih 5 assemblerskih ukazov sem?
snow
int __declspec( naked) __fastcall NearestPow2(int n){ _asm { dec ecx mov eax, 2 bsr ecx, ecx rol eax, cl ret } }
Drugače so se pa tu pogovarjali o tem: http://www.gamedev.net/community/forums...
Kaj poganjaš sedaj.. kak si naštimal zadevo da laufa?
Thomas
Poganjamo neko optimizacijo rudimentarnega algoritma. Do 10 milijonov je trenutno 2,5 krat POČASNEJŠA od tega, ki ga je dal Vesoljc.
Zgleda pa tkole:
if (np2<n) { np2=np2*np2; np2=np2+np2; if (np2<n) { np2=np2*np2; np2=np2+np2; while (np2<n) { np2=np2+np2; np2=np2+np2; } np2/=2; critticall1=np2-n; } } np2/=2; n=n-np2; if (critticall1<n) { np2=np2+np2; if (np2<n) { np2=np2+np2; } }
Thomas
Je pa res, da za majhna števila je pa že hitrejši!
Zdej bom pustil tole zevoluirati dokler bo kej kruha.
Tale assembler bom pa prevedel v strict C, ter ga tudi dal optimizirat.
Kaj tale assembler pravzaprav dela? Prevod v slovenščino:
dec ecx ;zmanjšaj C (register) za 1 mov eax, 2 ;v reg A daj 2 bsr ecx, ecx ;od tazgornjega bita dol poglej, kje je taprva 1 in daj v C rol eax, cl ;zavrti vsebino Aja v levo za taspodnjih 8 bitov Cja ret ;fertik si
Thomas
Hja ... sam tale assembler ne dela prav. On vedno da potenco števila 2 NAD n-jem (ecx-om).
Nismo se tko zmenil, mora dat v tabližjo potenco.
Thomas
Žal isto dela tudi C.
Prov, bo pa še Critticall tko!
snow
ja na višjo mora it.. ne bližjo :)
npr. 33 -> 64
oziroma če napišemo splošno: 2^(ceil(log2(x))
snow
In kako bi zgledalo poglej kje je prvi bit v c-ju? :)
snow
Jaz se igram s temle:
$declareint n i t out max num0 num1 $rinvar n (1,10000000) $retvar n max=24; num0=0; num1=1; $bes for(i=max;i!=num0;i--){ t = num1<<i; if(t>n){ out=t; } else { break; } } n=out; $ees
Thomas
Men je najdu eno čudno varianto. Bom objavu jutri zjutraj.
Je pa koristno snow, da midva to delava vsak po svojem tiru in tako mimogrede demonstrirava "necentralizirano distribuiranost".
snow
namesto t>n bi moralo biti tam t>=n.. ker drugace je 2 spremenilo v 4.
zaenkrat sem iz tistega prisel v:
$BES if (max>n) { num0=2; max=0; if (num0>=n) { goto labelcritticall14; } n=n+n; num0=num0^n; goto labelcritticall14; } critticall2=num1<<max; max+=-4; num0=num1<<max; if (num0>n) { max^=-6; critticall2=num0; num0=num1<<max; if (num0>n) { critticall2=num0; max+=-4; num0=num1<<max; if (num0>n) { critticall2=num0; num1+=1; } } } max=critticall2/n; while (max>num1) { num0=critticall2>>num1; max=num0/n; labelcritticall14:; critticall2=num0; } n=critticall2; $EES
snow
Aja vidiš da bi blo pametno imet critticall oglasno desko z kodami. :)
'To see what does community evolve'
Thomas
Ja no, sej tvoj predlog jemljem zelo resno.
Thomas
critticall1=-n; one=n&critticall1; while (n!=one) { one=n+one; n=one&critticall1; }
Tale koda je prišla meni ven. Za nekatera (predvsem majhna) števila je že hitrejša od originala, ker tisti bitsca je pri Intelu ZELO počasen, v primerjavi z drugimi strojnimi ukazi.
Ampak kasneje (zvečer) bom šel napast direktno tisto kodo.
snow
Kaj si mu tu dal za jest? :)
Jaz sem probal onega z bitshifti .. x|= x < < 1 ..
pa sem dobil ven:
n+=-1; critticall1=2; critticall2=n/critticall1; critticall2=n|critticall2; critticall2=critticall2/critticall1; n=n|critticall2; critticall1=8; critticall2=n/critticall1; n=n|critticall2; critticall1=critticall1*critticall1; critticall2=n/critticall1; critticall2=n|critticall2; critticall2=critticall2/critticall1; n=n|critticall2; n+=1;
Aja sem mu rekel da nebi bitshifta mel :)
Ko ne vem ravno koliko kater ukaz poje ciklov..
Vesoljc
@snow
mal pogugli za rdtsc ukazom (za cikle) in pa QueryPerformance* za cas izvajanja (za win platformo).
Otroška radovednost - gonilo napredka.
Zgodovina sprememb…
- spremenilo: OwcA ()
Vesoljc ::
skoda le, da moj monitor ne podpira kolacev v resoluciji 2048x768 
Abnormal behavior of abnormal brain makes me normal...
Zgodovina sprememb…
- spremenil: Vesoljc ()
Thomas ::
// nextpow.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <math.h>
#include <stdio.h>
#include <windows.h>
unsigned NextPow2( unsigned n )
{
const int MantissaMask = (1<<23) - 1;
(*(float*)&n) = (float) n;
n = n + MantissaMask & ~MantissaMask;
n = (unsigned) (*(float*)&n);
return n;
}
int NextPow2_Critticall( int n ) {
// ************* CR code begins ****************
int p2=0;
int i=n;
p2=16;
if (i<=p2) {
p2=1;
if (i<=p2) {
goto label;
}
}
p2=p2+p2;
if (i>p2) {
p2=p2+p2;
if (p2<i) {
p2=p2+p2;
if (i>p2) {
p2=p2+p2;
if (p2<i) {
p2=p2+p2;
}
}
}
}
label:;
// ************* CR code ends here ****************
return p2;
}
int main(int argc, char* argv[])
{
int t=GetTickCount();
for (int n=0; n<10000000; n++) {
NextPow2(n%512);
}
printf("time NextPow2 %d",GetTickCount()-t);
//printf("time NextPow2 %d",NextPow2(778));
system("pause");
t=GetTickCount();
for (n=0; n<10000000; n++) {
NextPow2_Critticall(n%512);
}
printf("time NextPow2_Critticall %d",GetTickCount()-t);
//printf("time NextPow2_Critticall %d",NextPow2_Critticall(778));
system("pause");
return 0;
}
Med "majhnimi števili", do 512, tale Critticall's invention reigns supreme. Ker je bil zevoluiran tam, najbrž. Se ga pa da raztegniti tudi na večja števila.
Man muss immer generalisieren - Carl Jacobi
Zgodovina sprememb…
- spremenil: Thomas ()
drejc ::
Škoda mi firefox ne more prikazat te teme v širini 1024px.
@T: Kako se je kej razvila debata med tabo in solomonci? Si imel z njimi že kaj kontakta ko si razmišljal o kritikalu? Kakšno je njihovo mnenje o tvojem stvoru? Zanima me namreč kaj si slovenski GA strokovnjaki mislijo o stvaritvah kritikala.
Imaš v prihodnosti tudi verzijo kritikala za Javo? Oziroma če bi ga tudi spisal v javi potem nebi bilo problema s cross-platformom.
Sem bolj analfabet o EA zadevah, a me zadeva izredno fascinira. (predvsem zato ker zna algoritme zakomplicirat do skorajšne nerazumljivosti a ohrani funkcionalnost:)
@T: Kako se je kej razvila debata med tabo in solomonci? Si imel z njimi že kaj kontakta ko si razmišljal o kritikalu? Kakšno je njihovo mnenje o tvojem stvoru? Zanima me namreč kaj si slovenski GA strokovnjaki mislijo o stvaritvah kritikala.
Imaš v prihodnosti tudi verzijo kritikala za Javo? Oziroma če bi ga tudi spisal v javi potem nebi bilo problema s cross-platformom.
Sem bolj analfabet o EA zadevah, a me zadeva izredno fascinira. (predvsem zato ker zna algoritme zakomplicirat do skorajšne nerazumljivosti a ohrani funkcionalnost:)
Thomas ::
Poznam kakšnega "solomonca", vendar že dolgo nisem nikogar videl.
Zaenkrat se še niso obremenjevali s Critticallom.
Ampak predvsem je pomembno to, da mi "njihova avtoriteta nič ne znači". Tole more postati "worldwide show", ne samo slovenski. Kar seveda ne pomeni, da zapiram vrata Slovencem, samo nič jih ne priviligiram.
Jurnal of Algorithms je trenutno moj target. Tukajle na Slotechu pa mau testiramo. Bomo začeli to kmalu na moji strani, upam.
Zaenkrat se še niso obremenjevali s Critticallom.
Ampak predvsem je pomembno to, da mi "njihova avtoriteta nič ne znači". Tole more postati "worldwide show", ne samo slovenski. Kar seveda ne pomeni, da zapiram vrata Slovencem, samo nič jih ne priviligiram.
Jurnal of Algorithms je trenutno moj target. Tukajle na Slotechu pa mau testiramo. Bomo začeli to kmalu na moji strani, upam.
Man muss immer generalisieren - Carl Jacobi
Thomas ::
> ce ga raztegnes, prednost pade?
Prednost pada ja. Ampak sem ravnokar dal kuhat 16 bitno varianto. Lahko da bo čisto drugačna. Že jutri ko vstanem, ali pa zvečer ko pridem domov. (V vsaki službi so službena potovanja. )
Prednost pada ja. Ampak sem ravnokar dal kuhat 16 bitno varianto. Lahko da bo čisto drugačna. Že jutri ko vstanem, ali pa zvečer ko pridem domov. (V vsaki službi so službena potovanja.
) Man muss immer generalisieren - Carl Jacobi
|SNap| ::
To bi blo pa hudo :> Al pa ce mu das "kuhat" eno standardno resitev, pa da jo zoptimizira za cimmanj premikov :>
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Najhitrejši programski jezik? (strani: 1 2 )Oddelek: Programiranje | 8142 (5962) | Senitel |
| » | Funkcija z logičnimi operaterji.... (strani: 1 2 )Oddelek: Programiranje | 6022 (5368) | CaqKa |
| » | Petaflopsu naproti (strani: 1 2 3 )Oddelek: Novice / Procesorji | 9730 (9730) | Marjan |
| » | cene permutacij help pleaseOddelek: Programiranje | 2224 (1831) | Sergio |
| » | kako definirtati prasteviloOddelek: Programiranje | 3936 (3741) | ooux |