0xDEADBEEF

RSS
««« »»»

Průnik množin ve Scale

3. 11. 2018

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 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)