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 データ構造のヒープへの挿入方法で質問です。 ヒープへの挿入は、今あるノードの末尾に新しいノードを追加し、 その後、ヒープの条件を満たすような修正のオペレーションをすることだと 書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」で見ました。 ネットでしらべても同様でした。 また挿入の計算量はlogH (Hは完全二分木の高さ)だとも見ました。 ここで疑問です。 そんなことをしなくても ヒープ構造をlinked_listで作っておいて、挿入時は前から順番に走査し、 大小関係を満たすところにlinked_listの新しいノードとして挿入すればO(n)で挿入(nはノードの個数)できます。 この方法のほうがシンプルですし、挿入もO(n)でできて速いのかなと思います。 まぁ、前者のほうがlogHなので高さと要素数の兼ね合いでは速いかもですね。 ただ、前述に述べた方法をみんな説明していたのでそれがスタンダートかつベストプラクティスなんだろうなと思っています。 私が書いた方法で実装するのはとてつもない欠点があるのでしょうか? 解決 私が書いた方法で実装するのはとてつもない欠点があるのでしょうか? ご自分のコメントでもう気付いておられるようですが、計算量の問題です。 (ついでに言うとLinked Listはデータ本体の他にリンクのための領域が必要になるので、その部分で避けたいと思う人があるかも知れませんが、この回答では触れません。) 挿入の計算量はlogH (Hは完全二分木の高さ)だ この部分に書き間違いがあるので、余計混乱したのかも知れませんが、ヒープの挿入の計算量は、総ノード数nに対して、(ワーストケースで)O(log n)です。高さHもlog nで表されるので、混同されたのでしょうか。(この辺り全部単純二分ヒープを想定しています。) 挿入もO(n)でできて速い 前者のほうがlogHなので高さと要素数の兼ね合いでは速いかも 先述したようにO(n)対O(log n)です。Big-O記法を見慣れた人なら「O(log n)の方がダントツに早い」なんて結論づけてしまうかも知れません。 n = 1000程度の時、log_2 n ≒ 10程度、いくら1回の操作がシンプルでも、1000回の繰り返しは、ほんのちょっと複雑な操作10回には負けるでしょうね。nが大きくなれば、この差はますます大きくなります。 一方n = 30程度の時にはどうなるでしょうか? log_2 n ≒ 5となります。シンプルな操作30回とちょっと複雑な操作5回ではなかなか微妙なところです。nが小さくなれば、この差はますます縮まります。 と言うわけで、 ヒープはデータの総量nが多い時には極めて有効な方法 と言えるでしょう。 アルゴリズム・データ構造には状況・条件によって向き不向きがありますし、Big-O記法での計算量評価は、nが小さい時にはあまりあてになりません。 ハッシュテーブル(辞書型とか言われることも多い)でのデータ1件取り出しはO(1)と言うことになっているんですが、n = 10程度なら配列を単純検索(O(n))の方が早くなることが多いです。 総数が最大でもn = 30程度にしかならない状況で、(コードが理解しづらい)ヒープ処理を書こうとしている同僚を見つけたら、私なら「やめとけやりすぎや」と言って止めるでしょうね。自分で実装できるようになるべきかどうかは置いといて、条件・状況によって最適なアルゴリズム・データ構造を選べるようになりたいものです。…(Continue Reading)

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

投稿者: Anonymous 40000行 x i 列の2次元配列にデータを入れていくコードを書いています。 現在1次元の配列なので、エラーが以下のように出ていますが、MATLABではどのように2次元配列を宣言するのでしょうか。 エラー 添字による代入の次元が一致しません。 コード num = 3 for i = 1:1:num rxData(i) = event.Data(:, i+1); end pythonだと for i in range(num): list 1 = [[0]*i]*40000 で0の40000xi列の2次元配列が作れますが、MATLABでの宣言方法を調べても見つけることができていない状態です。 MATLABドキュメントの多次元配列、行列および配列は目を通しましたが、宣言方法について細かく明記している箇所がありませんでした。 ご回答を受けて追記 ご回答いただきましてありがとうございます。 for i = 1:1:num rxData = zeros(40000, i); end for i = 1:1:num rxData(i) = event.Data(:, i+1); end とすると 「代入文A(:)=…(Continue Reading)

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

投稿者: Anonymous あるWebアプリケーションで本番サーバーのアプリケーションログファイルをローテーション設定をせずにずっと使いまわしていました。 いつの間にかログファイルのサイズが数十GBになっていました。 質問 ファイルにログを追記するときの書き込み速度はログファイルの容量が大きくなればなるほど遅くなるのでしょうか? 補足 テキストファイルのデータ構造がどうなってるのかわからないのですが、LinledListのような感じで最終行のポインタを保存しているのですかね。もしそうならどこに記入するかを判定する時間はO(1)でその要因では特に遅くはならなそうです。 テキストファイルへの情報の書き込みがどのように行われているのかを調べたのですが、どうやらファイルディスクリプタという存在があるというくらいまでしかわかりませんでした。 もし、それを知りたい場合どのように調べたらよいかも教えていただけると助かります。OSにおけるファイルへの書き込み方法みたいなことを勉強する必要があるのですかね。 解決 まあ普通に実装されているファイルシステムにおいては、次のことが言えそうです。 – 追記すべき場所を探す時間は増えるだろう(シークに要する時間は増える) – 追記をし続けている限りにおいては速度は(小さいファイルと)変わらないだろう ハードディスク(や SSD )上にファイルが置かれるとき – ファイルの内容(提示例では数十 GB になったもの) – ファイル自体の情報(ファイル名、権限、タイムスタンプなど、せいぜい数百バイト) – ファイル内容が装置上のどこに保存されているかの補助情報(可変サイズ) のように、情報はいくつかに分割されて記憶装置上の別々の個所に登録されます。 「ファイル自体の情報」はアクセスする際には必ずチェックされるし固定サイズなので、ここのアクセス時間はファイルの大きさに関係ありません。 追記するにはファイルの末尾がどこにあるかを知る必要があるので、補助情報を追っかけていく必要があります。なのでオープン直後(ないしは seek 時)にファイル補助情報の大きさにほぼ比例した時間を要するでしょう。書き込むだけで読み込まないのならファイル本体部分にアクセスする必要はないので(最後のクラスタを除く)追記自体にかかる時間は違わないでしょう。 OS がどうファイルシステムを実装しているかは、普通のプログラマはあまり気にしなくてよいと思います。それでも知りたいのなら、ファイルシステムの解説を読むのが良いでしょう( OS のソース読むより理解しやすいだろう)。 組み込み系だと SD/MMC カードをマイコンのソフトで自前で読み書きするとかの案件もある(=ファイルシステムの細かいところまで自前実装する)んですが、まあ例外っすよね。 オイラ何回も書いてますが、アルゴリズムやデータ構造やファイルシステムやその他の – 長所短所は知っておく必要がある。知らないと使い分けできない。 – 普通に使う上では、詳細実装を知る必要はない。 – 詳細実装を知りたくなったら資料はたいてい公開されているので探してみよう。 回答者: Anonymous

Outlineビューを実現したいが、木構造を一次元のリストで表現できるような構造の名前を知りたい

投稿者: Anonymous 概要 タイトル通り、実現したい構造があるのですが、いまいち具体的に言語化もできず、どのようにアプローチしたら良いのか分からず困っているので、以下の要件を実現できる構造をご存知であれば教えていただけると非常に助かります。 テーブルに木構造を表示するために、データを一次元配列で提供できる その際、Orderを保持できる(画像のイメージ) 定数時間での検索が可能O(1) AppendToParent, InsertBefore, InsertAfter, DeleteItemsがAPIとして利用可能 近いもの NSOutlineView,OutlineGroupのような仕組みを自作したいです。 これまで試したこと 木構造やグラフ理論に対する基礎以上の深い知見がないため、場当たりでいくつか試しました。(AVL木やB木など、一通り学んでみたのですが、この問題にマッチするか分かりませんでした。) まず探索に対してはハッシュテーブルに[Hash:Node]という形式でデータを保存し、キーを渡されると定数時間で取り出せるように試みました。ノードは class Node { var item: Item var children: [Node] var prent: Node? var index: Int } 上記のような構造を作り、追加・挿入・削除のたびに木をトラバースしてインデックスの振りなおしを試みました。変更のあったノードからルートへのパスにマークを付け、マークのついたノードより左の部分木には探索を行わない(枝刈り?)探索も試みました。 一次元の配列はハッシュテーブルの中身をインデックスでソートして、中身のアイテムだけ取り出すことで実現を試みました。 一応これらでも振る舞いとして意図通りに動いたものの、どうも効率が良いとは思えず、質問に至りました。 もしご存知であれば、何か該当するデータ構造やアルゴリズムについて「このキーワードでググれば分かるよ」程度でも教えていただると助かります。よろしくお願いします。 解決 おそらくNativeTreeと言われるものかと思います。 インデックスで別次元にデータを保持していますが、インデックスをやめて直接データをNodeに保持すれば最もシンプルなツリー構造と言えるでしょう。 それがNativeTreeともいわれている形になります。 今回の場合はデータを別の次元に保持しているだけで、実際はNativetreeから離れていないように思えます。 以下、蛇足ですが、 探索に対してはハッシュテーブルに[Hash:Node]という形式でデータを保存し、キーを渡されると定数時間で取り出せるように試みました 探索とは経路探索(Aにたどり着くためにはどの経路がいいのか?)や深さ探索(Bの子どもたちの最大の深さは?)がメインになります。どのノードにアクセスすればいいかわかっている状況でノードのデータを探しに行くことはどのツリー構造でも定数でアクセスができるでしょう。 経路探索をしてみるとなかなか大変なことに気づくと思います。 回答者: Anonymous

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

投稿者: Anonymous スタックを使った「深さ優先探索」とキューを使った「幅優先探索」について、入力と使い方に関してわからないことが2点あります。 現在のコードを実行するときは、2分探索木(以下の例)を入力としていますが、深さ優先探索と幅優先探索の入力は2分探索木でなければならないのでしょうか。 T = ((((), 111, ()), 11, ((), 112, ())), 1, (((), 121, ()), 12, ((), 122, ()))) 現在のコードで返す結果は探索順序となっていますが、実際に仕事や競技プログラミングなどで使われる時はどのように使用されるアルゴリズムなのでしょうか。 検索してみましたが、大学等の教育機関の資料が主でした。初心者にもわかりやすい「深さ優先探索」と「幅優先探索」のアルゴリズムが使われているコードがあれば教えていただきたいです。 どちらの探索方法が適しているのか判断の仕方が現在のコードだけだと理解できていません。 結果 depth_first_search(T) 1,12,122,121,11,112,111, breadth_first_search(T) 1,11,12,111,112,121,122, 深さ優先探索 from collections import deque def depth_first_search(T): D = deque() #スタック if len(T) > 0: D.append(T) #show(D) while len(D) > 0: L, a, R = D.pop()…(Continue Reading)

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

投稿者: Anonymous n 個の要素を持つヒープの、高さ h における節点が n/2^(h+1) 個である、理由がわかりません。 問題文の原文はこちらです: Show that there are at most ⌈n/2^(h+1)⌉ nodes of height h in any n-element heap. 以下がIntroduction to Algorithms 練習問題6.3-3に対するInstructor’s Manual の解説ですが、なぜh=0が正しいからの証明から始まるのか、また#は何をさしているのかよくわかりません。 もしもっとわかりやすい証明があれば、解説をお願いします。 解決 回答となると、この英文を訳すしかないので、解釈に必須の部分だけ書きますね。 この問題は二分ヒープを対象としていて、最深部以外は完全二分木になることが前提。上から各段のノードを数えると1,2,4,8…となりますが、最後の段は2の累乗になっているとは限りません。また”at most”はつまり取りうる最大の数という意味なので、1からn/2^(h+1)の間の数ならOKです。 ある関数f(k)があったとして、k=0,1,2,3…とします。f(k+1)をf(k)で表すことができるとき、初期条件f(0)が決まれば、あとは再帰的に答えが正しいことが証明できます。それがh=0の証明から始める理由です。これを数学的帰納法(mathematical induction)と言います。 説明中に出てくる変数 n: ツリー中の全ノード数 h: height(高さ)はノードを下から辿った数 d: depthまたはlevel(深さ)はノードをルートから辿った数 H: ツリー全体の高さ x: 最深部のノードの数 base caseのnが偶数xが奇数の説明 絵を描いてみました。下手くそですみません。 他の証明方法? xを末端の葉の数とした時、nは次のように表せますし、高さは最低log(n+1)あることを手掛かりに展開するような方向でいけるかもしれません。 回答者: Anonymous

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

投稿者: Anonymous 中間記法「3 + 4」は逆ポーランド記法だと「3 4 +」のように書けます。 では、被演算子が3個以上、たとえば中間記法「3 + 4 + 5」は逆ポーランド記法ではどのように書けばよいのでしょうか? 「3 4 + 5 + 」と書けばよさそうですが、「3 4 5 +」のように書くことはできないのでしょうか? (乗算でも同様にできそうですが引き算だとどうなるのかちょっとよくわからないですね) 解決 中間記法「3 + 4 + 5」は逆ポーランド記法ではどのように書けばよいのでしょうか? ご質問中にあるように、3 4 + 5 +でも構いませんし、3 4 5 + +でも構いません。 「3 4 5 +」のように書くことはできないのでしょうか? +がどのような演算として定義されているかによるわけですが、他の箇所に合わせて2数の加算と考えると、3 4 5 +だと、最後の4 5だけが加算されて、3 9と書いたのと同じ状態になってしまいます。 もし「スタック上から3つの数を取り出して全部を足し合わせる演算」、なんてものが定義できれば、3 4 5 add3なんて書き方もありになります。 逆ポーランド記法を基礎に置いた言語(と言うよりスタック操作を基礎、と言った方が良いかもしれませんが)Forthだとこんな感じ。(以降は行コメントです。) : add3 +…(Continue Reading)

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

投稿者: Anonymous ext3のパーティションフォーマットでB木が使われているそうなのですが、階層構造を表した時親に値が複数存在するB木だとどこか変だと思うのですが本当にB木が使われているのですか 自分のイメージでは木構造でフォルダを表しファイルをB木で表すことやDBMSの索引や検索機能では有効に働くと思いますが実際はどのようになっているのですか 解決 うまく説明できる自身がないので回答になっているか不安ですが・・・。 フォルダとファイルの構造が B-Tree なのではなく、ディレクトリ内のファイルのブロックを探索するときに B-Tree (HTree) 探索を行います。 ext3はdir_indexを有効にするとディレクトリ内のファイル探索にhashed b-tree (HTreeとも言います) を使いますので、無効な場合の線形探索に比べると、ファイルが多くなるほど探索結果がでるまでの時間が短くなります。 tune2fs のManページでは次のように説明されています。 dir_index Use hashed b-trees to speed up lookups in large directories. 回答者: Anonymous

二分探索木を分割する際の計算量

投稿者: Anonymous https://www.geeksforgeeks.org/split-a-bst-into-two-balanced-bsts-based-on-a-value-k/?ref=leftbar-rightbar こちらのコードを用いてBSTを分割する際の計算量は、O(h)(hはツリーの高さ)ということは直感的には理解できるのですが、どうしても具体的に証明する方法がわかりません。お力を貸していただけると嬉しいです。 以下上のサイトより部分的にコードを引用します。 // Function to split the BST // into two Balanced BST void splitBST(node* root, int k) { // Print the original BST cout << “Original BST : “; if (root != NULL) { inorderTrav(root); } else { cout << “NULL”; } cout << endl; // Store the size of BST1…(Continue Reading)

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

投稿者: Anonymous C++で自己参照構造体というものがあると思います。(後述の二分探索木の例を参照) この場合、p,l,rの型はNodeではなくてNode*です。 これはNodeではいけないのでしょうか? ネットで自己参照構造体をぐぐってみると、みんなポインタを使ってはいるものの、 ポインタである必要性を説明している記事が見当たらなかったので不思議に思ってます。 struct Node { int key; Node *p, *l, *r; } 解決 すでにあるコメントだけで十分だと言う気もしますが。 struct MyStruct { int a; int b; } なんて宣言があると、コンパイラはMyStruct型に「int2個分」の領域を割り当てます。 struct AnotherStruct { int key; MyStruct subStruct; } だと、AnotherStructの大きさは、keyの「int1個分」とsubStructの「int2個分」を合わせて「int3個分」なります。 もし、こんな宣言が可能だとしたら、LinkedListの大きさはどうなりますか? (二分木ではなく、単方向リストにして単純化しておきます。) struct LinkedList { int key; LinkedList next; } このように直接の自己言及(再帰)を許してしまうと、コンパイラはLinkedListのサイズも内部表現も決定できなくなってしまいます。 (x = 1 + x の解を探すようなもので、無限大を許す算術をこしらえないと、解無しになってしまいます。) このようなことを防ぐために、構造体等の宣言では直接の自己言及を禁止して、再帰的な構造はポインタ(ポインタのサイズは、ポイント先の大きさにかかわらず一定)を使用して表現します。…(Continue Reading)

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

投稿者: Anonymous ダイクストラ法のコード(python)を参考に以下のプログラムを実行しました。 出力として最短ルートは’A->C->B->D’と求められましたが、コストは「5+(-4)+1=2」になるところ、’A->B->D’の「3+1=4」が出力されました。原因がわからないです。 グラフ部分はコードのrouteにあたります。 出力 $ python dijkstra.py visited to A. visited to B. visited to D. visited to C. minimal cost is 4. optimum route is ‘A->C->B->D’. # dijkstra.py import sys INF = 10000 VISITED = 1 NOT_VISITED = 0 route = [ [INF, 3, 5, INF], [INF, INF, INF, 1], [INF, -4,…(Continue Reading)

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

投稿者: Anonymous 現在スタック、キュー、ツリー、ソートなどを始めとしたデータ構造とアルゴリズムの勉強をしています。これはエンジニアの基礎的なスキルだから(と世間様が言ってる)という理由が私のモチベーションです。 ですがここで質問です。 質問 これらが重要と認識されてる方は、これまでご自身の開発でどのようなシーンで使ってきたか教えてもらいたいです。もしできれば、実際の現場レベルでの活用事例を紹介したWebサイトの紹介もお願いしたいです というのも、RailsやDjangoやZend FrameworkなどによるWebアプリケーションやiOSアプリ、機械学習などの領域でこれらを使ったことがあるというエンジニアが周りにいないです。私も使った記憶がありません。でもなんで世間様はこんなにもデータ構造とアルゴリズムを重視されてるのでしょうか。特にアメリカ西海岸のIT企業などで。 コーディング面接で必要であったり、Googleのような超巨大なサービスではフルに活用しないとパフォーマンス、サーバーのコストなどに雲泥の差が出てくるんだろうなとは思っています。 ですが、世の中の殆どのSEのうち、このような巨大なサービスでパフォーマンスをチューニングしてる人は一握りだけでしょう。 彼ら以外でもデータ構造やアルゴリズムをうまく活用している人たちはいるかもしれませんが、どのように用いてるのか全く検討もつきません。「XXXのような仕様のアプリケーションでフレームワークにはXXXを用いており、具体的にこういう処理で必要になる」くらいの事例をものすごく知りたいです。 例えばソートは組み込み関数で行えるので、どのソートアルゴリズムを使うのかなんて考えないです。ツリー構造でのトラバーサルなどそもそもデータをツリー構造にする時点で全然イメージがわかないうえ、post order トラバーサルとかlevel order トラバーサルやAVL木なんて実務でいつ使うんでしょうか。RDBのインデックスで使ってるとかそういうのは知ってますが、そんな低レイヤーをいじるのは一握りの人だけですよね。 長々と書きましたが、データ構造やアルゴリズムが必要とされるのはかなり一握りの人たちだけでほとんどのSEには必要のないこと、知らなくても業務はこなせるのになんでこんなにデータ構造やアルゴリズムがもてはやされてるのでしょうか、ということが気になっています。 追記 実際にデータ構造やアルゴリズムの勉強をしていると、そんなのなんの役に立つの?などと聞かれることが多々あります。上長に説明しても、そんなのGAFAに入るために必要なだけでしょとか失笑されます。 解決 巨大なシステムでは重要≒普通のシステムでは知らなくてよい、とお考えのようですがとんでもない話です。資源の少ないマイコンでは RAM も貴重 ROM も貴重、電池も貴重で、最適なアルゴリズムやデータ構造を使わないと1つ1つの処理に余計な時間がかかります。電池機器(まあ端的にはスマホっすけど)では無駄な処理は一切許されません。ほぼ同じような処理をして A 社のスマホは電池が10時間保つけど B 社のスマホは20時間保つ、とかなればお客様は B 社に流れてしまいます。この辺の事情はPCでも同じことですよ。 データ構造、アルゴリズムの 詳しい実装までは知らなくてもよい(たいていは既にライブラリ化されているので、ありがたく使わせていただくだけで良い)のですが 本質的に何がどう違ってどういうメリット・デメリットがあるか、は知っておかないと選択の余地がありません 他にも例えばカルドセプトというゲームでサイコロの出目がバグっている事件なんてのがありましたが、これも「疑似乱数」というアルゴリズムを正しく理解せずに使ってしまったがゆえに発生したものと推定されています。こんなバグを出してしまったメーカーの技術力は大いに疑われる、つまり市場の信頼を失ってしまいます。 知っていればもてはやされる、レベルの話ではなくて 知らないと失笑される、と考えてください。 回答者: Anonymous

Linked Listのトラバーサルの方法で質問です

投稿者: Anonymous Linked ListをPython3実装し、トラバーサルの実装方法で質問です 下記のような前提条件があったとします。 前提条件 Linked Listのノードクラス class Node: def __init__(self, x): self.val = x self.next = None # 初期化 node = Node(1) node.next = Node(2) node.next.next = Node(3) 質問 ノードをたどっていく下記の二方法の実装ではどのような違いがありますか? 方法1 while node: node = node.next 方法2 while node is not None: node = node.next 補足 nodeがNoneでないことを素直に実装すると方法2になると思います。 ですが、LeetCodeやAOJ, AtCoderなどで他の人が実装したLinked Listを見ると、 たいてい方法1で実装しています。もし方法1でも方法2と同じ挙動なら方法1のほうが短くていいなと思っています。 解決 方法1と方法2には違いがあります。…(Continue Reading)

異なる文字列の接頭語と接尾語を比較

投稿者: Anonymous ある文字列S1、S2があるとして、S1の接尾語はS2の接頭語を反転させたものと等しいか比較し、一致する箇所だけをS2から削除したのち、その2つの文字列を連結させるというプログラムを実装したいのですが、効率的な方法はありますでしょうか。 現在は、 S1,S2を読み込む S1を反転 S1とS2の接頭語を一文字ずつ比較し、一致した回数を数える。一致しなくなった時点で終了。 S2から一致した回数分だけ文字を削除 元のS1と編集されたS2を結合 とういう、あまり効率的ではないようなアルゴリズムしか思いついていません。 接頭、接尾トライ木を使えば効率的にできる気がするのですが、実装方法が思いつきませんでした。 助言などいただけると幸いです。 追記 例えば、 S1=stringlist S2=tsilabcde の場合、 stringlist,(tsil)abcde (()内は削除)となり、期待される出力は stringlistabcde といったような感じです。 解決 実装例です。 #include <stdio.h> #include <sys/param.h> #include <string.h> void concatRemovingCommon(char *strA, char *strB, char *strResult, size_t bufLen) { size_t lenA = strlen(strA); size_t lenB = strlen(strB); size_t len = MIN(lenA, lenB); char *ptrA =…(Continue Reading)