ファイル読み込み + 演算のベンチマーク

ベンチマークシリーズ第二弾は、sum file です。テキストファイルから1行読み取り、整数に変換したものの和を求める、というもの。10000 行のファイルを使いました。

LabVIEW 8.5.1 ...... 968 [msec]
Python 2.5.2 ...... 371 [msec]
C (GCC 3.4.4) ...... 110 [msec]

LabVIEW 遅いな...。

# python
import sys, itertools
print sum(itertools.imap(int, sys.stdin))

/* C */
#include <stdio.h>
#include <stdlib.h>
#define MAXLINELEN 128
int main (void) {
  int sum = 0;
  char line[MAXLINELEN];
  while (fgets (line, MAXLINELEN, stdin)) {
    sum += strtol (line, NULL, 0);
  }
  printf ("%d\n", sum);
  return 0;
}

LabVIEW のベンチマーク - スペクトル・ノルム

http://shootout.alioth.debian.org/gp4/index.php
に、いろんな言語でいろんな計算を実装したベンチマークがあります。

スペクトル・ノルムの計算を試してみました。Panasonic CF-R5, U1300 @1.06GHz, 1GB RAM のノートパソコンでの結果です。

C++ のコードを、Visual Studio 2005 でコンパイルしたものと、それを愚直に LabVIEW に移植した場合で比較しました。N = 1000 のとき、

C++ ... 1.9 秒
LabVIEW 8.5.1 ... 79 秒
Python 2.5 ... 80 秒

壊滅的に LabVIEW と Python が遅いです。まあ、こんなもんでしょう。LabVIEW も Python も、四則演算なんかは直接コンパイルせずに、ランタイム/バーチャルマシン上で動かしているので、ネイティブコードに吐き出す C++ よりも遅くなるんではないかと。

LabVIEW には標準で行列演算の関数や VI が含まれるのでそれを使って実装しなおすと、もっと早くなります。ただ、この場合には、元の実装とは異なり、行列をあらかじめ用意します。なので、C++ でも eval_A(i,j) を、vector<vector<double> > A(N,N) に置き換えました。

C++ 改 ... 1.6 秒
LabVIEW 8.5.1 改 ... 0.4 秒

LabVIEW 速いです。とは言え、行列がらみの演算は LAPACK や BLAS を使っているので、C++ でそれを使っていないのはフェアではないです。ポイントは、解析系の演算はビルトイン関数を使うと、C 並のスピードで動くということです。DLL 呼んでるだけなので、当たり前ですが。

SpectralNorm.zipをダウンロード

LabVIEW で migemo を実装してみた

pure LabVIEW で Migemo を実装してみました。ローマ字から日本語を検索するような正規表現を生成します。C/Migemo 使えよって話なのですが、まあ、そこらへんは LabVIEW で書くことが目的ってことで。最近、バイナリサーチだとかクイックソートだとかにうつつを抜かしていたのは、これを作るのが目的でした。概念実証の段階なので、コードは遅いですし不安定です。これからちょっとずつ修正していきます。

lvmigemo-poc.zipをダウンロード

(2MBくらいあります）

村上春樹 / スプートニクの恋人

村上春樹の「スプートニクの恋人」を読みました。スプートニクは出てきません。ノルウェイの森にもノルウェイは出てきませんし。タイトルでは想像がつかないところが、村上龍との違いです。

22歳の女性すみれが、年上の女性に恋をして、服装が少しずつ変わっていく様を、「ぼく」の視点から語る。ようにみせかけて、ぼくの物語です。すみれの世界に対するディタッチメントとコミットメント、ぼくのすみれや世界に対するディタッチメントとコミットメントが描かれています。

話の途中でギリシアに場面が移るのですが、このときの描写が「遠い太鼓」に書かれている村上春樹のギリシア生活っぽいです。船着場での喧噪や、夜の静かさとかが。

個人的な好みでは、村上春樹ランキングは、

1. 国境の南、太陽の西



2. 世界の終りとハードボイルド・ワンダーランド



3. スプートニクの恋人

です。「大切であったことに失ってから気づく」ストーリー大好きなので。ねじまき鳥など未読の作品もあります。

Python Code Reading に行きたい

Python Code Reading 01 も 02 も参加していません。01 のときにはお客様とお食事会、02 のときには展示会＋セミナー講師をやっていたので、行きませんでした。次回は行きたいなぁ。

ちなみに展示会場はパシフィコ横浜で、Code Reading の日は、展示会最終日で後片付けとかやっていました。以前なら「行けなかった」と表現していたところです。自分がマーケティング担当している製品を出店する展示会で、他部署部署から応援をお願いしているので、私用で早退というのは、ちょっとどうかという状況でした。が、物理的に制限されていたわけではないので「行けなかった」のではなく「行かなかった」のです。というどうでもいいことに、こだわり始めた、ここ数日です。すぐに飽きるかもしれません。

Quick sort VI for LabVIEW

I have made a binary search library for LabVIEW few days ago and I found it is hard to sort an arry of any type.  So I made another VI to sort an array.

First, you need to create an VI to compare two values in advance of using the library.  The VI accepts two variants A and B, and returns the result of (A-B).  The VI should simply perform subtract B from A if you want to search a numeric array.  The VI, however, will be more complicated if you want to search an array of cluster.  Note that the VI must return 0 if matched.

Then, pass an array of data type and the VI you have just created to SortAny1DArray.vi , and then you will get the array sorted.  The sorting algorithm is quick sort.

Download lvqsort-0.1.zip

LabVIEW でクイックソート

先日、LabVIEW で二分探索するライブラリを作ったのはいいのですが、任意の型の配列をソートするのが意外にも面倒であることに気付きました。というわけで、ソートする VI も作りました。

まず、比較用の VI を作ります。2つのバリアント A と B を受け取って、その大小比較の結果 (A-B) で返すような VI を作ります。数値の場合は単純に引き算すればよいですし、クラスタのような複雑な型の場合には、それなりの演算をして大小比較します。一致した場合には 0 を返さないといけません。

任意の型の配列と、上記の VI へのリファレンスを、SortAny1DArray.vi に渡すと、あーら不思議ソートされます。別に不思議でもなんでもありません。アルゴリズムにはクイックソートを使っています。

lvqsort-0.1.zipをダウンロード

Binary Search libary for LabVIEW

LabVIEW provides a built-in 1D search function which is a linear search implementation.  That is the algorithm check a value from the very first element of an given array, then 2nd,... until it finds a matched value.  It is O(n) algoritm. Thus it is likely useless for large arrays.

If you have a sorted array, binary search is useful.  This algorithm checks the value in the middle of given array to determine the expected value is located in the first half or last half of the array.  Then it check the value in the middle of the first/last half portion, .... until it finds the value.  It is O(log n) algorithm.

Satoru Takabayashi has implemented the algorithm in Ruby; Ruby/BSearch and I ported it for LabVIEW.

First, you need to create an VI to compare two values in advance of using the library.  The VI accepts two variants A and B, and returns the result of (A-B).  The VI should simply perform subtract B from A if you want to search a numeric array.  The VI, however, will be more complicated if you want to search an array of cluster.  Note that the VI must return 0 if matched.

Okey, now you are ready to search with, say, BianarySearch.lvlib:Range.vi.  The example below shows the VI returns the index of first occurence of "2" and and 1+ the index of the last; i.e. 1 and 3 respectively.

download BinarySearch-0.1.zip

LabVIEW で2分探索するライブラリを作りました

LabVIEW の 1D 配列検索は線形探索です。つまり配列の先頭から要素を順番に確認していって、見つかったらおわり、というアルゴリズムです。配列サイズに比例して、つまり O(n) なので、確認する要素数が増えるので、データが大きくなると破綻しがちです。

配列が昇順または降順にソートされている場合、二分探索あるいはバイナリサーチと呼ばれる方法を使えます。これは、まず真ん中を見て、探している値が配列の前半にあるか後半にあるかを特定します。で、その前半なり後半なりの真ん中を見て... というの繰り返すアルゴリズムです。O(log n) です。

で、Ruby には高林さんが作った Ruby/BSearch というライブラリがあるので、それを LabVIEW に移殖しました。

使うときには、大小比較用の VI を最初に用意します。2つのバリアント A と B を受け取って、その大小比較の結果 (A-B) で返すような VI を作ります。数値の場合は単純に引き算すればよいですし、クラスタのような複雑な型の場合には、それなりの演算をして大小比較します。一致した場合には 0 を返さないといけません。

これで準備ができました。ってなわけで、BinarySearch.lvlib:Range.vi を使ってみましょう。下の例では、数値配列から 2 がある要素の最初の指標と、最後の指標+1 を返します。つまり 1 と 3 を返します。

BinarySearch-0.1.zipをダウンロード

LabVIEW の任意の配列は、バリアントの配列に変換できる

バリアントをごにょごにょしている、この頃でしたが、無駄足であることが分りました。もともと、任意の型の配列の要素に対して操作をするというのが目的です。OpenG のコードを読んでいて気付いたのですが、配列はバリアントの配列に変換できるようです。元の配列要素の型がクラスタでも大丈夫です。これがあれば任意の型の配列に対して、配列要素を取り出したり、入れ替えたりすることもできます。

また、元のデータが配列ではなかったり、次元が一致しない場合には静的型チェックでひっかかるので便利です。

バリアントに変換された配列のサイズを知る

バリアントの続きです。配列データをバリアントに変換した後で、元の配列のサイズを知ることもできます。当たり前ですが。

「バリアントから平坦化文字列に変換」したとき、タイプディスクリプタの 3 ワード目に次元数が格納されています。各次元のサイズは文字列の先頭に、符号なし32ビット整数で格納されています。たとえば 2 次元配列の場合、文字列の先頭 32 ビットに 1 次元目のサイズ、次の 32 ビット目に 2 次元目のサイズが格納されています。ブロックダイアグラムは以下のようになります。

バリアントの元の型が、配列かどうか判定する

OpenG のコードを読んでいると、バリアントの元の型が配列かどうかを判定する方法が分かりました。

「バリアントから平坦化文字列に変更」関数 （"Variant To Flattened String" function） の、タイプ文字列端子から出てくるデータを見ます。バリアントの元の型が配列の場合、Windows ではこのデータの 4バイト目タイプディスクリプタが  0x40 になるということです。正確には、この端子から出てくるデータは符号つき16ビット整数の配列で、ふたつめの要素の下位バイトが 0x40 です。

OpenG のバリアント系 VI がすごい

LabVIEW で任意の型のデータを受け渡しするときに、バリアントに型変換することがあります。このとき型情報を「バリアントから平坦化文字列に変換」関数を使って取り出せる


のですが、なんだか複雑でマニュアルを読むのが面倒です。

こんなときには LabVIEW のオープンソースライブラリ OpenG です。この中にバリアントを扱う VI もあって、これらを使うと実行時にバリアントの型情報を扱うのが容易になります。これを使うと、たとえば任意の型データを要素とする配列のソート、なんかも実現できます。下の例は、数値と文字列でできたクラスタ、の配列を、数値でバブルソート（ださっ！）する VI です。

bubblesort.zipをダウンロード