sudo #2

• ref:suとsudo (Fuktommyの場合)

普通の作業は一般ユーザ、管理の作業はrootと使い分けます。 気持ちを切り替えるためにsuコマンドを使って、 rootのパスワードを入力するようにします。 管理作業でも定型的なもの、 例えばDebianなら apt-get update; apt-get upgrade だとか、 Fedora Core なら yum check-update; yum update だとかは sudoでできるように設定します。 sudoで全てのコマンドが実行できるようにはしません。 全て「root権限を使うときは気持ちを切り替える」ためです。

一般ユーザのパスワードではなく、root のパスワードを入力するようにしたいのであれば、rootpw か runaspw か targetpw を設定すれば済む話でないかな。こんなの。

Defaults rootpw

キーワード検索

• ref:万有引力がはたらくcQueの日記(メニスカス) - 意外と盲点？連鎖googleなぐぐりかた

あー、結局それは現状のキーワード検索システムの限界というかなんというか。実は、自然文の検索要求文から人間が検索キーワードを決定して検索するより、bigram にぶった切って検索キーワードにしたほうがいい成績が出たりするんだよね。いや、検索内容とコーパスによるんだけだろうけど。
共起頻度情報とか使って自動的に検索キーワードを追加するような研究があるよな気がするけどどうなんだろう。
つか、そもそもキーワード検索自体、計算容量的な妥協の産物なんじゃないだろうか。

文字列ソーティング #3

今度は単語単位のソートにしてベンチマーク。元データは同じく新聞記事約 30MBytes (単語数 5,727,663)。
ついでに MSD Radix Sort も加えてみた。
で、きむらさんのところを見て、そういや、プロファイルとってないなと思ったので、g++ -O2 -pg でコンパイルして gprof で結果を見てみた。suffix_compare が strcmp の代わりの functor なんだけど普通にやるとインライン展開されちゃうから無理矢理別ファイルに分けてリンクしてある。

algorithm	time[sec]
quicksort	32.56
multikey quicksort	9.45
merge sort	20.46
MSD radix sort	15.74
std::sort	29.61
std::stable_sort	21.17

==> mergesort <==
 time   seconds   seconds    calls   s/call   s/call  name
 83.27     17.75    17.75 122506116     0.00     0.00  suffix_compare<unsigned char, int>::operator()(int, int) const
 10.73     20.03     2.29  1009070     0.00     0.00  int* std::merge<int*, int*, int*, suffix_compare<unsigned char, int> >(int*, int*, int*, int*, int*, suffix_compare<unsigned char, int>)
  2.35     20.53     0.50                             main

==> msd_radix_sort <==
 time   seconds   seconds    calls   s/call   s/call  name
 71.39     18.63    18.63        1    18.63    25.32  void _msd_radix_sort<unsigned char, int>(unsigned char const*, int*, int, int, int)
 22.43     24.48     5.85 62083188     0.00     0.00  suffix_compare<unsigned char, int>::operator()(int, int) const
  3.18     25.31     0.83   346637     0.00     0.00  void insertion_sort<int, suffix_compare<unsigned char, int> >(int*, unsigned int, suffix_compare<unsigned char, int>)

==> multikey_quicksort <==
 time   seconds   seconds    calls   s/call   s/call  name
 81.37     16.93    16.93        1    16.93    20.27  void multikey_quicksort<unsigned char, int>(unsigned char const*, int*, int, int)
 14.93     20.03     3.11  9933763     0.00     0.00  suffix_compare<unsigned char, int>::operator()(int, int) const
  2.50     20.55     0.52                             main

==> quicksort <==
 time   seconds   seconds    calls   s/call   s/call  name
 87.77     28.60    28.60 178720117     0.00     0.00  suffix_compare<unsigned char, int>::operator()(int, int) const
  9.04     31.55     2.95        1     2.95    31.58  void quicksort<unsigned char, int>(unsigned char const*, int*, int)
  1.57     32.06     0.51                             f()

==> stl_sort <==
 time   seconds   seconds    calls   s/call   s/call  name
 90.18     28.31    28.31 163298909     0.00     0.00  suffix_compare<unsigned char, int>::operator()(int, int) const
  5.74     30.11     1.80   598058     0.00     0.00  int* std::__unguarded_partition<int*, int, suffix_compare<unsigned char, int> >(int*, int*, int, suffix_compare<unsigned char, int>)
  1.56     30.60     0.49                             main

==> stl_stable_sort <==
 time   seconds   seconds    calls   s/call   s/call  name
 84.90     18.58    18.58 125713536     0.00     0.00  suffix_compare<unsigned char, int>::operator()(int, int) const
  9.85     20.73     2.16   818254     0.00     0.00  int* std::merge<int*, int*, int*, suffix_compare<unsigned char, int> >(int*, int*, int*, int*, int*, suffix_compare<unsigned char, int>)
  2.33     21.24     0.51                             main

MSD Radix Sort と Multikey Quicksort 以外について、比較関数の呼び出し回数と実行時間について並べてみる。

algorithm	呼び出し回数	合計実行時間[sec]	平均実行時間[nsec]
Quicksort	178,720,117	28.60	160
Merge sort	122,506,116	17.75	144
std::sort	163,298,909	28.31	173
std::stable_sort	125,713,536	18.58	148

要するにマージソートの方が、比較コスト、比較回数の両方で優れているということだな。

一応ソースを各種アルゴリズムの実装コードも書いておく。なんか変なところがあれば、指摘頼みます。

sudo #3

fuktommy fuktommy ↓rootpwはこの場合の解ではないです。alias su='sudo -k && sudo -s -H' かなあ。

む。私の誤読かな？どういうことだろ。
そもそも root の shell が必要な場面てないと思うんだけど。普通に -s, -i なしの sudo では駄目なのかな。本当に必要な箇所でだけ sudo を使ったほうがいいと思うんけどなぁ。
あと -H は set_home を設定しておけば、デフォルトになりますよ。sudo -i のがいいと思うけど、それはそれで・・・

サーバルーム

そういえば、某セキュリティの偉い先生のサーバには普通に root のパスワードが張ってあったりする。まぁ、当然サーバルームには鍵がかかるし、そもそもフロアに入るのにカードキーがいるんだけど。
「コンソールへのアクセスを許した時点で駄目」って話を象徴するような話ですな。

和訳 or カタカナ

array → 配列は鉄板として、suffixは拡張子とか接尾辞になるでしょうから、 まあ何も考えなければ「接尾辞配列」になっちゃうんですかねえ。

まぁ、和訳しなきゃならないとすれば、接尾辞配列は妥当なところだと思います。
というより、「中央演算処理装置」とか「電子計算機」とかあまり言わないよなぁと。別にカタカナで「サフィックスアレイ」かそのまま「Suffix Array」でいいじゃんと。
そういや、国立国語研究所の発表した「ユビキタス」の言い換えに「時空自在」なんてのがありましたね。あれもどうかと思いましたけど。

モラルハザード

なんか国立国語研究所のページを見ていたらモラルハザードの用例が

少年たちによる殺人事件の多発，モラルハザード〔倫理崩壊〕が叫ばれる大人社会，自己中心性の肥大化など社会病理現象があらわになっている。

に。意味が

倫理観や道徳的節度がなくなり，社会的な責任を果たさないこと

になっている。あれー。

本来は保険用語で，保険をかけてあるからと故意や不注意で事故を起こしてしまう危険性をいった。経済全般での倫理の欠如による行為に広がり，さらに経済以外の領域にも拡大して，使われている。

それはちがうんじゃないかな。モラルハザードって保険などによって、リスク回避のインセンティブが薄れてしまうことで、全体で見たときのリスクが増加することであって、倫理は関係ないと思う。経済以外の領域にも拡大したというより、勝手に意味を推測して使う人が多くてそっちが定着してしまったつう話では。

転置インデックス

そういや、以前誰かが、輪講で inverted index を「逆インデックス」って訳していて、それはないわ、と思ったけど。

転置インデックスには大きく分けて2通りの手法がある。転置ファイルインデックス(inverted file index)は単語と、その単語を含む全ての文書をリストとして備えている。完全な転置インデックス(full inverted index) は、単語を含む全ての文書の他に、その単語が文書中のどこに現れるかという位置情報まで含んでいる。
転置インデックスの実装手法にも幾通りかある。最も単純なものは全ての文書IDとその保存位置情報をペアで格納したものである。ディスク容量の節約にはなるが、その分、機能性も乏しいものとなってしまう。（普通検索エンジンで行うような）単語検索は可能だが、（検索クエリで引用符でくくるような）フレーズ検索は不可能だろう。

ちょ、最後の文がおかしい。単語出現位置の情報もあるならフレーズ検索できるよ。
多分、元になっている英文はコレだな。

There are two main variants of inverted indexes: An inverted file index contains for each word a list of references to all the documents in which it occurs. A full inverted index additionally contains information about where in the documents the words appear. This could be implemented in several ways. The simplest is perhaps a list of all pairs of document IDs and local positions. An inverted file index needs less space, but also has less functionality. You can do term search (what you usually do in a search engine), but not phrase search (what you usually get when you put quotes around your search query).

あー、後半から日本語訳の主語が変になっているねぇ。「This could be implemented」の This は full inverted index のことでそのあと、inverted file index の話になっているのに、訳で主語を省くから変なことになっている。
結論。超訳勘弁。つか、主語省くな。代名詞が何を指しているかぐらい理解してくれ。

クラスメソッドの抽出 #2

okuji さん曰く

素直にinspect.classify_class_attrsを使ってはどうでしょうか。

あー、標準にそんなモジュールが。というわけでコレを使えばこうなりますね。

import inspect

def get_class_methods(klass):
    return [attr[0] for attr in inspect.classify_class_attrs(klass)
            if attr[1] == 'class method']

あと、こういう他にこういう方法も

def get_class_methods(klass):
    return [name for name in dir(klass) if is_class_method(klass, name)]

def is_class_method(klass, name):
    if name in klass.__dict__:
        attr = klass.__dict__[name]
    else:
        attr = getattr(klass, name)
    return isinstance(attr, classmethod)

あれ、そういや、クラスをあらわす変数名は cls と klass のどっちが多いんだろ。klass だと思っていたら inspect.py では cls だったからちょっと面食らった。まぁ、どうでもいいといえばどうでもいいけど。
Ruby では klass が標準的だよね。確か。

root のパスワード潰し

• ref:rootのパスワードは潰さないほうがいいと思う件 - mputの日記。 (2007-03-15)

あー、通常ユーザのパスワードを全部禁止して root のコンソールログインだけ許可ってのはいいな。しかし、ユーザがみんな公開鍵認証を理解しているとしたらうらやましい限りだ。

なんでかというと、rootのパスワードを潰しちゃうとシングルユーザーモードが使えないし、コンソールからrootログインができないから。

あれ？Linux のシングルユーザモードでパスワード要求されるかどうかは /etc/inittab 次第では。もしかして root のパスワードを削除するまた違ったりするんだろうか。

謎略語

某氏が使う謎略語+謎読み

• rootのパスワード = su pass
• str = スター

su pass は分からなくもないけどな。password なのか passphrase なのかはたまた path なのか。すでに su = Super User でもないしな。
スターの方は完全に意味不明だったな。
略語とか専門用語ってのはうまく使えば便利だとは思うんだけど、ある程度自明でよく使われる単語でないとかえってコミュニケーションに支障をきたすことになるってことを自覚すべきだよな。つうか変な略語を作らないでくれ、とか思うわけだが。

excuse me

例の「悪いことをしたときは日本人のふりをするんだ」ってやつ、なんか英語字幕付きバージョンが出たみたいなんだけど、なんで「足を踏んだときは『すみません』って言うんだ」ってところの「すみません」に「Excuse me」をあてているんだろう。普通に考えておかしいと思うのだが。