Java競技プログラミングメモ - Qiita
class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; }else{ ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasN
Arrays#sort - てきとうなメモ
JavaにはArrays#sortというメソッドがあって配列をソートすることができる．ソートする対象がプリミティブ型だとquick sortで実装され，オブジェクトだとmerge sortで実装している．オブジェクトのソートはstableであるという仕様のためだと思われる． さらに，どちらの場合も配列のサイズが小さい場合はinsertion sortで実装されている．merge sortもquick sortも分割して再帰的に実行されるため，分割された配列の要素数が小さくなった時点で，insertion sortに切り替わっている．insertion sortはO(n^2)なんだけどもシンプルな実装なので短い配列の場合はそっちの方が効率がいいということだろう． その他いくつか面白いなと思った点． quick sortのpivot 配列を2等分(サイズが大きい場合は8等分)して，配列の両端と
グラフ理論ライブラリのJGraphTを使ってみた - kaisehのブログ
JGraphT JGraphTは、Javaのグラフライブラリです。グラフの描画ではなく、グラフ理論のモデルとアルゴリズムの方にフォーカスしています。とても使いやすかったので、紹介してみます。 無向グラフ UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>( DefaultEdge.class); g.addVertex("a"); g.addVertex("b"); g.addVertex("c"); g.addEdge("a", "b"); g.addEdge("b", "c"); System.out.println(g.vertexSet()); System.out.println(g.edgeSet()); System.out.println(g.edgesOf("c"));
西尾泰和のブログ: QuickSort祭り(一人)
後輩のQuickSortの課題を見ていて思ったのですけど、QuickSortは分割したリストのために新たに領域を確保していいかどうかによって難易度がだいぶ異なりますよね。高級言語は「QuickSortがこんなに簡単に書ける」なんてことを主張することがありますが、与えられた配列をその配列(+定数サイズ)の領域だけでソートするCとかで書かれたアルゴリズムを「真・クイックソート」だとすれば、新たな領域の確保を伴うQuickSortはちっとも早くないので「似非クイックソート」かもしれません。 で「似非クイックソート」なら簡単に書けるという話題で、ラボから赤坂某所への電車で書いたJavaのコード。 import java.util.Iterator; import java.util.Vector; public class Test { public static void main(String
GoogleのMapReduceアルゴリズムをJavaで理解する
GoogleのMapReduceアルゴリズムをJavaで理解する：いま再注目の分散処理技術（前編）（1/2 ページ） 最近注目を浴びている分散処理技術「MapReduce」の利点をサンプルからアルゴリズムレベルで理解し、昔からあるJava関連の分散処理技術を見直す特集企画（編集部） いま注目の大規模分散処理アルゴリズム 最近、大規模分散処理が注目を浴びています。特に、「MapReduce」というアルゴリズムについて目にすることが多くなりました。Googleの膨大なサーバ処理で使われているということで、ここ数年の分散処理技術の中では特に注目を浴びているようです（参考「見えるグーグル、見えないグーグル」）。MapReduceアルゴリズムを使う利点とは、いったい何なのでしょうか。なぜ、いま注目を浴びているのでしょうか。 その詳細は「MapReduce : Simplified Data Proc
dequeも忘れないであげてね（＞＜） - 神様なんて信じない僕らのために
Java 6 からdequeことArrayDequeが実装されています。 dequeって聞き慣れない！ とか思うかもしれないですが「Double Ended Queue」で両端キューです。 STLではvector,list,dequeはよく使われると思うのですが、Javaではなかったんですね。 特徴としては、 先頭への挿入（削除） 終端への挿入（削除） がO(1)で出来ます。 LinkedListでも同様のことができますが、LinkedListより高速で省メモリです。 （ただし、先頭と終端以外への挿入はLinkedListより遅いO(n)になります） また、ランダムアクセスも高速です。 アルゴリズム的にはリングバッファでvector（ArrayList）がわっかになっているようなイメージです。 headとtailの位置を覚えており、 配列（バッファ）の中のどこが先頭でどこが終端か、 を覚え
ネットで渋滞シミュレータ
Javaで動く渋滞シミュレータのミニ版です。いろいろな道路のタイプが選択でき、どれぐらいの自動車を走らせるのか、そのうちトラックの割合はどれぐらいにするのか？などのパラメータをマウスでぐりぐり動かして変更すれば、リアルタイムに反映されます。どういうのがきっかけで大渋滞が起き始めるのかが手に取るように分かります…。あと、渋滞が解消していく様子も分かります。 Microsimulation of road traffic http://vwisb7.vkw.tu-dresden.de/~treiber/MicroApplet/ 同じようなものだと、こういうのもあるようです。 Simulation Viewing http://www.cs.utexas.edu/~kdresner/2004aamas/index.html この理屈で行くと、全自動車にETCを付けると料金所付近が原因の渋滞は解消
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Java Compare and Swap Example - CAS Algorithm
西尾泰和のブログ: Javaで破壊的クイックソート