オープンソース図書館システム Next-L Enjuの紹介

この記事は klis advent calendarの9日目の記事です.
adventar.org

klis13 & slis17のhimktです.
twitter.com

ぼくはとても図書館が好きなので,今日は図書館,とりわけ図書館システムの話をします.
図書館も日々の情報技術の進歩の影響を受けていて,電子化に関する取り組みなどが多くなされています.
スタンフォード大学の電子資料メインの図書館の話などを聞いたことがある方もいらっしゃるかもしれません.
www.mercurynews.com

このような先進的な図書館が出現し始めていることは事実です.
しかし依然として図書館のシステムに対して「古い」という印象を受けるかたは多いのではないでしょうか.
(図書館のシステムというと骨董品のようなPCの上で動作する様子を想像しませんか?)
地方の公共図書館などの資料検索システムや貸し出しシステムはリプレースされずに古いものが使われ続けていることが多いです.
(出身地域の公共図書館システムに基づく主観的な意見)

Next-Lは,このような図書館システムの現状を変化させる可能性のあるプロジェクトです.
Next-L Enju - Project Next-L
Next-Lはオープンソースソフトウェアです.
ソースコードや議論が公開された状態で開発が行われています.
プログラムのソースコードGitHubで閲覧できます.
github.com
プログラムはRuby(Ruby on Rails)で書かれているため,klisの学生には比較的とっつきやすいです.
プログラムにバグを見つけた場合はGitHubのissueというページに報告をすることができます.
(開発に関わっている方々が反応してくれます.)
github.com
動作のデモは以下のページで確認可能です.
えんじゅ図書館 - Next-L Enju Leaf


Next-Lの図書館システムはいくつかの企業や大学図書館公共図書館で実際に稼働しています.
詳しくはホームページを参照してください.
FrontPage - Project Next-L


Next-Lは月に一回程度筑波大学春日エリアで開発ワークショップを行なっています.
コアの開発メンバーにはklisの方々なら統計の授業でお世話になったであろう高久先生がいらっしゃいます.
twitter.com
開発への貢献に関心を持った方は,先生に質問をしに行けば快く対応してくださると思います(無責任な発言).

個人的に,図書館システムもより短い周期で進化していくべきだと思っていて,Next-Lはこれを実現するプロジェクトだと思います.
開発ワークショップにも数回しか参加していない身の上で身内ぶった説明をしていることに罪悪感を覚えますが,
オープンソースの図書館システムの試みをklisの方々に知っていただければうれしいです.
図書館に携わりたいがプログラミングもしたいという方々は一度覗きにいくとよいと思います.

以上,12/9の記事でした.引き続きklis advent calendarをお楽しみください.

2017/10/24 ~ 2017/12/1

更新サボってたら記憶が消えた

latexのalign環境で行列の下に説明文を追加する

DeepLearning Bookの式7.46を再現したかった.
mathopによって実現した.
ただ,行列のサイズが異なる場合説明文が上下で微妙にずれてしまう問題が残っている.
今回でいえば \mathbf{x}だけ少し下にずれている.
どうすれば良いのかはあとで調べる.

\mathop{\begin{bmatrix}
  18 \\
  5  \\
  15 \\
  -9 \\
  -3
\end{bmatrix}}_{\textstyle \mathbf{y}} &=& 
\mathop{\begin{bmatrix}
  4 & 0 &  0 & -2 &  0 &  0 \\
  0 & 0 & -1 &  0 &  3 &  0 \\
  0 & 5 &  0 &  0 &  0 &  0 \\
  1 & 0 &  0 & -1 &  0 & -4 \\
  1 & 0 &  0 &  0 & -5 &  0
\end{bmatrix}}_{\textstyle \mathbf{A}} & &
\mathop{\begin{bmatrix}
  2 \\
  3 \\
  -2 \\
  -5 \\
  1 \\
  4
\end{bmatrix}}_{\textstyle \mathbf{x}}
\end{align}

  \begin{align}
    \mathop{\begin{bmatrix}
        18 \\
        5  \\
        15 \\
        -9 \\
        -3
      \end{bmatrix}}_{\textstyle \mathbf{y}} &=& 
    \mathop{\begin{bmatrix}
          4 & 0 &  0 & -2 &  0 &  0 \\
          0 & 0 & -1 &  0 &  3 &  0 \\
          0 & 5 &  0 &  0 &  0 &  0 \\
          1 & 0 &  0 & -1 &  0 & -4 \\
          1 & 0 &  0 &  0 & -5 &  0
        \end{bmatrix}}_{\textstyle \mathbf{A}} & &
    \mathop{\begin{bmatrix}
        2 \\
        3 \\
        -2 \\
        -5 \\
        1 \\
        4
      \end{bmatrix}}_{\textstyle \mathbf{x}}
  \end{align}

tex.stackexchange.com

Amazing Mazes

入力データからグラフを作る部分を慎重に作る.
あとは幅優先or深さ優先を書く.

```cpp
//#define _GRIBCXX_DEBUG
#include
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;


class Graph {
public:
int n_node;
vector> edge;

Graph(int n_node) : n_node(n_node){
edge.resize(n_node);
};

void add_edge(int i, int j);
};

void Graph::add_edge(int i, int j) {
// cout << i << ", " << j << endl;
edge[i].push_back(j);
}

int main() {
int w, h, c;
int block;


while (cin >> w >> h, w) {
Graph g(w*h);

rep (i, 2*h-1) {
if (i%2 == 0) {
// yoko
rep (j, w-1) {
cin >> block;
int offset = w * (i / 2);
int c = offset + j;
if (block == 0) g.add_edge(c, c+1);
if (block == 0) g.add_edge(c+1, c);
}
}
else {
// tate
rep (j, w) {
int offset = w * *1 {
int current = que.front(); que.pop();

for (int next_ : g.edge[current]) {
if (cost[next_] == 1001001001) {
que.push(next_);
cost[next_] = cost[current] + 1;
// cout << "current: " << current << ", next: " << next_ << endl;
// cout << "current_cost: " << cost[current] << endl;
}
}
}

if (cost[w*h-1] == 1001001001) {
cout << 0 << endl;
}
else {
cout << cost[w*h-1] << endl;
}
}
return 0;
}
```

Amazing Mazes | Aizu Online Judge

Pythonにはオブジェクトの`__dict__`を返してくれる`vars`という組み込み関数がある.
これを使うと`argparse`の`Namespace`オブジェクトを辞書型のオブジェクトとして持ちたいときに便利.

stackoverflow.com

エイリアスを張っているコマンドに対しても呼び出し元を確認したいときは`type`コマンドが使える.

unix.stackexchange.com

PRMLの実装

github.com

Jupyter Notebook(Python)とPythonのプログラムがある.


argparseのdescriptionの中で改行する

RawTextHelpFormatterというクラスをformatterとして指定する必要がある.

stackoverflow.com

*1:i - 1) / 2); cin >> block; c = j + offset; if (block == 0) g.add_edge(c, c+w); if (block == 0) g.add_edge(c+w, c); } } } // bfs queue que; que.push(0); vector cost(w*h); rep (i, w*h) cost[i] = 1001001001; cost[0] = 1; while (!que.empty(

2017/08/13 ~ 2017/08/16

c++のヘッダを探索パスに追加

毎回調べては忘れているのでメモ.
g++などのコンパイラのオプションとして渡せないときは環境変数を使う.


たとえば,deepnlのビルドにはeigenが必要である.
linuxbrewを使ってeigenをインストールしていた場合,
ヘッダファイルは $(brew --prefix)/Cellar/eigen/version_name/include/eigen3 にある.
よって以下のようにヘッダを指定してやればよい.

CPLUS_INCLUDE_PATH=$(brew --prefix)/Cellar/eigen/3.3.4/include/eigen3 python setup.py build

github.com

Vimでヤンクなしで一行を削除する

"_dというコマンドがあることを知った.
以下のようなmappingをすることでdでヤンクなし削除が実現できた.

github.com


stackoverflow.com

Recurring Decimals

繰り返す10進数 | Aizu Online Judge

 a_{k-1} の各桁の数値を持つベクターを作り,
ソートはベクターに対して行う.
ソート後に a_k を計算すればよい.
コードやや汚い.

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int make_number(vector<int> &a, int l) {
  int res = 0;
  for (int ll=l-1; ll>=0; --ll) {
    res += a[l-ll-1] * pow(10, ll);
  }
  return res;
}

int main() {
  int a0_raw, l, d;
  vector<int> a, a0;

  int i, j;
  int ak_raw;


  while (cin >> a0_raw >> l, a0_raw || l) {
    a0.resize(0); a.resize(0);
    bool reached = false;

    for (int ll=l-1; ll>=0; --ll) {
      d = a0_raw / pow(10, ll);
      a0_raw -= d * pow(10, ll);
      a0.push_back(d);
    }

    a.push_back(make_number(a0, l));

    while (1) {
      sort(a0.begin(), a0.end());
      int amin = make_number(a0, l);

      reverse(a0.begin(), a0.end());
      int amax = make_number(a0, l);

      a0_raw = amax - amin;
      a.push_back(a0_raw);

      i = a.size() - 1;
      rep (j_, i) {
        if (a[i] == a[j_]) {
          j = j_; reached = true;
          break;
        }
      }

      if (reached) break;

      a0.resize(0);
      for (int ll=l-1; ll>=0; --ll) {
        d = a0_raw / pow(10, ll);
        a0_raw -= d * pow(10, ll);
        a0.push_back(d);
      }
    }

    cout << j << " " << a0_raw << " " << i-j << endl;
  }

  return 0;
}
latexなどで利用可能なフォントの一覧を見る

XeLaTeX環境を作るとき,フォントの設定をどうすればよいかわからず色々調べた.
結果として,使用可能なフォントの一覧は fc-list というコマンドで確認できることがわかった.

Presentation with XeLaTeX

matplotlib.pyplot で日本語を使う

matplotlib.rcでフォントを指定できる.

from matplotlib import rc

font = {'family': 'YuGothic'}  # NOTE: use YuGothic for Japanese
rc('font', **font)

paper.hatenadiary.jp

2017/08/09 ~ 2017/08/11

shell script (bash) の配列

bashには配列というものが存在しないらしい.
stackoverflow.com

が,200から1000まで200ずつ増やした数字をループの中で作りたい状況に遭遇した.
seqコマンドでやりたいことができた.

HIDDEN_UNITS=$(seq 200 200 1000)

for hidden_unit in $HIDDEN_UNITS; do
  python train.py --hidden $hidden_unit
done

これでパラメータを変更しながら実験する作業を自動化できる.

A-un Breathing

阿吽の呼吸 | Aizu Online Judge


カッコの対応が取れているかを判定する問題と同じ.
bool wrongを初期値なしで初期化してWAを大量にもらってハマっていた.
bool wrongの初期値がtrueになる場合とfalseになる場合がある?

stackでもできるはずだけどREをいただいてしまう.なぜ?
http://jag2016-domestic.contest.atcoder.jp/submissions/1501888

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int n;
  cin >> n;

  int cnt = 0;
  bool wrong = false; // 初期値はtrueなことがある

  string s;
  rep (i, n) {
    cin >> s;
    if (s == "A") {
      cnt++;
    }
    else if (s == "Un") {
      if (cnt > 0) {
        cnt--;
      }
      else {
        wrong = true;
      }
    }
  }

  if (wrong || cnt > 0) {
    cout << "NO" << endl;
  }
  else {
    cout << "YES" << endl;
  }

  return 0;
}
Curry Making

カレー作り | Aizu Online Judge


はじめはカレーの濃度はCよりも低い.
Cよりも濃度が高くなるようにルーを追加し,
そのあとで水を加えれば良い.
そのため,水はルウの個数と切り離して考えることができる.
また,ルウは必ず整数個であることが保証されている.
つまり,ルウの個数を1から適当に大きな数まですべて試せばよい.

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int r_0, w_0, c, r;
  while(cin >> r_0 >> w_0 >> c >> r, r_0) {

    for (int x=0; x<1001001001; x++) {
      if (c <= (double)(r_0+x*r)/w_0){
        cout << x << endl;
        break;
      }
    }
  }
  return 0;
}

2017/08/04 ~ 2017/08/09

2582: Step Aerobics

両足で踏み台を登るか降りるかした回数をカウントする.
左足と右足が現在何段目にいるか,前回カウント時に両足は何段にいたかを変数として持つ.
実際にシミュレーションすれば解ける.

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int n;
  string input;

  while (cin >> n, n) {
    int prev_h = 0;
    int curr_l = 0, curr_r = 0;
    int ans = 0;

    rep (i, n) {
      cin >> input;

      // cout << input << endl;

      if (input == "lu") curr_l++;
      if (input == "ld") curr_l--;
      if (input == "ru") curr_r++;
      if (input == "rd") curr_r--;

      // cout << curr_l << "-" << curr_r << endl;

      if (curr_l == curr_r && curr_l != prev_h) {
        // cout << "count" << endl;
        ans++;
        prev_h = curr_l;
      }
    }

    cout << ans << endl;
  }
  return 0;
}


Step Aerobics | Aizu Online Judge

Entrance Examination

ギャップはi番目とi+1番目の学生の得点の差である,
合格者の数が条件を満たしているか確認したあとで
ギャップがこれまでのギャップの最大値以上か確認する.
ギャップがこれまでの最大値以上であった場合は合格者数を更新する.

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int n, left, right;
  vector<int> p;

  while (cin >> n >> left >> right, n) {
    p.resize(n);
    rep (i, n) cin >> p[i];

    sort(p.begin(), p.end());
    reverse(p.begin(), p.end());

    int n_passed = 0;
    int max_gap = 0;

    rep (i, n-1) {
      if (! (left <= i+1 && i+1 <= right) ) continue;
      if (max_gap <= p[i] - p[i+1]) {
        n_passed = i+1;
        max_gap = p[i] - p[i+1];
      }
    }
    cout << n_passed << endl;
  }
  return 0;
}

Entrance Examination | Aizu Online Judge

2017/07/31 ~ 2017/08/03

Python matplotlibとpandasで信頼区間つきのグラフを描画する

fill_betweenをつかうとよい.
これはpandas.DataFrameを使っているときにも利用できて便利.
pandasとmatplotlibの仲の良さはとてもありがたい.

以下にコード例を示す.

import math
import random
import pandas

x = [i for i in range(100)]
y = [math.sin(i) for i in range(100)]
stdy = [random.random() for i in range(100)]

data = zip(x, y, stdy)
df = pandas.DataFrame(list(data), columns=['x', 'y', 'ystd'])

plt = df.plot(x='x', y='y')
plt.fill_between(df.x, df.y-df.ystd, df.y+df.ystd, alpha=0.3)

実行するとこんな感じになる.
f:id:himkt:20170801094038p:plain

Pythonのコンテキストマネージャは1つで複数のコンテキストを管理できる

<|python|
with open('input1.txt') as input1_fp, open('input2.txt') as input2_fp:
for line1, line2 in zip(input1_fp, input2_fp):
print(line1, line2)
|

8. Compound statements — Python 3.6.2 documentation

pickleで大きなデータをシリアライズ

普通だとpickle.dumpに4GB以上のオブジェクトを渡すと

OverflowError: cannot serialize a bytes object larger than 4 GiB

と言われてしまう.これはpickle.dumpの中でint32が使われているせいらしい.
調べて見たらprotocol4というのがあって,このプロトコルではサイズをint64で管理していそう.

www.python.org

C++の非決定的な乱数生成

標準で使えるrand()は決定的な乱数を生成する.

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  for (int i=0; i<10; i++) {
    cout << rand() << endl;
  }
  return 0;
}

これをコンパイルして何回実行しても結果は以下のようになった.

16807
282475249
1622650073
984943658
1144108930
470211272
101027544
1457850878
1458777923
2007237709

一方,ハードウェアの状態などを用いて非決定的な乱数を生成する生成器がC++11にはある.
以下のように使える.

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  random_device rnd;
  for (int i=0; i<10; i++) {
    cout << rnd() << endl;
  }
  return 0;
}

C++11 乱数 std::random 入門

ディレクトリのツリー構造の可視化

treeコマンドでやっていたけどlsコマンドにも良い感じのオプションがあることを知った.

takuya-1st.hatenablog.jp

2017/07/27 ~ 2017/07/30

centos6にglibc2.14をビルド

何かと必要になるアイツ
centos6.5のglibcは2.12

configureのときにlinuxbrewで新しいgccをインストールしていた場合はコケることになる.
システムのgccを使うようにしてやればよい

wget http://ftp.gnu.org/gnu/glibc/glibc-2.14.tar.gz
tar xvf glib-2.14.tar.gz
mkdir build
cd build
CC=/usr/bin/gcc ../glibc-2.14/configure --prefix=$HOME/.local
Python3系ではkey in dict.keys()をすればよい

dictionary.keys()ってリストを返すと思っていた.
リストに対するin演算子は線形探索をするだろうからめちゃくちゃ遅そう.
KeyErrorを引っ掛ける実装をしたほうが良いのでは?と思ってずっとそのようにしていた.

key = 3334
dict = {i: 1 for i in range(100000)}
try:
    dict[key]
    print('found')
except KeyError:
    print('not found')

だが,調べてみたところPython3系ではdictionary.keys()はdict_keysというビューオブジェクト(イテレータ)を返す.
Pythonのドキュメントには以下のようにあった.

Calling d.keys() will return a dictionary view object. It supports operations like membership test and iteration, but its contents are not independent of the original dictionary – it is only a view.

5. Data Structures — Python 3.6.2 documentation

そしてこのオブジェクトに対するin演算子は定数時間で実行可能なようだ.

というわけで,Python3系を使っているなら安心して

key in dict.keys()

を使いましょう.

  • Python2系,dictionary.keys()がリストを返していることがわかる
In [3]: type(dic.keys())
Out[3]: list

In [4]: dic = {i: 1 for i in range(100000000)}

In [5]: %time 3333334 in dic.keys()
CPU times: user 1.34 s, sys: 160 ms, total: 1.5 s
Wall time: 1.5 s
Out[5]: True

In [6]: type(dic.keys())
Out[6]: list

In [7]:
  • Python3系
In [1]: dic = {i: 1 for i in range(100000000)}

In [2]: %time 3333334 in dic.keys()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 11.9 µs
Out[2]: True

In [3]: %time 0 in dic.keys()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 10.7 µs
Out[3]: True

In [4]: %time 11111120 in dic.keys()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 11.7 µs
Out[4]: True

In [5]: %time 1111112343220 in dic.keys()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 10.3 µs
Out[5]: False

In [6]: type(dic.keys())
Out[6]: dict_keys

In [7]:
pandas.read_csvのときに特定のラベルのデータの型を指定したい

read_csvの引数としてdtype=dictionaryを与えてやればよい.
たとえば以下のようなcsvファイルがあったとする.(test.csv

label, precision
+1,0.8
-1,0.7

このとき,ラベルのカラムのデータは数値というよりは文字列である.
pandasは+1も数値としてパースして1にしてしまうので,以下のようにしてやる.

pandas.read_csv('test.csv', dtype={'label': str}

pandas.read_csv — pandas 0.20.3 documentation

tmuxのタイトルにssh接続してるホスト名を表示させる

たくさんのサーバにsshする場合,tmuxのstatusが"ssh"で埋まってしまう.

f:id:himkt:20170730173747p:plain

以下のスニペットによってstatusにhost名を表示させることができる.

ssh() {
    if [ "$(ps -p $(ps -p $$ -o ppid=) -o comm=)" = "tmux" ]; then
        tmux rename-window "$(echo $* | cut -d . -f 1)"
        command ssh "$@"
        tmux set-window-option automatic-rename "on" 1>/dev/null
    else
        command ssh "$@"
    fi
}

こうなる.
f:id:himkt:20170730174126p:plain

Set tmux pane title on SSH connections – blog.no-panic.at

When Can We Meet?

When Can We Meet? | Aizu Online Judge

n人のミーティングに参加可能な日程が与えられ,もっとも参加人数の多い日を求める問題.
std::mapを使って簡単に解ける.最後に制約条件qを満たすかどうかを確認するのを忘れないように注意.

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int n, q, m, d;
  map<int, int>::iterator it;

  while (cin >> n >> q, n) {
    map<int, int> freq;
    rep (i, n) {

      cin >> m;
      rep (k, m) {
        cin >> d;

        it = freq.find(d);
        if (it == freq.end()) {
          freq[d] = 1;
        }
        else {
          freq[d]++;
        }
      }
    }

    int max_d = -1;
    int max_v = 0;

    for (pair<int, int> p : freq) {
      if (max_v < p.second) {
        max_d = p.first;
        max_v = p.second;
      }
    }

    if (max_v >= q) {
      cout << max_d << endl;
    }
    else {
      cout << 0 << endl;
    }
  }
  return 0;
}