Fibonacci, czyli wprawki (część 1: implementacje)

Niniejszy tekst opiera się na pomyśle wygenerowanym w moim sympatycznym korpo. Główne cele powstania tekstu to:

  • Wprowadzenie do podstaw testowania
  • Pokazanie, że dane zagadnienie można rozwiązać na różne sposoby
  • Pokazanie roli benchmarków w procesie powstawania kodu i oceny rozwiązań. Jak wybierając różne implementacje możemy wpływać na wydajność rozwiązania
  • I z zupełnie innej bajki. Pokazanie przy okazji implementacji serwera NIO, czyli czegoś co jest dzisiaj gorącym hitem.

Dziękuję Dorocie (sąsiadka w open space), która bezpośrednio mnie zainspirowała do powstania tego tekstu. Bez Ciebie Dorota, by nie powstał.

Pierwsza część wpisu to (jak mawiał klasyk) oczywista oczywistość. Implementacje algorytmu generowania liczb Fibonacciego są ogólnie znane, niemniej przytoczę je tutaj, by w dalszych częściach odnieść się do konkretnych implementacji.

Podstawą ćwiczenia było TDD, ale zaczynamy od modelu:

package robert.trening;

public interface Fibonacci {

  long compute(int n);

}

I założone testy, typowy pojedynczy test jednostkowy

package robert.trening;

import org.junit.Before;
import org.junit.Rule;
import org.junit.Test;
import org.junit.rules.ExpectedException;

import static org.junit.Assert.assertEquals;

public class FibonacciStreamImpTest {

  FibonacciStreamImp fibonacci;

  @Before
  public void init() {
    fibonacci = new FibonacciStreamImp();
  }

  @Test
  public void computePossitiveCase() {
    assertEquals(514229L, fibonacci.compute(29));
  }

  @Test(expected = IllegalArgumentException.class)
  public void computeNegativeCaseExpectedAttribute() {
    fibonacci.compute(-1);
  }

  @Rule
  public ExpectedException exception = ExpectedException.none();

  @Test
  public void computeNegativeCaseRuleExpectedException() {
    exception.expect(IllegalArgumentException.class);
    exception.expectMessage("The maximum input value for long type output is 92");

    fibonacci.compute(93);
  }
}

i jednostkowy test parametryczny

package robert.trening;

import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameter;

import java.util.Arrays;
import java.util.Collection;

import static org.junit.Assert.assertEquals;
import static org.junit.runners.Parameterized.*;

@RunWith(Parameterized.class)
public class FibonacciParametrizedTest {

  @Parameter()
  public int input;
  @Parameter(1)
  public long result;

  @Parameters(name = "{index}: fib({0})={1}")
  public static Collection<Object[]> data() {
    Object[][] data = new Object[][]{{0, 0}, {1, 1}, {2, 1}, {3, 2},
        {5, 5}, {29, 514229L}, {19, 4181},
        {50, 12586269025L},
        {91, 4660046610375530309L},
        {92, 7540113804746346429L}};
    return Arrays.asList(data);
  }

  @Test
  public void computePossitiveCase() {
    FibonacciStreamImp fibonacci = new FibonacciStreamImp();

    assertEquals("Result", result, fibonacci.compute(input));
  }
}

Naszym zadaniem jest napisać implementacje spełniającą testy

(uwaga: żeby nie mnożyć kodu, test parametryczny działa tylko dla jednej implementacji. Dla pozostałych zostawiono jedynie proste teksty jednostkowe, sprawdzające przypadkową wartość i warunki brzegowe, żeby mieć sygnał, jeżeli przy modyfikacjach kodu coś by poszło nie tak).

 

I implementacje, trzy chyba najbardziej popularne:

  • Klasyczna rekurencja
package robert.trening;

// In Java not a tail-end recursion
public class FibonacciRecursionImp implements Fibonacci {

  public long compute(int n) {
    if (n < 0) { 
      throw new IllegalArgumentException("The argument must be positive"); 
    } else if (n > 92) {
      throw new IllegalArgumentException("The maximum input value for long type output is 92");
    }

    if (n < 2) {
      return (long) n;
    } else {
      return compute(n - 1) + compute(n - 2);
    }
  }
}
  • Iteracja
package robert.trening;

public class FibonacciIterationImp implements Fibonacci {

  public long compute(int n) {
    if (n < 0) { 
      throw new IllegalArgumentException("The argument must be positive"); 
    } else if (n > 92) {
      throw new IllegalArgumentException("The maximum input value for long type output is 92");
    }

    if (n <= 1) {
      return (long) n;
    } else {
      long fibo = 0;
      long fibo_2 = 0;
      long fibo_1 = 1;

      for (int i = 2; i <= n; i++) {
        fibo = fibo_1 + fibo_2;
        fibo_2 = fibo_1;
        fibo_1 = fibo;
      }
      return fibo;
    }
  }
}
  • Implementacja strumieniowa
package robert.trening;

import java.util.stream.Stream;

public class FibonacciStreamImp implements Fibonacci {

  public long compute(int n) {
    if (n < 0) { 
      throw new IllegalArgumentException("The argument must be positive"); 
    } else if (n > 92) {
      throw new IllegalArgumentException("The maximum input value for long type output is 92");
    }

    if (n <= 1) { 
      return n; 
    } else { 
      return Stream
          .iterate(new long[]{0, 1}, 
              p -> new long[]{p[1], p[0] + p[1]})
          .limit(n)
          .skip(n - 1)
          .findFirst()
          .get()[1];
    }
  }
}

Tu słowo wyjaśnenia: poczynając od elementu zerowego konstruujemy n kolejnych par liczb: [0,1], [1,1],[1,2],[2,3],[3,5],…, odrzucamy wszystkie, poza ostatnią a z tej bierzemy drugą. I to jest szukany n-ty element ciągu Fibonacciego.

I tutaj mógłby być koniec historii, gdyby nie pytanie – która implementacja ma największą wydajność? Jak to zbadać? Czy można na podstawie tego prostego przykładu wyciągnąć bardziej ogólne wnioski?

(ale o tym w następnej części).

Link do kodu na githabie udostępnię w ostatnim odcinku.

3 myśli na temat “Fibonacci, czyli wprawki (część 1: implementacje)”

    1. Adam, dzięki za zwrócenie uwagi ale sam nie wiem 🙁 Nalezę do tych, którym łatwiej nauczyć się i zastosować algorytm, niż go poprawnie opisać. Dlatego zajrzałem do SJP a tam masło maślane:
      https://sjp.pl/rekurencja
      https://sjp.pl/rekursja
      i teraz sam nie wiem. Kiedyś, przez wiele lat pracowałem w PWN, spróbuję zapytać i jeszcze raz napiszę i ew. poprawię.
      Pozdrawiam.

      1. Dostałem taką odpowiedź (autora nie publikuję, bo ptanie było prywatne, odpowiedź tudzież):
        “… Robercie, ja nie znałam do dziś słowa rekursja. Matematycy i fizycy mówią REKURENCJA – to jest poprawny termin w j.polskim i tego się trzymajmy. ☺ Tak jak napisał ktoś w komentarzach REKURSJA to kalka z angielskiego być może używana przez informatyków którzy nie dbają o język, którym się posługują.
        Pozdrawiam
        …”

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

This site uses Akismet to reduce spam. Learn how your comment data is processed.