FC2ブログ

PCとかゲームの備忘録

Cで押し出し配列を実装してみた

正直ポインタを使って実用目的でコーティングしたのは初めてで楽しかったのでメモ。
今回作ったのは配列の要素数超えたら古いデータから消していくっていうものです。
配列の後ろに追加されていきます。
C++は把握しきれてないのでCだけで書いてみました。
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define NEW(x) (x*)malloc(sizeof(x))
#define NEWINT(x) (int*)malloc(sizeof(int) * (x))
typedef struct PushArray
{
	int* data;
	int len;
} PushArray;
void construct(PushArray* p, int n)
{
	//後で処理統一したいので+1
	p->data = NEWINT(n + 1);
	p->data++;
	p->len = n;
}
void dispose(PushArray* p)
{
	//ずらしたので-1
	free(p->data - 1);
	free(p);
}
void append(PushArray* p, int d)
{
	//新しくコピーを確保して
	int* moved = NEWINT(p->len + 1);
	memcpy(moved, p->data, sizeof(int) * p->len);
	//最後にデータ追加
	moved[p->len] = d;
	free(p->data - 1);
	//ずらして登録
	p->data = moved + 1;
}
int main()
{
	PushArray* hoge = NEW(PushArray);
	construct(hoge, 4);
	//初期化
	for (int i = 0; i < 4; i++){
		hoge->data[i] = 0;
	}
	//追加してみる
	for (int i = 1; i <= 5; i++){
		append(hoge, i);
	}
	//表示
	for (int i = 0; i < 4; i++){
		printf("%d\n", hoge->data[i]);
	}
	//出力
	//2
	//3
	//4
	//5
	dispose(hoge);
}
普段はC触らないので色んな言語の影響があるような気がします。
読めばわかるとは思いますが一応発想は確保した領域をずらせば押し出しを実現できるってところです。
でもそのまま領域をずらすのは無理なので新しく1つ多めに確保してコピーしてそこの最後に追加。で、元の領域はfreeして確保したのをずらして登録してます。
こういう実装の都合上配列の最後に追加するようになってますがまぁ大差はないですよね。
暇なのでゴリ押しした場合と比較してみます。
#define N 155
int main()
{
	PushArray* te = NEW(PushArray);
	construct(te, N);
	for (int i = 0; i < N; i++)
	{
		te->data[i] = 0;
	}

	clock_t start1 = clock();
	for (int i = 1; i <= 2000000; i++)
	{
		append(te, i);
	}
	clock_t end1 = clock();
	
	dispose(te);
	int hoge[N] = { 0 };

	clock_t start2 = clock();
	for (int i = 1; i <= 2000000; i++)
	{
		for (int j = N-2; 0 <= j; j--)
		{
			hoge[j+1] = hoge[j];
		}
		hoge[0] = i;
	}
	clock_t end2 = clock();

	printf("duration:%f\n", (double)(end1-start1));
	printf("duration:%f\n", (double)(end2-start2));
	//出力(N=100)
	//duration:602.000000
	//duration:409.000000

	//出力(N=155)
	//duration:628.000000
	//duration:633.000000

	//出力(N=1000)
	//duration:1077.000000
	//duration:4023.000000

	//出力(N=10000)
	//duration:7743.000000
	//duration:40342.000000
}
ゴリ押しVerは配列の向きが逆ですが速さには関係ないはずです。
結果は私の環境で配列の長さが155辺りからポインタのほうが早くなっていく、だそうです。
メモリの確保、コピーが遅いんでしょうか。でもmemcpyとかなしでは実装できないですよね……。他にアルゴリズムあるのかな。
いい方法知ってる方は教えてください。

スポンサーサイト
  1. 2019/01/04(金) 17:39:33|
  2. EscapeR3記録
  3. Programming
  4. | コメント:0



                    

プロフィール

ちゃい

Author:ちゃい
1ヶ月広告を出さないように
のんびり更新していきます。
自分が後に思い出として振り返って
見るために書いてる所あるので
読みにくいかもです。

最新記事

最新コメント

年別アーカイブ一覧

カテゴリ

未分類 (7)
PC (17)
BlueStacks (4)
ゲーム (34)
艦これ (30)
電子工作 (2)
自転車 (13)
Android (6)
Programming (3)
スマホ (2)

カウンター

検索フォーム

リンク

このブログをリンクに追加する

ブロとも申請フォーム

この人とブロともになる

QRコード

QR