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

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

ただいまの
回答率

91.35%

  • C

    2525questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • C++

    2412questions

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

C言語、配列の要素数を2の冪乗にする理由

解決済

回答 7

投稿 2017/11/22 17:51 ・編集 2017/11/23 22:14

  • 評価
  • クリップ 1
  • VIEW 686

strike1217

score 480

char buf[10];


配列の宣言についてなのですが・・・

配列の要素数を2のべき乗にする人がよくいますよね。
この理由は何でしょう?

2, 4, 8, 16, 32, 64, 128 などとやる理由はなんです?

アライメント関係があるのかと思ったのですが、ないような気がしてきました。
分かる方は理由を教えてください。
どのようなメリットがあるのでしょう??

「追記」
asmさんの回答を見て確かに、2,4は見かけないですね。
小さすぎて特に使わないという理由もあるかもしれませんが、もしかしてアセンブリ言語のスタックが32bit(4B)が関係しているんでしょうか??

8, 16, 32, 64, 128 2のべき乗と言うより、4の倍数ですか?

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 7

checkベストアンサー

+4

こんにちは。

アライメントでパディングが発生するくらいならその領域を使う時と、単なるキリ番の両方があると思いますよ。

投稿 2017/11/22 18:23

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/11/23 22:11

    アライメントと関係があるという事ですよね?
    2のべき乗にするとパディングが発生しないんですか?

    キャンセル

  • 2017/11/23 22:17

    アライメントは2のべき乗になりますから、2のべき乗に足りない分がパディングで埋められます。そのパディングをなくそうとすると2のべき乗になります。

    例えば、double型は通常8バイトのアライメントです。double型の直前にchar[11]の領域を確保していると5バイトのパディングが発生します。パディングで使わないより使ったほうが好ましい時はchar[16]にすることでパディングがなくなります。

    キャンセル

  • 2017/11/23 22:20

    ああ、なるほど!
    アライメントが2のべき乗になるのですね。

    だから、2のべき乗にした方が効率よくメモリを扱えるというわけですね!

    キャンセル

  • 2017/11/23 22:25

    例えがとても分かりやすいです。

    直前の配列の要素数は、次の変数と直前の変数の隙間に影響を与えると考えれば良いのですね!!

    キャンセル

+4

他回答者の方が仰るように、メモリなど、
パフォーマンス上のメリットは実際には少ないでしょう。

しかし、C言語に限らず、配列に限らず、
何かのデフォルトの数値に、2のべき乗を設定することが、
私はわりとよくあります。デフォルトのデフォルトです。


なぜそうするかというと、1に到達するまで、余りを出さずに、
どこまでも半分半分に分割できることが保証されているから、
多くしたり少なくしたりする操作が容易です。

普通のキリ番、たとえば300だと何が起こるかというと、
300→150→75→? で、もう半分に割りきれません。
とりあえず、37にしましょうか。

しかし、反対に倍に増やしたとき、74になります。
74→148→296となって、単純な操作では元に戻りません

もちろん、人間が判断するならそれくらい分かりますが、
機械に自動的に増減させるときに、処理が多少面倒です。


「100とか定数を増減させれば?」と思うかもしれませんが、
べき乗は圧倒的にスケールを変える足が速いです。

たとえば、2の20乗でもう約100万まで行きますが、
100を足すのでは1万回掛かります。

「桁数に応じて増減する値を変えて……」
ということもできますが、やっぱり処理が多少面倒です。


話は飛躍しますが、遺伝的アルゴリズムのような探索的な手法を取るときに、
100世代とか1万世代とか反復するので、
こういう細かいところで、意外と結果に差が付く場合があります。
カオスで誤差が増幅するみたいな話です。

結論として、2のべき乗を好むのは、
アルゴリズムによくある、再帰的な発想のひとつです。

投稿 2017/11/22 20:32

編集 2017/11/22 20:41

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/11/22 21:22

    ふむふむ・・・

    アライメントとは全く関係がないようですね。
    アルゴリズムの1つとして考えればよいんですかね。

    キャンセル

+2

現実にはあまりメリットはなく、単にキリが良いからというイメージからではないでしょうか。
とくにヒープの場合ですと、割当するバイト数以外の管理用の領域が必要だったりするので、アライメント上はかえって不利になる可能性さえあります。

投稿 2017/11/22 19:02

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/11/22 21:18

    そうなんですか!
    特別なものではないんですかね。
    ずっとアライメントと関係があるものかと思っていました。

    キャンセル

  • 2017/11/24 11:59

    > アライメント上はかえって不利になる可能性さえあります。

    一応、念のため指摘しておきますが、ヒープ領域を取得する際に2のべき乗にすることで不利になる可能性はありませんよ。私の知る限りでは(といってもVC++とgccぐらいしか知りませんが)mallocが返すヒープ領域の先頭アドレスは、サポートするすべてのデータ型のサイズ(少なくともdoubleの8バイト)にアラインメントが合うことが「保証」されています。ですので、特殊な事情(SSEやAVXの利用等)がない限りはアラインメントを気にする必要はありません。

    キャンセル

+2

昔のアセンブラー上がりのCプログラマーはバッファサイズなどを2のべき乗にする習慣があったのかもしれません。限られたメモリ領域を無駄なく隙間なく埋めるには2のべき乗サイズであると都合が良いですし、メモリレイアウトを考える際もきりの良い数字だと設計しやすいし(昔は方眼紙に書いていた!)、なによりも配列などのアドレス計算がビット演算でできるので少ない命令で高速に処理できます。あるいは、ハード(OS)寄りのCプログラマーも2のべき乗サイズにする習慣があるかもしれません。デバイスとやりとりするバッファサイズが2のべき乗であることが多いからです。
そして、そのような先輩プログラマーを見習った新人プログラマーが、あまり深く考えずになんとなくまねしているうちに2のべき乗サイズにする習慣が付いた、ということもあるかもしれません。

メモリもクロックもメガを通り越してギガに突入している今となっては2のべき乗にこだわるべき理由はないでしょう。ただ、リソースが乏しい小規模な組み込み系(搭載メモリの単位がキロバイトとか)などでは、メモリの効率利用やパフォーマンスのために考慮する価値はあると思います。

投稿 2017/11/23 20:56

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/11/23 22:10

    「限られたメモリ領域を無駄なく隙間なく埋めるには2のべき乗サイズであると都合が良いです」
    この理由はなぜでしょうか??

    キャンセル

  • 2017/11/23 22:15

    なぜ、2のべき乗にすると、無駄なく隙間なく埋めることができるんですか?

    キャンセル

  • 2017/11/23 22:40

    搭載メモリのサイズが大抵2のべき乗だからです。8キロバイトとか32キロバイトとか。無駄なく使うには綺麗に分割できるサイズにするのが自然だと思います。

    キャンセル

  • 2017/11/23 22:55

    ああ。なるほど!
    確かに、それもありますね。

    キャンセル

+1

char buf[255]等とすることはあります。
サイズを1バイトで表現できる0xffとしているためです。

0x100や0x200がきりよく感じられるということもあるかもしれません。

投稿 2017/11/22 18:50

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

私も気になったので検索してみました。かなり古い回答ですが、「mallocやfreeでのヒープ領域でのフラグメンテーションの発生を抑えるため」という回答があります。自動変数などが割り当てられるスタック領域にはとくにこの2の冪乗の意味はないようですが、おそらくmalloc等で確保したヒープ領域とサイズを合わせる風習があったのではないでしょうか。
http://thesmithfam.org/blog/2005/09/18/power-of-2-array-sizes/

投稿 2017/11/22 18:50

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/11/22 21:20

    ヒープ領域で使われていた・・・という事でしょうか?

    キャンセル

0

2,4はあまり見ないような?

割となんとなくですが大体の規模を考える時に考えやすい
データ数が30~70多くても100いかないくらい => ちょい余分に128にしとこう
100~150 => 256もあればいいだろう
とか

ただ、自分でメモリ管理ライブラリ組むとしたら256 or 1KByte単位で管理するので
ライブラリやコンパイラも同様の仕様になってる可能性もあるかなーとか

投稿 2017/11/22 19:13

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

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

ただいまの回答率

91.35%

関連した質問

同じタグがついた質問を見る

  • C

    2525questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • C++

    2412questions

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