次のタグが付いている話題の回答:

9
Accepted

データ構造とアルゴリズムは実務ではどんなシーンで役立つのか?

巨大なシステムでは重要≒普通のシステムでは知らなくてよい、とお考えのようですがとんでもない話です。資源の少ないマイコンでは RAM も貴重 ROM も貴重、電池も貴重で、最適なアルゴリズムやデータ構造を使わないと1つ1つの処理に余計な時間がかかります。電池機器(まあ端的にはスマホっすけど)では無駄な処理は一切許されません。ほぼ同じような処理をして A 社のスマホは電池が10時間保つけど B ...
  • 2.1万
7
Accepted

C++での自己参照構造体におけるポインタにおいて

すでにあるコメントだけで十分だと言う気もしますが。 struct MyStruct { int a; int b; } なんて宣言があると、コンパイラはMyStruct型に「int2個分」の領域を割り当てます。 struct AnotherStruct { int key; MyStruct subStruct; } だと、...
  • 1.9万
7

Judy arrayとは何ですか?

簡単に言えば、「CPUのキャッシュ効率を重視した木構造」です。 質問は、機能としてのレイヤと実装としてのレイヤが混ざっているようなので、分けて説明します。 機能レイヤ キーを与えられて、それに関連付けられた値を取り出せるデータ構造は一般的にマップと呼びます。マップには様々な実装があり得ます。単に機能としての「マップ」の話をしている場合は、操作(値の検索、挿入、削除等)...
  • 4,298
6
Accepted

ヒープデータ構造について

回答となると、この英文を訳すしかないので、解釈に必須の部分だけ書きますね。 この問題は二分ヒープを対象としていて、最深部以外は完全二分木になることが前提。上から各段のノードを数えると1,2,4,8...となりますが、最後の段は2の累乗になっているとは限りません。また"at most"はつまり取りうる最大の数という意味なので、1からn/2^(h+1)の間の数ならOKです。 ある関数f(k)...
4
Accepted

ext3ファイルシステムでB木がどのように使われているのか

うまく説明できる自身がないので回答になっているか不安ですが・・・。 フォルダとファイルの構造が B-Tree なのではなく、ディレクトリ内のファイルのブロックを探索するときに B-Tree (HTree) 探索を行います。 ext3はdir_indexを有効にするとディレクトリ内のファイル探索にhashed b-tree (HTreeとも言います) を使いますので、...
  • 7,666
4
Accepted

ハッシュ表のチェイン法による実装における単方向or双方向連結リストの比較

双方向リストの削除という場合キーや位置を指定しての削除と、ノードそのものを指定しての削除とで考え方が違います。 キーや位置を指定して削除する場合、そのノードを見つけるために順にたどっていく必要があるので、単方向リストで prev を発見するのと変わりません。おそらくAkiyama Naoさんが想定してるのはこちら。 一方ノードそのものを指定する場合、双方向リストではそのノード自身や prev, ...
  • 721
4
Accepted

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

計測のために関数を用意しました。 グローバル変数アクセスコストの影響を避けるために、必要な値は引数で渡します。 >>> def f1(n, nums): ... for i in range(n): ... if len(nums) > 0: ... pass ... >>> def f2(n, nums)...
3

逆ポーランド記法で被演算子が3個以上の演算はありうるのか?

もし質問の意図が、+演算子が、不定個数の被演算子を取れるようにできるか、ということだったら無理です。スタックから+演算子を取り出した時にどんな処理をすればいいのか、決定できないからです。 たとえば、乗算も加算も不定個数の被演算子を取れるようにしてみたとします。つまり2 * 3 * 4なら2 3 4 *、5 + 3なら5 3 +と書けるようにします。 ここで普通の式2 + 3 + 4 * 5を、...
  • 5,003
3
Accepted

データ構造のヒープへの挿入方法について

私が書いた方法で実装するのはとてつもない欠点があるのでしょうか? ご自分のコメントでもう気付いておられるようですが、計算量の問題です。 (ついでに言うとLinked Listはデータ本体の他にリンクのための領域が必要になるので、その部分で避けたいと思う人があるかも知れませんが、この回答では触れません。) 挿入の計算量はlogH (Hは完全二分木の高さ)だ この部分に書き間違いがあるので、...
  • 1.9万
3
Accepted

レーベンシュタイン距離(編集距離/エディットグラフ)の出力とグラフにおける最短経路に関して

レーベンシュタイン距離は各編集操作それぞれに別々のコストを割り当てることが可能です。ライブラリが出力したものは、挿入・削除・置換にコスト1を割り当てた場合のレーベンシュタイン距離だと思われます。グラフで求めているものは、挿入・削除にコスト1、置換にコスト2が割り振った場合(あるいは置換操作がなく、削除と挿入にした場合)のレーベンシュタイン距離となります。
  • 793
3

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

次のような配列numsがあったときに、配列の要素数が0かそれ以外かを判定する方法で、 実装方法によってパフォーマンスに後述のような差がありました。どういう理由でこのような差が生まれてくるのかを教えてほしいです。 こちらだけ。 cpython限定ですが、試しにCでループ内処理を書いてみました。 /* Py_DECREF忘れてるよっ!というのはご愛嬌 */ void exec1(...
  • 734
3
Accepted

逆ポーランド記法で被演算子が3個以上の演算はありうるのか?

中間記法「3 + 4 + 5」は逆ポーランド記法ではどのように書けばよいのでしょうか? ご質問中にあるように、3 4 + 5 +でも構いませんし、3 4 5 + +でも構いません。 「3 4 5 +」のように書くことはできないのでしょうか? +がどのような演算として定義されているかによるわけですが、他の箇所に合わせて2数の加算と考えると、3 4 5 +だと、最後の4 5だけが加算されて、3 ...
  • 1.9万
3
Accepted

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

一意に特定できないため不可能です。たとえば 3, 2, 1 という帰りがけ順に対応する二分木は次のふたつが考えられます。 1 | 2 | 3 1 / \ 3 2 一般に、n 個の要素からなる帰りがけ順の配列と n 個ノードがある(ノードに名前がついていない)二分木が与えられると、その帰りがけ順に対応するようにノードに名前をつけていくことができます。...
  • 2.3万
3

データ構造(スタックやキューについて)

スタックやキューは標準ライブラリに入ってるとおもわれるのですが、このクラスを自分で拡張したりすることはあるのでしょうか?? 技術的には、拡張可能です。 C++標準ライブラリが提供するstd::stack(LIFOデータ構造)とstd::queue(FIFOデータ構造)は、要素値のデータ格納機構を外部に委ねるコンテナアダプタ(Container Adapter)となっています。...
  • 9,919
2

ランダムな定休日を登録させる設計

個人的なやり方になりますが、大雑把でいいなら定休日は 大体同じパターンに収束するのでパターン部分を別テーブルにします。 テーブル1 close_id 定休日パターンに紐付けるIDカラム テーブル2 close_id close_pattern 定休日のパターン(計算式) 予想される休日のパターン数がある程度の数に収束するならこれで、 極端に多くなる(数千パターンとか)...
2

ヒープデータ構造について

他の回答者さんがおっしゃってるように、数学的帰納法を使っています。 文章の流れとしては(付番は本文のものとは無関係です) basis = 高さ0の場合の証明 高さ0のノードの個数<=葉の数より、葉の数<=ceil(n/2)を証明すれば十分 葉の数=ceil(n/2)の証明 (これが原文の大部分を占めています) inductive step = 高さh-1での成立を仮定して、...
  • 3,140
2
Accepted

深さ優先探索と幅優先探索の入力と使い方について

現在のコードを実行するときは、2分探索木(以下の例)を入力としていますが、深さ優先探索と幅優先探索の入力は2分探索木でなければならないのでしょうか。 いいえ。一般に、様々な探索問題に対して深さ優先探索や幅優先探索、及びこれらを改善した探索アルゴリズムが使われており、分かりやすい例ではグラフなどのデータ構造に対して用いられています。 現在のコードで返す結果は探索順序となっていますが、...
  • 4,819
2
Accepted

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

回答の前に用語を整理しておきます。 ZIPファイル = ZIPコンテナ仕様に従って、複数ファイルをデータ圧縮・格納したファイル。 ZIPコンテナ = 複数の圧縮データを単一ファイルとして表現する仕様。具体的なデータ圧縮アルゴリズムは選択可能。 ePubではZIPコンテナ仕様に従いつつ、追加要件を課したファイル仕様となっています。 ...
  • 9,919
2
Accepted

テキストログファイルへの追記書き込み速度はファイルの行数(サイズ)とどのような関係があるか?

まあ普通に実装されているファイルシステムにおいては、次のことが言えそうです。 - 追記すべき場所を探す時間は増えるだろう(シークに要する時間は増える) - 追記をし続けている限りにおいては速度は(小さいファイルと)変わらないだろう ハードディスク(や SSD )上にファイルが置かれるとき - ファイルの内容(提示例では数十 GB になったもの) - ファイル自体の情報(ファイル名、権限、...
  • 2.1万
2

ruby で ordered hash 的なことがやりたい

GemsのRBTreeを試してみてください。 https://rubygems.org/gems/rbtree/versions/0.4.2 RBTreeのDocumentationはリンク先ページの右側から見ることができます。
2

ダイクストラ法で最短経路を見つけるときに負の値を持つ辺があると経路は正しくても誤ったコストが出力される

ダイクストラ法では前提として「コストが負ではない」というものを仮定してます。 ルートが正しく表示されているのは偶然ですね。 例えば与えられたグラフにA->Dのコスト3の辺を追加するとコストもルートも共に間違ったもの(A->D:cost=3)が出力されます。(求めたいのは元のA->C->B->D:cost=2のまま)
  • 88
2
Accepted

ダイクストラ法で最短経路を見つけるときに負の値を持つ辺があると経路は正しくても誤ったコストが出力される

一言でいうと、このプログラムは、すべての辺が正であることを仮定したアルゴリズムを使っているため、うまく動きません。以下は、プログラムのwhileループを抜き出したものです。説明のために# for ループ 1と# for ループ 2というコメントを入れています。 while True: min = INF # for ループ 1 for i in range(size): ...
  • 5,003
2
Accepted

ヒープの深さと各深さにおける要素数から和を求めるプログラムのエラー

変数 depth はリストでなくて整数なので、depth[j] のように添え字をつけることはできないため生じているエラーです。
  • 2.3万
2
Accepted

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

このアルゴリズムでは最後のループが回る直前の C[i] の値が、配列 B における値 i の末尾のインデックスを示すように計算されています。このため最後のループでは配列 A を後ろから走査する形が自然です。 逆に考えると、最後のループで配列 A を前から走査したければ、C[i] の値が配列 B における値 i の先頭のインデックスを示すように計算すれば良いです。 ...
  • 2.3万
2
Accepted

有向グラフの表現で、E = {⟨u, v⟩ | u|v,⟨u, v⟩ ∈ V × V and u ̸= v} の表すものが分からない

おそらく u|v の部分が分からないのだと思いますが、今回頂点は自然数なので u や v も自然数で、自然数に対する u|v という書き方だと約数を表す記号として使われているのだと思います。Wikipedia の約数のページなどを参考にしてください。 ただしもちろん、プログラミングで関数を自由に定義できるように、数学でも定義さえすれば記号の意味は変わりうるので、...
  • 2.3万
2
Accepted

クイックソートのパーティションの定義について

どこから解説したらよいものやら・・・ quicksort のアルゴリズムは分かっていますか? ソートしたい配列内にある1つの要素をテキトーに選んでそれより大きいか小さいかを判別するわけですが、その要素をピボットと呼びます。ピボットより小さい要素を左側に、ピボットより大きい要素を右側に集めたら、ピボット要素はその中央に置けばよいわけです。これを分割区間を変えて再帰的に繰り返すと全要素をソートできます。...
  • 2.1万
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

逆ポーランド記法で被演算子が3個以上の演算はありうるのか?

まずはじめに、一般的な言語で大抵の場合は四則演算子+, -, *, ÷は二項演算子です。 これは、二つの数字を引数に取り、結果を返すというのが素直な理解だと思います。 なので、3 4 5 +の様に書けない理由は逆ポーランド記法が原因では無く、演算子が必要とする引数の個数の問題です。 なので、パーサーを自作するなどして、(式として見た場合)自分より左に異なる演算子が見つかるか、...
  • 3,133
1
Accepted

MATLABにおける2次元配列の宣言について

forは使わずに一行で rxData = event.Data(:, 2:end); はどうでしょうか。 (もったいないので前の回答も残しておきます) zerosという関数があります。例えば zeros(40000,5) で、すべての要素を0で初期化した40000x5の配列が作成されます。三次元配列なら zeros(2,3,4) のように作成できます。
  • 5,003

Only top scored, non community-wiki answers of a minimum length are eligible