Ładnie wygląda pierwszy odcinek w pokolorowanym HTML'u?
Pomóż przerobić bieżący!
Wdzięczność gwarantowana:-)

Dostrajanie rekurencji

Przy okazji zabaw z SVG (kiedyś pewnie o nich napiszę) wyniknął problem obliczania wartości funkcji trygonometrycznych. Tak, wiem, można to rozszerzeniami, ale równie dobrze można rozwiązać problem w czystym xslt. I jak się okazuje wyniki o zadowalającej dokładności uzyskamy szybciej (czas wykonania transformacji), niż korzystając z tak zwanych rozszerzeń.

Rozgrzewka

W bieżącym odcinku przedstawię proces dochodzenia do najbardziej optymalnego – moim zdaniem – rozwiązania. Na początek wygenerujemy plik z wartościami kątów, dla których będziemy obliczać sinus i cosinus.

07/00.js

var txml=new ActiveXObject('msxml2.domdocument.4.0');
txml.appendChild(txml.createProcessingInstruction('xml','version="1.0" encoding="UTF-8"'))
with(txml.appendChild(txml.createElement('R'))){
    for(var k=-1800;k<=1800;k++){
        appendChild(txml.createElement('I')).setAttribute('v',k/10)
    };
};
txml.save('t.xml');

Jak widać tworzymy plik z kolejnymi wartościami kątów z przedziału <-180,180> stopni co 0.1º. Daje nam to 3 600 węzłów, co jest ilością wystarczającą do badania szybkości działania kolejnych wersji transformacji. Nad rym jak sprowadzić kąty spoza powyższego zakresu do niego – szanując inteligencję czytelników – pisał nie będę.

Przed rozpoczęciem zgłębiania treści należy sobie koniecznie przypomnieć (lub przyswoić) zagadnienie rozwijania funkcji w szereg. Jak to działa dla sinusa i cosinusa można wydedukować z dwóch artykułów w Wikipedii:

Pierwsze podejście

Jak widać we wzorach przedstawionych w Wikipedii aby obliczyć wartość sinusa/cosinusa należy dodać do siebie nieskończoną liczbę mocno regularnych wyrażeń. Dla sinusa należy na przemian dodać/odjąć nieparzyste potęgi wartości kąta podzielone przez silnię wykładnika. Dla cosinusa to samo ale, z elementami parzystymi. Jako, że szeregi są malejąc i zbieżne możemy przyjąć, że istnieje n-ty wyraz ciągu o wartości mniejszej niż wymagana dokładność obliczanej wartości – i na takim wyrazie będziemy kończyć obliczenia.

07/01.xsl

Policzyć szereg do pewnego momentu? Cóż prostszego! Najpierw dwa szablony liczące silnię i n-tą potęgę zmiennej:

  <xsl:template name="XpowN">
    <xsl:param name="x"/>
    <xsl:param name="n"/>
    <xsl:param name="i" select="1"/>
    <xsl:param name="r" select="1"/>
    <xsl:choose>
      <xsl:when test="$i <= $n">
        <xsl:call-template name="XpowN">
          <xsl:with-param name="x" select="$x"/>
          <xsl:with-param name="n" select="$n"/>
          <xsl:with-param name="i" select="$i + 1"/>
          <xsl:with-param name="r" select="$r * $x"/>
        </xsl:call-template>
      </xsl:when>
      <xsl:otherwise>
        <xsl:value-of select="$r"/>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

  <xsl:template name="Nfact">
    <xsl:param name="n"/>
    <xsl:param name="i" select="1"/>
    <xsl:param name="r" select="1"/>
    <xsl:choose>
      <xsl:when test="$i < $n">
        <xsl:call-template name="Nfact">
          <xsl:with-param name="n" select="$n"/>
          <xsl:with-param name="i" select="$i + 1"/>
          <xsl:with-param name="r" select="$r * ($i + 1)"/>
        </xsl:call-template>
      </xsl:when>
      <xsl:otherwise>
        <xsl:value-of select="$r"/>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

Następnie szablon, który będzie sumował wyrazy do osiągnięcia zakładanej dokładności:

  <xsl:template name="sin">
    <xsl:param name="x"/>
    <xsl:param name="i" select="0"/>
    <xsl:param name="r" select="0"/>
    <xsl:choose>
      <xsl:when test="$i mod 2 = 0">
        <xsl:call-template name="sin">
          <xsl:with-param name="x" select="$x"/>
          <xsl:with-param name="i" select="$i + 1"/>
          <xsl:with-param name="r" select="$r"/>
        </xsl:call-template>
      </xsl:when>
      <xsl:otherwise>
        <xsl:variable name="XpowI">
          <xsl:call-template name="XpowN">
            <xsl:with-param name="x" select="$x"/>
            <xsl:with-param name="n" select="$i"/>
          </xsl:call-template>
        </xsl:variable>
        <xsl:variable name="Ifact">
          <xsl:call-template name="Nfact">
            <xsl:with-param name="n" select="$i"/>
          </xsl:call-template>
        </xsl:variable>
        <xsl:variable name="dr">
          <xsl:choose>
            <xsl:when test="$i mod 4 = 1">
              <xsl:value-of select="$XpowI div $Ifact"/>
            </xsl:when>
            <xsl:otherwise>
              <xsl:value-of select="$XpowI div $Ifact * -1"/>
            </xsl:otherwise>
          </xsl:choose>
        </xsl:variable>
        <xsl:choose>
          <xsl:when test="translate($dr,'-','') > $prc">
            <xsl:call-template name="sin">
              <xsl:with-param name="x" select="$x"/>
              <xsl:with-param name="i" select="$i + 1"/>
              <xsl:with-param name="r" select="$r + $dr"/>
            </xsl:call-template>
          </xsl:when>
          <xsl:otherwise>
            <xsl:value-of select="$r + $dr"/>
          </xsl:otherwise>
        </xsl:choose>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

Szablon dla cosinusa jest identyczny z dokładnością do wybierania nieparzystych elementów szeregu (test="$i mod 2 = 0") oraz ustalania znaku (test="$i mod 4 = 1").

Pozostaje do napisania kawałek xsl'a wywołującego szablony liczące funkcje trygonometryczne:

  <xsl:template match="/R">
    <xsl:copy>
      <xsl:apply-templates/>
    </xsl:copy>
  </xsl:template>
  <xsl:template match="/*/I">
    <xsl:copy>
      <xsl:copy-of select="@*"/>
      <xsl:attribute name="sin">
        <xsl:call-template name="sin">
          <xsl:with-param name="x" select="@v * 2 * $PI div 360"/>
        </xsl:call-template>
      </xsl:attribute>
      <xsl:attribute name="cos">
        <xsl:call-template name="cos">
          <xsl:with-param name="x" select="@v * 2 * $PI div 360"/>
        </xsl:call-template>
      </xsl:attribute>
    </xsl:copy>
  </xsl:template>

Na początku transformacji dodajemy dwa parametry:

  <xsl:param name="PI"   select="3.1415926535897932384626433832795"/>

Wartość PI z dokładnością jaką daje windowsowy kalkulator.

<xsl:param name="prc" select="0.0000000000000000000000000000001"/>

Wymaganą dokładność – którą ustalimy chwilowo na dokładność PI (jest ona co prawda nierealizowalna – dlaczego? - ale tym się na razie nie przejmujemy).

Pozostał nam do napisania krótki skrypt wykonujący transformację i mierzący czas jej wykonania:

07/01.js

var txml=new ActiveXObject('msxml2.domdocument.4.0');
var txsl=new ActiveXObject('msxml2.domdocument.4.0');
txml.load('t.xml');
txsl.load('01.xsl');
t=(new Date()).getTime();
txml.transformNodeToObject(txsl,txml);
WScript.Echo((new Date()).getTime()-t);
txml.save('01.xml');

Uruchamiamy (z linii poleceń):

cscript 01.js

I zapamiętujemy czas. Z jednej strony chwilę to trwało, z drugiej policzyliśmy w tym czasie 7 200 wartości.

Szybciej!

Pierwsze na co powinniśmy zwrócić uwagę przy tunigowaniu transformacji, to wielokrotne wyliczanie kolejnych potęg i silni.

Przenosimy więc ich liczenie bezpośrednio do szablonów sumujących elementy szeregów, a wyliczone wartości przekazywać będziemy dwoma dodatkowymi parametrami. Zauważmy także “puste przebiegi” dla parzystych i przy sinusie (i nieparzystych przy cosinusie), iterować będziemy więc co 2 a nie co 1.

07/02.xsl

Zmodyfikowany szablon dla sinusa będzie wyglądał następująco:

  <xsl:template name="sin">
    <xsl:param name="x"/>
    <xsl:param name="i" select="1"/>
    <xsl:param name="r" select="0"/>
    <xsl:param name="XpowI" select="$x"/>
    <xsl:param name="Ifact" select="1"/>
    <xsl:variable name="dr">
      <xsl:choose>
        <xsl:when test="$i mod 4 = 1">
          <xsl:value-of select="$XpowI div $Ifact"/>
        </xsl:when>
        <xsl:otherwise>
          <xsl:value-of select="$XpowI div $Ifact * -1"/>
        </xsl:otherwise>
      </xsl:choose>
    </xsl:variable>
    <xsl:choose>
      <xsl:when test="translate($dr,'-','') > $prc">
        <xsl:call-template name="sin">
          <xsl:with-param name="x" select="$x"/>
          <xsl:with-param name="i" select="$i + 2"/>
          <xsl:with-param name="r" select="$r + $dr"/>
          <xsl:with-param name="XpowI" select="$XpowI * $x * $x"/>
          <xsl:with-param name="Ifact" select="$Ifact * ($i + 1) * ($i + 2)"/>
        </xsl:call-template>
      </xsl:when>
      <xsl:otherwise>
        <xsl:value-of select="$r + $dr"/>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

Dla cosinusa analogicznie, z różnicami jak w poprzednim przykładzie. Uruchamiamy:

cscript 02.js

I zauważamy, że policzyło o wiele szybciej niż poprzednia transformacja (u mnie około 4-ech razy). Sama zaś transformacja zmalała o ponad 2 kB.

W poszukiwaniu straconego czasu

Ale to oczywiście nie wszystko, co z transformacji możemy wycisnąć. Sprawdźmy do których z kolei wyrazów szeregu dochodzi nasza rekurencja przy obliczaniu wartości. Zmodyfikujemy w tym celu człony zakończenia rekurencji:

07/03.xsl

      <xsl:otherwise>
        <xsl:value-of select="$i"/>
        <xsl:text>:</xsl:text>
        <xsl:value-of select="$r + $dr"/>
      </xsl:otherwise>
    </xsl:choose>

oraz sposób wpisywania wyników:

  <xsl:template match="/*/I">
    <xsl:copy>
      <xsl:copy-of select="@*"/>
      <xsl:variable name="sin">
        <xsl:call-template name="sin">
          <xsl:with-param name="x" select="@v * 2 * $PI div 360"/>
        </xsl:call-template>
      </xsl:variable>
      <xsl:attribute name="k">
        <xsl:value-of select="substring-before($sin,':')"/>
      </xsl:attribute>
      <xsl:attribute name="sin">
        <xsl:value-of select="substring-after($sin,':')"/>
      </xsl:attribute>
      <xsl:variable name="cos">
        <xsl:call-template name="cos">
          <xsl:with-param name="x" select="@v * 2 * $PI div 360"/>
        </xsl:call-template>
      </xsl:variable>
      <xsl:attribute name="i">
        <xsl:value-of select="substring-before($cos,':')"/>
      </xsl:attribute>
      <xsl:attribute name="cos">
        <xsl:value-of select="substring-after($cos,':')"/>
      </xsl:attribute>
    </xsl:copy>
  </xsl:template>

Uruchamiamy:

cscript 03.js

I sprawdzamy liczbę dodanych elementów szeregu (a właściwie wykładnik ostatniego). Na chłopski rozum (poparty windowsowym kalkulatorem) dokładność jaką widać w wynikach ma się nijak do liczonych elementów szeregów! Skracamy więc (choćby metodą prób i błędów) wymaganą dokładność do momentu zauważenia różnicy w wynikach. Okaże się, że 14 miejsc po przecinku to max jaki możemy uzyskać. I nie wydaje mi się, że w codziennej praktyce więszka dokładność będzie komuś potrzebna.

Dokładności PI nie ruszamy – można poeksperymentować w celu przekonania się, że nie wpływa ona na prędkość wykonania transformacji a na doładność owszem (pojawia się w wysokich potęgach w kolejnych elementach szeregu).

Obliczanie przyspieszyliśmy jeszcze o kilkadziesiąt procent.

Ale czy to na pewno wszystko?

Zaglądając w środek pliku zauważamy, że zawsze liczone są trzy (dla sinusa) i cztery (dla cosinusa) elementy szeregu, a prawie zawsze cztery i cztery. Wpiszmy więc odpowiednie wartości jako początkowe oraz wystawmy - dla porządku – wywołanie rekurencji do osobnych szablonów:

07/04.xsl

  <xsl:template name="sin">
    <xsl:param name="x"/>
    <xsl:variable name="xPow2" select="$x * $x"/>
    <xsl:variable name="xPow4" select="$xPow2 * $xPow2 "/>
    <xsl:variable name="xPow6" select="$xPow4 * $xPow2 "/>
    <xsl:call-template name="goSin">
      <xsl:with-param name="x" select="$x"/>
      <xsl:with-param name="i" select="9"/>
      <xsl:with-param name="r" select="$x - $x * $xPow2 div 6 + $x * $xPow4 div 120 - $x * $xPow6 div 5040"/>
      <xsl:with-param name="XpowI" select="$xPow4 * $xPow4 * $x"/>
      <xsl:with-param name="Ifact" select="362880"/>
    </xsl:call-template>
  </xsl:template>

  <xsl:template name="goSin">
    <xsl:param name="x"/>
    <xsl:param name="i" select="0"/>
    <xsl:param name="r" select="0"/>
    <xsl:param name="XpowI" select="1"/>
    <xsl:param name="Ifact" select="1"/>
    ...

Dla cosinusa analogicznie z potrzebnymi poprawkami.

Uruchamiamy:

cscript 04.js

Nie wiem jak u Was, ale u mnie obliczenia trwały 10 razy krócej niż te z pierwszego podejścia!

Czy można jeszcze szybciej? Pewnie można – ale to już raczej nie jest kwestia strojenia rekurencji. Można by pójść w stronę redukcji kątów do zakresu -90° – 90°. Ale nie jestem pewien czy da to zamierzony rezultat.

Bardziej istotne jest – moim zdaniem – ustalenie rozsądnej wymaganej dokładności. Przy rysowaniu na ekranie (od tego się wszystko zaczęło) dokładność 0.001 wystarczy, a policzy się jeszcze szybciej.

Ładnie wygląda pierwszy odcinek w pokolorowanym HTML'u?
Pomóż przerobić bieżący!
Wdzięczność gwarantowana:-)
UWAGA: To jest robocza wersja dokumentu i jego załączników. Udostępniona zasadniczo w celu testowania oraz zgłaszania uwag i spostrzeżeń.

Zasady korzystania:

  1. Do celów edukacyjnych, niezwiązanych z wykonywaną pracą zawodową (na przykład uczniowie, studenci i inni hobbyści nie zarabiający pieniędzy szeroko rozumianą działalnością informatyczną) – na własne potrzeby bezpłatnie i bez ograniczeń, ale w przypadku osiągania dochodów prośba o rozważenie skorzystania zasad zawartych w punkcie 2a.
  2. Do celów edukacyjnych związanych bezpośrednio z wykonywaną pracą/sposobem osiągania przychodów (na przykład programiści i koderzy) – na własne potrzeby (w tym wykonywania pracy zawodowej/osiągania przychodów) bez ograniczeń po spełnieniu następujących wymagań:
    1. Wsparcie kwotą jaką korzystający uzna za słuszną:
      Fundacja SERCE – Europejskie Centrum Przyjaźni Dziecięcej
      Organizacja Pożytku Publicznego
      58-100 Świdnica, ul. Kościelna 15
      numer konta: 42 1020 5138 0000 9102 0067 8961
      tytuł wpłaty: darowizna rzecz organizacji pożytku publicznego
      Będzie mi miło jeżeli dostanę na maila (skompresowany:-) skan/zrzut z ekranu z informacją o wpłacie.
    2. W przypadku bezpośredniego korzystania z udostępnionego kodu (w tym zmodyfikowanego, bez ingerencji w istotę rozwiązań) proszę o zamieszczenie w kodzie informacji o kursie z jego adresem: http://szomiz.republika.pl/.
    3. Przy wysyłaniu do przeglądarki wyników działania kodu wykonanego na serwerze zamieszczenie informacji o korzystaniu z kursu w tagu META.
    4. Poinformowanie mnie (jeżeli nie zabraniają tego zobowiązania wobec osób trzecich) o projektach i rozwiązaniach w których kod udostępniony w kursie został wykorzystany.
  3. Do wszelkich innych celów, zwłaszcza związanych z wykonywaną/prowadzoną działalnością edukacyjna, szkoleniową, wydawniczą lub publikacyjną – wykorzystanie możliwe wyłącznie po indywidualnym określeniu zasad i warunków pomiędzy autorem kursu a korzystającym.
  4. Osoby, wnoszące swój wkład w treści zawarte w kursie udzielają autorowi kursu nieodpłatnej licencji umożliwiającej co wykorzystanie i udostępnienie co najmniej na określonych tutaj zasadach.
  5. Oczywiście nie biorę żadnej odpowiedzialności za rezultaty działania kodu i jego modyfikacji :-)
© Sławomir Zimosz - wszelkie prawa zastrzeżone.
Przedruk, publikacja części lub całości bez wiedzy i zgody autora zabronione.
Kontakt: szomiz@poczta.onet.pl