project/oslik/oslik/index.shtml

   1 <HTML><HEAD><TITLE>Úloha oslíka</TITLE></HEAD>
   2 <BODY>
   3 <H1 ALIGN=CENTER>Oslík:</H1>
   4
   5 <HR>
   6 <A NAME="soft"><H2>Pou¾itý software:</H2></A>
   7 <P>Jako interpretr prologu jsem pou¾il
   8 <STRONG><A HREF="http://www.swi.psy.uva.nl/usr/jan/SWI-Prolog.html">SWI-Prolog</A></STRONG>,
   9 který je dodáván s vcelku pøijatelnými licenèními podmínkami
  10 (a zdrojové kódy jsou souèástí). Pøikládám <A HREF="pl-3.1.2.diff">krátký patch</A>, aby
  11 <STRONG><A HREF="http://www.swi.psy.uva.nl/usr/jan/SWI-Prolog.html">SWI-Prolog</A></STRONG>
  12 nepoèítal percentuální podíly funkcí pøi profilování a vypnutí automatického
  13 <I>garbage collector</I>u.</P><UL>
  14 <LI>Profiling se mi hroutil díky nezablokování v¹ech signálù pøi volání <CODE>sigblock()</CODE>,
  15 ale mù¾e to být jen problém mé instalace
  16 <LI><I>Garbage collector</I> se spou¹tìl na mùj vkus pøíli¹ èasto, jeho automatické spou¹tìní
  17 jsem tedy vypnul a volám jej explicitnì z Prologu
  18 </UL>
  19 <P>Aèkoliv by oba programy (obì <STRONG>Prolog</STRONG> a jedna <STRONG>C</STRONG> verze)
  20 mìly být spustitelné na jakékoliv platformì, uvádím testované/vývojové prostøedí:</P><UL>
  21 <LI><A HREF="http://www.linux.org/">GNU/Linux</A>, èásteènì <A HREF="http://www.redhat.com/">RedHat 5.0</A>
  22 systém,
  23 <A HREF="http://www.kernel.org/pub/linux/kernel/v2.1/linux-2.1.132.tar.bz2">kernel Linus-2.1.132</A>,
  24 glibc-2.0.7-980507, gcc version pgcc-2.91.57 19980901 (egcs-1.1 release),
  25 GNU Make version 3.76.1, GNU textutils 1.22.
  26 <LI><A HREF="http://www.swi.psy.uva.nl/usr/jan/SWI-Prolog.html">SWI-Prolog</A> verze 3.1.2.
  27 </UL>
  28 <P>Díval jsem se také na
  29 <A HREF="http://www.binnetcorp.com/BinProlog/">BinProlog</A>, ale zdrojové
  30 kódy nebyly vùbec k dispozici, a tudí¾ nepøipadl v úvahu.</P>
  31
  32 <HR>
  33 <H2>Øe¹ení úlohy:</H2>
  34 <P>Zadáním bylo pøevést hrací plochu ze vstupního tvaru:</P>
  35 <PRE>
  36   /-------\
  37   | {}{}# |
  38   | AB^#+ |
  39   | CDv#+ |
  40   | {}{}# |
  41   \-------/
  42 </PRE>
  43 <P>postupným pøesouváním kostek do tvaru:</P>
  44 <PRE>
  45   /-------\
  46   | ????? |
  47   | ???AB |
  48   | ???CD |
  49   | ????? |
  50   \-------/
  51 </PRE>
  52 <P>kde znaky &quot;<STRONG>?</STRONG>&quot; samozøejmì pøedstavují políèka,
  53 na kterých nezále¾í. Pro popis jednotlivých znaku bude lep¹í následující
  54 legenda:</P>
  55 <TABLE ALIGN=CENTER BORDER=1>
  56 <TR><TD ALIGN=LEFT VALIGN=BOTTOM><FONT COLOR="BLUE"><CODE>AB<BR>CD</CODE    ></FONT> - 2x2</TD>
  57     <TD ALIGN=LEFT VALIGN=BOTTOM><FONT COLOR="BLUE"><CODE>{}</CODE          ></FONT> - 2x1</TD>
  58     <TD ALIGN=LEFT VALIGN=BOTTOM><FONT COLOR="BLUE"><CODE>^<BR>v</CODE      ></FONT> - 1x2</TD>
  59     <TD ALIGN=LEFT VALIGN=BOTTOM><FONT COLOR="BLUE"><CODE>#</CODE           ></FONT> - 1x1</TD>
  60     <TD ALIGN=LEFT VALIGN=BOTTOM>-volno-<FONT COLOR="BLUE"><BR><CODE>+</CODE></FONT> - 1x1</TD>
  61 </TABLE>
  62 <P>Postupné stavy hrací plochy pøi jednotlivých krocích minimálního (nejkrat¹ího)
  63 øe¹ení jsou v souboru &quot;<A HREF="minsol.txt">minsol.txt</A>&quot;. Rozbor
  64 øe¹ení úlohy je sumarizován zde:</P>
  65 <TABLE ALIGN=CENTER BORDER=1>
  66 <TR><TD>Velikost stavového prostoru       <TD><STRONG>25955</STRONG></TD></TR>
  67 <TR><TD>Poèet rùzných øe¹ení              <TD><STRONG>482 (+sym.)</STRONG></TD></TR>
  68 <TR><TD>Poèet tahù nejkrat¹ího øe¹ení     <TD><STRONG>116</STRONG></TD></TR>
  69 <TR><TD>Poèet rùzných nejkrat¹ích øe¹ení  <TD><STRONG>1 (+sym.)</STRONG></TD></TR>
  70 <TR><TD>Poèet tahù nejdel¹ího øe¹ení      <TD><STRONG>158</STRONG></TD></TR>
  71 <TR><TD>Poèet rùzných nejdel¹ích øe¹ení   <TD><STRONG>7 (+sym.)</STRONG></TD></TR>
  72 <TR><TD>Maximální poèet tahù bez opakování<TD><STRONG>167</STRONG></TD></TR>
  73 </TABLE>
  74 <P>V¹echny tyto výsledky lze získat ze v¹ech verzí
  75  (<STRONG>Prolog</STRONG> <A HREF="oslik-assert.pl">assert</A>
  76 / <STRONG>Prolog</STRONG> <A HREF="oslik-hash.pl"  >hash</A  >
  77 / <A HREF="oslik.c">C</A>),
  78 z rychlostních dùvodù ov¹em doporuèuji pou¾ít <STRONG>C</STRONG> verzi. Pro nìkteré výsledky je
  79 tøeba zapnout ladící výpisy (v obou verzích se zapínají rùznì a nezdokumentovanì).</P>
  80 <P>Poznámka &quot;<STRONG>(+sym.)</STRONG>&quot; znamená, ¾e takových øe¹ení
  81 je ve skuteènosti dvojnásobný poèet ne¾ je uvedeno, ale tato zbylá øe¹ení
  82 jsou symetrická dle X-ové osy. To vyplývá ze symetriènosti zadání dle osy X
  83 a tomu, ¾e v¹echny povolené tahy ¾ádným zpùsobem neupøednostòují èi neomezují
  84 smìr pohybu.</P>
  85
  86 <HR>
  87 <A NAME="cost"><H2>Nároènost øe¹ení:</H2></A>
  88 <TABLE ALIGN=CENTER BORDER=1>
  89 <TR><TD>kategorie <STRONG>\</STRONG> verze<TD><A HREF="oslik-assert.pl">Prolog assert</A><TD><A HREF="oslik-hash.pl">Prolog hash</A><TD><A HREF="oslik.c">C</A></TD></TR>
  90 <TR><TD>doba bìhu bez výstupu<TD><STRONG>1m:55s=115s</STRONG><TD><STRONG>4m:27s=267s</STRONG><TD><STRONG>0m:0.22s=~1s</STRONG></TD></TR>
  91 <TR><TD>doba bìhu s výstupem<TD><STRONG>4m:29s=269s</STRONG><TD><STRONG>6m:19s=379s</STRONG><TD><STRONG>0m:1.90s=~2s</STRONG></TD></TR>
  92 <TR><TD>pamì»ová nároènost<TD><STRONG>cca 50MB</STRONG><TD><STRONG>cca 150MB (!)</STRONG><TD><STRONG>cca 1MB</STRONG></TD></TR>
  93 <CAPTION ALIGN=BOTTOM>Konfigurace:
  94 <A HREF="http://www.amd.com/">AMD</A>-<A HREF="http://www.amd.com/products/cpg/k623d/">K6-2</A> 350MHz,
  95 256MB SDRAM, 100MHz FSB</CAPTION>
  96 </TABLE>
  97 <P>V <STRONG>Prologu assert</STRONG> se vyu¾ívá funkcí <STRONG>assert</STRONG> a <STRONG>flag</STRONG>.
  98 Toto øe¹ení je rychlej¹í i pøehlednìj¹í ne¾ následující, ale neodpovídá duchu Prologovského programování.</P>
  99 <P>V <STRONG>Prologu hash</STRONG> pou¾ívám hashování s velikostí tabulky 150 polo¾ek (deklarace
 100 &quot;<STRONG>geths(150).</STRONG>&quot;, èím¾ se sna¾ím
 101 pøevést stavový prostor do ètvercového tvaru, aby Prolog lineárnì procházel
 102 hash index i hash link-list celkovì minimální èas.</P>
 103 <P><U>Varování:</U> Pøi standardním spu¹tìní (pøes SWI-Prolog) Oslíka budou obì Prologovské verze dumpovat
 104 velké mno¾ství ladících informací. Pro &quot;production&quot; pou¾ití slou¾í <I>bash</I> skript
 105 &quot;<A HREF="do">do</A>&quot;, který tyto ladící informace ve zdrojovém kódu zru¹í a spustí automaticky prolog.
 106 Pøi spu¹tìní bez parametrù vypí¹e tento skript help. Nadefinování prázdného termu jako funkce pro ladící
 107 výpis mìlo bohu¾el drtivý dopad na rychlost interpretace.</P>
 108 <P>Obì Prologovské verze víceménì neobsahují ¾ádné komentáøe, doporuèuji si pøípadnì k nim otevøít verzi
 109 v <A HREF="oslik.c">C</A>, kde je v¹e zøejmé.</P>
 110
 111 <HR>
 112 <H2>Prùbìh vývoje:</H2>
 113 <H3>Velikost výpoètu</H3>
 114 Pùvodnì jsem byl varován, ¾e výpoèet bude trvat pøíli¹ dlouho
 115 a pravdìpodobnì nedobìhne. Èekal jsem tedy poèet stavù prostoru minimálnì v øádu milonù, v hor¹ím pøípadì miliard.
 116 Nynìj¹í &quot;<A HREF="oslik.c">oslik.c</A>&quot;
 117 se pùvodnì jmenoval &quot;stategen.c&quot; a mìl opravdu slou¾it pouze k pøedgenerování v¹ech mo¾ných stavù a jejich
 118 oèíslování (mìlo by se vejít do 32-bitù, jinak by to stejnì asi nemìlo smysl prohlédávat bez
 119 <A HREF="http://www.distributed.net/">distributed.net</A> for my pleasure). Byl jsem ¹okován, kdy¾ program ihned dobìhl
 120 (tj. i mì) s celkovým poètem 25955 stavù. Proto je také kód pro sledování prùbìhu výpoètu
 121 (makro &quot;<CODE>STSTEP</CODE>&quot;)
 122 nyní jaksi nadbyteèný a pùsobí spí¹e humorným dojmem. Celý kód jsem se také sna¾il hned napoprvé napsat co mo¾ná nejrychlej¹í.
 123 Pro mno¾inu stavù mám konstantní hashovací pole, seznam doposud nezpracovaných stavù i zpìtné reference pro vypisování
 124 výsledku (tj. z kterého stavu jsme se do aktuálního dostali).
 125 <H3>Struktura stavu</H3>
 126 Stav se ukládá jako 20-ti (5x4) znakové pole, neukládám
 127 tedy polohu jednotlivých velkých kostek, ale naopak mám pro ka¾dé políèko hrací plochu uveden druh/èást kostky na nìm le¾ící
 128 (&quot;oslík&quot; je tedy ze 4 èástí a tyto èásti mùsí v ka¾dém korektním stavu le¾et ve správném poøadí u sebe).
 129 Výchozí stav je tedy vyjádøen øetìzcem &quot;<CODE>{}{}#AB^#+CDv#+{}{}#</CODE>&quot;.
 130 <H3>Struktura mno¾iny stavù</H3>
 131 Ústøedním problémem Oslíka
 132 je udr¾ování mno¾iny stavù, které jsme ji¾ prohledali èi jsme je ji¾ objevili, ale je¹tì nám zbývá je zpracovat.
 133 V &quot;<A HREF="oslik-hash.pl">oslik-hash.pl</A>&quot; verzi (první v Prologu)
 134 to byl úplnì nejdøíve lineární seznam, co¾ ov¹em bylo èasovì neúnosné. Profiler mi potvrdil dùvodné podezøení
 135 na kvadratickou èasovou slo¾itost programu díky tomuto seznamu, musel jsem ho tedy vymìnit. Pro jednoduchost implementace
 136 jsem zvolil hash tabulku jako v <A HREF="oslik.c">C verzi</A>, kterou jsem ov¹em byl nucen implementovat jako lineární seznam
 137 jenotlivých políèek a obsahem ka¾dého
 138 prvku seznamu byl vnoøený seznam v¹ech stavù, které mají stejnou hash hodnotu, a patøí tedy k sobì. Bohu¾el v takovémto
 139 uspoøádání neplatí obecné pravidlo hashù, ¾e èím vìt¹í, tím rychlej¹í (samozøejmì a¾ na úplnì extrémní pøípady díky
 140 inicializaci a efektu memory cache). Pøi pøíli¹ velké hash tabulce by bylo bohu¾el pøíli¹ èasovì nároèné dotraverzovat
 141 k pøípadnému prvku na konci hash tabulky (a tedy i na konci hash seznamu). Vzhledem k tomu, ¾e jsem ji¾
 142 z <A HREF="oslik.c">C verze</A> znal velikost úlohy, nastavil jsem velikost hash tabulky tak, aby
 143 byla pøibli¾nì stejná jako prùmìrný poèet prvkù v jednom hash políèku. Ve skuteènosti tedy vytvoøí taková tabulka ètverec
 144 a velikost hash tabulky (tj. jeho jedna strana) by mìla být odmocninou z celkového poètu prvkù. Zvolil jsem 150 prvkù
 145 (ideálnì pro 22500 stavù).
 146 <H3>Konverze stavu</H3>
 147 Vyjádøení stavu zùstalo jako 20-ti znakový øetìzec (jako v <A HREF="oslik.c">C verzi</A>),
 148 je-li tøeba, doèasnì jej konvertuji do seznamu a nazpìt (predikát &quot;string_to_list&quot;). Øetìzec by mìl být
 149 pamì»ovì efektivnìj¹í pro ukládání do mno¾iny stavù, jemné (v <STRONG>assert</STRONG> verzi dle profileru bohu¾el hlavní)
 150 zpomalení díky dvojitým konverzím je pravdìpodobnì levnìj¹í ne¾ zvý¹ené pamì»ové nároky (i kdy¾ jsem to reálnì nezkou¹el).
 151 <H3>Pøepsání do Prologu</H3>
 152 Co se týèe celkové implementace, pøiznám se, ¾e jsem víceménì pøepsal tu
 153 <A HREF="oslik.c">C verzi</A> s tím, ¾e jsem nìkteré cykly pøepsal na rekurzi. Hlavní kontrolní dvourozmìrná
 154 smyèka pro kontrolu korektnosti pohybu a smyèka pro pøesun kostek zùstaly implementovány pøes &quot;forall&quot;, nebo»
 155 se vyu¾ívá èíselných hodnot øídících promìnných pro adresaci polí stavu. Jména promìnných v predikátu &quot;chkpos&quot;
 156 zùstala zachována z <A HREF="oslik.c">C verze</A>, lze ji tedy pou¾ít jako pomocný text, nebo» je IMHO mnohem
 157 prùhlednìj¹í a ilustrativnìj¹í.
 158 <H3>Verze s assert/flag</H3>
 159 Pøepsání pøedchozí prologovské verze za vyu¾ití
 160 &quot;assert&quot; a &quot;flag&quot; pro uchování mno¾iny stavù místo pøedchozí hash table emulované dvojitým seznamem
 161 je v &quot;<A HREF="oslik-assert.pl">oslik-assert.pl</A>&quot;.
 162 Scope &quot;assert&quot;-u i &quot;flag&quot;-u je globální a odpadlo tedy velké mno¾ství nechutného tahání hash tabulky
 163 s sebou parametrem v¹ech funkcí a¾ dovnitø (jednou jako vstupní, podruhé jako výstupní) jako
 164 <A HREF="http://dm.cobaltmicro.com/~ninka/kotypic/koty.html">koèka ko»ata</A>. Výsledkem bylo kromì velkého zpøehlednìní
 165 a zjednodu¹ení kódu také výrazné zlep¹ení rychlosti i pamì»ové nároènosti (více viz <A HREF="#cost">nároènost øe¹ení</A>).
 166 Urèitì bych to byl býval psal tímto zpùsobem rovnou, bohu¾el jsem se o &quot;assert&quot;-u a &quot;flag&quot;-u dozvìdìl
 167 a¾ po napsání pøedchozí verze.
 168 <H3>Atomizace</H3>
 169 <P>V Prologu jsem se pùvodnì potýkal s problémem nefungující unifikace nezatomizovaných øetìzcù, ale poté, co jsem objevil
 170 predikát &quot;string_to_atom&quot; ji¾ SWI Prolog unifikoval jak mìl.</P>
 171
 172 <HR>
 173 <H2>Dodané soubory:</H2>
 174 <TABLE ALIGN=CENTER BORDER=1>
 175 <TR><TD><A HREF="oslik.zip"      >oslik.zip</A      ><TD>celý package (vèetnì Makefile-u apod.)</TD></TR>
 176 <TR><TD><A HREF="oslik-assert.pl">oslik-assert.pl</A><TD>oslík v SWI-Prologu, <STRONG>assert</STRONG> verze</TD></TR>
 177 <TR><TD><A HREF="oslik-hash.pl"  >oslik-hash.pl</A  ><TD>oslík v SWI-Prologu, <STRONG>hash</STRONG> verze</TD></TR>
 178 <TR><TD><A HREF="do"             >do</A             ><TD><I>bash</I> skript pro spu¹tìní pøedchozích dvou programù</TD></TR>
 179 <TR><TD><A HREF="oslik.c"        >oslik.c</A        ><TD>oslík v ANSI C (+<A HREF="http://www.bsd.org/">BSD</A> extenze)</TD></TR>
 180 <TR><TD><A HREF="minsol.txt"     >minsol.txt</A     ><TD>minimální øe¹ení (CR/LF)</TD></TR>
 181 <TR><TD><A HREF="pl-3.1.2.diff"  >pl-3.1.2.diff</A  ><TD>patch pro SWI-Prolog 3.1.2 (viz <A HREF="#soft">vý¹e</A>)</TD></TR>
 182 </TABLE>
 183
 184 <HR>
 185 <H2>Autor:</H2>
 186 <TABLE ALIGN=CENTER BORDER=1>
 187 <TR><TD>Datum:<TD ALIGN=CENTER>30. 12. 1998</TD></TR>
 188 <TR><TD>Autor:<TD ALIGN=CENTER>Jan Kratochvíl</TD></TR>
 189 <TR><TD>Kontakt:<TD ALIGN=CENTER>e-mail <A HREF="mailto:short@ucw.cz">short@ucw.cz</A></TD></TR>
 190 <TR><TD>Licence:<TD ALIGN=CENTER>Public domain</TD></TR>
 191 </TABLE>
 192 <P>Tento software je poskytnut bez jakýchkoliv záruk a autor nenese ¾ádnou zodpovìdnost
 193 za ¹kody zpùsobené jeho pou¾íváním. Autor se také vzdává jakýchkoliv práv, ale i závazkù,
 194 dle smyslu <I>public domain</I> licence.</P>
 195
 196 </BODY></HTML>