<< Prev Page Next Page >>

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。


凄いバカなプログラム

最近算数ばっかりですねこのブログ。だって面白いんだもの。

きしだのはてな「凄いバカなプログラムを作ろう」

こないださくらいさんと「バブルソートってたぶん再帰でできるよね」とかって話してたのですが、僕は今回、従来のソートアルゴリズムを越える画期的なアルゴリズムを考案しました。

名付けて「ショットガンソート」です。アメフトのショットガンフォーメーションをちょっとイメージしてます。

ショットガンソートのメリット

  • 計算量がたぶんO(1)。うわどうしようなんか賞とかもらっちゃったら!

追記。計算「量」は確かに要素数に比例なのでO(n)でした。で、計算「時間」が要素数によらないからO(1)?計算量と計算時間のオーダーが違うところがバカアルゴリズム?

ささいな問題点

  • ソートする数の大きさにより時間がかかることがある。でも時間がかかっている間はCPU資源を全く消費しないため、きっと他のプログラムを走らせられます。
  • ソートできる配列の長さが計算機の物理リソースに依存する。でもこれは他のアルゴリズムでも同じ事ですので。
  • この実装では安全を考慮していますが、高速化と引き替えに時々ちょっとソート間違えるかもしれない。あとWindowsだと10msの精度がゴニョゴニョ

ではコードをご覧ください

追記。try-catch使っちゃってるじゃんこれ。残念。

追記。どんどんバカが伝染していく(寝ても覚めても技術屋様)(褒めてます)。怖いです。


public class SortTest { protected static SortTest[] printers = { new SortTest(), new SortTest() { public void printNotNull(int[] data) { int p = BValue.bValue(data.length > 0); printers[p].printSorted(data); } public void printSorted(int[] data) { new ShotgunSorter().sort(data); } } }; public void printNotNull(int[] data) { System.out.println("nullでっせ"); } public void printSorted(int[] data) { System.out.println("空でっせ"); } public static void print(int[] data) { int p = BValue.bValue(data != null); printers[p].printNotNull(data); } /** * @param args */ public static void main(String[] args) { print(new int[]{14, 13, 31, 2, 24, 19}); print(new int[]{3, 2}); print(new int[]{5}); print(new int[]{}); print(null); } } /** * ショットガンソートアルゴリズムの実装 */ class ShotgunSorter { private static ShotgunSorter[] sorters = { new ShotgunSorter(), new ShotgunSorter() { protected void bang(int[] data, int idx) {} protected void waitFor(int idx) {} } }; private static Bullet[] bullets; public void sort(int[] data) { bullets = new Bullet[data.length]; // 要素の数だけ弾丸を発射する。 // 小さい数ほど早く着弾する・・・ bang(data, 0); // 全部終わるまで待つ。 waitFor(0); System.out.println(); } protected void waitFor(int idx) { synchronized(bullets[idx]) { } int p = BValue.bValue(idx + 1 >= bullets.length); sorters[p].waitFor(idx + 1); } protected void bang(int[] data, int idx) { bullets[idx] = new Bullet(data[idx]); new Thread(bullets[idx]).start(); int p = BValue.bValue(idx + 1 >= data.length); sorters[p].bang(data, idx + 1) ; } } /** * 弾丸 */ class Bullet implements Runnable { private int number; Bullet(int i) { number = i; } public void run() { synchronized(this) { try { Thread.sleep(number * 100); System.out.print(number); System.out.print(", "); } catch(InterruptedException e) { } this.notifyAll(); } } } class BValue { /** * trueなら1, falseなら0を返すメソッド。 */ public static int bValue(boolean b) { return 5 - Boolean.toString(b).length(); } }

この記事に対するコメント

ありがとうございます

>hituziotoko様
「管理人のみ表示を許可」にチェックされたため、他の方に話がつながりにくくなってしまったかもしれません。もしよろしければいったん削除させていただいて、こちらで誰からでも見られるように同じ文面にて再掲載してもよろしいでしょうか?

通りすがりとのことでもうここをごらんになることはないかもしれませんが・・・

【2007/03/26 11:34】URL | とっくり #-[ 編集]

いえいえ、実はしっかり見に来てますw。
無意識にチェックつけてしまったようです。
公開して頂いても全く構いませんよー。

【2007/03/26 13:31】URL | hituziotoko #-[ 編集]

面白いアイディアですね。ネーミングもかっこ良いし。(^_^)
通りすがりですが、一言だけ。
このままだと負値のソートがうまくないかもですね。
そして[30000,200000,10000]なんて配列がインプットだったら、、、
ちょっと泣いてしまいますね。

【2007/03/26 17:50】URL | hituziotoko #-[ 編集]

復活させました

hituziotokoさんになりかわってコメントを公開にしました。ありがとうございます。

で、負値のソート…想定してませんでした。2^nとかにすれば負の数でも正の単調増加関数になるからなんとか対応可能かと。
大きな値のソート…こちらはもちろん想定しております。本文にも書いて有るとおり、この忙しいご時世ですから、コンピュータがこのソート以外の他の作業を何もしてないはずがありません。ソートに時間がかかったとしても、スレッドが止まっている間に他のプログラムがCPUを有効に使ってくれるでしょう。

…えと、じょーだんですから。
バカプログラムを作るのが目的なのでこのへんで勘弁してくらはい。

【2007/03/26 17:57】URL | とっくり #-[ 編集]

この記事に対するコメントの投稿



管理者にだけ表示を許可する

この記事に対するトラックバック

トラックバックURL
http://tockri.blog78.fc2.com/tb.php/44-6df5a8d3
この記事にトラックバックする(FC2ブログユーザー)

凄いバカなプログラム

きしだのはてな凄いバカなプログラムを作うコレをまあ楽しく見てたわけですが…http://tockri.blog78.fc2.com/blog-entry-44.html↑には度肝を抜かれました。計算回数は少ないし、ロジックも超シンプルだ JAVAエンジニアの覚え書き兼日記【2007/03/31 14:44】


上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。