Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
4
Help us understand the problem. What is going on with this article?
@momeemt

Nimでジェネリックなアルゴリズムを使いこなそう algorithm

はじめに

こんにちは。高校2年の樅山です。
今回は、Nimでジェネリックなアルゴリズムを利用できる標準ライブラリである、algorithmをご紹介いたします。

この記事は、

の20日目に参加しています。

他の標準ライブラリを調べる👇

algorithm

algorithmは、汎用的に利用できるジェネリックなアルゴリズムを提供する標準ライブラリの一つです。

順列生成

与えられた配列から次の辞書式順列を生成します。生成できた場合、trueを、生成に失敗した場合、falseを返します。
可変変数に代入された配列を渡さなければなりません。生成された順列は、渡した可変変数に代入され、変更されます。
全ての要素からあり得る順列が生成されることが保証されているわけではなく、渡した配列から生成可能な順列のみが生成されます。1

次の順列を生成する

次の辞書式順列を生成するには、配列を nextPermutation に渡します。
このプロシージャは戻り値を返しますが、discardableなプロシージャなので、discardキーワードなしでも戻り値を捨てることができます。

nextPermutation
proc nextPermutation[T](x: var openArray[T]): bool {.discardable.}

実行例

次の順列を生成する
import algorithm

var arr = @[1, 2, 3]
echo arr
while arr.nextPermutation():
  echo arr
stdout
(stdout)
@[1, 2, 3]
@[1, 3, 2]
@[2, 1, 3]
@[2, 3, 1]
@[3, 1, 2]
@[3, 2, 1]

前の順列を生成する

前の辞書式順列を生成するには、配列を prevPermutation に渡します。
discardableなプロシージャなので、戻り値を暗黙に捨てることができます。

prevPermutation
proc prevPermutation[T](x: var openArray[T]): bool {.discardable.}

実行例

前の順列を生成する
import algorithm

var arr = @[3, 2, 1]
echo arr
while arr.prevPermutation():
  echo arr
stdout
(stdout)
@[3, 2, 1]
@[3, 1, 2]
@[2, 3, 1]
@[2, 1, 3]
@[1, 3, 2]
@[1, 2, 3]

逆順

与えられた配列から、逆順の配列を生成して返します。

全て逆順にする

与えられた配列の要素を、全て逆順にした配列を生成して返すには、配列を reversed に渡します。

reversed
proc reversed[T](a: openArray[T]): seq[T]

実行例

全て逆順にする
import algorithm

let arr = [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
echo arr.reversed
stdout
(stdout)
@[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

部分配列を逆順にする

配列 arr のインデックス first からインデックス last のスライスを切り出し、それを逆順にして返します。
つまり、arr[first..last]の逆順を生成し、返します。
ただし、範囲外のインデックスを渡した場合には、IndexDefect 例外が発生します。

reversed
proc reversed[T](a: openArray[T]; first: Natural; last: int): seq[T]

実行例

部分配列を逆順にする
import algorithm

let arr = [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
echo arr.reversed(5, 10)
stdout
(stdout)
@[5, 6, 7, 8, 9, 10]

ソート

与えられた配列の要素を、ある規則に則って並べ直すことを ソートする といいます。

戻り値のない昇降ソート

sortに、可変変数に代入された配列と、Ascendingを渡すことで、要素を 小さい順 に並べ替えます。これを、昇順ソートと呼びます。
また、Descendingを渡すことで、要素を 大きい順 に並べ替えます。これを、降順ソートと呼びます。

AscendingDescendingとは、algorithmモジュールで定義されている、SortOrder型という列挙型の要素です。

実行例

昇順ソート
import algorithm

var arr = @[7, 2, 1, 4, 9, 3, 10, 8, 5, 6]
arr.sort(Ascending)

echo arr
stdout
(stdout)
@[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

実行例

降順ソート
import algorithm

var arr = @[7, 2, 1, 4, 9, 3, 10, 8, 5, 6]
arr.sort(Descending)

echo arr
stdout
(stdout)
@[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

また、SortOrder型の引数は、デフォルト値 Ascending が設定されているため、昇順ソートの場合は引数を渡さなくてもソートされます。

実行例

SortOrderを省略する
import algorithm

var arr = @[7, 2, 1, 4, 9, 3, 10, 8, 5, 6]
arr.sort

echo arr
stdout
(stdout)
@[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

戻り値のあるソート

sortedに、配列とAscendingを渡すことで、要素を 小さい順 に並べ替えます。これを、昇順ソートと呼びます。
また、Descendingを渡すことで、要素を 大きい順 に並べ替えます。これを降順ソートと呼びます。

sortプロシージャと異なる点は、sortedはソートした配列を戻り値として返すことで、これによって渡す配列は不変変数で構いません。
より、sortedの方が関数型プログラミングの手法に近い形でソートを行うことができます。

AscendingDescendingとは、algorithmモジュールで定義されている、SortOrder型という列挙型の要素です。

実行例

昇順ソート
import algorithm

const arr = @[7, 2, 1, 4, 9, 3, 10, 8, 5, 6]
echo arr.sorted(Ascending)
stdout
(stdout)
@[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

実行例

降順ソート
import algorithm

const arr = @[7, 2, 1, 4, 9, 3, 10, 8, 5, 6]
echo arr.sorted(Descending)
stdout
(stdout)
@[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

また、SortOrder型の引数は、デフォルト値 Ascending が設定されているため、昇順ソートの場合は引数を渡さなくてもソートされます。

実行例

SortOrderを省略する
import algorithm

const arr = @[7, 2, 1, 4, 9, 3, 10, 8, 5, 6]
echo arr.sorted
stdout
(stdout)
@[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

カスタムソート

ソートの比較プロシージャにLambda式を渡すことで、ソート方法をカスタムすることができます。

sorted proc でカスタムソート

sorted プロシージャに配列とラムダ式、SortOrder(デフォルト値 Ascending が設定されているため省略可能)を渡すと、指定した手順でソートを行い、新しいソート済み配列を返します。

実行例

オブジェクトをフィールドでソートする
import algorithm

type Person = object
  height: int
  weight: int

proc person(height, weight: int): Person =
  result = Person(height: height, weight: weight)

const
  person1 = person(170, 55)
  person2 = person(162, 50)
  person3 = person(165, 49)
  people = @[person1, person2, person3]

const cprHeight = proc (x, y: Person): int =
  result = system.cmp(x.height, y.height)

echo people.sorted(cprHeight)
stdout
(stdout)
@[(height: 162, weight: 50), (height: 165, weight: 49), (height: 170, weight: 55)]

ここで、比較プロシージャに用いた cmp を確認しておきましょう。

cmpは、systemモジュールで定義されているプロシージャで、次のように定義されています。
二つの値を渡し、等しければ 0 を、一つ目の方が大きければ 1 を、二つ目の方が大きければ -1 を返します。

cmpの定義
proc cmp*[T](x, y: T): int =
  if x == y: return 0
  if x < y: return -1
  return 1

sort func でカスタムソート

sort 関数(func) に可変配列に代入された配列とラムダ式、SortOrder(デフォルト値 Ascending が設定されているため省略可能)を渡すと、指定した手順でソートを行い、渡した配列に破壊的変更を行います。戻り値はありません。

実行例

sort関数でカスタムソート
import algorithm

type Person = object
  height: int
  weight: int

proc person(height, weight: int): Person =
  result = Person(height: height, weight: weight)

var
  person1 = person(170, 55)
  person2 = person(162, 50)
  person3 = person(165, 49)
  people = @[person1, person2, person3]

const cprWeight = proc (x, y: Person): int =
  result = system.cmp(x.weight, y.weight)

people.sort(cprWeight)

echo people
stdout
(stdout)
@[(height: 165, weight: 49), (height: 162, weight: 50), (height: 170, weight: 55)]

ソート判定

ソートされているかを確かめる

isSortedに、配列と、SortOrderを渡すことで、ソートされているか確かめることができます。
SortOrder型の引数はデフォルト値が Ascending に設定されており、省略可能です。

実行例

ソートされているかを確かめる
import algorithm

const
  arr1 = @[1, 2, 3, 4, 5]
  arr2 = @[2, 4, 1, 3, 5]
  arr3 = @[5, 4, 3, 2, 1]

echo arr1.isSorted
echo arr2.isSorted
echo arr3.isSorted(Descending)
stdout
(stdout)
true
false
true

カスタムソートされているかをチェックする

isSorted 関数 (func) に、配列と、判定ラムダ式、SortOrderを渡すことで、カスタムソートされているかを確かめることができます。

実行例

カスタムソートされているかを確かめる
import algorithm

type Person = object
  height: int
  weight: int

proc person(height, weight: int): Person =
  result = Person(height: height, weight: weight)

const
  person1 = person(170, 55)
  person2 = person(162, 50)
  person3 = person(165, 49)
  people = @[person2, person3, person1]

const cprHeight = proc (x, y: Person): int =
  result = system.cmp(x.height, y.height)

echo people.isSorted(cprHeight)
stdout
(stdout)
true

要素を基にソートする

sortedByItテンプレートを用いると、テンプレート内部のみで利用できるローカル変数 it 2 を用いて、オブジェクトの要素を基にソートすることができます。
配列、基にする要素を渡す必要があります。

実行例

heightをソートする
import algorithm

type Person = object
  height: int
  weight: int

proc person(height, weight: int): Person =
  result = Person(height: height, weight: weight)

const
  person1 = person(170, 55)
  person2 = person(162, 50)
  person3 = person(165, 49)
  people = @[person1, person2, person3]

echo people.sortedByIt(it.height)
stdout
@[(height: 162, weight: 50), (height: 165, weight: 49), (height: 170, weight: 55)]

正負反転を行う

*演算子に、整数と、SortOrderを渡すことで、正負反転処理を行うことができます。

SortOrderが、Ascendingのとき、正負反転を行いません。
Descendingのとき、正負反転を行います。

実行例

正負反転を行う
import algorithm

echo `*`(1030, Ascending)
echo `*`(-1030, Ascending)
echo `*`(1030, Descending)
echo `*`(-1030, Descending)
stdout
(stdout)
1030
-1030
-1030
1030

探索

upperBoundlowerBoundbinarySearchという3つの探索アルゴリズムが提供されています。全てのプロシージャには、昇順にソートされた配列を渡す必要があります。

与えた値より大きい値を持つ要素が最初に出現する配列のインデックスを得る

upperBoundに、昇順にソートされた配列と値を与えると、計算量 $O(log n)$ で二分探索を行い、与えた値より大きいの値を持つ要素が出現する、配列のインデックスを得ることができます。

実行例

upperBound
import algorithm

const arr = @[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

echo upperBound(arr, 5)
echo upperBound(arr, 7)
stdout
(stdout)
5
7

比較ラムダ式を与える

upperBoundにも、比較ラムダ式を与えて、比較方法をカスタムすることができます。
本当に、upperBoundが計算量 $O(log n)$ で計算しているかどうかを確かめてみます。

実行例

比較ラムダ式を与える
import algorithm

const
  arrLm = proc (): seq[int] =
    result = @[]
    for i in 1..1000:
      result.add i
  arr = arrLm()
  cmpLambda = proc (x, y: int): int =
    echo x
    result = cmp(x, y)

discard upperBound(arr, 5, cmpLambda)
stdout
(stdout)
501
251
126
63
32
16
8
4
6
5

比較回数は10回であり、$log_2(1000) = 9.96578428466...$ より、計算量は $log n$ であることがわかります。

与えた値以下の値を持つ要素が最初に出現する配列のインデックスを得る

lowerBoundに、昇順にソートされた配列と値を与えると、計算量 $O(log n)$ で二分探索を行い、与えた値以下の値を持つ要素が出現する、配列のインデックスを得ることができます。

実行例

lowerBound
import algorithm

const arr = @[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

echo lowerBound(arr, 5)
echo lowerBound(arr, 7)
stdout
(stdout)
4
6

比較ラムダ式を与える

lowerBoundにも、比較ラムダ式を与えて、比較方法をカスタムすることができます。
本当に、lowerBoundが計算量 $O(log n)$ で計算しているかどうかを確かめてみます。

実行例

比較ラムダ式を与える
import algorithm

const
  arrLm = proc (): seq[int] =
    result = @[]
    for i in 1..2000:
      result.add i
  arr = arrLm()
  cmpLambda = proc (x, y: int): int =
    echo x
    result = cmp(x, y)

discard lowerBound(arr, 12, cmpLambda)
stdout
(stdout)
1001
501
251
126
63
32
16
8
12
10
11

比較回数は11回であり、$log_2(2000) = 10.965784284662...$ より、計算量は $log n$ であることがわかります。

与えた値を持つ要素が最初に出現する配列のインデックスを得る

binarySearchに、昇順にソートされた配列と値を与えると、計算量 $O(log n)$ で二分探索を行い、与えた値を持つ要素が出現する、配列のインデックスを得ることができます。
また、もし与えた値を持つ要素が存在しなかった場合は、-1 を返します。

実行例

binarySearch
import algorithm

const arr = @[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

echo binarySearch(arr, 12)
echo binarySearch(arr, 7)
stdout
(stdout)
-1
6

比較ラムダ式を与える

binarySearchにも、比較ラムダ式を与えて、比較方法をカスタムすることができます。
本当に、binarySearchが計算量 $O(log n)$ で計算しているかどうかを確かめてみます。

実行例

比較ラムダ式を与える
import algorithm

const
  arrLm = proc (): seq[int] =
    result = @[]
    for i in 1..100000:
      result.add i
  arr = arrLm()
  cmpLambda = proc (x, y: int): int =
    echo x
    result = cmp(x, y)

discard binarySearch(arr, 99999, cmpLambda)
stdout
(stdout)
50001
75001
87501
93751
96876
98439
99220
99611
99806
99904
99953
99977
99989
99995
99998
100000
99999

比較回数は17回であり、$log_2(100000) = 16.609640474436...$ より、計算量は $log n$ であることがわかります。

配列を埋める

fillに、配列と値を渡すことで、配列の要素を指定した値に置き換えることができます。

全て埋める

fillに、可変変数に代入された配列と、値を渡すことで、配列の全ての要素を指定した値に置き換えることができます。

実行例

全て埋める
import algorithm

var arr: array[10, int]
arr.fill(2003)
echo arr
stdout
(stdout)
[2003, 2003, 2003, 2003, 2003, 2003, 2003, 2003, 2003, 2003]

部分的に埋める

fillに、可変変数に代入された配列と、範囲インデックスと、値を渡すことで、配列の要素を部分的に指定した値で置き換えることができます。

実行例

部分的に埋める
import algorithm

var arr: array[10, int]
arr.fill(2, 7, 1192)
echo arr
stdout
(stdout)
[0, 0, 1192, 1192, 1192, 1192, 1192, 1192, 0, 0]

分配法則

productに、多次元配列を渡すことで、分配法則的な計算を行うことができます。
配列が複雑すぎると、計算量が爆発する可能性があります。

実行例

import algorithm

echo product(@[@[1, 2, 3, 4], @[5, 6, 7]])
stdout
(stdout)
@[@[4, 7], @[3, 7], @[2, 7], @[1, 7], @[4, 6], @[3, 6], @[2, 6], @[1, 6], @[4, 5], @[3, 5], @[2, 5], @[1, 5]]

回転

rotateLeftに、配列を渡すことで、要素を左向きに回転させることができます。

全体を回転させる

rotateLeftに、可変変数に代入された配列と、回転回数を与えることで、配列全体を左向きに回転させることができます。

実行例

全体を回転させる
import algorithm

var arr = @[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
arr.rotateLeft(5)
echo arr
stdout
(stdout)
@[6, 7, 8, 9, 10, 1, 2, 3, 4, 5]

部分的に回転させる

rotateLeftに、可変変数に代入された配列と、範囲インデックスと、回転回数を与えることで、配列を部分的に左向きに回転させることができます。

実行例

部分的に回転させる
import algorithm

var arr = @[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
arr.rotateLeft(2 .. 8, 4)
echo arr
stdout
@[1, 2, 7, 8, 9, 3, 4, 5, 6, 10]

終わりに

ソートや二分探索、さらには回転や分配法則など(使いどころは謎ですが)、自分で定義するにはいちいち面倒なアルゴリズムが標準ライブラリで提供されているとはとても嬉しいことです。
ぜひ、活用して、効率的な Nimプログラミングに役立ててみてください。


  1. 例えば、辞書式順列で最も後ろの並び方を渡した時、次の順列は生成できません。 

  2. 内部的には、テンプレートの untyped 引数の性質である 遅延評価を利用しています。itは、コンパイル時にはいったん無視され、その後テンプレート内で値が確定した後に書き換えられます。 

4
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
momeemt
こんにちは。高校3年生の樅山です。 Nimの記事を書いています。 標準ライブラリの解説をするのが好きです。
nim-in-japan
Nim言語の日本コミュニティです。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
4
Help us understand the problem. What is going on with this article?