19 czerwca 2013

Dzień 6 z taskassin w Scali - funkcja zliczająca zadania z @tailrec

Ależ to mi czasu zajęło, aby wpaść na pomysł skompletowania zadań na zadaną liczbę godzin! Próbowałem foldLeft i takeWhile z List, ale potrzebowałem nie tylko gromadzić dane o wielu elementach w liście (tutaj foldLeft mógłby być pomocny), ale również przerwać jej przetwarzanie w momencie zebrania wystarczających danych (takeWhile tylko z nazwy tutaj pasował, ale operuje wyłącznie na pojedynczych elementach). Co skłoniło mnie do intensywniejszej pracy umysłowej było obsłużenie sytuacji, w której należałoby przerwać przetwarzanie przy obsłudze list nieskończonych. Paradoks polegał jednak na tym, że najprawdopodobniej taka sytuacja nie ma prawa nastąpić, albo przynajmniej nie jest tematem w obecnym stanie aplikacji (!)

Rozwiązaniem okazało się stworzenie funkcji z rekurencją ogonową (użyłem dodatkowo @scala.annotation.tailrec dla wymuszenia tej cechy podczas kompilacji), której warunkiem końcowym byłoby właśnie zebranie wystarczającego zbioru zadań na daną jednostkę czasu.
object TaskUtils {

  def collectTasks(ts: List[Task], hours: Int): List[Task] = {
    @tailrec
    def collectTasks(ts: List[Task], accTs: List[Task], remHours: Int): List[Task] = 
      ts match {
        case t :: tail if (remHours >= 0 && remHours - t.timeSpanInHours >= 0) =>
          collectTasks(tail, t :: accTs, remHours - t.timeSpanInHours)
        case _ => accTs reverse
      }
    collectTasks(ts, Nil, hours)
  }
}
Uwagi i spostrzeżenia są wielce pożądane. Całość dostępna w projekcie taskassin na GitHubie.

3 komentarze:

  1. Hint: @tailrec _nie wymusza_. Wyraża oczekiwanie że kompilator zoptymalizuje tą metodą - jak nie zoptymalizuje będzie compile error - trochę jak z @Override w Javie, można żyć bez i zadziała tak samo ;)

    OdpowiedzUsuń
    Odpowiedzi
    1. Słuszna uwaga. W moim rozumieniu "wymuszać" oznaczało "zagwarantować, że tak jest" i przy braku spełnienia tego warunku "rzucić błędem kompilacji". Dzięki za sprostowanie!

      Usuń
  2. Jak zobaczyłem kod do zbierania tasków od razy pomyślałem o tym, że można spróbować napisać coś zo znajdzie taki zestaw zadań, żeby minimializować pozostały czas.

    Palą mi się lampki ze słowami "programowanie dynamiczne", "problem wydawania reszty" i ostatnie zadanie z coursery gdzie generowało się streamy wszystkich stanów.

    Pewnie w wolnej chwili spróbuje sobie takie coś napisać.

    OdpowiedzUsuń