0xDEADBEEF

RSS odkazy english edition
««« »»»

Průnik množin ve Scale

3. 11. 2018 #Scala #množiny

Dneska je čas na jeden malý trik jak ve Scale vypočítat velikost průniku dvou množin. Když mám dvě množiny as a bs, dá se to zařídit vytvořením množiny průniku.

as.intersect(bs).size

Jde o přímé řešení, které popisuje, o přesně dělá, ale je třeba alokovat dočasnou kolekci a to není nejrychlejší. Bez alokací se to samé dá zařídit takhle:

var i = 0
for (a <- as if bs.conains(a)) i += 1

To je zase poněkud zdlouhavé, nefunkcionální a také není na první pohled jasně vidět, co smyčka přesně dělá. Existuje ale ještě jedno řešení, které využívá bohatého API kolekcí Scaly, která je mnohem elegantnější:

as.count(bs)

Metoda count spočítá kolik prvků z množiny as odpovídá predikátu. Místo funkce je ale zadána druhá množina. Funguje to proto, že množina je ve Scale zároveň funkce testující členství elementu:

class Set[T] extends T => Boolean

Kompilátor pod kapotou kód přepíše na

as.count { a => bs.apply(a) }

což dělá to samé, co

as.count(bs.contains)

tedy počítá to počet prvků první množiny, které jsou přítomny v té druhé, neboli velikost průniku.

Podobné kousky je možné provádět i s mapami, které jsou ze své podstaty (parciální) funkce z klíčů na mapované hodnoty:

class Map[K, V] extends K => V

Dá se tak napsat třeba jednoduché generování slugů do url z titulků článků:

val from = "áčďéěíňóřšťúůýž "
val to   = "acdeeinorstuuyz-"
val txl = (from zip to).toMap withDefault (x => x)
def makeSlug(title: String) = title.map(txl)

Pozn: Když chcete počítat průniky množin opravdu rychle, mám na tohle téma celý článek.

píše k47 (@kaja47, k47)