9
票
承認済み
データ構造とアルゴリズムは実務ではどんなシーンで役立つのか?
巨大なシステムでは重要≒普通のシステムでは知らなくてよい、とお考えのようですがとんでもない話です。資源の少ないマイコンでは RAM も貴重 ROM も貴重、電池も貴重で、最適なアルゴリズムやデータ構造を使わないと1つ1つの処理に余計な時間がかかります。電池機器(まあ端的にはスマホっすけど)では無駄な処理は一切許されません。ほぼ同じような処理をして A 社のスマホは電池が10時間保つけど B ...
7
票
承認済み
C++での自己参照構造体におけるポインタにおいて
すでにあるコメントだけで十分だと言う気もしますが。
struct MyStruct {
int a;
int b;
}
なんて宣言があると、コンパイラはMyStruct型に「int2個分」の領域を割り当てます。
struct AnotherStruct {
int key;
MyStruct subStruct;
}
だと、...
4
票
承認済み
ハッシュ表のチェイン法による実装における単方向or双方向連結リストの比較
双方向リストの削除という場合キーや位置を指定しての削除と、ノードそのものを指定しての削除とで考え方が違います。
キーや位置を指定して削除する場合、そのノードを見つけるために順にたどっていく必要があるので、単方向リストで prev を発見するのと変わりません。おそらくAkiyama Naoさんが想定してるのはこちら。
一方ノードそのものを指定する場合、双方向リストではそのノード自身や prev, ...
4
票
承認済み
Pythonの配列の要素数が0かそれ以外かを判定する方法のパフォーマンス
計測のために関数を用意しました。
グローバル変数アクセスコストの影響を避けるために、必要な値は引数で渡します。
>>> def f1(n, nums):
... for i in range(n):
... if len(nums) > 0:
... pass
...
>>> def f2(n, nums)...
3
票
承認済み
レーベンシュタイン距離(編集距離/エディットグラフ)の出力とグラフにおける最短経路に関して
レーベンシュタイン距離は各編集操作それぞれに別々のコストを割り当てることが可能です。ライブラリが出力したものは、挿入・削除・置換にコスト1を割り当てた場合のレーベンシュタイン距離だと思われます。グラフで求めているものは、挿入・削除にコスト1、置換にコスト2が割り振った場合(あるいは置換操作がなく、削除と挿入にした場合)のレーベンシュタイン距離となります。
3
票
承認済み
帰りがけ順から二分探索木の生成
一意に特定できないため不可能です。たとえば 3, 2, 1 という帰りがけ順に対応する二分木は次のふたつが考えられます。
1
|
2
|
3
1
/ \
3 2
一般に、n 個の要素からなる帰りがけ順の配列と n 個ノードがある(ノードに名前がついていない)二分木が与えられると、その帰りがけ順に対応するようにノードに名前をつけていくことができます。...
3
票
Pythonの配列の要素数が0かそれ以外かを判定する方法のパフォーマンス
次のような配列numsがあったときに、配列の要素数が0かそれ以外かを判定する方法で、
実装方法によってパフォーマンスに後述のような差がありました。どういう理由でこのような差が生まれてくるのかを教えてほしいです。
こちらだけ。
cpython限定ですが、試しにCでループ内処理を書いてみました。
/* Py_DECREF忘れてるよっ!というのはご愛嬌 */
void exec1(...
3
票
承認済み
データ構造のヒープへの挿入方法について
私が書いた方法で実装するのはとてつもない欠点があるのでしょうか?
ご自分のコメントでもう気付いておられるようですが、計算量の問題です。
(ついでに言うとLinked Listはデータ本体の他にリンクのための領域が必要になるので、その部分で避けたいと思う人があるかも知れませんが、この回答では触れません。)
挿入の計算量はlogH (Hは完全二分木の高さ)だ
この部分に書き間違いがあるので、...
3
票
承認済み
逆ポーランド記法で被演算子が3個以上の演算はありうるのか?
中間記法「3 + 4 + 5」は逆ポーランド記法ではどのように書けばよいのでしょうか?
ご質問中にあるように、3 4 + 5 +でも構いませんし、3 4 5 + +でも構いません。
「3 4 5 +」のように書くことはできないのでしょうか?
+がどのような演算として定義されているかによるわけですが、他の箇所に合わせて2数の加算と考えると、3 4 5 +だと、最後の4 5だけが加算されて、3 ...
3
票
逆ポーランド記法で被演算子が3個以上の演算はありうるのか?
もし質問の意図が、+演算子が、不定個数の被演算子を取れるようにできるか、ということだったら無理です。スタックから+演算子を取り出した時にどんな処理をすればいいのか、決定できないからです。
たとえば、乗算も加算も不定個数の被演算子を取れるようにしてみたとします。つまり2 * 3 * 4なら2 3 4 *、5 + 3なら5 3 +と書けるようにします。
ここで普通の式2 + 3 + 4 * 5を、...
3
票
承認済み
データ構造(スタックやキューについて)
スタックやキューは標準ライブラリに入ってるとおもわれるのですが、このクラスを自分で拡張したりすることはあるのでしょうか??
技術的には、拡張可能です。
C++標準ライブラリが提供するstd::stack(LIFOデータ構造)とstd::queue(FIFOデータ構造)は、要素値のデータ格納機構を外部に委ねるコンテナアダプタ(Container Adapter)となっています。...
2
票
承認済み
ZIPコンテナを効率よく読み込むには?
回答の前に用語を整理しておきます。
ZIPファイル = ZIPコンテナ仕様に従って、複数ファイルをデータ圧縮・格納したファイル。
ZIPコンテナ = 複数の圧縮データを単一ファイルとして表現する仕様。具体的なデータ圧縮アルゴリズムは選択可能。
ePubではZIPコンテナ仕様に従いつつ、追加要件を課したファイル仕様となっています。
...
2
票
承認済み
テキストログファイルへの追記書き込み速度はファイルの行数(サイズ)とどのような関係があるか?
まあ普通に実装されているファイルシステムにおいては、次のことが言えそうです。
- 追記すべき場所を探す時間は増えるだろう(シークに要する時間は増える)
- 追記をし続けている限りにおいては速度は(小さいファイルと)変わらないだろう
ハードディスク(や SSD )上にファイルが置かれるとき
- ファイルの内容(提示例では数十 GB になったもの)
- ファイル自体の情報(ファイル名、権限、...
2
票
ダイクストラ法で最短経路を見つけるときに負の値を持つ辺があると経路は正しくても誤ったコストが出力される
ダイクストラ法では前提として「コストが負ではない」というものを仮定してます。
ルートが正しく表示されているのは偶然ですね。
例えば与えられたグラフにA->Dのコスト3の辺を追加するとコストもルートも共に間違ったもの(A->D:cost=3)が出力されます。(求めたいのは元のA->C->B->D:cost=2のまま)
2
票
承認済み
計数ソートを入力順にソートした際の安定性
このアルゴリズムでは最後のループが回る直前の C[i] の値が、配列 B における値 i の末尾のインデックスを示すように計算されています。このため最後のループでは配列 A を後ろから走査する形が自然です。
逆に考えると、最後のループで配列 A を前から走査したければ、C[i] の値が配列 B における値 i の先頭のインデックスを示すように計算すれば良いです。
...
2
票
承認済み
有向グラフの表現で、E = {⟨u, v⟩ | u|v,⟨u, v⟩ ∈ V × V and u ̸= v} の表すものが分からない
おそらく u|v の部分が分からないのだと思いますが、今回頂点は自然数なので u や v も自然数で、自然数に対する u|v という書き方だと約数を表す記号として使われているのだと思います。Wikipedia の約数のページなどを参考にしてください。
ただしもちろん、プログラミングで関数を自由に定義できるように、数学でも定義さえすれば記号の意味は変わりうるので、...
2
票
ruby で ordered hash 的なことがやりたい
GemsのRBTreeを試してみてください。
https://rubygems.org/gems/rbtree/versions/0.4.2
RBTreeのDocumentationはリンク先ページの右側から見ることができます。
2
票
承認済み
クイックソートのパーティションの定義について
どこから解説したらよいものやら・・・ quicksort のアルゴリズムは分かっていますか?
ソートしたい配列内にある1つの要素をテキトーに選んでそれより大きいか小さいかを判別するわけですが、その要素をピボットと呼びます。ピボットより小さい要素を左側に、ピボットより大きい要素を右側に集めたら、ピボット要素はその中央に置けばよいわけです。これを分割区間を変えて再帰的に繰り返すと全要素をソートできます。...
2
票
文字列結合した際に、文字Kが文字aを消してしまう
char tmp2 = 'A';で初期化したtmp2に対して、26回以上tmp2++;を繰り返したらどうなるでしょうか。
実際に試すと分かりますが、'Z'の次は'[','\',...'`'と変わっていき、32回目で'a'になります。
問題の入力例だとword2が33文字なので、merge = merge.replace(tmp2, c4);がmerge = merge.replace('a', '...
1
票
picojsonで階層構造のjsonファイルを読ませたい
この前と違ってvalue部分が"で囲まれて文字列となっているので、いったんstd::stringでgetしてstodとかstrtodで変換すれば良いでしょう。
以下のようになります。
for (unsigned int i = 0; i < feat.size(); i++) {
picojson::object& featN = feat[i].get<...
1
票
階層構造を含む JSON ファイルを読ませたい
回答の前に、直接は関係無いですが JSON Pretty Linter Ver3とかBest JSON Formatter and JSON Validator: Online JSON Validatorに掛けるとParse error on line 60:と出てくるのですが、その行の},のカンマを削除して}だけにしたらチェックは通ったようです。
...
1
票
承認済み
二分探索木を分割する際の計算量
O(h)(hはツリーの高さ)ではないです。
一旦通りがけ順に要素を列挙した後、その要素を二つの二分探索木に分割してるのでO(N)(Nはツリーのサイズ)です。
一般的な分割の方法では、それぞれの部分木に対して右か左の一方の子を再帰的に分割して、それを定数時間でマージするのでO(h)(hはツリーの高さ)になります。ただしバランスはとれません。
1
票
異なる文字列の接頭語と接尾語を比較
文字列の n 文字目にランダムアクセスできるのであれば、質問文に書かれているアルゴリズムを文字列 S1 を反転することなく行えば多少速くなります。S1 を反転させているのは文字列比較のためですが、どうせ 1 文字ずつ比較することになるので S1 は後ろから S2 は前から 1 文字ずつ比較すれば同じことです。こうすると S1 を反転する必要が無くなるので元のアルゴリズムより時間計算量が ...
1
票
承認済み
一つのプログラムで複数の連結リストの作成
連結リストがふたつ欲しいだけであれば、同じ struct の型を持った変数をふたつ定義すれば良いです。struct をふたつ定義する必要はありません。
typedef struct node
{
int data;
struct node * next;
} node;
...
int main()
{
/* ... */
node * list1 = /* ....
1
票
承認済み
ヒープの深さと各深さにおける要素数から和を求めるプログラムのエラー
変数 depth はリストでなくて整数なので、depth[j] のように添え字をつけることはできないため生じているエラーです。
1
票
承認済み
ダイクストラ法で最短経路を見つけるときに負の値を持つ辺があると経路は正しくても誤ったコストが出力される
一言でいうと、このプログラムは、すべての辺が正であることを仮定したアルゴリズムを使っているため、うまく動きません。以下は、プログラムのwhileループを抜き出したものです。説明のために# for ループ 1と# for ループ 2というコメントを入れています。
while True:
min = INF
# for ループ 1
for i in range(size):
...
1
票
動的計画法でナップサック問題を解く
#include <bits/stdc++.h>
using lli = long long int;
template <typename T>
bool chmax(T& a, T b) {
if (b > a) {
a = b;
return true;
}
return false;
}
...
1
票
承認済み
MATLABにおける2次元配列の宣言について
forは使わずに一行で
rxData = event.Data(:, 2:end);
はどうでしょうか。
(もったいないので前の回答も残しておきます)
zerosという関数があります。例えば
zeros(40000,5)
で、すべての要素を0で初期化した40000x5の配列が作成されます。三次元配列なら
zeros(2,3,4)
のように作成できます。
1
票
承認済み
Linked Listのトラバーサルの方法で質問です
方法1と方法2には違いがあります。
その違いを端的に示すコードは下記です。
初期化時にnode.next.next = Falseとしている点に注目してください。
# Linked Listのノードクラス
class Node:
def __init__(self, x):
self.val = x
self.next = None
# 初期化(...
無効化に投票