スパコンで力任せに数独の難しい問題を作<del>る</del>ったつもりが簡単な問題だった件
どうやら人間の手で解いたら、簡単に解けてしまうようです。 ここでの難易度の定義に含めていない解法(n国同盟など)を使うと、難しくない問題になっているのかもしれません。 その後調べたところ、基本テクニックだけで解けてしまうことがわかりました。 Pencil Marksが唯一残ったものしか確定しない、というDeterministic Solverを使っていたのが原因で、 難しくない問題を「難しい」と誤判定してしまったようです。 3月13日版よりだいぶ難易度があがったはずです。 概要 スパコンを使って力任せに数独の難しい問題を作ってみたところ、 2013年3月現在、おそらく世界で一番難しい問題を作ることに成功した失敗した。 上図がスパコンを用いて作られた、おそらく世界で一番難しい問題(2013年3月現在)。 後述する難易度の定義では、深さが10、通常幅が183530、平均幅が約100571である
Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream
<追記>ベンチマークプログラムに誤りがありました。ソート済のシーケンスに対してソートを掛けていました。ご指摘ありがとうございます＞ak氏 そんな夢のようなソートアルゴリズムがあるのかというと、あるらしいんです。それがtim sortと呼ばれるアルゴリズムです。 画期的（？）なソートアルゴリズム「Sleep Sort」：濃縮還元オレンジニュース｜gihyo.jp … 技術評論社 このあたりで拾ってきたネタですね。 merge sortを改良したアルゴリズムで、安定*1しており、しかも実行速度にも優れているとか。アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。 ならば当然Perlのソートも…と考えるわけですが、まず評価のためにJavaのソースをC++にそのまま移植してみました。それがこれ（いちおうテスト済）： https://github.co
![quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream](https://cdn-ak-scissors.b.st-hatena.com/image/square/f9103c273a45047a455a47c2322a4ec545cd77ee/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127143682567%2F17680117127143702106%2F1558185862)
画像圧縮アルゴリズム (5) LZ法
この章では、現在のデータ圧縮・画像圧縮などで広く用いられているLZ法について説明します。 前章までで説明したハフマン圧縮では、個々のデータをハフマン符号に変換して圧縮を試みるというものでしたが、LZ法では、あるデータ列に着目して、それが以前に出現したことがあるかをチェックし、すでに出現したことがあるのならば、そのデータ列を示す何らかの符号(当然、データ列より短くなければなりません)に置き換える処理を行うことにより、圧縮を行っています。 LZ法には、いくつかの種類があり、その種類によってさらに名称が変わります。しかし、その違いは符号化の方法だけで、処理の内容については全て同じです。 LZ法は、Abraham LempelとJacob Zivの二人による共同開発によって、1977年に誕生しました。正式名称はZiv-Lempel codingですが、間違ってLZ法として紹介したことから、現在の
常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream (legacy)
TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。 Genius sorting algorithm: Sleep sort 1 Name: Anonymous : 2011-01-20 12:22 諸君！オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う？ #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 なん…だと
良い乱数・悪い乱数
Ｃ言語標準ライブラリの乱数rand( )は質に問題があり、禁止している学会もある。 他にも乱数には様々なアルゴリズムがあるが、多くのものが問題を持っている。 最も多くの人に使われている乱数であろう Visual Basic の Rnd の質は最低である。 そもそも乱数とは 乱数とは、本来サイコロを振って出る目から得られるような数を意味する。 このような乱数は予測不能なものである。 しかし、計算機を使って乱数を発生させた場合、 次に出る数は完全に決まっているので、予測不能とはいえない。 そこで、計算機で作り出される乱数を疑似乱数(PRNG)と呼び区別することがある。 ここでは、特にことわらない限り乱数とは疑似乱数のことを指すとする。 計算機でソフト的に乱数を発生させることの最大のメリットは、 再現性があることである。 初期状態が同じであれば、発生する乱数も全く同じものが得られる。 このことは
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
VisuAlgo moves to https://visualgo.net/en
IDEA * IDEA