隣り合う2数の差は3以上、1つおいた数との差も3以上の順列は何通りあるか?

投稿者: Anonymous 次の問題を考えています。 (http://www004.upp.so-net.ne.jp/s_honma/mathbun/mathbun113.htm) 1からNまでのN個の整数で、  ア)隣り合う2数の差は3以上、1つおいた数との差も3以上  という条件を満たす順列は、何通りあるだろうか? ただし、順番を逆にしたものもそれぞれ1つずつ数えるものとします。 (より一般的には次のような問題です。 1からNまでのN個の整数で、  イ)隣り合う2数の差はD以上、1個おいた数との差もD以上、… 、D – 2個おいた数との差もD以上  という条件を満たす順列は、何通りあるだろうか? 例えば、N = 9、D = 3 のとき、 [3, 6, 9, 2, 5, 8, 1, 4, 7] [7, 4, 1, 8, 5, 2, 9, 6, 3] の2通りあります。) この問題の答えを速く求めるコードを考えてください。 以下、答えを求めるのが大変遅いコードです。 N = 11 D = 3 def check(a, i) j = 1 d_max…(Continue Reading)

vectorとlistどのように使い分けますか

投稿者: user4410 vectorとlistどのように使い分けますか?この様な質問を受けました。 そこで私は、vectorは配列でlistはリストだろう。 具体的な使い分けとなると、リストは切ったりつなげたりが得意でvectorは配列メモリが消費が少ない。 けれど、実際に表現するときに切ったりつなげたりして使う使い方なんて心当りがない。 中間地点への一つのデータを頻繁に削除・挿入するのだとしたら検索まで含めるとmapやsetの方が早い気がします。 最初や最後の地点だとしたらlistでなくてもqueueで足りるはずです。 となると、メモリを多く消費して実例の見当たらない切ったりつなげたりの動作が必要になる場面が思い浮かばず、「vectorの方が優れています。」と言ってしまいました。 stlのデータ構造のどれを差し置いてもlistで表現するのが適切となるアルゴリズムやプログラムは存在しますか 解決 大抵のケースでは vector<T> 利用で十分かと思います。(Tは要素の型) Scott Meyers, “Effective STL” でも、Item 1で次の言及があります vector is the type of sequence that should be used by default. list<T> の方が好ましいのは、下記条件を満たすときくらいです。どの程度なら”頻繁/多く/大きい”といえるかは、処理内容や要素型に強く依存するので、最終的には実測して判断すべきでしょう。 中間位置に対する要素の挿入/削除が頻繁に行われ、 コンテナに格納される要素数が非常に多く、 要素型のサイズ(sizeof T)が十分大きいとき。 下記に、vector と list の主な特徴を挙げておきます。 std::vectorシーケンスコンテナ いわゆる「可変長配列(variable length array)」コンテナ。 1要素あたりのメモリ使用量のオーバーヘッドが小さい。目安として sizeof T×容量+ポインタ型1個+整数型2個 分のメモリしか利用しないため、特にT型が小さいときに有利。 動的メモリ確保されるのは “×容量(capacity())” であって、”×要素数(size())” ではない事に注意。事前に要素数を予測できる場合は、適切な容量指定しておく(reserve())ことで、要素挿入時のメモリ再確保コストを削減できる。 任意位置要素へのランダムアクセス(operator[])が定数時間(ほぼゼロコスト)で可能。…(Continue Reading)

Excel VBA の1回の実行で、通過した通過しなかったfunction、subを分類する方法を教えて下さい

投稿者: Anonymous 全てのfunction, subに一行ずつ debug.print”function1通過” と書く方法しかありませんか? 書くとしたら、正規表現置き換えの方法で、対応可能ですか? 全エクスポートで、エディタの正規表現置換後、全インポートを予定しています。 例) 全てのfunction, sub2行目に debug.print "なまえ通過” を挿入する方法がありますか? 他言語でも、アドバイスをいただけると、助かります。 よろしくお願いします。 Sub Auto_Open() call aa end sub sub aa end sub sub bb end sub 通過したsubはAuto_Openとaa 通過しなかったsubはbb 解決 Fumu 7さんの回答の実装例です。 awkを使っています。WSLで確認しました。 引数で指定したbasファイルのSubとFunctionの定義の後にdebug.printを埋め込みます。変換結果は元のファイルの先頭にDebug_を付加したファイルに書き込みます。 書き込む内容はファイル名、行番号、定義の行です。 ※プロパティのアクセサは対象としていません。 【debug.print埋め込みスクリプト】 #!/bin/sh conv_bas(){ file=$1 awk ‘{ print $0 } /^Sub/||/^Function/{ sub(/r/,"") printf(" debug.print("%s:%s:%s")rn", FILENAME, FNR, $0);…(Continue Reading)

Ulam number の効率の良い求め方について

投稿者: Anonymous Ulam number とは以下の性質を持つ数である。 (http://en.wikipedia.org/wiki/Ulam_number) ①今まで現れた相異なる2つの Ulam number の和で表そうとしたとき、1通りしか出来ない。   注)相異なる2つの Ulam number の和で表せないときは、Ulam number ではない。 N = 339 とし、 N 以下の Ulam number を次のように求めてみた。 N = 339 ary = [1, 2] (3..N).each{|i| cnt = 0 (0..ary.size – 2).each{|j| break if ary[j] + ary[j + 1] > i (j + 1..ary.size – 1).each{|k| l…(Continue Reading)

STLにはなぜグラフが用意されていないのですか?

投稿者: user4410 STLには木構造を持つものは用意されていますが、C++でグラフを利用したいのですが、mapなどの木を持つ構造からグラフ化することはできますか。 解決 Introduction to Algorithms(アルゴリズムイントロダクションの1巻)を読むと答えに近づけます。 http://www.amazon.co.jp/gp/product/4764904063 グラフの表現方法がいくつかあり、一言で「グラフ」というデータ構造を表すものは定義できないと思います。 代表的なものだと次の2つでしょうか。 隣接リスト 接続行列 なので、 STLにはなぜグラフが用意されていないのですか? という質問に対しては、「これがグラフだ!」という一般的なデータ構造が決められないから というのでどうでしょうか?(ハイパーグラフとか出てくるとさらに大変なことになりそう) グラフ化することはできますか という質問に対しての解は、「STLを用いてグラフを表現することはできます」という感じでどうでしょうか。 回答者: Anonymous

動画をバージョン管理するための diff アルゴリズム

投稿者: Anonymous Git などのバージョン管理ツールの発展の背後には「テキストデータは行単位で簡単に差分が取れ、しかもどのような差分なのか閲覧しやすい」という特徴があるように思います。 逆に音声、画像、動画といったバイナリデータでは “良い感じ” の差分が取りづらく、定期的なバックアップを使ったバージョン管理より高度なバージョン管理がやりにくそうです。個人的に動画編集をしていると、動画に対して Git のようなバージョン管理ができれば良いのにと思うのですが、良いツールが見つかりません。 動画の差分を素朴に1フレームごとピクセル単位でとろうとすると、動画データの圧縮手法や編集手法によっては実際に編集した部分以外のピクセルが変わってしまうことも影響しそうです。機械学習を使えば上手く処理できるかもしれませんが、簡単に検索しただけだと既存研究が良く分かりませんでした。 質問 動画に対して、バージョン管理に使いやすい diff を生成するアルゴリズムは知られていますか? 解決 (私が知る限りですが)字義通りに「動画データ同士から分かり易い差分を抽出する」アルゴリズムは知られていないと思います。 動画データは、空間方向(2次元)×時間方向(1次元)に広がる3次元情報です。このような3次元情報間では単純一致/差分検知を行うことすら計算量的に困難です。さらに動画データは非可逆(lossy)圧縮されることが多いため、圧縮前データをほんの一部だけを改変した場合でも、改変点周辺(空間方向)およびそれ以降(時間方向)の圧縮後データが変化しえます。つまり単純一致検知アルゴリズムでは事実上は役に立たず、ちょうど良い“曖昧さ”をもった一致検知アルゴリズムが必要となるでしょう。 応用目的は異なりますが、動画データ間同士の類似度を計算する(Video Sequence Matching)アルゴリズムはいくつか知られています。この手のアルゴリズムは、例えば動画共有サービスへの違法な他者権利動画アップロード検知用途で実用されています。 回答者: Anonymous

ベクトルが与えられた時にノルムを求めるアルゴリズムについて

投稿者: Anonymous 前提 ベクトル(v = (v1, v2, …vn)^T))が与えられた時にノルム(√(v^(T)v))を求めるアルゴリズムを考えて、c言語で実装しようとしています。 実現したいこと ①擬似コードで文章になっている部分をどのように記号で表せるのか知りたい ②擬似コードのアルゴリズムを実行するためには、どのように参考記事のプログラムを変更するべきか知りたい ベクトルが与えられた時にノルムを求める、実装したいアルゴリズムの擬似コード norm <- 0 next_address <- v while next_address != NULL do current_cell <- *(next_address) norm <- (ベクトルの要素を2乗したものを足していくと考えられるが、擬似コードでどのようにかいたらいいかわからない) next_address <- (現在のセルのポインタが指すインデックスだと考えられるが、似コードでどのようにかいたらいいかわからない) return sqrt(norm) 参考記事のノルムを計算するプログラム #include <stdio.h> #include <math.h> /* ——————————————— ベクトルの長さを求める 引数1: vec ベクトル 引数4: n ベクトルの要素数 戻り値 vecの長さ ———————————————*/ double norm(double *vec, int…(Continue Reading)

計算式『10/3*3』について

投稿者: Anonymous お世話になります。 アルゴリズムか言語特有の問題かが解らないのですが… C#にて、スタックポインタを使用した、逆ポーランド法で式を計算するプログラムを 書いているときですが、計算する変数はdecimalを使って、小数まで計算できる ようにしたのですが、表題のような計算式を入れると、計算結果が『10.0000000000000000』 桁数は正確に数えたわけではないので、多分これくらいだったと思います。 これというのは、表示されてはいないものの、『ぴったり10ではない』ということなのでしょぅか。 それとも、10として計算してはいるけれど、直前の計算で10/3=3.333333333… としてしまっているため、その時の桁数通りに扱われているということなのでしょうか。 行いたいことは、当然『10』として結果を得たいのです。いくら数的に10であっても、 できれば小数点以下は表示させたくありません。もちろん、表示する時点に数値を 調べ、小数点以下が0ならば小数点から下は表示しないと言った文字列操作で できなくはないですが、あまり解決策としてはよくありません。 このように、『小数点でも割り切れない値』というものを、正しい値のまま 扱うことはできますでしょうか。 対策方法を教えてください。 お願いいたします。 解決 10/3は、循環小数(3.33333…が無限に続く)なので、メモリが有限であるので、(コンピュータで)小数を使って正確に数値を表すことはできません。(つまりどこかで丸めが生じる)。 計算上(無理数ではなく)こうした循環小数を扱う場合には、 循環小数は、分数の形に変換できるので、 数値計算を分子・分母のペア(つまり分数を内部表現として持つ)で扱う(計算を続けるうちに扱う数値が大きくなることが予想されるので、BigIntegerを使用する)ようにすれば、いいかと思います。 回答者: Anonymous

1からNまでの整数に対し、「約数の数がs個になる」のはいくつあるか調べるには?

投稿者: Anonymous n の約数の個数を d(n) と表すことにする。 1から10までの整数に対し、 d(n) = 1 となるのは1個、 d(n) = 2 となるのは4個、 d(n) = 3 となるのは2個、 d(n) = 4 となるのは3個ある。 一般に、 1からNまでの整数に対し、「約数の数がs個になる」のはいくつあるか調べるには どうすれば速く求まるでしょうか? とりあえずなんの工夫もしていないコードをあげておきます。 require ‘prime’ N = 10 ** 2 h = {} (1..N).each{|i| s = 1 i.prime_division.map{|j| s *= j[1] + 1} h.key?(s) ? h[s] += 1 : h[s] =…(Continue Reading)

論文などに書かれているアルゴリズムをC/C++に変換するトランスレータはありませんか

投稿者: Anonymous 論文に書かれているALGOLのような擬似コードを見るのですが、それを外形だけでもCやC++にしたいのですが、自分で打ち込むよりも手っ取り早く変換することができればより多くの論文を実行して読めると思いました。 擬似コードやALGOLをC/C++へ変換できるトランスレータはありませんか FORTRANをCに変換するソフトウェアは有名ですがALGOLや擬似言語については見当たりませんでした。 解決 疑似コードや論文にのってる抜粋のALGOLは、動いているFORTRANのソースとは別物で、根本的に実行に必要な情報が抜け落ちている物が多々ありますから、難しいかと思います。 自分ですぐに改変できるテストコードを沢山書くのが勉強にもなってよいでしょう。 データや実行のためのコードをgithubなどで公開する文化がもっと広まれば検証や改良が容易になって良いなとは思います。 回答者: Anonymous

入力された値の商が0.000001以下になるまで割り算

投稿者: Anonymous javaScript勉強中です。超初心者です。よろしくお願いいたします。 もし入力された数字が2から10の間の時、その入力された数字の商が0.000001以下になるまで2で割り続け、小数第6位以下(0.000001)に到達するまで何回割ったかというコードを書いています。例えば7/2を小数第6位まで割り切るのに23回割り算しました。という結果が欲しいです。 以下が自分のコードです。 このコードが間違っているのはわかっています。まだ途中です。わからないところは: while文での初期値: 2と10の間のどれかの数字から始まる 条件は0,000001以下なのか、以上なのか 入力された数字を2で割った答えが次の分母になるわけですが、そうなるとInputNum++ではない? もしくは小数点以下の桁数を数える方法の方がいいのか ご教授お願いいたします。 if (InputNum <= 1 || InputNum >= 11) { alert( ‘Please enter an invalid number.’ ); let InputNum = (InputNum > 1 && InputNum < 11) while (InputNum > 0.000001){ InputNum = InputNum / 2 alert( InputNum ) InputNum++ 解決 数学を勉強すべきです。log2とceilで求めることができます。 const count =…(Continue Reading)

変数の初期値設定の変更が結果に与える影響

投稿者: Anonymous CodilityのMaxSliceSumという問題 上記の問題を日本語で説明している記事 を解き、コンパイルして評価したのですが、テストケースA=[-10]の時に0ではなく-10を返すように修正する必要がわかったため、変数の初期値に問題で指定されている想定されうる最も小さい値を入れるコードにしました。 しかし、変更後のコードでは他のバグが生じてしまい、修正方法がわかりません。 変更前のコードでは、テストケースA=[3,2,-6,4,0]の時に5が返されて要求を満たしています。 変更前 def solution(A): maxsum = 0 start = 0 end = 0 for i in range(len(A)): tmp = A[i] for j in range(i+1, len(A)): if tmp + A[j] > maxsum: tmp = tmp + A[j] else: break if tmp > maxsum: maxsum = tmp return (maxsum) しかしながら、変更後のコードではA=[3,2,-6,4,0]の時に4が返されてしまうようになりました。 変更後…(Continue Reading)

2からNまでを、素因数分解したときの次数によって並べるには?

投稿者: Anonymous 以前(2からNまでを、素因数分解したときの素因数の最小値が小さい順に並べるには?) と異なる規則によって、2からNまでを並びかえを行います。 ①2〜Nまでを素因数分解を行い次数のみ取り出すものとします。 ②次数の小さい順に並べる。 例えば、N = 10 の場合、次のようになります。 ① 2 => 1, 3 => 10, 4 => 2, 5 => 100, 6 => 11, 7 => 1000, 8 => 3, 9 => 20, 10 => 101 ② 1 < 2 < 3 < 10 < 11 < 20 < 100 < 101 <…(Continue Reading)

Java,Cの計算問題についての質問です

投稿者: Anonymous ○○○○ - ○○○○ = ○○○○ 他のサイトにあった問題です。 この計算の中に0~9の数字を使わなければいけないといった問題です。 同じ数字を使っても良いです。 0~9の数字を全て使ってかつ、正しい筆算になるのは何通りなのか求めたいです。 javaかCで解きたいのですが、解き方が浮かびません。 また、このような問題を解くときに便利なライブラリ等はあるのでしょうか? 解き方や考え方を教えてください。 解決 正しい筆算ということなので、4718 – 0023 = 4695のような式は除外しました。 #include <stdio.h> int digit(int num) { int a = num / 1000; int b = (num – a * 1000) / 100; int c = (num – a * 1000 – b * 100) /…(Continue Reading)

KMP法が分からないので調べているのですが

投稿者: Anonymous リンク先下表について Q1 ・「abbabbababに対するシフト幅」とはどういう意味ですか? ・「検索テキスト」と「パターン」を比較しているわけではなく、事前の「パターン」同士の比較テーブルを作成する時の話? ・「abbabbabab」はパターンのこと?? Q2 ・備考欄に「一致なし」と記載されていますが、どういう意味? ・「何」と「何」が一致していないのでしょうか? 解決 「abbabbabab」は検索する元文字列の内容 不一致と判断した場合に読み込んでいる文字列とシフト幅 一致していない場合の振る舞いを示しているので、とある検索文字列と、「abbabbabab」が一致していない、ということですね そもそも一致した場合、ってのは議論の必要はないですから 回答者: Anonymous

Java における Scavenge GC と Full GC の違い

投稿者: Anonymous Scavenge GC と Full GC の処理の違いは何か教えて下さい。以下については理解しています。 Scavenge GC が Eden 領域がいっぱいになった時に実行される MaxTenuringThreshold の回数文、S0 から S1 に移動が発生した場合に、OLD 領域への移動が発生する Old がいっぱいになった時に Full GC が発生する。 つまり、Old に残っているオブジェクトは、どこからか参照されていて、それ故に残っていると考えられます。したがって、Full GC が Scavenge GC と同様の処理である場合、Old のオブジェクトは、どこからか参照されていると判定されるので、破棄できないのではないかと思いました。 しかし、実際にはそんなはずは無いので、Full GC と Scavenge GC には、不要なオブジェクトを探索するアルゴリズムに差異があるのでは(Full GC のほうが深く探索するなど)、と推測しているのですが裏付けとなる情報が得られていません。 よろしくお願いします。 解決 Scavenge GC の対象の Eden 領域などを含む NEW 領域は、直近で生成された短命なオブジェクトが残り、しきい値を超えた寿命を持つオブジェクトが OLD 領域に入るだけなので、OLD 領域は寿命の長いオブジェクトが入ることになります。ですので、どちらに居ても、他のオブジェクトから参照されているオブジェクトは破棄されません。 GC の方式としては、Scavenge GC…(Continue Reading)

連続 i 個の和が N 以下の組み合わせの総数の求め方について

投稿者: Anonymous [条件] 1.配列 ary はソートされている。 2.N は ary の最大値以上 上記条件をみたすような一般の ary、N に対し、 連続 i (> 0) 個の和が N 以下の組み合わせの総数の求めたいと考えています。 どのように求めるのが効率的でしょうか? 例を示しますので、「下記の非効率な箇所」もしくは「より効率的な求め方」 を教えて頂けたら、幸いです。 N = 10 ary = (1..N).to_a # 最大値がN以下の(ソートされた)配列の例 size = ary.size cnt = size # 連続i(> 1)個取り出す i = 2 i_sum = ary[0] + ary[1] sum = i_sum while sum <= N…(Continue Reading)

DOT言語の有向グラフが木構造か木構造でないかの判定方法を教えて下さい。

投稿者: Anonymous ①有向グラフが木構造か木構造でないかの判定方法を教えて下さい。 ②rootは入力ですか よろしくお願いします。 (参考)DOT言語 https://ja.wikipedia.org/wiki/DOT%E8%A8%80%E8%AA%9E (参考)WebGraphviz is Graphviz in the Browser http://www.webgraphviz.com/ (判定) 有向グラフが木構造 digraph graphname {a -> b -> c;b -> d; } 有向グラフが木構造とならない digraph graphname {a -> b -> c;b -> d;c ->d} 解決 ライブラリ・ツール PyDotPlusや pydot にはDOT言語をパースしてグラフ構造を構築する能力があります。 NetworkXは内部的にPyDotPlusを利用する事が出来て、作ったグラフ構造に対して木構造か判定する is_tree という関数も持っています。 Any Python Tree Data (anytree) は木構造の操作に特化したライブラリです。 Graphviz の出力形式には plain や…(Continue Reading)

フィボナッチ数列の下20桁を高速に求めるには?

投稿者: Anonymous 大きな自然数nに対しても、 フィボナッチ数列f(n)の下20桁を高速に求める にはどうすればよろしいでしょうか? なお、私は以下のように f(n)を高速に求め(※)、mod をとりました。 # (a + b√x)^nの計算 def power(a, b, x, n) return [1, 0] if n == 0 c, d = power(a, b, x, n >> 1) c, d = c * c + x * d * d, 2 * c * d return [c, d] if n…(Continue Reading)

Rubyでアルゴリズムを学ぶのに適した書籍やサイトを教えてください

投稿者: Anonymous はじめまして、よろしくお願い申し上げます。 以下質問となるので、お答えいただければ幸いです。 例えばなのですが、15枚の絵札から5枚のカードを引くプログラムを書いてください. といった問題をRuby言語で学習する場合に適した書籍、サイトなどあるのでしょうか?? 上記のようなテスト行い、基準点に達することができず、アルゴリズムの学習をよりしなければと強く思いググっみたのですが、あまり適したサイトを見つけることができなかった為、こちらで質問させていただきます。 できればRubyの言語でアルゴリズムの学習ができればと考えております。 解決 アルゴリズムを学ぶのに適した書籍はたくさんあるのですが、 とりわけRubyでと指定されると少ない気がします。 だからと言って、別の言語で解説している書籍をわざわざ Rubyに置き換えるのも面倒なので、主にRubyで書かれた書籍を 紹介します。 「プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問」 (http://www.shoeisha.co.jp/book/detail/9784798142456) →コードが載っているだけでなく、対話も交えているので読みやすいと思います。  また、一問一問の量が多くないので、時間が空いている時にさっと読めます。 (Rubyで書かれた書籍でアルゴリズムにも言及している書籍) 「Ruby②」 (http://www.shoeisha.co.jp/book/detail/9784798118000) →第7章でアルゴリズムにふれています。 「Rubyによる情報科学入門」 (http://www.kindaikagaku.co.jp/information/kd0362.htm) →題名からは分かりませんが、アルゴリズムの書籍と言えるのではないでしょうか?  演習が豊富で、かなり数学寄りの書籍。 (おまけ) その他の言語(C,C++,Javaが主)によるアルゴリズムに関する書籍 【基礎的なことが書いてある書籍】 ②初心者向け 「プログラミングの宝箱 アルゴリズムとデータ構造」 (http://www.sbcr.jp/products/4797324198.html?sku=4797324198) ③中級者向け 「アルゴリズムクイックリファレンス」 (http://www.oreilly.co.jp/books/9784873114286/) 【プロコンっぽい書籍】 ①超初心者向け 「オンラインジャッジではじめるC/C++プログラミング入門」 (https://book.mynavi.jp/ec/products/detail/id=25382) ③中級者向け 「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」 (https://book.mynavi.jp/ec/products/detail/id=35408) 「世界で闘うプログラミング力を鍛える150問 トップIT企業のプログラマになるための本」 (https://book.mynavi.jp/ec/products/detail/id=22752) 「プログラミングコンテストチャレンジブック [第2版]」 (https://book.mynavi.jp/ec/products/detail/id=22672) 「最強最速アルゴリズマー養成講座」 (http://www.sbcr.jp/products/4797367171.html) 【パズル】 ③中級者向け 続ナノピコ教室 (http://www.kyoritsu-pub.co.jp/bookdetail/9784320025417)…(Continue Reading)

大きな行列から指定された文字列を探し出すには?

投稿者: Anonymous 文章の一部を縦に読んだり横に読んだりすると、ある言葉が見つかることがあります。 このことをより一般的に次のように考えることにします。 ①文章(縦書きと横書きがありますが、ここでは横書きとします。)を  x×y行列に文字がおさまったもののように扱う。 ②行列の任意の場所から出発し、一つ右もしくは一つ下の文字をたどっていく。  注)縦読みや横読みを含んでいますが、斜めに読むことは含んでいません。 さて、指定した文字列が見つかれば、 “I found it!” を出力し、見つからなければ、 “Not found” を出力するものとします。 次に示すコードでは、 出発点から一つずつ順番に指定した文字列と一致する文字を探している のですが、 xが大きくなっても指定された文字列を高速に探し出せるようにするには どうすればよろしいでしょうか? # -*- coding: cp932 -*- x = 10 y = 11 @num = (0..x * y – 1).to_a # x×y行列(ただしy列目は番兵をおく) ary1 = [ ‘あ’, ‘か’, ‘ま’, ‘き’, ‘が’, ‘み’, ‘ま’, ‘き’, ‘ま’, ‘き’, ‘番兵’,…(Continue Reading)

量子コンピュータによってソートは速くなりますか?

投稿者: Anonymous ランダムアクセスできる配列に対してソートを行うとき、量子アルゴリズムは逐次の古典的アルゴリズムより漸近的に速くなりえますか? 解決 比較ソートに限定した場合、長さ n の配列に対する量子アルゴリズムの時間計算量は Ω(n log n) になる[1]ので、漸近的には古典アルゴリズムの場合と変わりません。 「比較ソート以外の場合はどうなのか?」「他に制限を課した場合はどうなるのか?」についてはよく知りません。英語版 Wikipedia の “Quantum sort” によると空間が制限されたときに量子の方が有利になる場合があるようです。 Høyer, P., Neerbek, J., Shi, Y. (2001). “Quantum complexities of ordered searching, sorting, and element distinctness”. 28th International Colloquium on Automata, Languages, and Programming. pp. 62–73. arXiv:quant-ph/0102078. doi:10.1007/3-540-48224-5_29. 回答者: Anonymous

グラフ構造で節点にデータを入れたい

投稿者: user4410 グラフ構造を実装しようとしています。 枝の距離をデータとして格納する方法はどの教科書を見ても詳細に記載されていましたが、節点の場合どうすればよいか分かりません。 O’Reilly Japan – アルゴリズムクイックリファレンスP.154 隣接行列のデータ構造 int A[][]= { {0, 0, 0, 0, 0, 0}, {6, 0,18, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 9}, {0, 0, 0, 0, 0, 0}, {0, 0, 0,12, 0, 0} }; 隣接リストのデータ構造 (書籍を頼りに多分このようなデータ構造だろうと推測しました): std::vector<std::list<std::pair<int,int>>>A; このようなグラフ構造で、節点に何らかのデータを入れたい場合どのようにしたらよいでしょうか? 解決 グラフの関心はノード間の位置と関係かと思います。ですので、各ノードはただのラベルがあれば良いはずです(該当本Figure 6-4の「v0」など)。まぁ実際にはインデックスで管理しますかね。 ですので、各ノードが何であるかについては、別の配列なりデータ構造などでラベルとの対応関係を管理するのはどうでしょうか。素直にするのであればインデックスで対応関係を取りますが、ハッシュテーブルなどを使っても良いのかもしれません。…(Continue Reading)

(openssl の) RSA 秘密鍵の中身はそれぞれ何を表す?

投稿者: Anonymous openssl で rsa の鍵を適当に test.pem で生成して、その中身を openssl rsa -in test.pem -text -noout で眺めていました。(長いので、この質問の末尾に付与します) この中で、prime1, prime2 はそれぞれ 1536 == 3072/2bit 長の素数(以降、p, q と呼びます)、 modulus は p * q のかけ算の結果(以降、 n と呼びます)、 public exponent は公開鍵の exponent であって(以降、 e と呼びます)、つまり公開鍵は (e, n) なタプル、ということまでは理解できたのですが、それ以外が何を表しているのかがちょっと検討がついていないです。 e^(-1) mod (p-1)*(q-1) の値は、複合化の際に利用される値なので、それが private exponent か coefficient のどちらか、かなとは思ってはいるのですが、そうするとこれらのうちのあまりは何を表しているのか、がちょっと良く分かっていないです。また、 exponent1, exponent2 も謎です。 質問…(Continue Reading)

Pythonの配列の要素数が0かそれ以外かを判定する方法のパフォーマンス

投稿者: Anonymous 次のような配列numsがあったときに、配列の要素数が0かそれ以外かを判定する方法で、 実装方法によってパフォーマンスに後述のような差がありました。どういう理由でこのような差が生まれてくるのかを教えてほしいです。 もし可能であればそれらの判定方法の計算量も教えてもらいたいです。 おそらくO(1)であって、O(N)まではいかないにしてもわずかながら差があるのだろうなと思っています。 用意した配列nums nums = [1,2,3,4] 方法1 純粋にlen()を使って判定した場合 # 9.7 ms ± 399 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) %%timeit n = 10**5 for i in range(n): if len(nums) > 0: pass 方法2 if numsとした場合。方法1の3倍くらい速い # 3.75 ms ± 23.4 µs per loop (mean…(Continue Reading)

計数ソートを入力順にソートした際の安定性

投稿者: Anonymous 下の疑似コードで実装された計数ソート(Counting Sort)の探索を現在と逆順にした場合、安定したソートを保持したままにするにはどの方法が効率がいいでしょうか? 事実、このアルゴリズムでは入力配列を後ろからソートしないと、同じ要素が現れた場合その要素の順番は逆になってしまい、安定したソートではなくなります。 私は。同じ要素が複数回出現した場合に限り、その要素数-1をしたものをそれぞれのカウンターから引けばいいと思ったのですが、その場合はもう一つ余計な配列を用意しなければならず、非効率的ではないかと指摘されました。しかし、それ以外の方法が思いつきません。 なにか手法などありましたら教えていただけると幸いです。 pseudo-code (reference: Algorithm Introduction, MIT Press) COUNTING-SORT(A,B,k) C[0..k] を新しい配列とする for i = 0 to k C[i] = 0 for j = 1 to A.length C[A[j]] = C[A[j]] + 1 //C[i] は i と等しい要素の数を示す. for i = 1 to k C[i] = C[i] + C[i−1] //C[i] は i 以下の要素の数を示す.…(Continue Reading)

ZIPコンテナを効率よく読み込むには?

投稿者: Anonymous 通信用語の基礎知識さんのZIPコンテナの記事を見て、自分でZIPコンテナファイルの実装を作ろうと考えているのですが、ZIPファイルを解凍せずにZIPファイルの中身を読み込んだり書き込んだりするにはどうすればいいのでしょうか? (ZIPコンテナというのはePubで使われている規格です。) プログラミング言語などを特定せずに書いているのはあらゆるZIPファイルを読み込むライブラリを想定して書いているからです。 解決 回答の前に用語を整理しておきます。 ZIPファイル = ZIPコンテナ仕様に従って、複数ファイルをデータ圧縮・格納したファイル。 ZIPコンテナ = 複数の圧縮データを単一ファイルとして表現する仕様。具体的なデータ圧縮アルゴリズムは選択可能。 ePubではZIPコンテナ仕様に従いつつ、追加要件を課したファイル仕様となっています。 ZIPファイルを解凍せずにZIPファイルの中身を読み込んだり書き込んだりするにはどうすればいいのでしょうか? 「複数ファイルを含んだZIPファイル全体を解凍することなく一部ファイルデータのみ読み出したい」のであれば、対象データ以外はスキップして必要な部分だけ解凍(データ展開)することは可能です。 一方で「複数ファイルを含んだZIPファイル全体を解凍することなく、一部ファイルデータのみ更新したい」場合は、圧縮後データサイズが変わってしまうため汎用対応は困難と思います。(非圧縮ファイルの編集ならば単純バイト置換+CRC再計算で済むはず) 回答者: Anonymous

帰りがけ順から二分探索木の生成

投稿者: Anonymous ネットでは、行きがけ順・通りがけ順、通りがけ順・帰りがけ順からBSTを生成する方法はよく見かけますが、帰りがけ順のみ与えられた場合、そこから探索二分木を生成することは可能なのでしょうか?また、その場合どういったアルゴリズムになりますか? 解決 一意に特定できないため不可能です。たとえば 3, 2, 1 という帰りがけ順に対応する二分木は次のふたつが考えられます。 1 | 2 | 3 1 / 3 2 一般に、n 個の要素からなる帰りがけ順の配列と n 個ノードがある(ノードに名前がついていない)二分木が与えられると、その帰りがけ順に対応するようにノードに名前をつけていくことができます。普通に深さ優先探索をしつつ、帰るときに名前をつけていけば良いです。つまりあるひとつの帰りがけ順に対応する二分木は少なくとも木の形の数だけ存在します。 回答者: Anonymous

分割統治法を利用した数式についてです。

投稿者: Anonymous 分割統治法についてです。 下記画像の再帰的に代入すると4^2 T(n/2)=….4^log2^n T(1)=n^log2^4 T(1)と数式が変化する過程、理由がわかりません。 数学に弱く数学的な知見が不足しているかもしれません。 噛み砕き解説いただけると幸いです。 参照:データ構造とアルゴリズム 解決 「再帰的に代入」という部分が肝です。 この計算過程では T(n) = 4 T(n/2) という等式を T(n) に対して代入するという操作を繰り返し(再帰的に)行っています。ここでこの等式は任意の n について成り立つので、たとえば T(n/2) = 4 T(n/4) という風にも使えます。 T(n) = 4 T(n/2) = 4 × 4 T(n/4) = 4^2 T(n/4) = 4^2 × 4 T(n/8) = 4^3 T(n/8) = … また、ある正の整数 k を使って n = 2^k…(Continue Reading)

C#でスレッドセーフなシングルトンクラスを実装したい

投稿者: Anonymous タイトルの件、WCFサービス上でシングルトンクラスを扱うことを想定してスレッドセーフな 実装をしたいと考えております。 検索もしてみたのですが、いくつか方法があるようで実際どれが正しいのか よく分かりません。。 大変恐縮ですが、サンプルコード等のリンクでも構いませんので、 ご教示頂けないでしょうか? 解決 シングルトンパターンにはおおむね3パターンの実装方法があります。 最初の方法は class Hoge { private static Fuga _Piyo; public static Fuga Piyo => _Piyo ?? (_Piyo = new Fuga()); } とプロパティにアクセスしたタイミングでインスタンスを作成するものです。この方法は_Piyoがnullかどうかを判定してからnew Fuga()を代入するまでの間に他のスレッドでもnew Fuga()を作成し始め、結果的にインスタンスが複数作成される危険性があります。つまりスレッドセーフではありません。 この問題はスタティックメンバーの初期化子を使用すると回避できます。 class Hoge { public static Fuga Piyo { get; } = new Piyo(); } このような実装はstaticメンバーの初期化がランタイムにより厳密に一度しか行われないことが保証されるため、new Fuga()が複数回呼び出されることはありません。ですがHoge型が初期化されるタイミングが不定という問題があります。 タイミングも制御したい場合は、static初期化子でロックオブジェクトを作成します。 class Hoge { private…(Continue Reading)