SWTでは、たとえばSHIFT+CTRL+F5をメニューのアクセラレータに指定するには
from org.eclipse.swt import SWT menu.setAccelerator(SWT.SHIFT + SWT.CTRL + SWT.F5)
というようにおのおのの値を足しあわせてやる必要があります。しかしいちいちSWTと書くのは面倒ですし、 from org.eclipse.swt.SWT import * とやってSWTパッケージの中身を全部取得してしまうのはスマートではありません。そこで "SHIFT+CTRL+F5" という文字列を"+"でsplitして、"SHIFT"という文字列からSWT.SHIFTの値を取得しようと思いました。
Pythonでは、あるパッケージ X の中にある name という名前のオブジェクトは X.__dict__[name] で取得することができます。しかしJythonでこれをやると、オブジェクトは取得されますが、フィールドが整数であっても取得されたオブジェクトはPyIntegerではなくPyReflectedFieldです。_dogetを呼んでPyIntegerを取得してやる必要があります。
下のコードでは、"CTRL+SHIFT+O"などという文字列がaccelに入っている場合に、 SWT.CTRL + SWT.SHIFT + ord("O") をメニューmenuのアクセラレータに指定し、与えられた文字列自身もメニューに表示します。
if accel != "":
from org.eclipse.swt import SWT
intAccel = 0
for key in accel.split("+"):
if SWT.__dict__.has_key(key):
v = SWT.__dict__[key]._doget(SWT)
intAccel += v
else:
intAccel += ord(key)
menu.setAccelerator(intAccel)
menu.setText(text + " " + accel)
書いてしまったので一応載せておきます。勉強用のコードなので入力文字列が巨大になったときにどういう挙動を示すかは考えていません。
後輩のレポートを僕が解いてしまうと勉強にならないと思って我慢していましたが、レポート内容はクイックソートではなくてそれを利用してSuffixArrayを作ることらしいです。帰りの電車で作ったのでとりあえず貼っておきます。皮の部分は「QuickSort祭り(一人)」を参照。
後輩のレポートにはin placeでvec[i]をvec[pivotPos]の手前に持ってくるためにpivotPos～i-1のすべてを一つ右にずらしていたのですけど、単に「iをバックアップし、pivotPos+1をiに書き、pivotPosをpivotPos+1に書いてpivotPosにバックアップしたiを戻す」でもいいような気がします。
むう、10000件のソートで、非破壊的ソートが32ミリ秒なのに、この破壊的ソートは3515ミリ秒かかって100倍遅い。Vectorである必要性がないので最初に配列に変換してみたけども、それでも351ミリ秒なので10倍遅い。上の段落で書いた高速化を入れて47ミリ秒なので1.5倍遅い。どういうことかな…。
非破壊的ソートではNlogNのメモリを消費して1回の分割でN回読んでN回書いているけど、破壊的ソートではNのメモリを消費して、約1/2の確率で起きる値の移動で3回ずつ読み書きするのでだいたい1.5N回の読み書きを行うと。ソートの対象が十分に小さければ、メモリの確保が大した問題にならないので破壊的ソートに約1.5倍の時間がかかるというわけですかな。で、メモリの確保に苦労するような巨大なリストをソートする場合には破壊的ソートの方が早いかというと…うーん、ひとかたまりの配列として保持しづらいし、何度も同じ所を読むからキャッシュに期待できないし…。
いや、待てよ、上の計算は正しくないか。非破壊的ソートの方はVectorを使っているから、Vectorを使った破壊的ソートと使わない破壊的ソートの比程度のオーバーヘッドがあるはず。だから非破壊的ソートと破壊的ソートの比は1.5倍どころじゃない。
後輩のQuickSortの課題を見ていて思ったのですけど、QuickSortは分割したリストのために新たに領域を確保していいかどうかによって難易度がだいぶ異なりますよね。高級言語は「QuickSortがこんなに簡単に書ける」なんてことを主張することがありますが、与えられた配列をその配列(+定数サイズ)の領域だけでソートするCとかで書かれたアルゴリズムを「真・クイックソート」だとすれば、新たな領域の確保を伴うQuickSortはちっとも早くないので「似非クイックソート」かもしれません。
で「似非クイックソート」なら簡単に書けるという話題で、ラボから赤坂某所への電車で書いたJavaのコード。
import java.util.Iterator;
import java.util.Vector;
public class Test {
public static void main(String[] args) {
Vector<Integer> vec = new Vector<Integer>();
vec.add(5);
vec.add(1);
vec.add(2);
vec.add(4);
vec.add(3);
print(vec);
vec = sort(vec);
print(vec);
}
private static void print(Vector<Integer> vec){
System.out.print("{");
for (Iterator<Integer> iter = vec.iterator(); iter.hasNext();) {
Integer element = iter.next();
System.out.print(element);
if(iter.hasNext()){
System.out.print(", ");
}
}
System.out.print("}");
}
private static Vector<Integer> sort(Vector<Integer> vec) {
if(vec.size() < 2){
return vec;
}
Integer pivot = vec.get(0);
Vector<Integer> less = new Vector<Integer>();
Vector<Integer> more = new Vector<Integer>();
for(int i = 1; i < vec.size(); i++){
Integer v = vec.get(i);
if(v < pivot){
less.add(v);
}else{
more.add(v);
}
}
Vector<Integer> result;
result = sort(less);
result.add(pivot);
result.addAll(more);
return result;
}
}
この通り非常に簡単(？) 似非クイックソートは高級言語だとかなり短く書けるのですけど、まぁJavaはそれほど高級じゃないということでしょう。Pythonなら4行で実装できますし。
def sort(a):
if len(a) > 1:
return sort([x for x in a[1:] if x < a[0]]) + a[:1] + sort([x for x in a[1:] if x >= a[0]])
return a
print sort([5,4,1,3,2])
まぁ、冗談はさておきまともに書いても15行程度でしょうか。
def sort(aList):
if len(aList) < 2: return aList
pivot = aList.pop()
less = []
more = []
for item in aList:
if item < pivot:
less.append(item)
else:
more.append(item)
less = sort(less)
more = sort(more)
less.append(pivot)
return less + more
Schemeだと「リストを結合する関数」と「条件を満たす要素だけを取り出す関数(filter?)」を「車輪の再開発」してもこんな感じでしょうか。
(define (get less aList pivot)
(if (null? aList)
()
(if (less (car aList) pivot)
(cons (car aList) (get less (cdr aList) pivot))
(get less (cdr aList) pivot))))
(define (join list1 list2)
(if (null? list1)
list2
(cons (car list1) (join (cdr list1) list2))))
(define (sort aList)
(let
((less (lambda (x y) (< x y)))
(more (lambda (x y) (>= x y))))
(if (null? aList)
()
(join (sort (get less (cdr aList) (car aList)))
(cons (car aList)
(sort (get more (cdr aList) (car aList))))))))
この後、「真・クイックソート」をJavaやPythonで実装すると後輩の目標を奪ってしまうのでSchemeでやろうとしてかなり苦しみました。 一度「一方向の連結リストじゃダメなんじゃないか」と考えて双方向リストを実装してみたり。
(define (makeDoublyLinkedList aList prev)
(if (null? aList)
()
(if (null? (cdr aList))
(cons (car aList) (cons () prev))
(let ((c (cons (car aList) ())))
(set-cdr! c
(cons
(makeDoublyLinkedList (cdr aList) c)
prev))
c))))
(define (getNext dList)
(car (cdr dList)))
(define (getPrev dList)
(cdr (cdr dList)))
(define dl (makeDoublyLinkedList '(1 2 3) ()))
(car dl) ;-> 1
(car (getNext dl)) ;-> 2
(car (getPrev (getNext dl))) ;-> 1
僕にとって関数型言語はパズル用言語なので、letやsetを使うのは自分的に禁止だったのですが、この手のモノをやるのには必要不可欠ですね。あと、LispやSchemeは確かにツリー状のモノを扱うのには適していますが、双方向リストのような本質的にループだらけの構造は逆に書きづらいかもしれません。
で、とりあえず破壊的ソートは「与えられたリストのcarをピボットにしてピボットより小さいモノをピボットの前に移動する」って所までできました。あとはピボットの前と後ろとを再帰的にソートしていけばいいのですけど…ここまで書いて設計がまずい気がしてきました。
(define (sort! head tail)
(if (null? head)
()
(find head (cdr head) tail (lambda (x) (< x (car head))))))
(define (shiftOne head tail)
(display "shiftOne")
(display tail)
(display "\n")
(if (null? tail)
tail
(if (null? (car (cdr tail)))
(begin
(set-car! (cdr tail) (car tail))
(set-car! tail ())
head)
(shiftOne head (cdr tail)))))
(define (shift wholeList)
(display "shift")
(if (null? (car wholeList))
wholeList
(shift (shiftOne wholeList wholeList))))
(define (find aList start end condition)
(if (equal? start end)
()
(if (condition (car start))
(begin
; rotation
(let ((x (car start)))
(set-car! start ())
(set-car! (shift aList) x))
; partial sort required
(find aList (cdr start) end condition))
(find aList (cdr start) end condition))
))
うーん。「リストのこの範囲にこの処理を行う」だとか「この値を手前のこの位置に移動して間の物はずらす」だとかを定義して、それを組み合わせるほうがよさそうです。でももう26時半だしなぁ。
凡例{ ●: 単一エントリーへのリンク, □: そこから最新記事までを一覧表示, ■: そこから最新記事までをwindow.openで開く}(comming soon)
2006年06月02日
