Effect Курс SortedMap и SortedSet

SortedMap и SortedSet

Упорядоченные коллекции с Order.

Теория

Зачем нужны отсортированные коллекции

HashSet и HashMap обеспечивают O(1) lookup, но не гарантируют порядок элементов. Когда порядок критичен:

HashSet:    { 3, 1, 4, 1, 5 }  →  { 5, 3, 1, 4 }  (произвольный порядок)
SortedSet:  { 3, 1, 4, 1, 5 }  →  { 1, 3, 4, 5 }  (всегда отсортирован)

HashMap:    { b→2, a→1, c→3 }  →  { c→3, a→1, b→2 }  (произвольный)
SortedMap:  { b→2, a→1, c→3 }  →  { a→1, b→2, c→3 }  (по ключу)

Внутренняя структура

SortedSet и SortedMap основаны на сбалансированных деревьях (Red-Black Tree), обеспечивающих логарифмическую сложность:

SortedSet({ 1, 3, 5, 7, 9 })

           ┌───┐
           │ 5 │
           └───┘
          /     \
       ┌───┐   ┌───┐
       │ 3 │   │ 7 │
       └───┘   └───┘
      /         \
   ┌───┐       ┌───┐
   │ 1 │       │ 9 │
   └───┘       └───┘

   Высота: O(log n) → все операции O(log n)

Сравнение сложностей

┌─────────────────┬─────────────┬──────────────┐
│ Операция        │ Hash*       │ Sorted*      │
├─────────────────┼─────────────┼──────────────┤
│ Lookup          │ O(1) avg    │ O(log n)     │
│ Insert          │ O(1) avg    │ O(log n)     │
│ Delete          │ O(1) avg    │ O(log n)     │
│ Min/Max         │ O(n)        │ O(log n) ✅  │
│ Range query     │ O(n)        │ O(log n + k) │
│ Ordered iterate │ O(n log n)  │ O(n) ✅      │
│ Порядок         │ Нет         │ Да ✅        │
└─────────────────┴─────────────┴──────────────┘

Order — тайпкласс упорядочивания

Order<A> — это тайпкласс, определяющий полный порядок для типа A. Он является обязательным параметром для SortedSet и SortedMap.

Встроенные Order


// Числа
Order.number   // 1 < 2 < 3

// Строки (лексикографический)
Order.string   // "a" < "b" < "c"

// Даты
Order.Date     // раньше < позже

// Boolean
Order.boolean  // false < true

Создание кастомного Order


interface Person {
  readonly name: string
  readonly age: number
}

// Order по одному полю
const byAge = Order.mapInput(
  Order.number,
  (person: Person) => person.age
)

// Order по нескольким полям
const byNameThenAge = Order.combine(
  Order.mapInput(Order.string, (p: Person) => p.name),
  Order.mapInput(Order.number, (p: Person) => p.age)
)

// Обратный порядок
const byAgeDesc = Order.reverse(byAge)

Утилиты Order


// Сравнение
Order.lessThan(Order.number)(1, 2)             // true
Order.greaterThan(Order.number)(5, 3)          // true
Order.lessThanOrEqualTo(Order.number)(2, 2)    // true

// Min / Max
const min = Order.min(Order.number)
min(3, 7) // 3

const max = Order.max(Order.number)
max(3, 7) // 7

// Clamp
const clamp = Order.clamp(Order.number)
clamp(15, { minimum: 0, maximum: 10 }) // 10
clamp(-5, { minimum: 0, maximum: 10 }) // 0
clamp(5, { minimum: 0, maximum: 10 })  // 5

// Between
Order.between(Order.number)(5, { minimum: 1, maximum: 10 }) // true
Order.between(Order.number)(15, { minimum: 1, maximum: 10 }) // false

SortedSet

Создание


// Пустой SortedSet
const empty = SortedSet.empty<number>(Order.number)

// Из значений
const set = SortedSet.fromIterable(Order.number)([5, 3, 1, 4, 2])
// SortedSet(1, 2, 3, 4, 5) — автоматически отсортирован

// Из Iterable с дубликатами
const noDups = SortedSet.fromIterable(Order.number)([1, 2, 2, 3, 3, 3])
// SortedSet(1, 2, 3)

Основные операции


const set = SortedSet.fromIterable(Order.number)([3, 1, 4, 1, 5, 9])
// SortedSet(1, 3, 4, 5, 9)

// Добавление (возвращает новый SortedSet)
const withTwo = SortedSet.add(set, 2)
// SortedSet(1, 2, 3, 4, 5, 9)

// Удаление
const withoutFour = SortedSet.remove(set, 4)
// SortedSet(1, 3, 5, 9)

// Проверка наличия
SortedSet.has(set, 5) // true
SortedSet.has(set, 7) // false

// Размер
SortedSet.size(set) // 5

Трансформации


const set = SortedSet.fromIterable(Order.number)([1, 2, 3, 4, 5])

// map
const doubled = SortedSet.map(Order.number)(set, (n) => n * 2)
// SortedSet(2, 4, 6, 8, 10)

// filter
const evens = SortedSet.filter(set, (n) => n % 2 === 0)
// SortedSet(2, 4)

// flatMap
const expanded = SortedSet.flatMap(Order.number)(
  set,
  (n) => SortedSet.fromIterable(Order.number)([n, n * 10])
)
// SortedSet(1, 2, 3, 4, 5, 10, 20, 30, 40, 50)

// reduce
const sum = SortedSet.reduce(set, 0, (acc, n) => acc + n)
// 15

// partition
const [odds, evenSet] = SortedSet.partition(set, (n) => n % 2 === 0)

Получение значений


const set = SortedSet.fromIterable(Order.number)([5, 3, 1, 4, 2])

// Итерация — ВСЕГДА в отсортированном порядке
const values = SortedSet.values(set)
// Iterator: 1, 2, 3, 4, 5

// В массив
const arr = [...set]
// [1, 2, 3, 4, 5]

SortedMap

Создание


// Пустой SortedMap
const empty = SortedMap.empty<string, number>(Order.string)

// Из пар ключ-значение
const map = SortedMap.fromIterable(Order.string)([
  ["charlie", 35],
  ["alice", 30],
  ["bob", 25]
])
// SortedMap(alice→30, bob→25, charlie→35) — отсортирован по ключу

Основные операции


const map = SortedMap.fromIterable(Order.string)([
  ["alice", 30],
  ["bob", 25],
  ["charlie", 35]
])

// GET — возвращает Option
SortedMap.get(map, "alice")    // Some(30)
SortedMap.get(map, "unknown")  // None

// SET — возвращает новый SortedMap
const updated = SortedMap.set(map, "diana", 28)
// SortedMap(alice→30, bob→25, charlie→35, diana→28)

// REMOVE
const smaller = SortedMap.remove(map, "bob")
// SortedMap(alice→30, charlie→35)

// HAS
SortedMap.has(map, "alice") // true

// SIZE
SortedMap.size(map) // 3

Трансформации


const scores = SortedMap.fromIterable(Order.string)([
  ["alice", 85],
  ["bob", 92],
  ["charlie", 78]
])

// map — трансформация значений
const graded = SortedMap.map(scores, (score) =>
  score >= 90 ? "A" : score >= 80 ? "B" : "C"
)
// SortedMap(alice→"B", bob→"A", charlie→"C")

// filter — фильтрация
const highScores = SortedMap.filter(scores, (score) => score >= 85)

// reduce
const total = SortedMap.reduce(scores, 0, (acc, score) => acc + score)
// 255

// forEach
SortedMap.forEach(scores, (score, name) => {
  console.log(`${name}: ${score}`)
})
// alice: 85
// bob: 92
// charlie: 78
// (в алфавитном порядке!)

Получение ключей и значений


const map = SortedMap.fromIterable(Order.string)([
  ["c", 3],
  ["a", 1],
  ["b", 2]
])

// Ключи — всегда в отсортированном порядке
const keys = SortedMap.keys(map)
// Iterator: "a", "b", "c"

// Значения — в порядке ключей
const values = SortedMap.values(map)
// Iterator: 1, 2, 3

// Записи
const entries = SortedMap.entries(map)
// Iterator: ["a", 1], ["b", 2], ["c", 3]

Кастомные Order

Order для объектов


interface Task {
  readonly priority: number
  readonly name: string
  readonly createdAt: Date
}

// Сортировка: сначала по приоритету (выше = важнее), потом по дате
const taskOrder = Order.combine(
  Order.reverse(
    Order.mapInput(Order.number, (t: Task) => t.priority)
  ),
  Order.mapInput(Order.Date, (t: Task) => t.createdAt)
)

const tasks = SortedSet.fromIterable(taskOrder)([
  { priority: 1, name: "Low task", createdAt: new Date("2024-01-01") },
  { priority: 3, name: "High task", createdAt: new Date("2024-01-02") },
  { priority: 3, name: "High task earlier", createdAt: new Date("2024-01-01") },
  { priority: 2, name: "Medium task", createdAt: new Date("2024-01-03") }
])

// Итерация: High earlier, High, Medium, Low

Order для enum-like типов


type LogLevel = "debug" | "info" | "warn" | "error" | "fatal"

const logLevelRank = (level: LogLevel): number => {
  switch (level) {
    case "debug": return 0
    case "info":  return 1
    case "warn":  return 2
    case "error": return 3
    case "fatal": return 4
  }
}

const logLevelOrder: Order.Order<LogLevel> = Order.mapInput(
  Order.number,
  logLevelRank
)

const logCounts = SortedMap.fromIterable(logLevelOrder)([
  ["error", 5],
  ["debug", 100],
  ["info", 50],
  ["warn", 10]
] as ReadonlyArray<readonly [LogLevel, number]>)

// Итерация: debug→100, info→50, warn→10, error→5

SortedSet vs HashSet

┌──────────────────────┬────────────────┬─────────────────┐
│ Критерий             │ HashSet        │ SortedSet       │
├──────────────────────┼────────────────┼─────────────────┤
│ Порядок              │ Нет            │ Да (Order<A>)   │
│ Lookup               │ O(1) avg       │ O(log n)        │
│ Insert               │ O(1) avg       │ O(log n)        │
│ Delete               │ O(1) avg       │ O(log n)        │
│ Min/Max              │ O(n)           │ O(log n)        │
│ Range queries        │ O(n)           │ O(log n + k)    │
│ Equality             │ Equal + Hash   │ Order<A>        │
│ Итерация             │ Произвольная   │ Отсортированная │
│ Set operations       │ ✅ union, etc  │ ⚠️ Ограничено   │
│ Worst case           │ O(n) (hash)    │ O(log n) ✅     │
└──────────────────────┴────────────────┴─────────────────┘

Когда что использовать:

  • HashSet — когда порядок не важен и нужна максимальная скорость lookup
  • SortedSet — когда нужен порядок, range queries, или гарантированный O(log n) worst case

Паттерны использования

Priority Queue (через SortedMap)


interface PriorityItem<A> {
  readonly priority: number
  readonly value: A
  readonly id: number
}

const itemOrder = <A>(): Order.Order<PriorityItem<A>> =>
  Order.combine(
    Order.mapInput(Order.number, (item: PriorityItem<A>) => item.priority),
    Order.mapInput(Order.number, (item: PriorityItem<A>) => item.id)
  )

Leaderboard


// Leaderboard отсортированный по очкам (по убыванию)
const scoreOrder = Order.reverse(Order.number)

const leaderboard = SortedMap.fromIterable(scoreOrder)([
  [950, "Alice"],
  [1200, "Bob"],
  [800, "Charlie"],
  [1100, "Diana"]
])

// Итерация: Bob(1200), Diana(1100), Alice(950), Charlie(800)
SortedMap.forEach(leaderboard, (name, score) => {
  console.log(`${name}: ${score}`)
})

Time-series данные


const timestampOrder = Order.number // Unix timestamp

type TimeSeriesEntry = {
  readonly value: number
  readonly label: string
}

const timeSeries = SortedMap.fromIterable(timestampOrder)([
  [1704067200, { value: 42, label: "start" }],
  [1704153600, { value: 55, label: "middle" }],
  [1704240000, { value: 38, label: "end" }]
] as ReadonlyArray<readonly [number, TimeSeriesEntry]>)

// Данные всегда отсортированы по времени

Упражнения

Упражнение

Упражнение 1: Top N Elements

Легко

Реализуйте функцию, возвращающую N наибольших элементов из массива:

import { SortedSet, Order } from "effect"

const topN = (arr: ReadonlyArray<number>, n: number): ReadonlyArray<number> => {
  // Ваш код
}

// topN([5, 3, 8, 1, 9, 2, 7], 3) → [9, 8, 7]
Упражнение

Упражнение 2: Sorted Event Log

Средне

Создайте иммутабельный event log с автоматической сортировкой по timestamp:

import { SortedMap, Order, Option } from "effect"

interface Event {
  readonly type: string
  readonly data: string
}

type EventLog = SortedMap.SortedMap<number, Event>

const emptyLog: EventLog = SortedMap.empty(Order.number)

const addEvent = (log: EventLog, timestamp: number, event: Event): EventLog => {
  // Ваш код
}

const getEventsInRange = (
  log: EventLog,
  from: number,
  to: number
): ReadonlyArray<readonly [number, Event]> => {
  // Ваш код
}
Упражнение

Упражнение 3: Interval Scheduler

Сложно

Реализуйте планировщик интервалов, который находит свободные слоты:

import { SortedMap, Order } from "effect"

interface TimeSlot {
  readonly start: number
  readonly end: number
  readonly label: string
}

type Schedule = SortedMap.SortedMap<number, TimeSlot>

const createSchedule = (slots: ReadonlyArray<TimeSlot>): Schedule => {
  // Ваш код
}

const findFreeSlots = (
  schedule: Schedule,
  dayStart: number,
  dayEnd: number,
  minDuration: number
): ReadonlyArray<{ readonly start: number; readonly end: number }> => {
  // Ваш код — найти все свободные слоты минимальной длительности
}