15
票
Accepted
Git の 3-way merge とは具体的にどのようなアルゴリズムですか?
「way」とは
ここでの「way」とは、マージする際に "見て" いる場所のこと。3-way merge は 3 つの場所を見ている。
2-way merge:「マージの起点コミット」「マージさせたいコミット」を見てマージする
3-way merge:「マージの起点コミット」「マージさせたいコミット」「2 つのコミットの最近共通祖先となるコミット」を見てマージする
...
13
票
ログインシステムのためのパスワードのハッシュ方式、互換性、照合方法について
(suzukisさんの回答への補足です)
パスワードハッシュにSHA256などのメッセージダイジェストハッシュを使うことは推奨されません。 パスワードハッシュ用のアルゴリズムが開発されているので、それを使いましょう。
まずは結論から
現時点でベストとされているのはArgon2です。パスワードハッシュアルゴリズムの優劣を競うコンペで2015年に最良と判断されました。ただ、比較的新しいので、...
12
票
ログインシステムのためのパスワードのハッシュ方式、互換性、照合方法について
ハッシュアルゴリズムを切り替える方法
DBのユーザー情報を保存しているテーブルにハッシュアルゴリズムを保存するカラムを追加します。すべてのユーザーに旧アルゴリズムを表す値を入れておくか、NULであれば旧アルゴリズムと見なす、とします。
ユーザー認証時は、このカラムの値を見てアルゴリズムを選択します。
パスワード変更時は新アルゴリズムを用いてハッシュ値を計算し、...
12
票
Accepted
クイックソートの2種類の実装法で実行速度に顕著な違いが出る
クイックソートでは(ほぼ)ソート済みの配列や同一要素の配列に対して平均的なO(N log N)ではなくO(N^2)のワーストケースになります。
VCやMinGWではRAND_MAXが0x7fffしかないため10000000要素の配列では305個程度同じ値があり、性能の劣化が起こります。
void randomize(vector<int> &arr) {
std::...
9
票
使用頻度を計算するには?
一般的というのは、存在しません。
hosiさんが欲しいと思っている使用頻度だけがhosiさんの正しい使用頻度であって、他の見知らぬ人々(一般)が欲しがるものに惑わされる事は不毛だと思います。
「過去に良く使用されていたものが上位に表示されるのは問題がある」という事であれば、
a) 直近1年とか、直近1か月とかを調査対象期間にする、
b) (使用回数/アプリが提供されていた期間)で頻度を求める
...
9
票
長方形と円の衝突判定を行うコードを教えて下さい
言語の指定がないので、アルゴリズムだけ示します。
下記の図で細かい説明を省いて結論だけ言うと、長方形(赤)の外側に引いた水色の実線の中に、円の中心 P1 が入った際には衝突したとみなせます。水色の線は、長方形の外縁から r の距離に相当します。そのため角を除く部分は長方形に並行に、角の部分は半径 r の円の 1/4 となっています。
あとはこの水色の実線内に入ったかどうかの判定ですが、...
9
票
Accepted
データ構造とアルゴリズムは実務ではどんなシーンで役立つのか?
巨大なシステムでは重要≒普通のシステムでは知らなくてよい、とお考えのようですがとんでもない話です。資源の少ないマイコンでは RAM も貴重 ROM も貴重、電池も貴重で、最適なアルゴリズムやデータ構造を使わないと1つ1つの処理に余計な時間がかかります。電池機器(まあ端的にはスマホっすけど)では無駄な処理は一切許されません。ほぼ同じような処理をして A 社のスマホは電池が10時間保つけど B ...
8
票
Accepted
組み合わせ計算で 64C32 の結果がオーバーフロー
オーバーフローが起こっているのはこの計算をするときです。
(n - r + 1) * combi(n, r - 1) / r
たとえば combi(64, 32) の呼び出しでは以下の計算をすることになりますが、
33 * combi(64, 31) / 32
₆₄C₃₁ = 1,777,090,076,065,542,336 なので、これに 33 を掛けると 2⁶⁴ - 1 = 9,...
7
票
Accepted
連続する整数値の中に「7」がいくつ出現するか数えるプログラムの高速化
ものごとは分けて考えましょう。
「1からnまでの連続する整数値」のうち(以下A)、1の位には 7 はいくつでてくるでしょうか? n が 10 以上ならば、少なくとも int(n / 10) 回はでてきますよね? さらに n % 10 が 7 以上であれば、それに +1 回加えて登場するはずです。つまり n = 30 までなら 7, 17, 27 の 3回ですが、n = 37 ならば前の 3 つに ...
7
票
Accepted
プログラミングCの再帰に関しての質問です。
max() がどういう動作をするか、頭から追いかけていけば、原因が分かります。
max() が最初に呼び出されると、
変数 i が作成される
変数 result が作成され、0 に初期化される。
scanf で自然数が i に読み込まれる。 ここでユーザは 5 を入力したと仮定します。つまり i は 5 になります。
i と result, つまり 5 と 0 を比べるので、最初の if ...
7
票
Accepted
C++での自己参照構造体におけるポインタにおいて
すでにあるコメントだけで十分だと言う気もしますが。
struct MyStruct {
int a;
int b;
}
なんて宣言があると、コンパイラはMyStruct型に「int2個分」の領域を割り当てます。
struct AnotherStruct {
int key;
MyStruct subStruct;
}
だと、...
7
票
私の作った乱数はストリーム暗号に使えますか?
乱数や暗号は自前で考えるとたいてい穴があるものしかできないので、既成のものを使われるほうがよいです。
勉強したいのであれば、入門書としてまず「暗号技術入門(ISBN 4797382228)」を読んでみてはいかがでしょうか
具体的な欠陥を1つ示しておきます。
a==a[Z]になると、a^a[Z]は0となります。以後生成される数列は0となります。^a==a[Z]となっても同様です。
...
6
票
Accepted
ヒープデータ構造について
回答となると、この英文を訳すしかないので、解釈に必須の部分だけ書きますね。
この問題は二分ヒープを対象としていて、最深部以外は完全二分木になることが前提。上から各段のノードを数えると1,2,4,8...となりますが、最後の段は2の累乗になっているとは限りません。また"at most"はつまり取りうる最大の数という意味なので、1からn/2^(h+1)の間の数ならOKです。
ある関数f(k)...
6
票
数値からランダムに値を取り出す『軽い』方法
候補を小さい順に見ていき、選択するか否か、毎回ダイスを振れば、ランダムかつ小さい順に選択されると思います。
以下はPythonの例です。
これがいかなる意味でランダムなのか、本当にランダムなのか、などは私は分かりません。
#!/usr/bin/python3
import random
start = 0
last = 19
need = 6
selected = 0
for c in ...

mjy♦
- 1.2万
6
票
Accepted
リナックスのはじめの方のコードでつまずきました。
#define BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2*!!(condition)]))
conditionが0以外だったらコンパイルエラーにする。
!は単に論理否定で、二つ続けて!!とすることで、肯定論理にしています。conditionの値がたとえ10でも論理結果(0 or 1)を返します。
char[1 - 2*!!(condition)...
6
票
リナックスのはじめの方のコードでつまずきました。
一部だけ。
否定の否定 (!!)
C言語の!演算子などを使いNOT演算(否定)を行なうと対象の真偽を逆転させます。
対象が真と見なせる値であれば真偽値の偽を、偽と見なせる値であれば真偽値の真を返します。
これを!!のように2回行うと、逆転させて、また逆転させるので、真偽は元にもどり変わりません。
対象を真偽値にする、という効果だけが得られます。
この機能は、...

mjy♦
- 1.2万
6
票
Accepted
8パズルで、最初にシャッフルさせる時の考え方
どうやってランダム生成するか?
1~9 の並べ替えをランダムに生成する
以下の判定問題を解く
(もし解けないことが分かったら) 9 (空ブロック) 以外の2つの異なるブロックをランダムに選んで入れ替える
問題の定式化
問題 正解
31_ 123
275 -> 456
684 78_
上記のような盤面であったとき、これは以下のような並べ替え問題であると考える。
3 ...
6
票
Accepted
DOMが書き換わった後ブラウザはどのように再描画していますか?
基本的には、DOM, HTML, CSS の仕様に準拠する範囲で不要な処理をしない、の積み重ねです。
大まかには「DOM変更→スタイル計算→レイアウト→ペイント→コンポジション」というステップがあります。以下のような処理はどのブラウザエンジンもやっているのではないかと思います。
DOM変更が、表示されているDocumentのツリーに接続していない部分で起きたら、何もしない
...
6
票
Accepted
C++での深さ優先探索が無限に終わらない
コメントに示したように単純な総当たりではケース数が増えすぎて実用的な時間では解けない設定になっています。
最初に水1700gを入れた場合、
入れられる砂糖の最大量は1700*55/100=935(g)です。
全部多い方の「操作 4: ビーカーに砂糖を D(26)[g] 入れる。」を選んだとしても、
935 ÷ 26 = 35...25
となるので、最低35回「砂糖を入れる」...
6
票
Accepted
計算量O(1)とO(n)
計算量O(1)の例 で一番肝心なのは、
この部分です。
// Here c is a constant
cは定数なのです。どんな値を取っても良いものが「定数」と言われると、理解するのが難しいのですが、このcとは別に何らかの変量(変数と言っても良い、計算量の場合はよくnが使われる)がある時に「cは変量nが変化しても何の影響も受けずに一定の値である」と言うことを表しています。
...
6
票
Accepted
fileの読み込みや、書き込みで出てくるstreamとは何でしょうか?
言語や処理系によって詳細は異なることがあるので一般論になってしまいますが、例えば c においては「高水準入出力」「低水準入出力」と呼ばれる違いになります。
高水準入出力
プログラマにとって扱いやすいよう物理デバイス・物理機能を抽象化したものです。提示「ストリーム」はこっち。たいてい高度なバッファリング機能が実装されています。例えば c の fopen() はこっち。
低水準入出力
物理デバイス・...
5
票
四則演算と論理演算で実行速度を比較した表はありませんか
アルゴリズムの改善であれば、普通は適当な擬似コードに落とした時の操作の総数をベースに考えれば十分です。ループのネストを減らしたり、枝刈りで処理を丸ごとスキップするのがアルゴリズム改善の常套手段なのは処理の総数が大幅に削減されるからです。個々の操作にかかる時間を気にしてそれを減らそうとするのは、言うなれば擬似コードの行数を減らそうとしているようなものです。
...
5
票
Accepted
使用頻度を計算するには?
時系列データに対して、過去n日の動きを知りたい時は移動平均がよく使われます。直近の値を重視し、遠い過去の影響を少なく計算するには、経過日数の逆数で重み付けすればいいわけです。重み付けのやり方は色々ありますが指数移動平均もよく使われています。
例えば1日あたりの起動回数をアプリごとにカウントし、窓の大きさを1ヶ月などとすれば過去1ヶ月の動きが分かります。リリース日からということなら1年とか、...
5
票
Accepted
無限ループはどのようにして検出しているのですか?
一般的にアプリが何らかの無限ループにはまっていることを検出することはできず、単に「プログラムが応答しない」ことを検出しているにすぎません。
WindowsなどのGUI系アプリの場合、イベントキューを用いたイベントドリブンな書き方をするのが一般的ですから、「イベントが一定時間以上の間処理されない」ことで「応答がない」と判定できます。
Windowsの場合superuser(...
5
票
Accepted
数値からランダムに値を取り出す『軽い』方法
mjyさんのPython版と同じですが、i=0~19の範囲でループしつつ、その都度、選択される確率を求めて、採るか捨てるか決めていけばいいと思います。
i=0のとき、6/20の確率で選択します。i=0が選択されたとき、i=1が選択される確率は5/19になります。i=0が選択されなかったとき、i=1が選択される確率は6/19になります。この繰り返しです。
#include <stdio.h&...
5
票
Accepted
ビッグオー、ビックシータの計算方法 (関数に再起がある場合、if文がある場合等)
基本的には、ランダウの記法の定義通りに考えることになります。リンクした Wikipedia 記事だと「その他の漸近記法」にまとめられています。
ビッグオーは関数を上からおさえる、ビッグオメガは関数を下からおさえる、ビッグシータは両方からおさえる "気持ち" があり、その直感のもと数学的な定義がなされていると考えてください。
(1)
はい。fnc(n) の実行時間は O(n) です。つまり「...
5
票
Accepted
文字がCODE128の範囲かチェックしたい
CODE128は制御文字を含めてASCIIのすべての文字を表現できますので、
Regex.IsMatch(input, @"^[\x00-\x7f]+$")
という正規表現で判定可能です。ただ通常はアプリケーション側の要件の方がCODE128仕様より厳しいと思われますので、そちら側に合わせた検証を行った方が良いと思います。
5
票
Accepted
AIZU ONLINE JUDGEの0009で何回やってもTime Limit Exceedと表示されます。
原因
確かに質問者さんのプログラムは Time Limit Exceeded (TLE) となります。これはアルゴリズム部分の実行が遅いためです。特に、各入力に対して毎回試し割りして素数判定を行っていることが実行時間を嵩ませています。
原因の割り出し方
まず、Yosh さんのコメントにあるように main 関数内の print(prime(line)) を print(42) に変えると ...
5
票
どのような多面体かを知るコード
この質問は、Graphで扱える問題です。Graphにはいろいろありますが、ウィキペディア日本語版では「グラフ (データ構造)」のGraphです。
以下に、PythonのNetworkXを使ったサンプルコードとその結果を書いておきます。
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
s = '''...
5
票
Accepted
テストケースに通らない理由がわかりません。
ざっと見て、一番怪しそうなのは
} while (i < a);
のところです。例えばa=6, b=12のとき、6も両方の数を割り切る正整数ですが、この条件式だと除外されてしまいます。
i <= aとしてみたらどうでしょうか。
ちなみにdo whileではなくforを使った方が分かりやすいと思います。
Only top scored, non community-wiki answers of a minimum length are eligible