Małe perełki biblioteki standardowej Scali

Język programowania Scala posiada naprawdę bogatą bibliotekę standardową, szczególnie jeśli chodzi o funkcjonalność związaną z kolekcją. Istnieje wiele funkcji, które są często pomijane, ale jeśli zostaną zastosowane, mogą znacznie uprościć kod. W tym artykule postaram się przedstawić niektóre z mniej znanych, ale naprawdę użytecznych metod, które pomagają w pisaniu czystszego, solidniejszego i wydajniejszego kodu.

Zacznijmy od zbudowania sobie małej sekwencji liczb całkowitych do eksperymentowania:

val xs = Seq(4, 5, 2, -1, -3, 4)

Zostanie ona użyta w większości przykładów z tego artykułu. Możesz wypróbować wszystkie fragmenty kodu, które tutaj przedstawię w arkuszach Scala IntelliJ IDEA lub Scala IDE for Eclipse (lub online, przy użyciu Scastie).

A więc zaczynajmy (w żadnej szczególnej kolejności):

partition

partition pozwala na podział kolekcji na dwie kolekcje w oparciu o dany predykat. Więc zamiast pisać:

val even = xs.filter(_ % 2 == 0)
val odd = xs.filterNot(_ % 2 == 0)

możesz napisać:

val (even, odd) = xs.partition(_ % 2 == 0)

Kod jest czystszy, ma mniej miejsca na błędy i wykonuje pracę w jednym przejściu nad oryginalną kolekcją. Jedyne, o czym musisz pamiętać, to to, że w wynikowej krotce, pierwszy element zawiera wszystkie elementy, które pasują do Twojego predykatu, a drugi - te które nie pasują.

minBy / maxBy

Możliwe że kusi cię aby posortować całą kolekcję tylko po to, aby uzyskać najmniejszą (lub największą) wartość. Jest to bardzo zbędny i nieefektywny sposób na wykonanie pracy.

Np. powiedzmy, że chcesz uzyskać liczbę, która ma najmniejszą wartość bezwzględną. Zamiast pisać:

val minByAbs = xs.sortBy(Math.abs).head

Możesz napisać:

val minByAbs = xs.minBy(Math.abs)

W rzeczywistości IntelliJ IDEA automatycznie sugeruje ci wykonanie takiej refaktoryzacji. Chyba, że oszalejesz i zrobisz coś w stylu

val maxByAbs = xs.sortBy(Math.abs).reverse.head

Wówczas nawet IntelliJ nie będzie w stanie ci pomóc...

Wystarczy pamiętać, że zarówno minBy jak i maxBy rzucą UnsupportedOperationException w przypadku, gdy są one wywołane na pustej kolekcji (i tak samo min i max). Jednak head i last rzucą NoSuchElementException w takim przypadku (co, ściśle mówiąc, sprawia, że powyższe wyrażenia nie są równoważne).

collect / collectFirst

Czasami chcesz zarówno przefiltrować kolekcję, jak i wykonać mapowanie jej wartości. Na przykład:

val doublesOfPositive = xs.filter(_ > 0).map(2 * _)

Można to ładnie wyrazić za pomocą collect (jeśli chcesz filtrować, a następnie przetwarzać) lub collectFirst (jeśli chcesz przetwarzać tylko pierwszą wartość odpowiadającą predykatowi):

val doublesOfPositive = xs.collect {
  
case x if x > 0 => 
    2 * x
}

collectFirst ma tę samą składnię, ale zwraca Option (co w przypadku gdy nie było wartości pasujących do predykatu, daje None) i jest bezpieczny w użyciu na pustych kolekcjach (tak jak find).

splitAt

splitAt to miły sposób na podzielenie kolekcji na dwie sąsiadujące ze sobą części danego indeksu. Więc zamiast pisać:

val leftHalf = xs.take(3)
val rightHalf = xs.drop(3)

możesz napisać:

val (leftHalf, rightHalf) = xs.splitAt(3)

Jest to podobne do partition, różnica polega na tym, że dzielisz według indeksu, a nie przez jakiś predykat boolowski. Uwaga: Bezpieczne jest połączenie splitAt z indeksem przekraczającym wielkość Twojej kolekcji. W takim przypadku otrzymasz całą oryginalną kolekcję w leftHalf, a rightHalf będzie pusta.

grouped

grouped(n) dzieli kolekcję na takie, z których każdy zawiera n elementów (ostatni z nich może zawierać mniej niż n elementów, w zależności od wielkości oryginalnej kolekcji):

xs.grouped(3).toList // List(List(4, 5, 2), List(-1, -3, 4))

Np. może być używany do przetwarzania danych w partiach o ograniczonym rozmiarze. Uwaga: grouped zwraca iterator nad wynikowymi kolekcjami, więc musiałem wywołać toList  by wymusić jego wykonanie i uzyskać rzeczywisty wynik.

count

Dość często trzeba policzyć ilość elementów w kolekcji, które pasują do jakiegoś predykatu. Zamiast filtrować pasujące elementy, a następnie pobierać wielkość powstałej kolekcji, jak w przypadku:

val evenCount = xs.filter(_ % 2 == 0).size

Możesz napisać:

val evenCount = xs.count(_ % 2 == 0)

(jest to również sugerowane jako automatyczna refaktoryzacja przez IntelliJ).

exists

Potrzebujesz sprawdzić, czy istnieje jakiś element pasujący do danego predykatu? Zamiast pisać:

xs.find(_ % 42 == 0) != None

lub

xs.count(_ % 42 == 0) > 0

Możesz napisać:

xs.exists(_ % 42 == 0)

(lub ponownie pozwolić IntelliJ naprawić to za ciebie).

last

last robi to co myślisz  -  zwraca ostatni element kolekcji, więc nie ma potrzeby korzystania z .reverse.head (lub dostępu do ostatniego elementu przy pomocy indeksu).

A na deser, mój osobisty ulubieniec:

indexOfSlice / lastIndexOfSlice

Dotyczy to głównie wydajności (pod względem notacji Big O). Powiedzmy, że musisz znaleźć dany podłańcuch w obrębie jakiegoś łańcucha. Jeśli jesteś doświadczonym programistą Javy, od razu zasugerujesz użycie String.indexOf(substring). Pewnie, będąc metodą java.lang.String, jest ona również dostępna dla nas w Scali. Ale poczekaj chwilę! Co się stanie, jeśli ja (lub jakiś złośliwy użytkownik publicznie dostępnego API) postaram się zapewnić Ci pewne "niewygodne" wejścia? Na przykład:

val string = "a" * 2000000
val substring = "a" * 1000000 + "b"
string.indexOf(substring)

(na wypadek gdybyś się zastanawiał, "foo" * x to miły sposób na uzyskanie łańcucha "foo" powtarzanego x razy w Scali).

Po prostu nie wstrzymuj oddechu, próbując uruchomić ten kod! Stracisz go na długo zanim kod się wykona. Dzieje się tak dlatego, że implementacja String.indexOf w Javie wykorzystuje naiwny algorytm dopasowywania podłańcuchów  -  dla każdego wystąpienia pierwszego znaku wyszukiwania podłańcuchów ('a') próbuje porównać każdy kolejny znak podłańcuchów aż do momentu znalezienia niedopasowania (lub aż podłańcuch będzie w pełni dopasowany).

Ten konkretny input, który dałem jest przeznaczony do ujawnienia kwadratowej (O(nm)) najgorszej złożoności czasowej (n jest długością głównego ciągu znaków, a m - the długości podciągania wyszukiwania) tej implementacji: wykona się milion udanych dopasowań znaku 'a' anim algorytm napotka pierwsze niedopasowanie 'b'. I powtarza się to mniej więcej milion razy! Ale jak może nam pomóc standardowa biblioteka Scali? Spróbujmy zrobić tak:

val string = "a" * 2000000
val substring = "a" * 1000000 + "b"
string.indexOf
Slice(substring)

Ten kod robi to samo, ale kończy się natychmiast! Jedyną zmianą jest zastąpienie indexOf przez indexOfSlice (metoda pochodząca z cechy SeqLike w bibliotece standardowej Scali).

Ale dlaczego działa o wiele lepiej na tym wejściu? Jeśli się przyjrzymy, pod maską tej metody możemy znaleźć implementację algorytmu Knuth-Morris-Pratt, który jest naprawdę sprytnym algorytmem wyszukiwania podciągów. Ma liniową (O(n + m)) złożoność, nawet w najgorszym przypadku (czyli - dla każdego dowolnego wejścia). Jeśli spróbujesz zbenchmarkować indexOf Javy i indesOfSlice Scali na losowych wejściach, jestem pewien, że indexOf Javy wygra. Po prostu dlatego, że specjalizuje się w łańcuchach, podczas gdy Scala indexOfSlice obsługuje sekwencje typu generycznego. Ponadto, implementacja naiwnego algorytmu wyszukiwania ma mniej kosztów ogólnych.

Jednakże, indexOfSlice ma przewagę, gdy trzeba być defensywnym wobec wejść, których nie kontrolujemy  -  na przykład, gdy użytkownicy mogą dostarczyć wystarczająco duże ciągi i uruchomić wyszukiwanie na nich. Ponadto, liniowa czy kwadratowa złożoność naprawdę ma znaczenie w zawodach programistycznych.

Częścią mojej obecnej pracy jest wprowadzenie nowych członków zespołu do Scali. Jedną z rzeczy, o które ich proszę, jest kilkukrotne przejrzenie dokumentacji typowej klasy kolekcji Scali (np. IndexedSeq), aby poznać metody, które mogą być przydatne w codziennej pracy, takie jak te, o których właśnie rozmawialiśmy. Ale mam nadzieję, że nawet doświadczeni programiści Scali nauczyli się czegoś nowego z tego artykułu.


Oryginał tekstu w języku angielskim przeczytasz tutaj.