suffix arrayを一番簡単なアルゴリズムで実装する - アルゴリズム学習(その6) - $shibayu36->blog;
文字列アルゴリズムを学んでいると、suffix array(接尾辞配列)という配列が出てくる。これは文字列の接尾辞の集合を辞書順にソートし、その順でそれぞれの接尾辞の文字列中の開始位置のindexを格納した配列のことである。以下が参考になる。 接尾辞配列 - Wikipedia サービス終了のお知らせ 例えばbananaの場合、接尾辞は - banana (position=0) - anana (position=1) - nana (position=2) - ana (position=3) - na (position=4) - a (position=5)となり、これを辞書順にソートしたものは - a (position=5) - ana (position=3) - anana (position=1) - banana (position=0) - na (position=
【アルゴリズム】Hash Tableの概要 - Qiita
対象読者 アルゴリズムを勉強したい人 Javaで実装してみたい人(次回) Java/アルゴリズム勉強シリーズです。今回はhash tableを勉強したので実装してみます。 Javaのクラスとしては、単一スレッドなど、synchronizationを気にしないケースではHashtableよりもHashMapの方がよく使われるようです(こちらの記事で言及しました)。今回はJavaによらず、データ構造の一般論としての hash tableを指して、記事を書いていきます。次回Javaで実装します。 hash table ハッシュテーブル wikipediaより ハッシュテーブル (hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。ハッシュテーブルは連想配列や集合の効率的な実装のうち1つである。 概要 キ
色の距離（色差）の計算方法 - Qiita
はじめに 例えば以下の2つの画像，左と右の色を比べたときにどちらの方が色が近いと思いますか？ #FF0000と#400000 #FF0000と#FFBF00 単純にRGB値の距離を計算すると二つの色の距離は同じ． しかし１つ目の画像は単に暗くなっただけなのに対して，２つ目の画像は色相が変わっているため，例えば写真のマッチングを取る場合は上の方が似た色として判別した方が都合が良くなったりする． こうした色の距離，色差の計算について実装してみた． ソースはJava 8を前提に書いているが，Androidでも動作する（はず）．ただし，AndroidではColorクラスが違うため適宜変更してほしい． 下準備 JavaとAndroidのColorクラスの違いや，RGB値の保存などを目的として下記のクラスを準備する．RGB値のint値を受け取るとそれぞれをdoubleの値として配列を作成し，保存する．
Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne
essential information that every serious programmer needs to know about algorithms and data structures Online content. This booksite contains tens of thousands of files, fully coordinated with our textbook and also useful as a stand-alone resource. It consists of the following elements: Excerpts. A condensed version of the text narrative, for reference while online. Lectures. Curated studio-produc
Mathの高速化を検証する - Qiita
Mathは本当に遅いのか 色の距離（色差）を計算するときにちょっとだけ試してみたので，実際によくある（小手先）高速化手法でMathが速くなるのか検証してみた． 検証方法 JavaとAndroidで検証． 単純に実行時間をSystem.nanoTimeで取得し，比較している． 検証順や検証タイミングで最適化がかかったりするので，何回か実行して落ち着いた値で比較している． Javaの検証はIntel Xeon E5 3.5GHzのMac Pro，Androidの検証はQualcomm Snapdragon 800 MSM8974 2.2GHzのSO-02Fで試している． 従来のMathクラスと，実装したDMathクラスで比較した． 10万回実行して1回あたりの実行時間をnano秒で表示している．詳しい方法は一番下を参照． べき乗の高速化 べき乗を計算するMath.pow()は小数のべき乗もサポ
深さ優先探索を使った部分和問題の解法。 - かずきちの備忘録
2016 - 01 - 09 深さ優先探索を使った部分和問題の解法。 競プロ 蟻本 アルゴリズム AtCoder のARCのA問題が終わり、ちょくちょくABCのC問題を解いていたのですが、 TLE(Time Limit Error ) が頻発し、これは駄目だということで プログラミングコンテスト チャレンジブック、通称・蟻本 を購入しました。 競プロerのバイブルなんだとか。 ということで、今回は蟻本にも載っている 全探索 アルゴリズム の一つ、 「 深さ優先探索 」 を使って問題を解いてみようと思います。言語は Java です。 というのも、蟻本で出てくる ソースコード の言語は g++ 用に書かれた C++ なので(とても読みやすいですが)、 Java では少し違うので、 Java での記述例を出してみることにしました(とはいえ、問題の核となる アルゴリズム 自体は同じですが)。 そも
Red-Black Tree by Java -- これで分かった赤黒木
このページは、マップと呼ばれるデータ構造の実装の１つである赤黒木 (２色木、red-black tree)について解説するページです。赤黒木は、要素の 挿入・削除・検索などの操作が \(O(\log n)\) の計算量で実行出来る平衡木 です(\(n\) は要素数)。赤黒木はやっていることは単純なのですが、とにかく 場合分けがたくさんあって、習得しようとしながらもくじけてしまった人も 多いのではないでしょうか？ しかし、ご安心ください。このページは場合分けを出来るだけ減らし、 挿入操作で４パターン、削除操作で８パターンさえ理解すれば赤黒木が分かる ように書かれています。削除操作に関しては、左右対称のパターンを省けば ４パターン理解すればおおむね OK です。これから赤黒木を勉強しようという人 はもちろん、一度は勉強したが挫折してしまったという人も是非とも読んでみて ください。 【準備】 ま
#JJUG - Java で最速のハッシュアルゴリズムを求めて
【東京】【聴講者募集】JJUG ナイト・セミナー 「ビール片手にLT&納涼会」の発表資料です。 https://jjug.doorkeeper.jp/events/28182
組み合わせを列挙する - kuidaored’s blog
SRMとかやってると組み合わせをみる必要があったりして、そのたびに同じようなコードを書いていたので、なんとか出来ないかと思って書いてみた。 import java.util.*; public class Combinations<T> implements Iterator{ private List<List<T>> combinations; private List<T> list; private int[] index; private boolean[] visited; private int r; private Iterator<List<T>> iterator; public Combinations(T[] array, int r){ this.list = Arrays.asList(array); this.index = new int[r]; this.
Visualizing Garbage Collection Algorithms
Most developers take automatic garbage collection for granted. It’s just another amazing feature provided by our language run-times to make our jobs easier. But if you try to peek inside a modern garbage collector, it’s very difficult to see how they actually work. There are thousands of implementation details that will confuse you unless you already have a good understanding of what it’s trying t
Java8 で java.lang.Object#hashCode() の生成アルゴリズムが変更されていました。 - 地平線に行く
java.lang.Object#hashCode()の性質という記事で書いたのですが、Java の Object#hashCode() の値はただの乱数となっています。 この乱数のアルゴリズムが、Java SE 8 で「線形合同法」から「XORシフト方式」に変更になっていました。 といっても、変更されたのはたった1文字。 VMオプションのデフォルト設定が -XX:hashCode=0 から -XX:hashCode=5 に変わっただけでした。 hotspot-rt Udiff hotspot/src/share/vm/runtime/globals.hpp どういうこと？ もともと、Java の以前の実装*1 *2から、Object#hashCode() のアルゴリズムはVMオプション -XX:hashCode=? で選べるようになっていました。 ですが、デフォルトは長いこと 0(=線形
グラフの自動レイアウトに挑戦 #1 グラフ構造をSVGで表示
2022-08-12 13:50:22 作成したアプリケーションとソースコード アプリケーション： https://refd6y.csb.app/ （ブラウザで実行します） ソースコード： https://codesandbox.io/s/graph-layout1-refd6y はじめに 連載記事のトップのところに書いた図はこのようなものだ。 これをコンピュータに自動配置させたい。 Eadesのばねモデル このような、つながった複数の物体をコンピュータに自動配置させるのは「グラフ描画」または「グラフレイアウト」と呼ばれる分野であり、さまざまなアルゴリズムが研究されている。この連載記事では比較的単純な「Eadesのばねモデル」というアルゴリズムを採用する。 Eadesのばねモデルとは、次のようなモデルをつくって物理シミュレーションすることで、物体を配置するアルゴリズムだ。 各ノード(頂点)
グラフ理論ライブラリの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"));
EclipseやSpringで使われている基盤技術OSGiとは (3/3) - ＠IT
【特集】Java本来の実力を引出すOSGi徹底解説 日立ソフトウェアエンジニアリング株式会社 一瀬成広 株式会社日立製作所 中央研究所 中野正樹 2009/5/12 ■ OSGiバンドルの開発ツールとしての「Eclipse PDE」 OSGiバンドルの開発を支援するツールもオープンソースとして開発されており、OSGiバンドルの開発環境も整っています。 代表的な開発ツールとしては、「Eclipse PDE（Plug-in Development Environment）」があります。Eclipse PDEは、基本的にEclipseのプラグインの開発環境ですが、Eclipse 3.2用のものから標準のOSGiバンドルの開発ができます。 新しいプロジェクト作成時にプラグインプロジェクトを選択すると、標準のOSGiフレームワークをターゲットとしたプラグイン（バンドル）を開発するオプションがあります
統計的に正しいランキングを行う方法をJavaで書く - バイオインフォマティクスって何ですか？
Java | 統計的に正しいランキングを行う方法を見たのでちょっとJavaで書いてみる。はじめになにがしたいかというと、「レイティング」というのをご存じでしょうか。Amazonとかで商品を購入者が星つけて評価したりしてるやつ。ああいうので「良かったランキング」というのを作りたい。みんなが「購入して良かった」という評価をつけてる商品は、他の人にとっても「良かった商品」になる可能性が高い。いい商品だということがわかるわけです。問題点じゃあどういうふうにランキングをつければいいの？ということを考えると、次の問題にぶちあたる。評価してる人の数の違い。例えば、Aという商品は100人が評価していて、平均の星の数は 4.8 だとする。一方、Bの商品は1人が星5つで評価していたとする。このとき、Aの商品とBの商品ではどちらをランキング上位にすればいいだろうか？あなたならどちらを買いたい？Aはたくさんの人が
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
IBM Developer
Algorithm Database
Javaを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計 (リスト＆マップ編) - 何かしらの言語による記述を解析する日記