質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

2回答

1288閲覧

列における無駄な表現?

reotantan

総合スコア295

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2015/12/24 01:48

front変数を最後尾indexに固定して、そこには要素をいれずにrearに要素を追加しながら1を足していくリストです。
11oo 1は要素が入っているという表現です
rear 1 front 3
IsFullで
((rear + 1) % maxQue == front)となっていますが
maxQueで割ってあまり出す必要ないのではと考えました。
確かに結果は変わらないのですが、無駄なものはできるだけ削りたいなと思って質問させていただきました。
皆さまのご意見を聞かせてください

コード bool QueType::IsFull() const { return ((rear + 1) % maxQue == front); } void QueType::Enqueue(ItemType newItem) { if (IsFull()) throw FullQueue(); else { rear = (rear + 1) % maxQue; items[rear] = newItem; } }

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

こんにちは。

これは定石です。

rearが0~maxQue-2の時は単に+1でOKです。しかし、rear == maxQue-1の時、+1するとnになります。これはキューの範囲外です。ですので、++rear; if (maxQue<= rear) rear=0;のようなコードを書きますね。計算してみれば分かりますが、これと同じ結果になります。

そして、「剰余算」と「(maxQue <= rear)判定」の処理時間が同じCPU(現代のPCやスマホは全て該当します)の場合は、++rear; if (maxQue<= rear) rear=0;より、rear = (rear + 1) % maxQue;のほうがブランチしない分高速なのです。

従って、下記のようにするより、提示されたコードの方が高速ですしスマートなのです。

C+++

1bool QueType::IsFull() const { 2 int temp = rear+1; 3 if (maxQue<= temp ) temp=0; 4 return (temp == front); 5}

投稿2015/12/24 02:23

Chironian

総合スコア23272

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

catsforepaw

2015/12/26 11:27

ちょっと気になったので横から失礼します。 > 「剰余算」と「(maxQue <= rear)判定」の処理時間が同じCPU(現代のPCやスマホは全て該当します) これは誤りです。剰余算はCPUの除算命令で計算するのですが、除算命令はどのCPUでも非常に遅い命令に該当します。本気でパフォーマンスを考えるのであれば、できるだけ除算命令を使わないようにするのが定石です。 ちなみに、x86系のCPUの場合、条件分岐なら数クロック程度ですが、除算命令は除数にもよりますが数十クロックかかります。しかもビット数が増えるとクロック数も増えます。同じソースコードなら基本的に32bitより64bitでコンパイルした方がパフォーマンスが上がりますが、size_tなどの計算で除算が使われていると(このようなケースでは大いにあり得ることですが)逆にパフォーマンスが下がることがあるので要注意です。
Chironian

2015/12/26 12:24

げっ。検索してみたところ確かにそのようですね。 うひゃ~。ずっと気にせずに剰余でやってました。 この場合はifの方が速いのですね! どこかで大きな記憶違いをしてしまったようです。 訂正、ありがとうございます。
guest

0

普通はキューの長さを2のn乗(たとえば256)にしてrear= (rear+1)&0x00ff;とかしますねd^^
「加筆」
こうする事で、アセンブラレベルでaddとandの2命令になります。

投稿2015/12/26 10:13

編集2015/12/26 12:34
cateye

総合スコア6851

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問