[GPC] opgave 2 poging 2

[D2k]

Op dinsdag 11 december 2001 19:42 schreef Dash2in1 het volgende:

[..]

Enig idee wanneer de volgende begint?

ik wel

[Verwijderd]

Oeps, ik heb volgens mij een O(a^n) oplossing, maar ik ga wel vantevoren de combi's zo veel mogelijk beperken...

Affijn, na middernacht meer discussie

[Twilight Burn]

Toen ik nog niet wist dat je de prioriteiten van meegaan/meedoen/meemaken e.d. voor het woord 'mee' op moest tellen had ik een best efficient ding gebouwd, maar het prog dat ik nu heb is zo inefficient als het maar zijn kan denk ik (hoewel ie toch "slechts" 400ms nodig neeft voor die 255 test)

[Theswitch]

Op dinsdag 11 december 2001 19:50 schreef D2k het volgende:

[..]

ik wel

Krijg ik nog mail?

[Dash2in1]

Op dinsdag 11 december 2001 21:21 schreef Twilight Burn het volgende:
Toen ik nog niet wist dat je de prioriteiten van meegaan/meedoen/meemaken e.d. voor het woord 'mee' op moest tellen had ik een best efficient ding gebouwd, maar het prog dat ik nu heb is zo inefficient als het maar zijn kan denk ik (hoewel ie toch "slechts" 400ms nodig neeft voor die 255 test)

Haha, ik heb de meest inefficiente gebouwd Komt ongeveer neer op iets als while(true); bij die van 255

[D2k]

Op dinsdag 11 december 2001 21:22 schreef Theswitch het volgende:

[..]

Krijg ik nog mail?

sjorry

<edit>
done

[Verwijderd]

Op dinsdag 11 december 2001 00:18 schreef Xalista het volgende:
_piranha_: 10 miliseconden als ik em ook zo pipe.

Gelukkig... Ik schold je uit voor aap als je niet sneller kon dan mijn onefficiente code

Met de overhead van die STL zooi (dat progt lekker snel ) en mijn 'who cares hoeveel woorden en hoe lang ze zijn' aanpak (met dus bijhorende creatieve datastructuren die niet gebouwd zijn op snelheid) stond ik er zelf al versteld van dat het zo snel ging
Naja, als je 225 woorden kan doen in 50 ms, dan zal 10 minuten wel volstaan om er max 1000 te doen zeker En daar ging het me om. Bonuspunten zal ik toch wel niet krijgen, want ik stuur altijd als laatste in, en bovendien optimaliseer ik m'n code niet echt Laat staan dat ik het beste algo ga zoeken Doet er mij aan denken, ik moet 'm nog ff insturen dus....
See ya guys in part 3 !

btw : kunnen we worden verwittigd als er een tussenstand is ? Ik wel wel 'ns weten of ik in de top 25 sta

edit:
Ik heb 'm net doorgestuurd. Dus geen oplossingen meer doorsturen nu, anders klopt bovenstaande niet meer

[wasigh]

de nieuwe opgave komt morgen een uurtje of 14:00

we moeten eerst het jury systeem aan de praat krijgen en in gaan voeren

[wasigh]

Als dat uitloopt kan het ook vrijdag worden...trouwens

[Verwijderd]

Begrijp dat de opgave gesloten is...Echter, de oplettende lezer raadt het al, ik heb d opgave niet terug gehad...??

[D2k]

Op woensdag 12 december 2001 09:40 schreef Joshua30 het volgende:
Begrijp dat de opgave gesloten is...Echter, de oplettende lezer raadt het al, ik heb d opgave niet terug gehad...??

lijkt me stug
ga het ff nazoeken maar volgens mij ben je weer gemaild

<edit>
en idd
op je zonnet adres

[Verwijderd]

Op woensdag 12 december 2001 09:41 schreef D2k het volgende:

[..]

lijkt me stug
ga het ff nazoeken maar volgens mij ben je weer gemaild

<edit>
en idd
op je zonnet adres

Ik word gek...Echt niks binnengekregen, terwijl dit een ander mail-adres is als het probleemgeval van de laatste dagen...
Kun je hem nog een keertje sturen, of hier even melden of-ie goed was, kan hem nu toch niet meer aanpassen...
Tnx!

[D2k]

Op woensdag 12 december 2001 09:54 schreef Joshua30 het volgende:

[..]

Ik word gek...Echt niks binnengekregen, terwijl dit een ander mail-adres is als het probleemgeval van de laatste dagen...
Kun je hem nog een keertje sturen, of hier even melden of-ie goed was, kan hem nu toch niet meer aanpassen...
Tnx!

zal het maar ff posten
want mailen met jou is onmogelijk geloof ik
hij was ...... <tromgeroffel>................. goed

[Verwijderd]

Op woensdag 12 december 2001 09:55 schreef D2k het volgende:

[..]

zal het maar ff posten
want mailen met jou is onmogelijk geloof ik
hij was ...... <tromgeroffel>................. goed

Oke! Dank, dank! Mailen lijkt inderdaad vrij onmogelijk op dit moment...Hoewel ik wel andere mailtjes binnenheb op het zonnet-account... Dat andere account was aangemeld bij ordb (proest...) foutje van de provider (zal geen namen noemen...hebben al genoeg problemen na mevr. Brink, oeps...)

[Munters]

Op dinsdag 11 december 2001 13:30 schreef Xalista het volgende:

[..]

Precies. En ik denk zelf dat je niet het hele algoritme O(n) kunt krijgen. Bij mij gaat het afdrukken van het rijtje woorden dat bij 1 cijfercode hoort in O(n), maar alleen door een handige datastructuur waarvan het vullen in O(n log n) gaat.
[..]

Nee, da's niet waar, er mag best een loop inzitten, maar dan wel 1 met een constate lengte. In principe is iets O(1) als het altijd even lang duurt (op een constante na), onafhankelijk van de invoer.

Ok, nieuwe poging (nu niet het opzoeken van 1 coderegel, maar van het hele programma).

Stel de lengte van de dictionary op D.
Stel het aantal invoergetallenreeksen op R.
Stel de gemiddelde lengte van een getallenreeks op L.

Dan is de totale verwerking van mijn programma:
De Dictionary wordt eenmalig geparsed: D * O(1)
Ieder getal wordt L maal verwerkt. Een verwerking gaat met log(D): R * L * O(log D).

Totaal dus: O(D) + O(R * L * log D).
Stel nu N = R * L.
Dan is de totale tijd: O(D) + O(N log D).

Omdat D en N constant zijn, is de orde gelijk. Oftewel O(D) = O(N). Daarmee komen we op O(N) + O(N log N).

Totaal dus: O(N log N).

[Verwijderd]

Op woensdag 12 december 2001 10:15 schreef Munters het volgende:

[..]

Ok, nieuwe poging (nu niet het opzoeken van 1 coderegel, maar van het hele programma).

Stel de lengte van de dictionary op D.
Stel het aantal invoergetallenreeksen op R.
Stel de gemiddelde lengte van een getallenreeks op L.

Dan is de totale verwerking van mijn programma:
De Dictionary wordt eenmalig geparsed: D * O(1)
Ieder getal wordt L maal verwerkt. Een verwerking gaat met log(D): R * L * O(log D).

Totaal dus: O(D) + O(R * L * log D).
Stel nu N = R * L.
Dan is de totale tijd: O(D) + O(N log D).

Omdat D en N constant zijn, is de orde gelijk. Oftewel O(D) = O(N). Daarmee komen we op O(N) + O(N log N).

Totaal dus: O(N log N).

Ik zou het toch iets anders berekenen:

Ik ga ervan uit dat de orde bepalingen die je voor de delen van je algoritme geeft goed zijn.

Stel de lengte van de dictionary op D.
Stel het aantal invoergetallenreeksen op R.

De gemiddelde lengte van een getallen reeks is op de lange duur gewoon 25 (of iig constant) dus die neem ik niet mee.

Je parst je dictionary in O(D) en je print alle woorden die bij 1 getallenreeks horen in O(log D). Er zijn R van zulke getallenreeksen dus de totale rekentijd wordt O(D) + O(R)*O(log D) = O(R log D). Ik zou R en D niet vervangen door N, want zoals het er nu staat geef je mooi aan dat het vergroten van de dictionary minder invloed heeft op de rekentijd van je algoritme dan het vergroten van het aantal getallenreeksen.

[Munters]

Op woensdag 12 december 2001 10:41 schreef Xalista het volgende:

[..]

De gemiddelde lengte van een getallen reeks is op de lange duur gewoon 25 (of iig constant) dus die neem ik niet mee.

Dat begrijp ik niet. De lengte van de gemiddelde getallenreeks is gelijk aan de gemiddelde lengte van nederlandse woorden. Ik kan me niet voorstellen dat dat 25 is. Maar dat is puur op gevoel hoor.

Je parst je dictionary in O(D) en je print alle woorden die bij 1 getallenreeks horen in O(log D). Er zijn R van zulke getallenreeksen dus de totale rekentijd wordt O(D) + O(R)*O(log D) = O(R log D). Ik zou R en D niet vervangen door N, want zoals het er nu staat geef je mooi aan dat het vergroten van de dictionary minder invloed heeft op de rekentijd van je algoritme dan het vergroten van het aantal getallenreeksen.

Dat klopt, maar dat is nu het (on)aardige van "orde van grootte".
Ik vind dat net zoiets als een O(n^2) oplossing die in de dagelijkse praktijk best altijd beter kan uitpakken dan een O(n log n) oplossing. (Zo kan in een bepaalde situatie een bubblesort() algoritme best altijd sneller zijn dan quicksort()).

O() zegt eigenlijk alleen iets over de schaalbaarheid, meestal naar zeer grote getallen.
Anders kun je ook zeggen dat het zonde is om de constanten niet op te nemen (Dan krijg je van die opmerkingen als O(3n log n/2) algoritme is minder dan jouw O(6n log n/3) algoritme).

Wel grappig is dat ik door deze discussie alweer twee optimalisaties heb bedacht. Maar allemaal dingen die alleen constante verbeteringen zouden kunnen opleveren. Dus waarom zou ik?

Jammer trouwens dat ik opgave 1 heb gemist. Lijkt me een veel interessanter probleem. Misschien ga ik me daar nog eens over buigen.

[Verwijderd]

Op woensdag 12 december 2001 14:11 schreef Munters het volgende:

[..]

Dat begrijp ik niet. De lengte van de gemiddelde getallenreeks is gelijk aan de gemiddelde lengte van nederlandse woorden. Ik kan me niet voorstellen dat dat 25 is. Maar dat is puur op gevoel hoor.

Idd, maar voor deze opgave is het de maximale lengte 50, dus de gemiddelde lengte ~25 voor veel woorden.

[..]

Dat klopt, maar dat is nu het (on)aardige van "orde van grootte".
Ik vind dat net zoiets als een O(n^2) oplossing die in de dagelijkse praktijk best altijd beter kan uitpakken dan een O(n log n) oplossing. (Zo kan in een bepaalde situatie een bubblesort() algoritme best altijd sneller zijn dan quicksort()).

O() zegt eigenlijk alleen iets over de schaalbaarheid, meestal naar zeer grote getallen.
Anders kun je ook zeggen dat het zonde is om de constanten niet op te nemen (Dan krijg je van die opmerkingen als O(3n log n/2) algoritme is minder dan jouw O(6n log n/3) algoritme).
[..]

Ja en nee, die opmerking over O(n^2) vs O(n log n) kan wel waar zijn, maar in de praktijk maakt het echt wel uit hoor. Vergelijk het sorteren van 1000000 getallen met quicksort vs. bubblesort. 1000000 is geen extreem groot getal, maar met bubblesort kost het in de orde van 100000 keer langer dan met quicksort, en daar veranderd een (eventueel) lagere constante bij bubblesort niks aan.
Maar aan de andere kant, een lagere orde van complexiteit garandeert geen efficienter programma, dat is zeker waar. Ook daar is quicksort weer een goed voorbeeld van, want de quicksort heeft een worstcase complexiteit van O(n^2) terwijl het in de praktijk toch ongeveer het snelste sorteer algoritme is dat we hebben, ook veel ZEER grote inputs.

[Munters]

Op woensdag 12 december 2001 15:32 schreef Xalista het volgende:

[..]

Idd, maar voor deze opgave is het de maximale lengte 50, dus de gemiddelde lengte ~25 voor veel woorden.

Oh, vandaar 25. Ik zat aan het alfabet te denken.
Maar als de max. lengte 50 is zal het denk ik niet gemiddeld 25 zijn. Er zijn gewoon een aantal vaste grenzen, zodat het coden makkelijker wordt. Net als dat je van correcte invoer uit mag gaan.

Ja en nee, die opmerking over O(n^2) vs O(n log n) kan wel waar zijn, maar in de praktijk maakt het echt wel uit hoor. Vergelijk het sorteren van 1000000 getallen met quicksort vs. bubblesort. 1000000 is geen extreem groot getal, maar met bubblesort kost het in de orde van 100000 keer langer dan met quicksort, en daar veranderd een (eventueel) lagere constante bij bubblesort niks aan.

Voor een sorteerroutine vind ik 10^6 best groot hoor.
Ik kwam hiermee omdat ik in de praktijk voorbeelden heb gezien waarbij (een eigen slechte variant van) quicksort gebruikt werd, op een array van ca 25 stuks, die eigenlijk altijd vrijwel gesorteerd was (dit omdat de toevoegmodule er geen rekening mee hielt dat de array al gesorteerd was en alles gewoon achteraan plakte).

Maar aan de andere kant, een lagere orde van complexiteit garandeert geen efficienter programma, dat is zeker waar. Ook daar is quicksort weer een goed voorbeeld van, want de quicksort heeft een worstcase complexiteit van O(n^2) terwijl het in de praktijk toch ongeveer het snelste sorteer algoritme is dat we hebben, ook veel ZEER grote inputs.

Volgens mij zijn we het gewoon eens.

Hm, ik heb sterk de behoefte aan de uitslag en een nieuwe opgave.

[D2k]

Op woensdag 12 december 2001 15:49 schreef Munters het volgende:
Hm, ik heb sterk de behoefte aan de uitslag en een nieuwe opgave.

op beide zal je moeten wachten

[Mithrandir]

Ik doe aan topicmishandeling

[Verwijderd]

En ik heb last van ongeduld.

[Theswitch]

De volgende opgave zal wel iets uitdagender worden denk ik zo

[D2k]

Op woensdag 12 december 2001 20:52 schreef Theswitch het volgende:
De volgende opgave zal wel iets uitdagender worden denk ik zo

goh hoe zou jij dat weten ??

Op woensdag 12 december 2001 20:47 schreef Doekman het volgende:
En ik heb last van ongeduld.

zie
|
v

Op woensdag 12 december 2001 09:24 schreef wasigh het volgende:
de nieuwe opgave komt morgen een uurtje of 14:00

we moeten eerst het jury systeem aan de praat krijgen en in gaan voeren

[Verwijderd]

Op woensdag 12 december 2001 20:52 schreef Theswitch het volgende:
De volgende opgave zal wel iets uitdagender worden denk ik zo

No problem

Maar als ik ff een suggestie mag doen ? Laat dan bvb deze vrijdagavond beginnen ofzo, en geef tot zondag 23 of maandag 24 december ofzo. Dan hebben we 2 weekends, en da's voor mij - en waarschijnlijk voor de meeste mensen - net iets aangenamer coden. Geeft ons een fractie meer tijd, en da's wel handig meegenomen als je gedurende de week niet kunt coden bij accuut gebrek aan tijd... Bovendien moeten we dan nog eens een deel van de komende weekends gaan spenderen aan Christmas shopping enzo, dus dan rest er al helemaal geen tijd meer om te coden
Het is maar ff mijn mening verkondigen hoor, dus ga me nu niet lopen afbreken. Tenslotte is 't toch de jury die beslist, want ik heb niets te zeggen Maar 't kan geen kwaad om ff iets te 'suggereren' dacht ik