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

EvernoteのAPIをいじってみた

ちょっと諸事情でEvernoteのAPIを使ってあるJSONからデータを取り出してノートを作らないといけなくなりました。
そこでEvernoteAPIをPython3.6でいじって一部ハマったのでメモ。
参考
Evernote Pythonから画像つきノートを作成する時の注意点
PythonからEvernote APIを使う方法
EvernoteのAPIを使ってみる

pipでevernote3をinstallしてAPI keyの取得してActivateして。
Activateは1回送って5営業日でも連絡なかったので再送信して放置してたらいつの間にか来てました。(何日かは忘れた
ProductionだとDevTokenが
Update: the creation of developer tokens is temporarily disabled.
とかで取れなかったので仕方なくOAuth認証をしたんですがちょっとハマりました。
コールバックURLとかあるんですがWebアプリを作っているわけではないので困りました。
ちょっとスクリプト動かしたいだけなんですが……。
いろいろ試行錯誤の末コールバックURLには適当に"http://www.foo.com"とか入れて返ってきたURLをprintしてブラウザでアクセスして承認、で
"http://www.foo.com/?oauth_token=<ユーザー名>.<文字列>&oauth_verifier=<文字列>&sandbox_lnb=false"
みたいなURLに飛ばされるのでoauth_verifierの<文字列>をコピーしてinput()で渡してget_access_tokenでうまくいきました。
長いですね。コードにすると

request_token = client.get_request_token("http://www.foo.com")
redirect_url=client.get_authorize_url(request_token)
print(redirect_url)
verifier = input()
auth_token = client.get_access_token(request_token["oauth_token"], request_token["oauth_token_secret"], verifier)

みたいな感じです。
で、EvernoteClientをtoken=auth_token, sandbox=Falseで作ったら、後はsandboxでのコードのままです。
ノート作るのは参考URLのをコピペで動きます。まぁそれも公式ガイドのコピペみたいですがw

  1. 2018/12/05(水) 21:18:22|
  2. EscapeR3記録
  3. Programming
  4. | コメント:0

VisualStudio Community 2017 C#でまともにデバッグできないとき

症状としてはマイコード以外もデバッグ可能にしてたら
自動変数タブで
"ローカル変数または引数はこの命令ポインターで利用できないため、値を取得することはできません。最適化されている可能性があります。"
でほとんどのローカル変数の中身が見れない、ステップ実行しても訳わからん順番になる、でまともにデバッグできない。
マイコードのみデバッグを有効にしてたら
そもそもブレークポイントが有効にならず、"シンボルが読み込まれていない"みたいな事言われる。
プロジェクトプロパティ、ビルドタブDebug構成でコードの最適化チェック入れてないしPdbファイル作られてるし
探しても探しても解決できる情報見つからず1,2時間ひたすら調べてました。

結局デバッグのオプションのそれっぽいの色々いじってみて
"モジュールの読み込み中に JIT 最適化を抑制する"にチェック入れたら直りました。
なぜ最初からそのオプション有効になってないんだ…。
なんか結構昔にも同じようなことで沼ったような気がするのでメモしておきます。

  1. 2017/09/30(土) 22:36:21|
  2. EscapeR3記録
  3. Programming
  4. | コメント:0



                    

プロフィール

ちゃい

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

最新記事

最新コメント

年別アーカイブ一覧

カテゴリ

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

カウンター

検索フォーム

リンク

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

ブロとも申請フォーム

この人とブロともになる

QRコード

QR