Computer Algorithm and Information Technology

全73件の内、新着の記事から10件ずつ表示します。

まだ標準じゃないのかな

投稿者：和投稿日：2005年 9月15日(木)20時30分13秒

STLの拡張ですかね。例の外部クイックソートは自作の外部マージに比べ5倍(!)の速度が出せました。転送回数が少ないです。外部マージ15000,外部クイック3000,内部クイック900。 128MBデータをソートしました。外部の場合バッファは64KBでやりました。最初エラーか！？と思いましたがそれぞれの実行の結果を比較するとまったく同じで。乱数、int,short,char,昇順、逆順、シャッフル、色んな要素数、色んなバッファサイズを試しましたが結果はあっていました。ちょっと感動。

HDD

投稿者：DO++ 投稿日：2005年 9月15日(木)07時59分52秒

の特性なども大きく影響しそうですね。外部記憶領域を利用したアルゴリズムについては私も調べ始めたところですが、ライブラリなどもいくつかありそうなのでそれらを参考にするとよいかも私が知っているものとしてはSTXXLがあります。 http://i10www.ira.uka.de/dementiev/stxxl.shtml

バッファリングを工夫して…

投稿者：和投稿日：2005年 9月 7日(水)02時03分43秒

アルゴリズムに特化したバッファリングを考えてます。メモリに対する操作、メモリからHDDへ書き込み、メモリからHDDへ読み込みの時間はそれぞれ同じぐらいでした。さらに使えるメモリが少なくなってしまいますが、非同期で読み込み書き込みすると効果高いかも？と考えています。 4つのファイルを使ったのは単に左側読み込み右側読み込み左側書き込み右側書き込みファイルが別にあると綺麗に決まるからです。 N個のファイル…うーむ複雑ですね。クイックを外部ソートに適応したら使えるメモリがマージの2倍になるので実は早いかもしれません。アルゴリズムに特化したバッファリングする必要がありますね。

おひさです。

投稿者：DO++ 投稿日：2005年 9月 7日(水)01時36分42秒

>現在バッファサイズをいくつにするかなどを検討しています。 >ソースみて他に改良点ないでしょうか？　実際につくってみたんですね。ファイルを常に４個だけ保持してやるとかはあまり見たことがないです。よくある話なんでしょうかね。　うまくいくかはわかりませんが、マージソートは同時に2個マージすることに限る必要はなくて、ｎ個同時にマージすることもできます。外部記憶領域が読み込みより書き込みの方がコストがかかるということも聞いたことがあるので、書き込み回数を減らすためにもn個同時にマージとかも試すといいかも。

久々にオセロ

投稿者：和投稿日：2005年 9月 1日(木)10時20分17秒

4×4のオセロの完全解をディスクに保存し、最適な手を検索できるようになりました。 6×6はまだです。実行すると数日かかりそうなので十分にテストする必要があります。その過程で作った以前より大分高速な外部ソートです。これはこれでどこまで高速化出来るか最近はまっています。現在バッファサイズをいくつにするかなどを検討しています。ソースみて他に改良点ないでしょうか？

http://urrryyy.hp.infoseek.co.jp/computer/outer_sort.htm

計算量

投稿者：DO++ 投稿日：2005年 5月 1日(日)08時50分27秒

編集済

前で話していた意味は、計算量では同じですね。混同してましたでも、最近実装しているもので特にそのへんの「実際計算量」とかいうものを意識していたもので。O(1)で定数だったためしはそうそうなくて・・ >オセロの完全読みきりは5万nps(秒/局面) 　（局面/秒）？　数GHz（数十億/秒）で動く今はディスク、キャッシュの扱い方をうまくやれば不可能な数ではなさそうですけど、簡単ではなさそうな。評価関数の設計がうまいんでしょうかね。

言葉の取り方でちょっと行き違いが

投稿者：和投稿日：2005年 5月 1日(日)00時41分0秒

ここでいう計算量とはいわゆるビッグオーではなく、実際の速度という意味ですね。元に戻りますがオセロの完全読みきりは5万nps(秒/局面)を操作できるぐらいです。しかしzebraっていうオセロは評価関数という重い処理をしながら50万npsという性能を出しています。神だ…。

なるほど

投稿者：DO++ 投稿日：2005年 4月30日(土)12時01分28秒

>メモリでやったときとは変らないでしょうね。単に出来るだけシーケンシャルにやれるというだけで。ディスクの密度がどんどん高くなっているためシーケンシャルとランダムでは今では10倍から100倍程度の差が出ているそうです。だから、シーケンシャルにするというのはすごく意味があると思います。DBMSではディスクアクセスが多いためこのへんはかなり注意して作られているみたいですけど >シリアルATA2の300MB/SECだったら性能発揮できるかもしれませんね。メモリ上のアクセスでもシーケンシャルとランダムでは性能は違うので（キャッシュに載りやすいかということとも別に）メモリ上でも意味があるかも。あ、でも４つのメモリにふりわけるなんてないか

計算量は

投稿者：和投稿日：2005年 4月29日(金)00時56分25秒

メモリでやったときとは変らないでしょうね。単に出来るだけシーケンシャルにやれるというだけで。シリアルATAは150MBなんでもしかしたら帯域は足りないかも。シリアルATA2の300MB/SECだったら性能発揮できるかもしれませんね。シーケンシャルといっても実際にはファイルが断片化しているかもしれないです。ちゃんとデフラグ後に実行しないとダメですね。

http://urrryyy.hp.infoseek.co.jp/computer/outer_sort.htm

4つのドライブ

投稿者：DO++ 投稿日：2005年 4月28日(木)14時28分13秒

とかってないなぁ・・。買うか(笑）計算量解析とかっては難しいですかね。単純に計算量が1/4になるとかもっとへるとか

以上は、新着順21番目から30番目までの記事です。

1 2 3 4 5 6 7 8 | 《前のページ | 次のページ》