Keskustelu: Ohjelmointiputka: Putkaposti 21: Hyödyllinen sana

Taas on putkapostin aika:

https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=hysa

Ratkaisutavoista saa mielellään keskustella tässä.

Ratkaisutapa 1. Selasin sanalistaa. Osui sopiva sana silmään.

Myöhemmin tapa 2, johon mietin sopivaa algoritmia.

Olenko ymmärtänyt jotakin väärin vai onko tuossa tarkistuksessa virhe?

Syötän siihen sanan "ahaa". Se vastaa, että löysi sanat "ahaa" ja "haa".
Mutta siinähän on 4 sanaa: "ahaa", "ha", "haa", "ah".

E: Kappas, niinpä näkyy :)

Tehtävässä on pikku sivuhuomautus:

Putkaposti 21 kirjoitti:

- - sekä lisäksi sanoissa täytyy olla ainakin kolme kirjainta.

Syynä tähän on, että lyhyemmät sanat ovat lähinnä huudahduksia ja vastaavia, joita ei ole minusta kiinnostavaa laskea mukaan.

Tuossa taustalla putkahtelee tuloksia lähinnä brute forcea käyttävästä pikku ohjelmasta. Pitänee ehkä optimoida algoritmia, mutta vaarana on, että optimoinnissa menee enemmän aikaa kuin tuon nykyisen suoritukseen ;-)

Kolme eri sanaa antaa tuloksen 17 näiden tietojeni mukaan. Lisää voi olla, ehkäpä parempikin sana löytyy.

Intelin Core 2 Duo E4500 raksutti brute forcea noin 15 min 15 sek. Hyödyntäen kylläkin vain toista ydintä. Koodi oli täysin optimoimaton.
Onneksi on kaksi ydintä niin kone ei ihan kokonaan jumitu vaan voi tehdä muutakin ajan kuluksi.

Kopeekka kirjoitti:

Kolme eri sanaa antaa tuloksen 17 näiden tietojeni mukaan. Lisää voi olla, ehkäpä parempikin sana löytyy.

Tuskin löytyy parempia kuin 17..

Minulla jumittui Firefox ohjelman ajon aikana, kun muistin kulutus oli aika hurrja :)

Parempia sanoja en löytänyt, mutta 17:ään saattaa kyllä päästä useammallakin sanalla. Brute force se on joka jyllää.

Ensimmäinen toteutus noin 50 riviä ja meni 10 sekuntia, eli eipä pahemmin tarvinnut edes lähteä optimoimaan. :)

Rivit jäi laskematta, kun kirjoittelin vaan jotakin tulkkiin. Linja on mennyt kehitysajan optimointiin näissä, koska malliratkaisuja ja muiden ratkojien ohjelmia ei juuri julkaista. Joskus ennen jaksoin vielä tehdä Putkaposteihin oikeita ohjelmia, jopa kommentoida koodin sekä selittää ratkaisun, ja mailata Antille. Vaan nykyään on luontainen laiskuus voittanut.

Olisihan tuo kiva nähdä esim. Samin ohjelma, niin voisi miettiä miksi se on omaa noin paljon nopeampi. Toisaalta oma meni jo hukkaan, kun suljin tulkin ja koneen :-/

Tarkoitus ei ole ahdistaa Anttia julkaisemaan asiaa vanhoista tehtävistä. Onhan tässä itse kullakin muuta tekemistä. Olisi vain kiva, jos Putkassa olisi enemmän toimintaa, jonka yhtenä seurauksena näkisi muiden huolellisesti tekemää koodia. Sellaisesta kun voi joskus vaikka oppia jotakin ...

</jaarittelu>

Kopeekka kirjoitti:

Parempia sanoja en löytänyt, mutta 17:ään saattaa kyllä päästä useammallakin sanalla.

Oman ohjelmani mukaan neljällä sanalla. Kaikilla niillä on muuten eräs yhteinen piirre.

Oma ohjelmani on bruteforce, joka kylläkin valikoi sanoja niiden pituuden perusteella. Suoritusaika on puolisen minuuttia.

Voisipa itsekin koittaa tuon ratkaista jotenkin. Brute forcella raksuttamalla varmasti tuohon 17:ään toista pääsisi, mutta voisi koittaa jonkin hienomman/älykkäämmän algoritmin kehittää. Jos pääsisi huomattavasti vähemmällä kuin vain sen raa'an voiman käytön vaatimalla ajalla. Hauskempaakin niin ratkaista. Se ei paljon taitoja tai ajattelua vaadi, että osaa laatia kaikkia sanoja kaikilla muilla testaavan algoritmin. Ainoastaan aikaa voi vaatia.

Tulipa tässä mieleen sellainen ehdotus, että voisi tuolta tehtävien sivulta poistaa näkyvistä ne muiden tulokset. Laittaisi vain sijoitukset näkyville, joka sitten antaisi osviittaa siitä, mitä tasoa se oma tulos on. Niistä kun helposti löytää sen parhaan tuloksen, jolloin myös oman ratkaisun keksiminen helpottuu huomattavasti.

Kopeekka: Collections.binarySearch

Ja tajusinpahan juuri hyvinkin yksinkertaisen optimoinnin (indeksointirajojen muuttaminen siten, että se ei tutki alle 3 merkin alisanoja), joka pudotti suoritusajan 6 sekuntiin.

Unohtuipa tuosta edellisestä viestistä vielä, että itsestäkin olisi mukava nähdä noita muiden ratkaisuja tuon postin päättymisen jälkeen. Tietysti ymmärrän, että mr. Ylläpitäjällä on muutakin elämää ja erinäisiä kehitysehdotuksiakin on kovin paljon tullut esille käyttäjiltä (Olisi myös kiva kuulla Antin mielipiteitä niistä ja tulevaisuudennäkymiä).

Tietysti jos ei putkaan noita saada, niin itse en näkisi myöskään huonona vaihtoehtona sellaista, että joku voisi omalle palvelintilalleen niitä sorsia varastoida näytille. Ne eivät paljoa tilaa edes vie. Itse ainakin voisin tuollaista tehdä, jos vain olisi sitä tilaa.

Kopeekka kirjoitti:

Kolme eri sanaa antaa tuloksen 17 näiden tietojeni mukaan. Lisää voi olla, ehkäpä parempikin sana löytyy.

Neljä löysi oma ohjelma noita 17 tuloksisia.

Neljähän noita löytyi tylsällä bf:llä. Sanan pituuden toimiessa karsijana suoritusaika 10 sekunnista ylöspäin. Täytyypä tutkia tuota binäärihakua...

Sekunneista puhutte? Päälle 3 minuuttia (202625ms, 3:11min) se tuota raksutteli optimoituna pituustarkistuksella ja sanalistaa lajittelematta... en pysty tuosta enää puristamaan mitään :P Kyllähän se 13 sekuntiin meni jos huijaa pituusrajan säännöttömän korkealle.

Athlon 64 Core 2 4200

User137 kirjoitti:

Kyllähän se 13 sekuntiin meni jos huijaa pituusrajan säännöttömän korkealle.

No niinpä, ilman pituustarkistusta tuo tekeleeni suoritusaika lasketaan tunneissa :)

Pääsyy vanhojen tehtävien ratkaisujen puuttumiseen on saamattomuuteni, mutta ratkaisujen julkaisussa on myös muutama ongelma. Ensinnäkin jos ratkaisut julkaistaan kaikkien nähtäville, moni voi katsoa suoraan ratkaisun tehtävää miettimättä. Muihinkin kuin uusimpaan putkapostiin tulee aina välillä ratkaisuja. Jos taas ratkaisut julkaistaan vain vastauksen lähettäneille, pitäisi joka tehtävässä erikseen päättää, kuinka hyvä lähetys riittää ratkaisun näkemiseen.

Alkuperäinen ajatus oli laatia tehtävistä kattavia selostuksia, ja muutama sellainen valmistuikin. Tällaisten ratkaisuiden kirjoitus on kuitenkin osoittautunut niin työlääksi, että olisi kenties parempi julkaista tulevat ratkaisut koodivinkkien tapaan, jolloin ratkaisu muodostuu koodista ja sen kuvauksesta. Tietysti samaan tehtävään voisi olla monta vaihtoehtoista ratkaisua.

Päärynämies kirjoitti:

Tulipa tässä mieleen sellainen ehdotus, että voisi tuolta tehtävien sivulta poistaa näkyvistä ne muiden tulokset.

Olen yrittänyt valita vastauksista näytettävän tiedon niin, että se paljastaa mahdollisimman vähän tehtävän ratkaisusta. On kyllä totta, että usein joku löytää parhaan ratkaisun pian tehtävän julkaisun jälkeen, jolloin tehtävän miettimisestä saattaa mennä osittain hohto. Mutta minusta muiden saamien tulosten vertailu omiin tuloksiin on yleensä sen verran hauskaa, että en haluaisi muuttaa nykyistä järjestelmää.

Kuten Kopeekka ja Päärynämies ovat arvailleet, Putkapostin toimintaa rajoittaa käytössä oleva aikani. Tärkein tavoite on, että uusia tehtäviä ilmestyy säännöllisesti, ja tämä on toteutunut melko hyvin. Muissa asioissa onkin vielä parantamista, ja toivon teiltä kärsivällisyyttä.

User137 kirjoitti:

Sekunneista puhutte? Päälle 3 minuuttia (202625ms, 3:11min) se tuota raksutteli optimoituna pituustarkistuksella ja sanalistaa lajittelematta... en pysty tuosta enää puristamaan mitään :P Kyllähän se 13 sekuntiin meni jos huijaa pituusrajan säännöttömän korkealle.

Athlon 64 Core 2 4200

Eli parannettavaa löytyy :P.

Oma ratkaisuni käy tuon listan läpi 3.5 sekunnissa (Athlon64 X2 4000+). Sen kummemmin tutkittavia sanoja valitsematta.

Ehdotin tätä Laaksoselle seuraavaksi putkapostiksi, mutta hän taas ehdotti että pistäisin sen tänne vain lisätehtäväksi, koska se on hyvin samankaltainen tämänkertaisen postin kanssa.
Eli siis tässä pieni lisätehtävä niille, jotka pitivät varsinaista postia liian helppona tai muillekin, jotka haluavat yrittää hieman vaikeutettua tehtävää:
Samaa sanalistaa käyttäen, minkä sanan kirjaimista pystyy muodostamaan eniten muita, vähintään 3 kirjaimen pituisia, suomen kielen sanoja? Esimerkiksi sanasta "maailma" saisi ainakin "maa", "ilma", "lima", "maali", "maila" ja "laama", mutta varmasti muitakin löytyy.
Jos joku tahtoo tarkistaa saamansa vastauksen, niin kyhäsin pienehkön tarkistusohjelman (java-appletti) sitä varten, joka toivottavasti toimii ja löytyy osoitteesta http://www.students.tut.fi/~maki36/OP/Tarkistaja.html. Appletti ei tosin tarkista ovatko sanat oikeita sanoja, koska sillä ei ole sanalistaa käytössä, joten se osa jää tehtävän ratkaisijan tehtäväksi.

Ja jotta kukaan ei pilaisi heti muiden iloa, niin pyytäisin ettei kukaan pistä ainakaan heti parasta sanaa esille, mutta sanamäärän tietysti voi ja on jopa suotavaakin kertoa, sekä sen kuinka helposti tehtävä ratkesi.

Onkos joku minun lisäkseni koettanut ratkaista Samin tehtävää? Pienen mietinnän jälkeen sain aikaan kohtuullisen nopean hakuohjelman, joka löysi eniten anagrammeja sisältävän sanan alle viidessä minuutissa. Tuolla tavalla sanan sisälle saakin mahtumaan huomattavasti suuremman joukon muita sanoja.

Mahtaako tähän uuteen ongelmaan olla parempaa ratkaisua kuin n2a, missä n on sanojen määrä ja a aakkoston koko?

Putkapostin vastauksen etsimiseen meni noin 1,2 s. Samin tehtävän vastaus (11255) löytyi noin 2 minuutissa. Ajat pystyisi puolittamaan dual core prossulla, jos jaksaisi pistää tuohon toisen threadin pyörimään. Mulla oli molempiin tehtävään aika paljon valmista koodia entuudestaan, joten noihin ei mennyt kuin 20-30 riviä javakoodia kumpaankin.

Jaksoinpa tehdä tuon lisätehtävän, algoritmi on tosiaan pohjimmiltaan n2a. Niin kutsutulla OMG-optimoinnilla saa tässä syötteessä sijoitettua a:n paikalle pieniä numeroita (32-bittisellä koneella nelosen, 64-bittisellä tietenkin kakkosen, SSE2:n avulla kai jopa ykkösen), kun tiedetään, että mikään kirjain ei esiinny yhdessä sanassa yli seitsemää kertaa. Ohjelmani löysi sanan ajassa 13 min 37 s vanhalla 333 megahertsisellä tietokoneella, uudempi kone pääsee lähes puoleentoista minuuttiin.

Metabolix kirjoitti:

Niin kutsutulla OMG-optimoinnilla saa tässä syötteessä sijoitettua a:n paikalle pieniä numeroita - -

Mitä tämä optimointitapa tarkoittaa (yleensä ja tässä tapauksessa)?

OMG-optimointi viittaa toisinaan kaikenlaisiin merkillisiin temppuihin, jotka eivät kuulu selkeään ja hyvään ohjelmointitapaan mutta mahdollisesti nopeuttavat ohjelmaa marginaalisesti.

Tehtävän kannalta olennaista on tietää, onko tietyssä sanassa tiettyä kirjainta enemmän tai yhtä paljon kuin toisessa sanassa. Kun lasketaan jokaisen sanan eri kirjainten lukumäärät, huomataan, että suurin tulos on sopivasti seitsemän, joten määrät voi tallentaa näppärästi kolmen bitin alueisiin.

Kun kaksi n-bittisissä muuttujissa olevaa n-1-bittistä lukua vähennetään toisistaan, ylimmästä bitistä nähdään, tuliko negatiivinen tulos. Tätä voidaan soveltaa niin, että tallennetaan lasketut kolmibittiset arvot peräkkäisille neljän bitin alueille laajempaan muuttujaan. Koska olennaista ei ole laskun tulos vaan tuloksen mahdollinen etumerkki, samassa muuttujassa olevat laskut eivät häiritse toisiaan: korkeammat bitit eivät vaikuta matalampiin missään tapauksessa, matalammat taas vaikuttavat korkeampiin vain, jos tulos on negatiivinen.

Aakkostossa on kaikkiaan 29 kirjainta, joten tarvitaan 116 bittiä eli neljä 32-bittistä lukua. Tarkistus käy helposti:

bool operator >= (sana const& ylasana, sana const& alasana)
{
  for (i = 0; i < 4; ++i) {
    if ((ylasana.k[i] - alasana.k[i]) & 0x88888888) {
      // Jostain tuli negatiivinen, joten alasana ei muodostu ylasanasta
      return false;
    }
  }
  return true;
}

SSE2 mahdollistaa käsittääkseni 128-bittiset laskutoimitukset, mutta en tiedä siitä sen enempää.

Joo, minäkin mietin vähän tuollaisia bittivirityksiä, mutta en ole vielä toteuttanut niitä omaan ohjelmaani. Kokeilitko, miten paljon tuo nopeuttaa tavalliseen anagrammin tarkistukseen verrattuna?

Kysymys kuuluu edelleen, onko tähän ongelmaan jokin toinen tehokkaampi lähestymistapa. Voiko anagrammihakua toteuttaa aidosti nopeammin kuin vertaamalla kaikkia sanoja toisiinsa, jos sanastosta ei saa tehdä mitään oletuksia?

On tuohon nopeampikin tapa, tosin sen koodaamiseen menee enemmän kuin tuo 2 min. Järjestetään aluksi sanat pituuden mukaan, pisimmät ensin. Sitten tutkitaan noita sanojen lukumäärää alkuperäistä listaa vastaan ja samalla kaikki osuvat sanat karsitaan tutkittavien sanojen listasta. Näin mitään sanaa mikä löytyy pidemmästä sanasta anagrammina ei tutkita uudestaan. Tämän pitäisi pudottaa suoritusajan murto-osaan alkuperäisestä.

Käytännössä tuo on toki hyvä optimointi, mutta pahimpaan tapaukseen se ei auta. Sanasto nimittäin voi olla sellainen, että mikään sana ei ole toisen sisällä.

Tein PHPeellä 22 rivisen viritelmän. Laitan runnaamaan 120 mhz koneella(koitin ensi lähettään nettiin mutta tuli että kestää liian kauan).
Edit: taas valittaa ajasta, pitää portata QBeelle.
Edit2: Ny tulee sanojen taulukkoon lukemises "Out of string space"

QB ei ole tällaisiin (DOS-mittapuulla) paljon dataa käsittäviin tehtäviin paras mahdollinen väline, ja PHP-ohjelmien ajaminen palvelimella yleensä aiheuttaa ongelmia siksi, että palvelinskriptien aikarajat ovat usein melko tiukkoja. PHP-ohjelman voi ajaa myös komentoriviltä, php jotain.php (tai php-cgi jotain.php, jolloin kylläkin tuloste sisältää HTTP-ainesta).

Kun kurssilla tuli (minulle) uusia tietorakenteita vastaan, niin päätin kokeilla niistä yhtä. Kieli on C, koneella (Core2Dual läppäri) kestää 2 sekuntia tunkea sanat tietorakenteeseen ja sekunti etsiä paras sana. Hörppää muistia noin 70 mt. Jos syöte olisi isompi, tuohon voisi kokeilla muutamaa optimointia vielä. Pitää kokeilla etsiä englannin kielestä vastaava lista :)

Tiedoston lukuajasta ei kyllä varmaankaan saa nipistettyä.

edit: juuh, noin 2100 ms kestää lukea ja noin 190 ms löytää paras sana. En löytänyt isompaa sanastoa, tietääkö kukaan muu? Saa olla vaikka englanniksi.

Aha, tietorakenteen lukemisessa olikin optimoimisen varaa.. Reallocki osoittautui hitaaksi, niin mallokoin kerralla 100000 alkiota sanoille ja oletan, ettei niitä ole enempää. :)

Tiedoston luku noin 350 ms ja parhaan sanan etsintä noin 170 ms. Koko ohjelma (freet yms.) alle 900 ms.

Näyttää hölmöltä kun on 3 omaa viestiä peräkkäin :P

Paras anagrammisana löytyy noin 58 sekunnissa.. oikeastaan itse sana löytyy jo alle 13 sekunnissa, mutta loppujen sanojen läpikäynti näköjään kestää. Tähän olisi helppo keksiä jotain optimointeja, mutta en voisi olla varma, että menevätkö ne heuristiikan puolelle.

Ajattelin tätä ongelmaa lähteä ratkomaan, mutta
miten käytännössä ratkomisen voisi toteuttaa
PHP:llä? Taroitan sitä, kun tulee se 30s tms
aikaraja vastaan jne...

Eli voiko tällaista PHP:n avulla ratkoa?

_{edit: Kirjoituksen oikeellisuutta korjailtu.}

reca kirjoitti:

Eli voiko tällaista PHP:n avulla ratkoa?

a) Voit poistaa aikarajan PHP:n asetuksista.
b) Voit ajaa php-ohjelman komentoriviltä, esimerkiksi php koodi.php.
Vastaus olisi löytynyt jo tuosta ylempääkin.

Metabolix kirjoitti:

b) Voit ajaa php-ohjelman komentoriviltä,
esimerkiksi php koodi.php.

Mitä käytännössä tapahtuu kun php ajetaan komentoriviltä?
Mitä se muuttaa verrattuna normaaliin? Miten komentoriviltä
ajettu php tulostaa tietoja?

_{edit: Sekoilua tagien kanssa.}

reca kirjoitti:

Mitä käytännössä tapahtuu kun php ajetaan komentoriviltä?
Mitä se muuttaa verrattuna normaaliin? Miten komentoriviltä
ajettu php tulostaa tietoja?

PHP:n tuloste tulee oletuksena komentoriville. Mitään isoja eroja "normaaliin" skriptien suorittamiseen ei ole (tietenkään esim. evästeitä ei oikein voi käyttää).

Kokeilemalla selviää:

$ echo "<?php echo 'terve'; ?>" > testi.php
$ php testi.php
terve

Minäkin ratkaisin tämän PHP:llä. Itse käytin ratkaisuna Roadsend PHP-kääntäjää, jolla voi siis luoda ihan binääreitäkin.

Metabolix kirjoitti:

reca kirjoitti:

Eli voiko tällaista PHP:n avulla ratkoa?

a) Voit poistaa aikarajan PHP:n asetuksista.
b) Voit ajaa php-ohjelman komentoriviltä, esimerkiksi php koodi.php.
Vastaus olisi löytynyt jo tuosta ylempääkin.

c) Voit ratkasta ongelman alle 30 sekunnissa. Oma Java ohjelma vääntää tuota 12-13 sekkaa.

Aikarajan voi poistaa myös PHP funktiolla set_time_limit(0).

Onko muut päätyny tulokseen 18 sanaa? Mulla nimittäin toi väittää että siitä löytys 18 sanaa, ja 2 merkkiset sanat on kyl karsittu pois. Putkapostiin kun ton sanan laitto ni se kyllä laski 17.

Matso: ettet olisi laskenut samaa sanaa kahdesti? Ainakin yksi ratkaisuista nimittäin sisältää yhden lyhyemmän sanan kaksi kertaa.

Sami kirjoitti:

Matso: ettet olisi laskenut samaa sanaa kahdesti? Ainakin yksi ratkaisuista nimittäin sisältää yhden lyhyemmän sanan kaksi kertaa.

Niin on vissiin sit käynyt.