Luceneでレーベンシュタイン距離を求める - CLOVER🍀
先日、Apache Solrを使った「もしかして検索」や単語のサジェストみたいなところを調べていて、「レーベンシュタイン距離」なるものがあることを知りました。 レーベンシュタイン距離 - Wikipedia このあたりも参考になりました。 編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー スペルミス修正プログラムを作ろう また、Luceneで行った場合のエントリも。 2つの文字列間の距離計算の抽象化（スペルチェック）（2.4） | 関口宏司のLuceneブログ SolrのSuggesterを試してみる Wikipediaによれば、レーベンシュタイン距離は2つの文字列がどの程度異なっているかを示す距離で（編集距離）、文字列を何回の手順でもう片方の文字列とするように変形できるか、という感じみたいです。 同じく、Wikipediaのまんまですが、「kitt
Java で最速の乱数生成器を目指す: (3) ガンマ分布に従う乱数
TL;DR: ガンマ分布に従う乱数生成器を Java で実装し、Commons Math の実装と比較して 最大で約 16 倍 (任意の形状パラメータの乱数を生成する場合) の速度効率を達成しましたよ、というお話です。 (Header image: Mundhenk at en.wikipedia) ガンマ分布に従う乱数生成の実装方法Permalink これまで 正規分布に従う乱数生成、指数分布に従う乱数生成 をそれぞれ Java で実装してきましたが、今回はガンマ分布に従う乱数生成を Java で実装してみます。 ガンマ分布 は、形状パラメータ k>0 と スケールパラメータ θ>0 (もしくは形状パラメータ α=k と比率パラメータ β=1/θ) の 2 つのパラメータを持ち、その確率密度関数は次の式で表されます。 f(x)=xk−1e−x/θΓ(k)θk ガンマ分布の形状パラメータ
#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.
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(=線形
darts-clone の Java 移植 - アスペ日記
矢田さんのdarts-cloneをJavaに単純に移植したので、GitHubに上げました。 https://github.com/hiroshi-manabe/darts-clone-java darts-clone については、矢田さんの日記に詳しい解説があります。 これを移植したときは、仕事で使えるかと思ってやってみたのですが、結局そのときは容量の小ささを重視して takawitter さんのtrie4jを改造して使うことになりました。 せっかくなので置いておきます。 これはいろいろな事情があり、かなり Java 的でないものになっています。 その背景には、上記の trie4j の存在もあります。 trie4j はダブル配列も含むため、通常であればそちらを使うのが簡単でいいと思いますが、darts-clone はいろいろと変態的な工夫（1ノードあたり 4 バイトしか消費しないとか、値が
素数列挙について - MugiCha
Competitive Programming Advent Calendar 3日目は、数学っぽい話をしたいと思います。 N以下の素数をすべて求めよ。 N以下の素数の個数を求めよ。 A以上B以下の素数の個数を求めよ。 こんな感じの問題を見たことがあると思います。また問題としてでなくても、解く過程にこのようなサブ問題を解かなければいけない場合もよくあると思います。素数については説明しなくてもいいですよね？ このような問題を素数列挙と呼ぶことにします。素数列挙ができれば、大きい数の素数判定や素因数分解をめっちゃ高速化したり、トーティエント関数、メビウス関数等、数学系のいろんな関数を求めたりできます。最近のもので素数列挙がほぼ必須のものだと Codeforces Beta Round #86 (Div. 1 Only) C. Double Happiness ICPC 国内予選 2011 A
LZO圧縮は速い - maachangの日記
最近圧縮ファイルの速度について気になるので、いろいろ調べてみると、圧縮率は低いが、速度は爆速だと言われているLZOと言うのがあるみたいだ。 HTTPの圧縮にも使われているGZIPは結構オーバーヘッド小さいと思っていたのだが、実際にLZOをJavaのJNI経由で呼び出すJava実装をSeabassNativeIOに追加して、それぞれの速度を量ってみる。 ちなみにGZIP圧縮解凍は、java.util.zip.GZIPInputStream,java.util.zip.GZIPOutputStreamで処理する。 これらをそれぞれ、java.io.ByteArrayInputStream,java.io.ByteArrayOutputSteamをかまして処理する。 private static final int LEN = 20 ; /** * @param args */ public s
第76回 計算量の数学 計算量と実際のコード その2 | gihyo.jp
物事はシンプルであればあるほど記憶しやすく、組み合わせて何事かを処理するのも容易になります。アルゴリズムもシンプルであればあるほど優れていると言えます。ただ、物事をシンプルにする、とひとことで言っても、いくつかの処理のステップをまとめて1つの名前を付けること、つまり、抽象化によってシンプルにした場合には注意が必要です。抽象化してシンプルになった名前の裏では、汗水たらしててんてこ舞いして働いている人がいるかもしれませんから。営業担当者が「簡単です！うちに任してください！」といって取ってきた仕事を、製造現場の労働者が泣きの涙で作って出荷している・・・という笑えない状況と、どこか似ているような似ていないような。いえ、決して営業さんは悪くないんですよ。悪くないんですけど。 図76.1 笑顔の営業、涙の現場 計算量：ハッシュサーチの場合O(1) バイナリサーチは十分高速な検索アルゴリズムです。これ以
JGraphT
a Java library of graph theory data structures and algorithms now with Python bindings too! flexible any object can be used for vertex and edge types, with full type safety via generics edges can be directed or undirected, weighted or unweighted simple graphs, multigraphs, and pseudographs unmodifiable graphs allow modules to provide “read-only” access to internal graphs listenable graphs allow ex
GoogleのMapReduceアルゴリズムをJavaで理解する
GoogleのMapReduceアルゴリズムをJavaで理解する：いま再注目の分散処理技術（前編）（1/2 ページ） 最近注目を浴びている分散処理技術「MapReduce」の利点をサンプルからアルゴリズムレベルで理解し、昔からあるJava関連の分散処理技術を見直す特集企画（編集部） いま注目の大規模分散処理アルゴリズム 最近、大規模分散処理が注目を浴びています。特に、「MapReduce」というアルゴリズムについて目にすることが多くなりました。Googleの膨大なサーバ処理で使われているということで、ここ数年の分散処理技術の中では特に注目を浴びているようです（参考「見えるグーグル、見えないグーグル」）。MapReduceアルゴリズムを使う利点とは、いったい何なのでしょうか。なぜ、いま注目を浴びているのでしょうか。 その詳細は「MapReduce : Simplified Data Proc
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - bacak/TrAP: TrAP is a tree averaging program. It computes medians and means of phylogenetic trees.
Sim Queue in Java (part 1/2)
GitHub - jparkie/PDD: Advanced Bloom Filter Based Algorithms for Efficient Approximate Data De-Duplication in Streams
Javaでフィボナッチ数を求める関数を末尾再帰最適化する
The NAG Blog: The NAG Library for Java – An Illustrative Example Using Black And Scholes Pricing
Sign in - Google Accounts
加藤 和彦 Kazuhiko KATO, Dr. Prof.
http://www.algosort.com/