サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
大谷翔平
vivi.dyndns.org
背景 シーケンス(1次元的に並んだ)データを管理するデータ構造としては、「配列」「双方向リスト」の2つが一般的である。 これらは相補的な特徴を持つ。 すなわち、配列は、ランダムアクセスが O(1) であるが、挿入・削除といった編集処理が O(N) である。 双方向リストは、編集処理は O(1) であるが、ランダムアクセスは O(N) である。 一般的に許容出来るのは O(log N) までであり、配列・双方向リストともに、シーケンスデータ用データ構造としては問題がある。 テキストエディタは文字のシーケンスデータを取り扱うものであり、ランダムアクセスと編集処理が高速である必要がある。 テキストエディタのデータ構造として、「配列」または「双方向リスト」をそのまま用いるのは、上記の点で好ましくない。 ひとつの解決方法として、改行で区切られる1行を動的配列で管理し、行を双方向リストで管理するという
Site will be available soon. Thank you for your patience!
C++11 ではいろんなことがとても便利になった。 その中で、簡単に使えてとっても便利なもののひとつが、本稿で説明する「範囲ベース for ループ(range-based for loop)」だ。 範囲の値を参照 「範囲ベース for ループ(range-based for loop)」の書き方は「for( 変数宣言 : 範囲)」だ。範囲としては、通常配列・コンテナクラスオブジェクトが指定できる。 こう書くと、範囲をループし、各要素を変数に自動的に代入してくれる。 例えば、通常配列の要素を全て表示するコードは以下のように書ける。 int ar[] = {1, 2, 3, 4, 5, 6, 7}; for(int x : ar) { std::cout << x << "\n"; // 1 2 3・・・7 と順に表示される } 上記のコードは、下記のコードと同じ意味だ。すごく楽になったのがお
C言語/C++ VisualStudio とは Microsoft がリリースしている C/C++ を含む各種プログラミング言語の統合開發環境。 2014年に Community 版がリリースされ、個人等では無償でフル機能を利用することが出来る。 商用利用可能。最新版は VSC2013。 詳しくは MS の サイト を参照。 新規プロジェクト作成 ファイル(F)>新規作成(N)>プロジェクト(P)... メニュー。または Ctrl + Shift + N 上記を実行すると、下図の「新しいプロジェクト」ダイアログが表示されるので、言語、種別等を選び、プロジェクト名等を入力する。 たとえば、コンソールアプリのプロジェクトを作成したい場合は、下図の様に「Win32 コンソールアプリケーションを選び、 名前を入力し、場合によってはプロジェクトの場所を指定して、【OK】を押す。 【OK】を押すと、下
概要 C# 動的配列 List とは、動的にサイズを増減できる便利な配列クラスだぞ。 ※ 以前は ArrayList というクラスがあったらしいが、問題があったようで、現在は List の使用が推奨されているようだ。 通常の配列では使用前にサイズを指定する必要があり、アプリ実行中の状況に応じて必要なサイズが増減するような場合は、 どの程度のサイズを指定しておいたらいいか困ってしまう。少ないと足りなくなりにっちもさっちもいかなくなるし、 十分大きなサイズを指定するとメモリの無駄で、場合によってはそれによってパフォーマンスが低下することもある。 その点、動的配列である List を使っておけば、アプリ実行中必要に応じて配列のサイズを増減させることができ安心だ。 i 番目の要素は [i] で参照できるので、使い方も通常の配列とほとんど違わず、必要最低限のことだけ覚えれば、便利な配列として十分使え
C++ 連想配列クラス std::map とは std::map とは C++ で標準に使用できる便利な連想配列クラスでござるぞ。 「連想配列クラス」とは検索可能なキーと、キーに対応する値の組(ペア)を要素とするコンテナクラスで、 保持している要素から、キーを指定して値を高速に取り出せるクラスのことだ。 例えば、string 型の人名と int 型の年齢を組にした要素を保持しておくと、名前をキーにして年齢を高速に取得することができる。 名前から年齢への写像(mapping)のようなものなので map というクラス名を持つ。 ※ タイトルのところにある画像のように地図(map)という意味ではない。 ちなみに、単純な配列を使ってキーから要素を取得する処理時間は O(N) であるが、map は O(log N) と高速である。 これは map クラスが2分木(実装に依るけど、たいていは赤黒木)で
Nビットの数値を16進数に変換すると、(Nが4の倍数であれば、)N/4桁の16進数で表記できる。 演習問題 10進数の100を、2進数、16進数に変換してみなさいshow 100 = 0b01100100 = 0x64 2進数の 01011010 を 10進数、16進数に変換してみなさいshow 0b01011010 = 0x5a = 16*5 + 10 = 90 32ビットの数値を16進数に変換すると何桁になるか?show 32/4 = 8桁 4桁の16進数を2進数に変換すると何桁になるか?show 4*4 = 16桁 C言語、C++ での 2進数、16進数 C言語、C++ による2進数表記 Visual Studio 2013 までは、C/C++で2進数をソースコードを記述することはできなかったが、VS2015 で C++14 対応が進み、 0b プレフィックスで2進数表記が可能になっ
C++ iterator(イテレータ) とは iterator(イテレータ)とは抽象化されたポインタのことで、コンテナ の要素を指し、移動、要素を参照・変更することが出来る。 iterator(イテレータ)は日本語では「反復子」と訳されるが、最近では「イテレータ」と呼ぶことが多いと思う。 もともとは、外部ライブラリであった STL(Standard Template Library) で導入されたものだが、現在では C++ の標準に取り込まれている。 コンテナクラスとSTLアルゴリズムを結びつける結合器的な役割を持つ STLアルゴリズムも現在は標準アルゴリズムとしてC++に取り込まれている イテレータを引数にとる、便利なアルゴリズムが多数用意されている 標準アルゴリズムを使用せず、イテレータ経由でコンテナを操作し、なんらかの処理を行うことも可能 これは、自分でアルゴリズムを書いていることに
ハッシュ連想配列クラス unordered_map とは std::unordered_map とは C++11 で標準に使用できるようになった便利な連想配列クラスでござるぞ。 「連想配列クラス」とは検索可能なキーと、キーに対応する値の組(ペア)を要素とするコンテナクラスで、 保持している要素から、キーを指定して値を高速に取り出せるクラスのことだ。 例えば、string 型の人名と int 型の年齢を組にした要素を保持しておくと、名前をキーにして年齢を高速に取得することができる。 名前から年齢への写像(mapping.)のようなものなので map というクラス名を持つ。 ※ タイトルのところにある画像のように地図(map)という意味ではない。 本来であれば、unordered_map は hash_map のようなクラス名になるべきであったが、そのような名前のライブラリが数種公開されていた
* は C++11 で追加されたコンテナクラス コンテナクラス特徴 コンテナクラスのデータ構造は以下の4種類に分類出来る 配列:vector, array, deque リスト:list, forward_list 二分木(赤黒木):map, multimap, set, multiset ハッシュテーブル:unordered_map, unordered_multimap, unordered_set, unordered_multiset 配列は、ランダム・アクセス:O(1)、挿入削除:O(N)、検索:O(N) ただし、ソート済み配列の二分探索は O(log N) リストは、ランダム・アクセス:O(N)、挿入削除:O(1)、検索:O(N) 二分木は、ランダム・アクセス:O(N)、挿入削除:O(log N)、検索:O(log N) ハッシュテーブルは、ランダム・アクセス:O(N)、挿入削
はじめに 初学者が C/C++ 言語を勉強するときに、ポインタでつまづく人が多いようだ。 少しでも、それらの人達の助けになればと思い、本稿を書いてみた。 多くの人がポインタでつまづく原因のひとつとして、「メモリ」、「16進数」といった知識が必要なのに、 それらをちゃんと理解していないことが多いからではないかと思う。 そこで本稿では、準備編として、それら基礎事項を解説してから、ポインタの解説に入ることにする。 基礎編では、ポインタの基礎について解説する 演習問題編では、多くの問題を用意している。簡単な問題を数多く用意しているので、何度も解いてポインタの使い方を身につけて欲しい 一度説明を読む・聞くと直ぐに理解できて忘れない、という人も極稀にいるようだが、たいていの人は新たな概念をなかなか理解できないし、直ぐに忘れてしまう。 正しく理解して記憶に定着させるには演習問題を手を動かして何度も解くこ
static 修飾子とは 「static」は静的という意味で「dynamic(動的)」の対義語である。 下記の様に変数宣言または関数宣言時に「static」を付加することで、付加された変数または関数が静的であることを宣言する。 static int var; static int func() { return 0; } ここで言う「静的」の具体的な意味は変数、関数の種類によってかなり異なる。なので、static は初級者にとってマスターしづらいもののひとつではないかと思う。 本稿では、それぞれの種類について具体的に解説し、お約束の演習問題も用意している。 理解しづらい概念も、手を動かして演習問題を解いていけば誰でもマスターできるものなので、ちゃんと演習問題をクリアーしてほしい。 static 関数 下記のように、同じプロジェクトに含まれる複数のファイルに、同じ関数名・引数の関数があると、
C++ のクラス とは 「クラス」は C++ の看板娘である。クラスをマスターせずに C++ をマスターしたことにはならない。 そもそも、C++ は最初「C with classes(クラス付きのC)」という名前だったくらいだ。 ただしいつもニコニコして座っているだけの看板娘ではない。結構自己主張が強く、多才で、芸達者だ。簡単にくどき落とすことは出来ないぞ。 「C++ のクラス」とは、型として識別可能な名前を持ち、構造体にメンバ関数を追加したものだ。 クラスとはなんらかの物体・概念を抽象化したもので、メンバ変数により状態を保持することができ、メンバ関数によりそれを参照・操作することが出来る。 クラスは UML という形式で下図のように図示することが出来る。 箱を3つに区切り、一番上にはクラス名を記述する。2番めにはメンバ変数、3番目にはメンバ関数を1行ずつ記述する。 具体的な例としては下図
C 言語は 1972年にUSの有名なベル研究所で Dennis Ritchie らが設計・実装した言語だ。 今となっては低水準な言語だが、充分な機能、簡潔な記法とアセンブラに近いパフォーマンスを持ち、 Unix, Windows, Linux 等の OS をはじめ、コンパイラ、テキストエディタ等のツールや、ビジネスアプリやゲームなど多くの各種アプリケーション開発に用いられてきた。 C++ 言語は 1980年頃、やはりベル研究所の Bjarne Stroustrup が開発したもので、C にオブジェクト指向などの機能を追加したものだ。 C との互換性を維持しつつオブジェクト指向が可能で、パフォーマンスも高かったことから、 1990年頃から、ビジネスアプリやゲームなど多くのアプリケーション開発に使用されるようになった。 C++ は、過去の互換性を維持しつつ最先端のプログラミングパラダイムを多く
概要 プログラム開発当初から過度のパフォーマンス最適化を行うのは良くないと言われている。 プログラムソースの柔軟性が失われる可能性があるし、必要無いかもしれない最適化に時間を費やすのは開発工数管理的に好ましくないからだ。 プログラムがある程度動作するようになり、パフォーマンスが悪い(実行速度が遅すぎる)場合は、 処理時間計測を行い処理時間を要している箇所を探しだし、アルゴリズムやデータ構造の変更などのパフォーマンス・チューニングを行う必要がある。 予備調査として、色々なアルゴリズム・データ構造を採用した場合の処理時間計測を行い、 どれが最適か、どのような性質があるかを知ることも重要である。 本稿では、上記のような目的のためにプログラムの処理時間を計測する方法について説明する。 場合によっては、ストップウォッチを片手にプログラムを実行し、処理時間を計測することもあるかもしれないが、 精度が1
C++ 文字列クラス std::string とは std::string とは C++ で標準に使用できる便利な文字列クラスでござるぞ。 C/C++ ではダブルクォートで文字列リテラルを表し、通常配列に文字を格納し加工することもできる。 strlen() など文字列の状態を返したり、sprintf() などの文字列を作成する関数などが用意されている。 しかし、リテラル文字列は動的な操作に不向きで、柔軟性に欠ける。 そのため、C++では動的にサイズを変更可能な文字列クラス std::string が導入された。 通常文字列と同じように [] 演算子で文字を参照・代入することはもちろん、サイズ情報等の取得や文字の挿入削除なども可能だ。 std::string は std::vector とよく似ている。size(), push_back() など、用意されているメンバ関数もほぼ同じで、 文字
動的配列クラス std::vector とは std::vector とは C++ で標準に使用できるとっても便利な動的配列クラスでござるぞ。 通常配列と同じように [] 演算子で値を参照・代入することはもちろん、サイズ情報等の取得やデータの挿入削除なども可能だ。 「動的配列」とは配列サイズを自由に増減できるという意味。「可変長配列」と呼ばれることもある。 通常の配列は非常に便利で使用頻度の高いデータ構造だが、サイズを予め指定する必要があり、実行時に動的にサイズを変更することが出来ない。 例えば、「int data[100]; 」と宣言した場合、実行時にデータ数が100を超えるとお手上げだ。 スネークゲームでは、ヘビの胴体の長さがどんどん長くなるので、 胴体座標を動的配列で実装している。 これを普通の配列で実装すると、胴体の最大長を保持する可能性があるので、78*21=1638 のサイズの
rand() の問題点 これまで広く使用されてきた rand() による乱数生成には以下の問題点がある。 生成される範囲が [0, 32767] と狭い rand() % N は一様では無い 周期があまり長くない 乱数生成アルゴリズムが固定(通常は線形合同法) 正規分布など、一様でない乱数生成が面倒 rand() で生成される値の範囲は [0, 32767] と狭い。15ビットしかない。 (rand() << 15) + rand() とすれば、30ビット乱数にすることは可能だが、スマートではないし、 生成アルゴリズムの関係で、乱数に偏りが出る場合がある。 通常、乱数として欲しいのは [0, N) 範囲の値であることが多い。この場合は rand() % N とすることが一般的だ。 しかし、このようにして生成した乱数は一様でなく偏りがある。特に N が大きい時にその現象が顕著になる。 例えば
はじめに ニコニコ生放送のプログラミング放送を見ていると、ゲーム開発に挑戦している初級者の若者が多い。 が、当人の知識・能力・経験に対して、目標が高すぎてゲーム完成までに至らないケースが多いようだ。これを業界用語で「失踪」と呼ぶ。 彼らは、充分な経験値・武器・魔法もなく、いきなりRPGのラスボス(小規模だが、フルスペックのゲーム開発)に挑んで、ひとひねりされているようなものだ。 ゲーム開発をやり遂げるには、プログラミング言語の知識はもちろん、各種データ構造・アルゴリズム・コーディングテクニック・デザインパターン・ コンピュータグラフィックス・ユーザインタフェース・フレームワークなどのコンピュータサイエンス・工学に関する幅広い基本的知識・経験が必要だ。 さらに、ゲームによっては幾何学や微積などの数学や、プロジェクトをどう進めるかといったソフトウェア工学の知識・経験も必要だ。 それらの知識・経
概要 QtDesigner は Qt の Widget アプリの画面を簡単に作成・編集することが出来るツールです。 メニュー編集、ウィジットの配置・プロパティ編集、シグナルスロットの設定などをWYSIWYGで簡単に行うことが出来ます。 本稿は Qt 5.2.0 に付属する QtDesigner (QtCreator 3.0.0) について述べています。 基本は変化無いと思いますが、バージョンが異なると細部が異なる場合がありますのでその点はご了承ください。 起動方法・画面説明 QtCreator を使用している場合は、左側に表示されるファイルツリーのフォームの部分を開き、 ui ファイルをダブルクリックすることで、QtDesigner を呼び出すことが出来ます。 VisualStudio+QtAddin を使用している場合も、同様で、ソリューションツリーのフォームの部分を開き、ui ファイル
pointer's boot camp は C/C++ のポインタを学習するための4択問題集です。 以下の10問の答えを選択し、画面下部の【採点】を押してください。 ※ sizeof(void*) は 4、sizeof(int) は 4、sizeof(short) は 2 とする。 ※ 文字エンコーディングは ASCII 、文字列は '\0' を終端とする。 ※ バイトオーダはリトルエンディアンとする。 Q1: ★ int data[100] がある時、配列の先頭アドレスを int *ptr に設定するには? ptr = data[]; ptr = &data; ptr = data[0]; ptr = data; Q2: ★ char *ptr が文字 'A' ~ 'F' を指している時、文字を数値(10~15)に変換するコードはどれ? *ptr + 'A'; *ptr + 'A' +
その他の実装済み機能: 自動・手動 動的補完 マークダウン 豊富な文字変換機能 インクリメンタルサーチ 矩形選択 ※ もし「さくさくエディタ」よりも全置換処理が高速なテキストエディタをご存知であれば、お知らせください。 機能を削ってでも、世界最速になるようにしたいと考えています。 ※ 「さくさくエディタ」のソースコードは「さくさくエディタ」自身で編集しています。 もちろん、このページも「さくさくエディタ」で編集しています。 ライセンス 「さくさくエディタ」32bit 版は基本無料(フリーミアム)なソフトウェアです。 通常使用する基本機能は無料で使用することができ、高度な機能には使用回数制限があります。 が、使用回数は時間がたつと徐々に回復して行きます。 有料ライセンスをご購入(課金)されるとその使用回数制限が無くなります。 また、コマンドを覚えるゲームを行うことで、使用可能な機能を増やすこ
概要 tmlib.js は phi氏開発のゲーム向け JavaScript ライブラリ class 定義、jQueryライクなDOM操作、ajax機能、HTML5 Canvasラップ、アニメーション、 ベクター・行列、サウンド、PC・スマホ対応 などなど MIT License Google Chrome、Safari、Firefox 対応。IE なんて知りません. 多くのクールなサンプルが公開されている スライド ドキュメント tmlib.js > ダウンロード tmlib.js を使って、SBP(スライディング ブロック パズル)を作ってみたよ SBP とはブロックをスライドさせて目的の配置にするパズルの総称 スライディングブロックパズル 15パズル、 箱入り娘、 ラッシュアワー などが有名 tmlib.js のすべての機能を使ってみたわけじゃないけど、使ってみた部分について解説するよ
目次 Signals and Slots 概要 moc_foo.cpp connect disconnect emit シグナル ※注意:本稿は Qt のソースを引用しており、その部分の著作権は Nokia にあり、 ライセンスは LGPL である。 したがって、本稿のソース部分をあなたのプロジェクトで使用するとLGPLに感染するので注意されたし。 引用元の著作権・ライセンス: /**************************************************************************** ** ** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies). ** All rights reserved. ** Contact: Nokia Corporation (qt-i
技術文章> ゲーム・パズル関係 Follow @vivisuke Tweet ビット演算(ビットボード)によるライフゲーム高速化 Nobuhide Tsuda 23-Dec-2012 概要 単純な遷移ルールによる2次元セル・オートマトンである Conway's Game of Life(ライフ・ゲーム)の次世代状態計算を行う高速なアルゴリズムを調査・考案・実装・評価した。 ビットボード演算により8近傍のON状態数をカウントすることで、条件分岐をまったく使用せず多くのビットをパラレルに処理することができる。 本稿では32ビット長までの実装・計測を行なったが、レジスタのビット数に比例した処理速度を得ることが出来るので、 SSE の128ビットレジスタを使用すれば、テーブルを引く方法のように多量のメモリを使用することもなく、さらに4倍程度の高速化も可能である。 ライフゲーム Conway's G
次のページ
このページを最初にブックマークしてみませんか?
『ViVi web site』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く