Visual StudioでCMakeを使ってライブラリをインストール

最近, やりたくないけどwindowsで作業せざるをえず, 色々と詰まってしまっていたのでメモしておく. qpOASESをwindowsにインストールする場合を例にして, visual studioでビルドからインストールするまでの手順をメモ.

1. CMakeのインストール

CMakeを入れる. 普通にバイナリインストールでOK.
Download | CMake

pathを通しておくことを忘れずに.

2. qpOASESのダウンロード

zipファイルをダウンロード.
QpoasesDownload – qpOASES

展開しておく.

3. visual studio用コマンドプロンプトを開く

スタートメニューから探していくと見つかる.
開いたら, qpOASESのフォルダ(CMakeLists.txtがあるところ)までcdする.

4. CMake configuration

続いて以下のコマンドを叩く.

mkdir build
cd build
cmake -G "Visual Studio 14 2015" ..

buildフォルダの中に, ビルド&インストール用のvisual studioプロジェクトファイルが生成される.

5. ビルド&インストール

・visual studioを管理者権限で開く
・buildフォルダ内の ALL_BUILDプロジェクトを開く
・ビルドモードをDebugからReleaseに変える
・ALL_BUILDをビルドする
・INSTALLをビルドする

エラーがなければ, ¥C:/Program Files 以下にqpOASESフォルダが現れ, 中にincludeフォルダとlibフォルダが生成される.

6. qpOASESを使う

5. で生成されたincludeファイルとlibファイルをインクルードおよびリンクして使う

参考

#53 (Failed to install qpOASES on Windows using Visual Studio) – qpOASES

ハッシュ探索 (アルゴリズムクイックリファレンス 5.3)

ハッシュ探索.
ハッシュテーブルを作って, そこから探索する. ハッシュテーブルに複数の要素が格納されると衝突が起きるので, 対策が必要. 衝突した要素を同じハッシュ表の空いている部分に入れておく方法がわかりやすい. 衝突が起きてハッシュ表の適切な場所に格納されなかった要素は線形探索等で探索する.

参考:
necophys.hatenablog.com

計算量

• 最良 O(1)
• 平均 O(1)
• 最悪 O(n)

サンプルコード

function hash_store(A, hash_key)

    H = zeros(hash_key+1)
    for x in A
        k = Int(x % hash_key)
        while H[k+1] != 0
          k = (k + 1) % hash_key
        end
        H[k+1] = x
    end

    return H

end

function hash_search(ls, x, hash_key)

    k = Int(x % hash_key)
    while ls[k+1] != 0
        if ls[k+1] == x
            return k + 1
        else
            k = (k + 1) % hash_key
        end
    end

    return nothing

end

function hashSearch(A, hash_key, t)

    hash_array = hash_store(A, hash_key)
    hash_index = hash_search(hash_array, t, hash_key)

    return hash_array, hash_index

end

function main()

  # list to be sorted
  rng = MersenneTwister(1234);
  list_size = 10
  A = shuffle(rng, Vector(1:list_size))

  # Search
  search_num = 10
  hash_array, index_found = @time hashSearch(A, 11, search_num)

  print("Search for : ")
  println(search_num)

  print("Found index: ")
  print(index_found)
  println(" (in hash array)")

  print("Found value is ... ")
  println(hash_array[index_found])

end

if contains(@__FILE__, PROGRAM_FILE)
    main()
end

二分探索 (アルゴリズムクイックリファレンス 5.2)

続いて二分探索.
リストの中央値の値と探索したい値を大小比較して, 中央値が大きければ, 中央値より小さい領域を探索. 大きければ, 中央値より大きい領域を探索. この処理を繰り返す. 二分探索実行時にはリストは整列されている必要がある.

計算量

• 最良 O(1)
• 平均 O(log n)
• 最悪 O(log n)

function binarySearch(A, t)

  low = 1
  high = length(A)
  while low <= high
    mid = Int(round((low + high) / 2))
    if t == A[mid]
      return mid
    elseif t < A[mid]
      high = mid - 1
    elseif t > A[mid]
      low = mid + 1
    end
  end
  return false

end

function main()

  # list to be sorted
  rng = MersenneTwister(1234);
  list_size = 1e7
  A = Vector(1:list_size) # The list is to be sorted for binary search

  # Search
  search_num = 3000
  index_found = @time binarySearch(A, search_num)

  print("Search for : ")
  println(search_num)

  print("Found index: ")
  println(index_found)

  print("Found value is ... ")
  println(A[index_found])

end

if contains(@__FILE__, PROGRAM_FILE)
    main()
end

実行結果

0.000010 seconds
Search for : 3000
Found index: 3000
Found value is ... 3000.0

逐次探索 (アルゴリズムクイックリファレンス 5.1)

続いて逐次探索.
その名の通り, リストの最初から終わりまで一致するものを探索する.

計算量

• 最良 O(1)
• 平均 O(n)
• 最悪 O(n)

サンプルコード

function sequentialSearch(A, t)

  for (index, value) in enumerate(A)
    if value == t
      return index
    end
  end
  return false

end

function main()

  # list to be sorted
  rng = MersenneTwister(1234);
  list_size = 1e7
  A = shuffle(rng, Vector(1:list_size))

  # Search
  search_num = list_size/2
  index_found = @time sequentialSearch(A, search_num)

  print("Search for : ")
  println(search_num)

  print("Found index: ")
  println(index_found)

  print("Found value is ... ")
  println(A[index_found])

end

if contains(@__FILE__, PROGRAM_FILE)
    main()
end

実行結果

0.001650 seconds
Search for : 5000000
Found index: 2045999
Found value is ... 5000000

マージソート (アルゴリズムクイックリファレンス 4.7)

今日はマージソート.
マージソートではまず, 全体を大きさが等しい二つの集合に分けて, それぞれをソートする. そして, ソートされた集合をマージする.

例のごとく以下のページがわかりやすい.
www.codereading.com

#
# Merge Sort
#

function mergeSort(A)

  Anew = copy(A)
  mergesort_array(Anew,  A,  1,  length(A)+1)

end

function mergesort_array(A, result, left, right)

  if right - left < 2
    return
  end
  if right - left == 2
    if result[left] > result[left+1]
      result[left],  result[left+1] = result[left+1], result[left]
    end
    return
  end

  mid = Int(round((right + left) / 2))
  mergesort_array(result, A, left,  mid)
  mergesort_array(result, A, mid, right)

  i = left
  j = mid
  idx = left
  while idx < right
    if j >= right || (i < mid && A[i] < A[j])
      result[idx] = A[i]
      i = i + 1
    else
      result[idx] = A[j]
      j = j + 1
    end
    idx = idx + 1
  end

end

function main()

  # list to be sorted
  rng = MersenneTwister(1234);
  A = shuffle(rng, Vector(1:100))
  Aorigin = copy(A)

  # sorting
  @time mergeSort(A)

  print("The original list: ")
  println(Aorigin)

  print("The sorted list: ")
  println(A)

end

if contains(@__FILE__, PROGRAM_FILE)
    main()
end

バケットソート (アルゴリズムクイックリファレンス 4.6)

今日はバケットソート.
本よりこっちの方がわかりやすい.
www.codereading.com

#
# Bucket Sort
#

function bucketSort(A, min_bucket, max_bucket)
    buckets = []
    for i in min_bucket:max_bucket
        push!(buckets, nothing)
    end

    for i in A
        buckets[A[i]] = A[i]
    end

    x = 1
    for i in min_bucket:max_bucket
        if buckets[i] != nothing
            A[x] = buckets[i]
            x = x + 1
        end
    end
end

function sortValues(A)

  n = length(A)
  bucketSort(A, 1, n)

end

function main()

  # list to be sorted
  A = [15,  9,  8,  1,  4,  11,  7,  12,  13,  6,  5,  3,  16,  2,  10,  14]

  # sorting
  @time sortValues(A)
  print(A)

end

if contains(@__FILE__, PROGRAM_FILE)
    main()
end

ヒープソート (アルゴリズムクイックリファレンス 4.3)

ヒープソート.
トーナメント方式でソートしていくアルゴリズム (とりあえず一言だけ添えとけ感がすごい...けれども, 書かないよりはマシということで, 今年は質より量で定期更新を意識していきたい. 質は量に伴って上がってくると期待して.)

#
# Heap Sort
#

function sortValues(A)

  buildHeap(A)

  n = length(A)
  i = n
  while i > 0

    tmp = A[1]
    A[1] = A[i]
    A[i] = tmp

    heapify(A, 1, i)

    i = i - 1
  end

end

function buildHeap(A)

  n = length(A)
  i = Int(n/2)
  while i > 0

    heapify(A, i, n)

    i = i - 1
  end

end

function heapify(A, idx, idx_max)
  largest = idx
  left = 2 * (idx-1) + 1
  right = 2 * (idx-1) + 2

  if left < idx_max && A[left] > A[idx]
    largest = left
  end
  if right < idx_max && A[right] > A[largest]
    largest = right
  end
  if largest != idx
    tmp = A[idx]
    A[idx] = A[largest]
    A[largest] = tmp
    heapify(A,  largest,  idx_max)
  end
end

# list to be sorted
A = [15,  9,  8,  1,  4,  11,  7,  12,  13,  6,  5,  3,  16,  2,  10,  14]

# sorting
@time sortValues(A)

print(A)

ソースコードは下記のレポジトリにまとめていきます.
github.com