LoginSignup
27
22

More than 5 years have passed since last update.

nimコレクション操作

Last updated at Posted at 2016-05-31

概要

nimのコレクション操作をコツコツと。

  • algorithm
  • tables
  • sets
  • lists
  • queues
  • critbits
  • intsets

以下メモ

同じ値で埋める(fill)

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var ary : array[0..3,int]
  # 範囲指定なし
  fill(ary,1)
  for x in ary:
    echo x
  # 範囲指定
  fill(ary,0,3,5)
  for x in ary:
    echo x
(stdout)
1
1
1
1
5
5
5
5

リバース

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var ary = @[1,2,3,4]
  echo ary
  ary.reverse
  echo ary
  var ary2 = ary.reversed
  echo ary2
(stdout)
@[1, 2, 3, 4]
@[4, 3, 2, 1]
@[1, 2, 3, 4]

検索(バイナリサーチ)

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var ary = @[1,2,3,4,5,6,7,8,9]
  echo ary.binarySearch(8)
  echo ary.smartBinarySearch(3)
(stdout)
7
2

lowerBound

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var ary = @[1,2,3,4,5,6]
  for x in 0..10 :
    echo x," ",ary.lowerBound(x)
(stdout)
0 0
1 0
2 1
3 2
4 3
5 4
6 5
7 6
8 6
9 6
10 6

ソート

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  # cmp関数でソート
  var ary = @[3,4,1,8,6,5,7,0,1]
  echo ary
  ary.sort(system.cmp[int])
  echo ary
(stdout)
@[3, 4, 1, 8, 6, 5, 7, 0, 1]
@[0, 1, 1, 3, 4, 5, 6, 7, 8]

ソート(procを渡す)

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var ary = @[3,4,1,8,6,5,7,0,1]
  ary.sort( proc (x,y:int) : int = cmp(x,y) )
  echo ary
(stdout)
@[0, 1, 1, 3, 4, 5, 6, 7, 8]

ソート(doを使ったソート)

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var ary = @[3,4,1,8,6,5,7,0,1]
  ary.sort do (x,y:int) -> int : result = cmp(x,y)
  echo ary
(stdout)
@[0, 1, 1, 3, 4, 5, 6, 7, 8]

ソート(sorted)

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  # doを使ったソート
  var ary = @[3,4,1,8,6,5,7,0,1]
  var ary2 = ary.sorted do (x,y:int) -> int :
    result = cmp(x,y)
  echo "original=",ary
  echo "sorted  =",ary2
  echo ary.isSorted(system.cmp[int])
  echo ary2.isSorted(system.cmp[int])
(stdout)
original=@[3, 4, 1, 8, 6, 5, 7, 0, 1]
sorted  =@[0, 1, 1, 3, 4, 5, 6, 7, 8]
false
true

順列 (prevPermutation)

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var ary = @[1,2,4,3]
  ary.prevPermutation
  echo ary
(stdout)
@[1, 2, 3, 4]

templateを使ったソート

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var ary = @[3,4,1,8,6,5,7,0,1]
  echo ary.sortedByIt(it)
(stdout)
@[0, 1, 1, 3, 4, 5, 6, 7, 8]

hashesによるハッシュを取得

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var name1 = "Mr.スポック"
  var name2 = "Mr.スポック"
  echo name1.hash == name2.hash
(stdout)
true

tables サンプル

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
#[
tableは、ハッシュキーを拡張したものっぽいです。
独自構造体?をキーにする場合は、hash関数を実装しないと動作しないようです。
]#
type
  Person = object
    firstName, lastName: string
proc hash(x: Person): Hash =
  ## Piggyback on the already available string hash proc.
  ##
  ## Without this proc nothing works!
  result = x.firstName.hash !& x.lastName.hash
  result = !$result
proc `$`(x: Person) : string =
  result = x.firstName
block:
  var
    salaries: Table[Person,int] = initTable[Person, int]()
    p1, p2, p3: Person
  p1.firstName = "Steven"
  p1.lastName = "Rogers"
  salaries[p1] = 30_000
  p2.firstName = "Tony"
  p2.lastName = "Stark"
  salaries[p2] = 40_000
  p3.firstName = "Bruce"
  p3.lastName = "Banner"
  echo "contains=",salaries.contains(p1)
  echo "get value=",salaries[p1]
  echo "length=",salaries.len
  echo "get or default=", salaries.getOrDefault(p3)
  ### toTableを使った初期化
  let salaries2: Table[Person,int] = {p1:30_000,p2:40_000}.toTable
  echo salaries == salaries2
  #salaries2[p3] = 10_000
  let salaries3: OrderedTable[Person,int] = {p1:30_000,p2:40_000}.toOrderedTable
  for k,v in salaries :
    echo k
  for k,v in salaries2 :
    echo k
  for k,v in salaries3 :
    echo k
(stdout)
contains=true
get value=30000
length=2
get or default=0
true
Steven
Tony
Steven
Tony
Steven
Tony

COuntTable キーのみで、その数をカウントする

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var count = initCountTable[string]()
  count.inc("DEC")
  count.inc("DEC")
  count.inc("ABC")
  count.inc("ABC")
  count.inc("ABC")
  echo count
  count.sort
  echo count
(stdout)
{ABC: 3, DEC: 2}
{ABC: 3, DEC: 2}

HashSet

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  # initSetで初期化
  var hashSet1: HashSet[string] = initSet[string]()
  hashSet1.incl("key1")
  hashSet1.incl("key2")
  echo "hashSet1=>",hashSet1
  echo "contains=>",hashSet1.contains("key1")
  # 取り除く
  hashSet1.excl("key1")
  hashSet1.excl("key2")
  echo "hashSet1=>",hashSet1
  # 再び追加
  hashSet1.incl("key1")
  hashSet1.incl("key2")
  # toSetで初期化
  var hashSet2 = ["key1","key2"].toSet
  echo "hashSet2=>",hashSet2
  echo "equals  =>",hashSet1 == hashSet2
  for x in hashSet1.items :
    echo "item=>",x
(stdout)
hashSet1=>{key2, key1}
contains=>true
hashSet1=>{}
hashSet2=>{key2, key1}
equals  =>true
item=>key2
item=>key1

OrderedHashSet(値を追加した順番を保持)

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  # initOrderedSetで初期化
  var hashSet1: OrderedSet[string] = initOrderedSet[string]()
  hashSet1.incl("key1")
  hashSet1.incl("key2")
  echo "hashSet1=>",hashSet1
  # toOrderedSetで初期化
  var hashSet2: OrderedSet[string] = ["key1","key2"].toOrderedSet
  echo "hashSet2=>",hashSet2
  #echo hashSet1 == hashSet2
  var hashSet3: OrderedSet[string] = initOrderedSet[string]()
  hashSet3.incl("key1")
  hashSet3.incl("key2")
  echo "equals=>",hashSet1 == hashSet3
(stdout)
hashSet1=>{key1, key2}
hashSet2=>{key1, key2}
equals=>true

双方向リンクリスト

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var list1 : DoublyLinkedList[int] = initDoublyLinkedList[int]()
  # 末尾に追加
  list1.append(1)
  list1.append(2)
  list1.append(3)
  list1.append(4)
  echo "list1=>",list1
  # 先頭に追加
  list1.prepend(4)
  list1.prepend(5)
  list1.prepend(6)
  list1.prepend(7)
  echo "list1=>",list1
  # 検索
  echo "find=>",list1.find(7).value
  # 削除
  list1.remove(list1.find(7))
  echo "list1=>",list1
(stdout)
list1=>[1, 2, 3, 4]
list1=>[7, 6, 5, 4, 1, 2, 3, 4]
find=>7
list1=>[6, 5, 4, 1, 2, 3, 4]

Queue

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var q : Queue[string] = initQueue[string]()
  q.enqueue("abc")
  q.add("def")
  q.add("ghi")
  echo "len=>",q.len
  echo "q  =>",q
  var v = q.dequeue()
  echo "v  =>",v
  echo "q  =>",q
  for v in q :
    echo "val=>",v
  echo "q  =>",q
(stdout)
len=>3
q  =>[abc, def, ghi]
v  =>abc
q  =>[def, ghi]
val=>def
val=>ghi
q  =>[def, ghi]

Crit-Bit ハッシュ ( http://blog.livedoor.jp/dankogai/archives/51853853.html )

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var r: CritBitTree[string]
  r["abc"] = "ABC"
  r["def"] = "DEF"
  echo "tree=>",r.contains("abc")
  for x in r.keys :
    echo "key=>",x
  for k,v in r :
    echo "key=>",k," val=>",v
(stdout)
tree=>true
key=>abc
key=>def
key=>abc val=>ABC
key=>def val=>DEF

intsets

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var intSet: IntSet = initIntSet()
  # キーを追加
  intSet.incl 1
  intSet.incl 2
  # ダンプ
  echo intSet
  for x in intSet.items :
    echo "key=>",x
  # 格納されているか?
  echo "contains(1)=>",intSet.contains(1)
  intSet.excl 1
  echo "contains(1)=>",intSet.contains(1)
  # containsOrInclを試す
  echo "contains(3)=>",intSet.contains(3)
  echo "           =>",intSet.containsOrIncl(3)
  echo "contains(3)=>",intSet.contains(3)
(stdout)
{1, 2}
key=>1
key=>2
contains(1)=>true
contains(1)=>false
contains(3)=>false
           =>false
contains(3)=>true

sequtils.concat

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  # サンプルのまんま
  let
    s1 = @[1, 2, 3]
    s2 = @[4, 5]
    s3 = @[6, 7]
    total = concat(s1, s2, s3)
  echo total
(stdout)
@[1, 2, 3, 4, 5, 6, 7]

sequtils.cycle

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    s = @[1, 2, 3]
    total = s.cycle(3)
  echo total
(stdout)
@[1, 2, 3, 1, 2, 3, 1, 2, 3]

sequtils.repeat

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    total1 = repeat(5, 3)
    total2 = repeat(@[1,2,3], 3)
  echo "total1=>",total1
  echo "total2=>",total2
(stdout)
total1=>@[5, 5, 5]
total2=>@[@[1, 2, 3], @[1, 2, 3], @[1, 2, 3]]

sequtils.deduplicate

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    dup1 = @[1, 1, 3, 4, 2, 2, 8, 1, 4]
    dup2 = @["a", "a", "c", "d", "d"]
    unique1 = deduplicate(dup1)
    unique2 = deduplicate(dup2)
  echo "unique1=>",unique1
  echo "unique2=>",unique2
(stdout)
unique1=>@[1, 3, 4, 2, 8]
unique2=>@[a, c, d]

sequtils.zip

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    short = @[1, 2, 3]
    long = @[6, 5, 4, 3, 2, 1]
    words = @["one", "two", "three"]
    zip1 = zip(short, long)
    zip2 = zip(short, words)
  echo "zip1=>", zip1
  echo "zip2=>", zip2
  echo "zip1[2].b=>", zip1[2].b
  echo "zip2[2].b=>", zip2[2].b
(stdout)
zip1=>@[(a: 1, b: 6), (a: 2, b: 5), (a: 3, b: 4)]
zip2=>@[(a: 1, b: one), (a: 2, b: two), (a: 3, b: three)]
zip1[2].b=>4
zip2[2].b=>three

sequtils.distribute

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let numbers = @[1, 2, 3, 4, 5, 6, 7]
  echo "(2      )=>",numbers.distribute(2)
  echo "(2,false)=>",numbers.distribute(2, false)
  echo "(3      )=>",numbers.distribute(3)
  echo "(3,false)=>",numbers.distribute(3, false)
  echo "(4      )=>",numbers.distribute(4)
  echo "(4,false)=>",numbers.distribute(4, false)
  echo "(5      )=>",numbers.distribute(5)
  echo "(5,false)=>",numbers.distribute(5, false)
  echo "(6      )=>",numbers.distribute(6)
  echo "(6,false)=>",numbers.distribute(6, false)
(stdout)
(2      )=>@[@[1, 2, 3, 4], @[5, 6, 7]]
(2,false)=>@[@[1, 2, 3, 4], @[5, 6, 7]]
(3      )=>@[@[1, 2, 3], @[4, 5], @[6, 7]]
(3,false)=>@[@[1, 2, 3], @[4, 5, 6], @[7]]
(4      )=>@[@[1, 2], @[3, 4], @[5, 6], @[7]]
(4,false)=>@[@[1, 2], @[3, 4], @[5, 6], @[7]]
(5      )=>@[@[1, 2], @[3, 4], @[5], @[6], @[7]]
(5,false)=>@[@[1, 2], @[3, 4], @[5, 6], @[7], @[]]
(6      )=>@[@[1, 2], @[3], @[4], @[5], @[6], @[7]]
(6,false)=>@[@[1, 2], @[3, 4], @[5, 6], @[7], @[], @[]]

sequtils.map

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    a = @[1, 2, 3, 4]
    b = map(a, proc(x: int): string = $x)
    c = a.map do (x:int) -> string : $(x+1)
  echo "b=>",b
  echo "c=>",c
(stdout)
b=>@[1, 2, 3, 4]
c=>@[2, 3, 4, 5]

sequtils.apply(var 引数が渡される) deprecatedらしいです。

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var a = @["1", "2", "3", "4"]
  echo a
  map(a, proc(x: var string) = x &= "42")
  echo a
(stdout)
@[1, 2, 3, 4]
@[142, 242, 342, 442]

sequtils.filter

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    colors = @["red", "yellow", "black"]
    f1 = filter(colors, proc(x: string) : bool = x.len < 6)
    f2 = filter(colors) do (x: string) -> bool : x.len > 5
  echo "f1=>",f1
  echo "f2=>",f2
  echo "abc".startsWith("a")
  let f3 = colors.map(
    proc(x:string)  : string = x & " is color"
  ).filter(
    proc (x:string) : bool = x.find("black") != -1
  )
  echo f3
(stdout)
f1=>@[red, black]
f2=>@[yellow]
true
@[black is color]

sequtils.keepIf

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var floats = @[13.0, 12.5, 5.8, 2.0, 6.1, 9.9, 10.1]
  keepIf(floats, proc(x: float): bool = x > 10)
  echo "floats=>",floats
(stdout)
floats=>@[13.0, 12.5, 10.1]

sequtils.delete

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let outcome = @[1,1,1,1,1,1,1,1]
  var dest = @[1,1,1,2,2,2,2,2,2,1,1,1,1,1]
  dest.delete(3, 8)
  echo "outcom=>",outcome
(stdout)
outcom=>@[1, 1, 1, 1, 1, 1, 1, 1]

sequtils.insert

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var dest = @[1,1,1,1,1,1,1,1]
  let
    src = @[2,2,2,2,2,2]
    outcome = @[1,1,1,2,2,2,2,2,2,1,1,1,1,1]
  dest.insert(src, 3)
  echo "dest=>",dest
(stdout)
dest=>@[1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1]

sequtils.all すべての要素にたいして条件を満たすかどうかをチェック

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let numbers = @[1, 4, 5, 8, 9, 7, 4]
  echo all(numbers, proc (x: int): bool = return x < 10)
  echo all(numbers, proc (x: int): bool = return x < 9)
(stdout)
true
false

sequtils.any どれか1つの要素にたいして条件を満たすかどうかをチェック

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let numbers = @[1, 4, 5, 8, 9, 7, 4]
  echo any(numbers, proc (x: int): bool = return x < 10)
  echo any(numbers, proc (x: int): bool = return x > 9)
## sequtils マクロ
(stdout)
true
false

filterIt

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    temperatures = @[-272.15, -2.0, 24.5, 44.31, 99.9, -113.44]
    acceptable = filterIt(temperatures, it < 50 and it > -10)
    notAcceptable = filterIt(temperatures, it > 50 or it < -10)
  echo "acceptable   =>",acceptable
  echo "notAcceptable=>",notAcceptable
(stdout)
acceptable   =>@[-2.0, 24.5, 44.31]
notAcceptable=>@[-272.15, 99.90000000000001, -113.44]

keepIfIf

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var candidates = @["foo", "bar", "baz", "foobar"]
  keepItIf(candidates, it.len == 3 and it[0] == 'b')
  echo "candidates=>",candidates
(stdout)
candidates=>@[bar, baz]

allIt

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let numbers = @[1, 4, 5, 8, 9, 7, 4]
  echo "numbers=>",allIt(numbers, it < 10)
  echo "numbers=>",allIt(numbers, it < 9)
(stdout)
numbers=>true
numbers=>false

anyIt

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let numbers = @[1, 4, 5, 8, 9, 7, 4]
  echo "numbers=>",anyIt(numbers, it > 8)
  echo "numbers=>",anyIt(numbers, it > 9)
(stdout)
numbers=>true
numbers=>false

toSeq

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    numeric = @[1, 2, 3, 4, 5, 6, 7, 8, 9]
    odd_numbers = toSeq(filter(numeric) do (x: int) -> bool:
      if x mod 2 == 1:
        result = true)
  echo "odd_numbers", odd_numbers
(stdout)
odd_numbers@[1, 3, 5, 7, 9]

foldl

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    numbers = @[5, 9, 11]
    addition = foldl(numbers, a + b)
    subtraction = foldl(numbers, a - b)
    multiplication = foldl(numbers, a * b)
    words = @["nim", "is", "cool"]
    concatenation = foldl(words, a & b)
  echo addition , " Addition is (((5)+9)+11)"
  echo subtraction  , " Subtraction is (((5)-9)-11)"
  echo multiplication , " Multiplication is (((5)*9)*11)"
  echo concatenation
(stdout)
25 Addition is (((5)+9)+11)
-15 Subtraction is (((5)-9)-11)
495 Multiplication is (((5)*9)*11)
nimiscool

foldl 初期値あり

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    numbers = @[0, 8, 1, 5]
    digits = foldl(numbers, a & (chr(b + ord('0'))), "")
  echo digits
(stdout)

foldr

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    numbers = @[5, 9, 11]
    addition = foldr(numbers, a + b)
    subtraction = foldr(numbers, a - b)
    multiplication = foldr(numbers, a * b)
    words = @["nim", "is", "cool"]
    concatenation = foldr(words, a & b)
  echo addition , " Addition is (5+(9+(11)))"
  echo subtraction , " Subtraction is (5-(9-(11)))"
  echo multiplication, " Multiplication is (5*(9*(11)))"
  echo concatenation
(stdout)
25 Addition is (5+(9+(11)))
7 Subtraction is (5-(9-(11)))
495 Multiplication is (5*(9*(11)))
nimiscool

mapIt

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    nums = @[1, 2, 3, 4]
    strings = nums.mapIt(4 * it)
  echo "strings=>",strings
(stdout)
strings=>@[4, 8, 12, 16]

mapIt

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  let
    nums = @[1, 2, 3, 4]
    strings = nums.mapIt(4 * it)
  echo "strings=>",strings
(stdout)
strings=>@[4, 8, 12, 16]

applyIt(自分自身に適用)

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
block:
  var nums = @[1, 2, 3, 4]
  nums.applyIt(it * 3)
  echo nums[0] + nums[3]
(stdout)
15

newSeqWith

import algorithm,tables,hashes,math
import sets,lists,critbits,sequtils,queues,intsets,strutils
import random
block:
  var seq2D = newSeqWith(4, newSeq[bool](4))
  seq2D[0][0] = true
  seq2D[1][0] = true
  seq2D[0][1] = true
  echo seq2D
  var seqRand = newSeqWith(4, random(4))
  echo seqRand
(stdout)
27
22
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
27
22