要素の挿入、削除、ランダムアクセスが全部高速なリストを作った - kaisehのブログ
スキップリスト（Skip List）は1990年に発表された比較的新しいアルゴリズムで、要素の挿入や削除、検索を平衡木と同等のパフォーマンスで実行可能なリスト構造です。 Skip Listは連結リストの多層構成になっています。路線に例えると、最下層のリンクは各駅停車のように、全要素を結んでいます。一方、上層のリンクは急行や特急のように、途中の要素をスキップするようになっています。この路線を特急→急行→…→各駅と乗り継ぐことで、目的の要素に高速に到達できる仕組みです。もっと詳しい解説はこちらやこちらにあります。 で、ここからが本題です。Skip Listの実装はいくつも出ているんですが、Sorted Listとしての実装ばかりで、要素を任意順序で格納できてランダムアクセス（indexを指定してのアクセス）可能なSkip Listが見つからなかったので、自分で作ってみました。 通常のSkip
グラフ理論ライブラリの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"));
04-g1-paper-ismm.pdf [GarbageFirst Garbage Collection]
Garbage-First Garbage Collection David Detlefs, Christine Flood, Steve Heller, Tony Printezis Sun Microsystems, Inc. 1 Network Drive, Burlington, MA 01803, USA {david.detlefs, christine.flood, steve.heller, tony.printezis}@sun.com ABSTRACT Garbage-First is a server-style garbage collector, targeted for multi-processors with large memories, that meets a soft real-time goal with high probability,
グラフを扱うJavaライブラリ「Jung」の紹介 - Twitterのグラフ構造を視覚化 - public static void main
java-ja 第12回のLTで話そうと思ったのですが、出番がなかったので資料をブログで公開しておきます。 Jungは研究などでグラフ構造が出たときに、理解しやすくするために可視化するのに使っています。他にもいくつかグラフを扱うライブラリは存在していますが、日本語の資料があったのと拡張可能なことが多かったのでJungを結果的に使うようになりました。 以下はそのJungについての簡単な解説です。 Jungとは Jungの正式名称はJava Universal Network/Graph Frameworkで、ネットワーク(グラフ) 構造の分析や視覚化を行うためのJavaのOSSライブラリです。グラフ理論、データマイニング、ソーシャルネットワーク分析のアルゴリズムを数多く実装しています。 安定バージョンは1.7.6で最新は2.0betaで、BSDライセンスで使用できます。 http://jun
2008-11-20 - きしだのはてな: スレッドで投機的実行を実現する方法を考えてみた
スレッドのロックをする場合、読み込み処理同士は他に影響を与えないのでロックをする必要がない。 Javaでは、ReadWriteLockを使うと、読み込みスレッドは同時にいくつでも動くけど書き込みスレッドは他のスレッドが動いていると処理をまち、書き込み処理中は読み込み処理もできなくなる。 ただ、ReadWriteLockの場合、処理が読み込みなのか書き込みなのかがロック取得時に決まっている必要がある。 なので、あらかじめ読み込み処理か書き込み処理か決めれず、通常は書き込みを行わないけど条件によって書き込むというような場合にはReadWriteLockは使えない。 ということで、書き込みの頻度が少ない場合には、とりあえず処理を行っておいて、書き込みなければそのまま実行、書き込みがあっても他のスレッドによって値が変えられてなければやはりそのまま実行、もし他のスレッドによって書き込みがあれば、処理
GoogleのMapReduceアルゴリズムをJavaで理解する
GoogleのMapReduceアルゴリズムをJavaで理解する：いま再注目の分散処理技術（前編）（1/2 ページ） 最近注目を浴びている分散処理技術「MapReduce」の利点をサンプルからアルゴリズムレベルで理解し、昔からあるJava関連の分散処理技術を見直す特集企画（編集部） いま注目の大規模分散処理アルゴリズム 最近、大規模分散処理が注目を浴びています。特に、「MapReduce」というアルゴリズムについて目にすることが多くなりました。Googleの膨大なサーバ処理で使われているということで、ここ数年の分散処理技術の中では特に注目を浴びているようです（参考「見えるグーグル、見えないグーグル」）。MapReduceアルゴリズムを使う利点とは、いったい何なのでしょうか。なぜ、いま注目を浴びているのでしょうか。 その詳細は「MapReduce : Simplified Data Proc
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
JGraphT