Spec-Zone.ru › Nim

std/algorithm

Исходный кодРедактировать

Этот модуль реализует некоторые общие обобщённые алгоритмы над openArray.

Основные примеры использования

Пример:

import std/algorithm
type People = tuple
  year: int
  name: string

var a: seq[People]

a.add((2000, "John"))
a.add((2005, "Marie"))
a.add((2010, "Jane"))

# Sorting with default system.cmp
a.sort()
assert a == @[(year: 2000, name: "John"), (year: 2005, name: "Marie"),
              (year: 2010, name: "Jane")]

proc myCmp(x, y: People): int =
  cmp(x.name, y.name)

# Sorting with custom proc
a.sort(myCmp)
assert a == @[(year: 2010, name: "Jane"), (year: 2000, name: "John"),
              (year: 2005, name: "Marie")]

См. также

  • модуль sequtils для работы с встроенным типом seq
  • модуль tables для сортировки таблиц

Импорты

since

Типы

SortOrder = enum
  Descending, Ascending
Исходный код Редактировать

Процедуры

proc `*`(x: int; order: SortOrder): int {.inline, ...raises: [], tags: [],
    forbids: [].}

Изменяет знак x если order == Descending. Если order == Ascending то возвращается x.

x должен быть результатом компаратора, т.е.

< 0 для меньше чем,
== 0 для равно,
> 0 для больше чем.

Пример:

assert -123 * Descending == 123
assert 123 * Descending == -123
assert -123 * Ascending == -123
assert 123 * Ascending == 123
Исходный код Редактировать 
proc binarySearch[T, K](a: openArray[T]; key: K;
                        cmp: proc (x: T; y: K): int {.closure.}): int {.
    effectsOf: cmp.}

Бинарный поиск key в a. Возвращает индекс key или -1, если не найдено. Предполагается, что a отсортирован в соответствии с cmp.

cmp - функция компаратора, ожидаемые значения возврата такие же, как у system.cmp.

Пример:

assert binarySearch(["a", "b", "c", "d"], "d", system.cmp[string]) == 3
assert binarySearch(["a", "b", "c", "d"], "c", system.cmp[string]) == 2
Исходный код Редактировать 
proc binarySearch[T](a: openArray[T]; key: T): int
Бинарный поиск key в a. Возвращает индекс key или -1, если не найдено. Предполагается, что a отсортирован.

Пример:

assert binarySearch([0, 1, 2, 3, 4], 4) == 4
assert binarySearch([0, 1, 2, 3, 4], 2) == 2
Исходный код Редактировать 
proc fill[T](a: var openArray[T]; first, last: Natural; value: T)

Присваивает value всем элементам среза a[first..last].

Если передан недопустимый диапазон, генерируется исключение IndexDefect.

Пример:

var a: array[6, int]
a.fill(1, 3, 9)
assert a == [0, 9, 9, 9, 0, 0]
a.fill(3, 5, 7)
assert a == [0, 9, 9, 7, 7, 7]
doAssertRaises(IndexDefect, a.fill(1, 7, 9))
Исходный код Редактировать 
proc fill[T](a: var openArray[T]; value: T)
Присваивает value всем элементам контейнера a.

Пример:

var a: array[6, int]
a.fill(9)
assert a == [9, 9, 9, 9, 9, 9]
a.fill(4)
assert a == [4, 4, 4, 4, 4, 4]
Исходный код Редактировать 
func isSorted[T](a: openArray[T]; cmp: proc (x, y: T): int {.closure.};
                 order = SortOrder.Ascending): bool {.effectsOf: cmp.}

Проверяет, отсортирован ли a в order с использованием cmp для сравнения. Параметры идентичны sort. Требует O(n) времени.

См. также:

  • isSorted proc

Пример:

let
  a = [2, 3, 1, 5, 4]
  b = [1, 2, 3, 4, 5]
  c = [5, 4, 3, 2, 1]
  d = ["adam", "brian", "cat", "dande"]
  e = ["adam", "dande", "brian", "cat"]
assert isSorted(a) == false
assert isSorted(b) == true
assert isSorted(c) == false
assert isSorted(c, Descending) == true
assert isSorted(d) == true
assert isSorted(e) == false
Исходный код Редактировать 
proc isSorted[T](a: openArray[T]; order = SortOrder.Ascending): bool

Сокращённая версия isSorted, которая использует system.cmp[T] в качестве функции сравнения.

См. также:

  • isSorted func

Пример:

let
  a = [2, 3, 1, 5, 4]
  b = [1, 2, 3, 4, 5]
  c = [5, 4, 3, 2, 1]
  d = ["adam", "brian", "cat", "dande"]
  e = ["adam", "dande", "brian", "cat"]
assert isSorted(a) == false
assert isSorted(b) == true
assert isSorted(c) == false
assert isSorted(c, Descending) == true
assert isSorted(d) == true
assert isSorted(e) == false
Исходный код Редактировать 
proc lowerBound[T, K](a: openArray[T]; key: K;
                      cmp: proc (x: T; k: K): int {.closure.}): int {.
    effectsOf: cmp.}

Возвращает индекс первого элемента в a , который не меньше (т.е. больше или равен) key, или последнего, если такого элемента нет. Другими словами, если у вас отсортированная последовательность и вы вызываете insert(thing, elm, lowerBound(thing, elm)), последовательность по-прежнему будет отсортирована. Предполагается, что a отсортирован в соответствии с cmp.

Если передан недопустимый диапазон, генерируется исключение IndexDefect.

Этот вариант использует cmp для сравнения элементов. Ожидаемые значения возврата такие же, как у system.cmp.

См. также:

  • upperBound proc отсортировано по cmp в указанном порядке
  • upperBound proc

Пример:

var arr = @[1, 2, 3, 5, 6, 7, 8, 9]
assert arr.lowerBound(3, system.cmp[int]) == 2
assert arr.lowerBound(4, system.cmp[int]) == 3
assert arr.lowerBound(5, system.cmp[int]) == 3
arr.insert(4, arr.lowerBound(4, system.cmp[int]))
assert arr == [1, 2, 3, 4, 5, 6, 7, 8, 9]
Исходный код Редактировать 
proc lowerBound[T](a: openArray[T]; key: T): int

Возвращает индекс первого элемента в a , который не меньше (т.е. больше или равен) key, или последнего, если такого элемента нет. Другими словами, если у вас отсортированная последовательность и вы вызываете insert(thing, elm, lowerBound(thing, elm)), последовательность по-прежнему будет отсортирована. Предполагается, что a отсортирован.

Этот вариант использует функцию сравнения по умолчанию cmp.

См. также:

  • upperBound proc отсортировано по cmp в указанном порядке
  • upperBound proc
Исходный код Редактировать 
proc merge[T](result: var seq[T]; x, y: openArray[T]) {.inline.}

Сокращённая версия merge , которая использует system.cmp[T] в качестве функции сравнения.

См. также:

  • merge proc

Пример:

let x = [5, 10, 15, 20, 25]
let y = [50, 40, 30, 20, 10].sorted

var merged: seq[int]
merged.merge(x, y)
assert merged.isSorted
assert merged == @[5, 10, 10, 15, 20, 20, 25, 30, 40, 50]
Исходный код Редактировать 
proc merge[T](result: var seq[T]; x, y: openArray[T];
              cmp: proc (x, y: T): int {.closure.}) {.effectsOf: cmp.}
Объединяет две отсортированные openArray. x и y предполагаются отсортированными. Если вы не хотите предоставлять свой cmp, вы можете использовать system.cmp или вместо этого вызвать перегруженную версию merge, которая использует system.cmp.
Примечание: Исходные данные result не очищаются, новые данные добавляются к result.

См. также:

  • merge proc

Пример:

let x = @[1, 3, 6]
let y = @[2, 3, 4]

block:
  var merged = @[7] # new data is appended to merged sequence
  merged.merge(x, y, system.cmp[int])
  assert merged == @[7, 1, 2, 3, 3, 4, 6]

block:
  var merged = @[7] # if you only want new data, clear merged sequence first
  merged.setLen(0)
  merged.merge(x, y, system.cmp[int])
  assert merged.isSorted
  assert merged == @[1, 2, 3, 3, 4, 6]

import std/sugar

var res: seq[(int, int)]
res.merge([(1, 1)], [(1, 2)], (a, b) => a[0] - b[0])
assert res == @[(1, 1), (1, 2)]

assert seq[int].default.dup(merge([1, 3], [2, 4])) == @[1, 2, 3, 4]
Исходный код Редактировать 
proc nextPermutation[T](x: var openArray[T]): bool {.discardable.}

Вычисляет следующее лексикографическое перестановку, непосредственно изменяя x. Результат — произошла ли перестановка, иначе мы достигли последней упорядоченной перестановки.

Если вы начинаете с неупорядоченного массива/последовательности, повторяющиеся перестановки не дадут вам все перестановки, но остановятся на последней.

См. также:

  • prevPermutation proc

Пример:

var v = @[0, 1, 2, 3]
assert v.nextPermutation() == true
assert v == @[0, 1, 3, 2]
assert v.nextPermutation() == true
assert v == @[0, 2, 1, 3]
assert v.prevPermutation() == true
assert v == @[0, 1, 3, 2]
v = @[3, 2, 1, 0]
assert v.nextPermutation() == false
assert v == @[3, 2, 1, 0]
Исходный код Редактировать 
proc prevPermutation[T](x: var openArray[T]): bool {.discardable.}

Вычисляет предыдущее лексикографическое перестановку, непосредственно изменяя x. Результат — произошла ли перестановка, иначе мы достигли первой упорядоченной перестановки.

См. также:

  • nextPermutation proc

Пример:

var v = @[0, 1, 2, 3]
assert v.prevPermutation() == false
assert v == @[0, 1, 2, 3]
assert v.nextPermutation() == true
assert v == @[0, 1, 3, 2]
assert v.prevPermutation() == true
assert v == @[0, 1, 2, 3]
Исходный код Редактировать 
proc product[T](x: openArray[seq[T]]): seq[seq[T]]
Производит декартово произведение массива. Каждый элемент результата — комбинация одного элемента из каждой последовательности в x, где i-й элемент берется из x[i].
Предупреждение: сложность может увеличиться.

Пример:

assert product(@[@[1], @[2]]) == @[@[1, 2]]
assert product(@[@["A", "K"], @["Q"]]) == @[@["K", "Q"], @["A", "Q"]]
Исходный код Редактировать 
proc reverse[T](a: var openArray[T])

Обращает содержимое контейнера a.

См. также:

  • процедура reversed обращает срез и возвращает seq[T]
  • процедура reversed обращает и возвращает seq[T]

Пример:

var a = [1, 2, 3, 4, 5, 6]
a.reverse()
assert a == [6, 5, 4, 3, 2, 1]
a.reverse()
assert a == [1, 2, 3, 4, 5, 6]
Исходный код Редактировать 
proc reverse[T](a: var openArray[T]; first, last: Natural)

Обращает срез a[first..last].

Если передан недопустимый диапазон, генерируется IndexDefect.

См. также:

  • процедура reversed обращает срез и возвращает seq[T]
  • процедура reversed обращает и возвращает seq[T]

Пример:

var a = [1, 2, 3, 4, 5, 6]
a.reverse(1, 3)
assert a == [1, 4, 3, 2, 5, 6]
a.reverse(1, 3)
assert a == [1, 2, 3, 4, 5, 6]
doAssertRaises(IndexDefect, a.reverse(1, 7))
Исходный код Редактировать 
proc reversed[T](a: openArray[T]): seq[T] {.inline.}

Возвращает элементы a в обратном порядке.

См. также:

  • процедура reverse

Пример:

assert [10, 11, 12].reversed == @[12, 11, 10]
assert seq[string].default.reversed == @[]
Исходный код Редактировать 
proc reversed[T](a: openArray[T]; first: Natural; last: int): seq[T] {.inline,
    ...deprecated: "use: `reversed(toOpenArray(a, first, last))`".}
Устаревшее: используйте: `reversed(toOpenArray(a, first, last))`
Исходный код Редактировать 
proc rotatedLeft[T](arg: openArray[T]; dist: int): seq[T]

То же, что и rotateLeft, только с разницей, что не изменяет аргумент. Вместо этого создает новый seq.

См. также:

  • процедура rotateLeft для in-place версии этой процедуры
  • процедура rotatedLeft для версии, которая вращает диапазон

Пример:

var a = @[1, 2, 3, 4, 5]
a = rotatedLeft(a, 2)
assert a == @[3, 4, 5, 1, 2]
a = rotatedLeft(a, 4)
assert a == @[2, 3, 4, 5, 1]
a = rotatedLeft(a, -6)
assert a == @[1, 2, 3, 4, 5]
Исходный код Редактировать 
proc rotatedLeft[T](arg: openArray[T]; slice: HSlice[int, int]; dist: int): seq[
    T]

То же, что и rotateLeft, только с разницей, что не изменяет аргумент. Вместо этого создает новый seq.

Элементы за пределами slice останутся неизменными. Если передан недопустимый диапазон (HSlice), генерируется IndexDefect.

slice
Индексы диапазона элементов, которые должны быть повернуты.
dist
Расстояние в количестве элементов, на которое должны быть повернуты данные. Может быть отрицательным, может быть любым числом.

См. также:

  • процедура rotateLeft для in-place версии этой процедуры
  • процедура rotatedLeft для версии, которая вращает весь контейнер

Пример:

var a = @[1, 2, 3, 4, 5]
a = rotatedLeft(a, 1 .. 4, 3)
assert a == @[1, 5, 2, 3, 4]
a = rotatedLeft(a, 1 .. 3, 2)
assert a == @[1, 3, 5, 2, 4]
a = rotatedLeft(a, 1 .. 3, -2)
assert a == @[1, 5, 2, 3, 4]
Исходный код Редактировать 
proc rotateLeft[T](arg: var openArray[T]; dist: int): int {.discardable.}

То же, что и rotateLeft, но с аргументами по умолчанию для среза, чтобы эта процедура работала со всем arg, а не только с частью его.

См. также:

  • процедура rotateLeft для версии, которая вращает диапазон
  • процедура rotatedLeft для версии, которая возвращает seq[T]

Пример:

var a = [1, 2, 3, 4, 5]
a.rotateLeft(2)
assert a == [3, 4, 5, 1, 2]
a.rotateLeft(4)
assert a == [2, 3, 4, 5, 1]
a.rotateLeft(-6)
assert a == [1, 2, 3, 4, 5]
Исходный код Редактировать 
proc rotateLeft[T](arg: var openArray[T]; slice: HSlice[int, int]; dist: int): int {.
    discardable.}
Выполняет циклический сдвиг влево на диапазон элементов. Если вы хотите повернуть вправо, используйте отрицательное значение dist. В частности, rotateLeft вращает элементы по индексам slice на dist позиций.

Элемент по индексу slice.a + dist будет по индексу slice.a.
Элемент по индексу slice.b будет по индексу slice.a + dist - 1.
Элемент по индексу slice.a будет по индексу slice.b + 1 - dist.
Элемент по индексу slice.a + dist - 1 будет по индексу slice.b.

Элементы за пределами slice останутся неизменными. Время выполнения пропорционально slice.b - slice.a + 1. Если передан недопустимый диапазон (HSlice), генерируется IndexDefect.

slice
Индексы диапазона элементов, которые должны быть повернуты.
dist
Расстояние в количестве элементов, на которое должны быть повернуты данные. Может быть отрицательным, может быть любым числом.

См. также:

  • процедура rotateLeft для версии, которая вращает весь контейнер
  • процедура rotatedLeft для версии, которая возвращает seq[T]

Пример:

var a = [0, 1, 2, 3, 4, 5]
a.rotateLeft(1 .. 4, 3)
assert a == [0, 4, 1, 2, 3, 5]
a.rotateLeft(1 .. 4, 3)
assert a == [0, 3, 4, 1, 2, 5]
a.rotateLeft(1 .. 4, -3)
assert a == [0, 4, 1, 2, 3, 5]
doAssertRaises(IndexDefect, a.rotateLeft(1 .. 7, 2))
Исходный код Редактировать 
func sort[T](a: var openArray[T]; cmp: proc (x, y: T): int {.closure.};
             order = SortOrder.Ascending) {.effectsOf: cmp.}

Стандартная процедура сортировки Nim (реализация слиянием). Сортировка гарантированно устойчива (элементы с одинаковым значением сохраняют свой порядок) и в худшем случае гарантированно имеет сложность O(n log n). Сортирует по cmp в указанном order.

Текущая реализация использует итеративный алгоритм слияния. Использует временную последовательность длиной a.len div 2. Если вы не хотите предоставлять собственную cmp, вы можете использовать system.cmp или вызвать перегруженную версию sort, которая использует system.cmp.

sort(myIntArray, system.cmp[int])
# do not use cmp[string] here as we want to use the specialized
# overload:
sort(myStrArray, system.cmp)

Вы можете встраивать процедуры сравнения adhoc с помощью до-нотации. Пример:

people.sort do (x, y: Person) -> int:
  result = cmp(x.surname, y.surname)
  if result == 0:
    result = cmp(x.name, y.name)

См. также:

  • процедура sort
  • процедура sorted отсортированная по cmp в указанном порядке
  • процедура sorted
  • шаблон sortedByIt

Пример:

var d = ["boo", "fo", "barr", "qux"]
proc myCmp(x, y: string): int =
  if x.len() > y.len() or x.len() == y.len(): 1
  else: -1
sort(d, myCmp)
assert d == ["fo", "qux", "boo", "barr"]
Исходный код Редактировать 
proc sort[T](a: var openArray[T]; order = SortOrder.Ascending)

Короткая версия sort, которая использует system.cmp[T] в качестве функции сравнения.

См. также:

  • функция sort
  • процедура sorted отсортированная по cmp в указанном порядке
  • процедура sorted
  • шаблон sortedByIt
Исходный код Редактировать 
proc sorted[T](a: openArray[T]; cmp: proc (x, y: T): int {.closure.};
               order = SortOrder.Ascending): seq[T] {.effectsOf: cmp.}

Возвращает a отсортированную по cmp в указанном order.

См. также:

  • функция sort
  • процедура sort
  • шаблон sortedByIt

Пример:

let
  a = [2, 3, 1, 5, 4]
  b = sorted(a, system.cmp[int])
  c = sorted(a, system.cmp[int], Descending)
  d = sorted(["adam", "dande", "brian", "cat"], system.cmp[string])
assert b == @[1, 2, 3, 4, 5]
assert c == @[5, 4, 3, 2, 1]
assert d == @["adam", "brian", "cat", "dande"]
Исходный код Редактировать 
proc sorted[T](a: openArray[T]; order = SortOrder.Ascending): seq[T]

Короткая версия sorted которая использует system.cmp[T] в качестве функции сравнения.

См. также:

  • функция sort
  • процедура sort
  • шаблон sortedByIt

Пример:

let
  a = [2, 3, 1, 5, 4]
  b = sorted(a)
  c = sorted(a, Descending)
  d = sorted(["adam", "dande", "brian", "cat"])
assert b == @[1, 2, 3, 4, 5]
assert c == @[5, 4, 3, 2, 1]
assert d == @["adam", "brian", "cat", "dande"]
Исходный код Редактировать 
proc upperBound[T, K](a: openArray[T]; key: K;
                      cmp: proc (x: T; k: K): int {.closure.}): int {.
    effectsOf: cmp.}

Возвращает индекс первого элемента в a, который больше key, или последний, если такой элемент не найден. Другими словами, если у вас отсортированная последовательность, и вы вызываете insert(thing, elm, upperBound(thing, elm)), последовательность останется отсортированной. Предполагается, что a отсортирована по cmp.

Если передан неверный диапазон, возникает IndexDefect.

Эта версия использует cmp для сравнения элементов. Ожидаемые значения возврата такие же, как у system.cmp.

См. также:

  • процедура lowerBound отсортированная по cmp в указанном порядке
  • процедура lowerBound

Пример:

var arr = @[1, 2, 3, 5, 6, 7, 8, 9]
assert arr.upperBound(2, system.cmp[int]) == 2
assert arr.upperBound(3, system.cmp[int]) == 3
assert arr.upperBound(4, system.cmp[int]) == 3
arr.insert(4, arr.upperBound(3, system.cmp[int]))
assert arr == [1, 2, 3, 4, 5, 6, 7, 8, 9]
Исходный код Изменить 
proc upperBound[T](a: openArray[T]; key: T): int

Возвращает индекс первого элемента в a, который больше key, или последний, если такой элемент не найден. Другими словами, если у вас отсортированная последовательность, и вы вызываете insert(thing, elm, upperBound(thing, elm)), последовательность останется отсортированной. Предполагается, что a отсортирована.

Эта версия использует функцию сравнения по умолчанию cmp.

См. также:

  • процедура lowerBound отсортированная по cmp в указанном порядке
  • процедура lowerBound
Исходный код Изменить

Шаблоны

template sortedByIt(seq1, op: untyped): untyped

Удобный шаблон вокруг процедуры sorted для уменьшения набора текста.

Шаблон вставляет переменную it, которую вы можете использовать непосредственно в выражении.

Поскольку базовая процедура cmp() определена для кортежей, вы также можете выполнить вложенную сортировку.

См. также:

  • функция sort
  • процедура sort
  • процедура sorted отсортированная по cmp в указанном порядке
  • процедура sorted

Пример:

type Person = tuple[name: string, age: int]
var
  p1: Person = (name: "p1", age: 60)
  p2: Person = (name: "p2", age: 20)
  p3: Person = (name: "p3", age: 30)
  p4: Person = (name: "p4", age: 30)
  people = @[p1, p2, p4, p3]

assert people.sortedByIt(it.name) == @[(name: "p1", age: 60), (name: "p2",
    age: 20), (name: "p3", age: 30), (name: "p4", age: 30)]
# Nested sort
assert people.sortedByIt((it.age, it.name)) == @[(name: "p2", age: 20),
   (name: "p3", age: 30), (name: "p4", age: 30), (name: "p1", age: 60)]
Исходный код Изменить

© 2006–2024 Andreas Rumpf
Licensed under the MIT License.
https://nim-lang.org/docs/algorithm.html

Spec-Zone.ru

Настройки Оффлайн Что нового Помощь О нас
Spec-Zone .ru
спецификации, руководства, описания, API