teratail
回答率
85.48%
質問するログイン新規登録

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

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

新規登録して質問してみよう
ただいま回答率
85.48%
トップJavaScriptに関する質問
JavaScript

JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。

Q&A

6回答

5783閲覧

配列で特定位置の周囲の値を効率よく調べたい アルゴリズム

bakemon-gogogo
bakemon-gogogo

総合スコア14

JavaScript

JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。

1グッド

3クリップ

投稿2017/09/16 02:25

編集2017/09/16 14:30

1

3

JavaScriptを勉強している初心者です。
自分のスキルでは限界なのでどなたかご教授いただけないでしょうか。

###前提・実現したいこと
配列：10×10マス があり、下記の「◎」箇所にフラグが立ったら
次にその周囲、その次はそれのまた周囲…といったプログラムを作りたいのですが、
どのように書けば効率がよい（コードの簡潔さ・パフォーマンス）のか皆目見当がつきません・・・

何かアルゴリズムや効率の良い書き方をご存知の方、
どうかお知恵を貸してください。

よろしくお願いいたします。

###図解

◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◯◯◎◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯

   ↓↓↓↓

◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◯◎◎◎◯◯◯◯◯
◯◯◎◯◎◯◯◯◯◯
◯◯◎◎◎◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯

   ↓↓↓↓

◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◎◎◎◎◎◯◯◯◯
◯◎◯◯◯◎◯◯◯◯
◯◎◯◯◯◎◯◯◯◯
◯◎◯◯◯◎◯◯◯◯
◯◎◎◎◎◎◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯

###コード

下準備までで挫折してしまいました。
ここからどのようにして効率良く基準フラグの周囲、そのまた周囲を求めていけば良いのかがわかりません。。。

https://codepen.io/bakemon-gogogo/pen/zEvObR

html
1
2<!DOCTYPE html>
3<html lang="ja">
4<head>
5<meta charset="utf-8">
6<style>
7body {
8    text-align: center;
9    cursor: pointer;
10}
11div {
12    margin: 50px auto;
13    font-size: 30px;
14    letter-spacing: .5em;
15    user-select: none;
16}
17</style>
18<script>
19
20var map = [];
21var col = 10;    // マップ：列
22var row = 10;    // マップ：行
23var set = {
24    col: 5,    // 基準フラグの位置：6列目
25    row: 3    // 基準フラグの位置：4行目
26};
27var count = 0;
28var wrap; 
29
30// 初期化
31function init () {
32
33	// HTML出力枠 生成
34	wrap = document.createElement('div');
35	document.body.appendChild(wrap);
36
37	// 配列のマップ生成（縦×横：10マス）
38	for (var i=0; i<col; ++i) {
39	    map[i] = [];
40	    for (var j=0; j<row; ++j) {
41	    	map[i][j] = '◯';
42	    }
43	}
44
45	test(count);
46
47	// クリックイベント
48	window.addEventListener('click', function() { 
49		count = check('◎') ? (count + 1) : 0;
50		test(count);
51	});
52
53}
54
55// 基準フラグの周囲を調査
56function test (size) {
57
58	// 縦横最小・最大範囲4点を求める
59	var rect = {
60		xmin: set.row - size,
61		xmax: set.row + size,
62		ymin: set.col - size,
63		ymax: set.col + size
64	};
65
66	// マップ全体から基準フラグの周囲を走査
67	for (var i=0; i<col; ++i) {
68	    for (var j=0; j<row; ++j) {
69			
70			// 該当するマス目にフラグ付与
71	    	map[i][j] = ((j == rect.xmin || j == rect.xmax) && (rect.ymin <= i && i <= rect.ymax)) || ((i == rect.ymin || i == rect.ymax) && (rect.xmin <= j && j <= rect.xmax)) ? '◎' : '◯';
72
73	    }
74	}
75
76	draw();
77
78}
79
80// マップ全体からフラグを検索
81function check (string) {
82
83	for(var i in map){
84	    for(var j in map[i]){
85	    	if (map[i][j] == string) {
86	    		return true;
87	    		break;
88	    	}
89	    }
90	}
91	return false;
92
93}
94
95// HTMLに描画
96function draw () {
97
98	var html = '';
99
100	for (var i=0, l=map.length; i<l; ++i) {
101	    for (var j=0, m=map[i].length; j<m; ++j) {
102	    	html += map[i][j];
103	    }
104	    html += '<br>';
105	}
106
107	wrap.innerHTML = html;
108
109}
110
111document.addEventListener('DOMContentLoaded', init);
112
113</script>
114</head><body></body></html>
115
116
manzyunが👍を押しています

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

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

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

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

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

kei344
kei344

2017/09/16 02:30

ご自身で書かれたコードを質問文に追記されたほうが回答を得られやすいと思います。
Lhankor_Mhy
Lhankor_Mhy

2017/09/16 03:02

補足願います。『どのように書けば効率がよいのか』←この場合の効率とは、計算量と考えてよいですか？　また、どの程度の効率のコードをお求めなのか不明ですので、効率がよくないコードの例をご提示いただけますか？
bakemon-gogogo
bakemon-gogogo

2017/09/16 03:11

言葉足らずで申し訳ありません。『どのように書けば効率がよいのか』というのは議題のような場合、方程式なるものがあるのかなと思い、「効率的なコード＝アルゴリズム」と記載いたしました。コード例を掲載できればよいのですが、どのように求めるのかも皆目検討がつかない状況でして・・・。
退会済みユーザー

退会済みユーザー

2017/09/16 04:15

丸投げですね。。。高々25の項の調査なので、べた書きでも良いです。まず、それが書けてからかと。
bakemon-gogogo
bakemon-gogogo

2017/09/16 04:20 編集

@te2ji さん すみません。。自分なりにもう少し考えてコード書いてみます。
退会済みユーザー

退会済みユーザー

2017/09/16 04:32

ちなみにですが、今のままだと「何を調査するのか？」「配列はどのようなフォーマットか？」等の仕様が明確でないので、コードの提示をすることは出来ません。そのあたりも考慮したご自身のコードがあれば、回答がつきやすいかと。
guest

回答6件

0

渦を描くアルゴリズム

下記スレッドを想起させる質問ですね。

起点となる座標を一つ設定し、時計回り/反時計回りに周回すれば効率よく走査できます。
例えば、X座標/Y座標をそれぞれ -N (※N は自然数) すれば、左下の起点を求める事が可能です。

(2017/09/17 12:30追記)
「左上の起点」と書いていましたが、正しくは「左下の起点」でしたので、訂正しました。

処理効率

時計回り/反時計回りに周回するようにループ走査した方が処理効率やパフォーマンスとして優れているという理解であっておりますか？

処理効率は何かのコードと比較して出るものなので、漠然と優れていると判断する事は出来ません。
処理効率を考える時には、はコードではなく、アルゴリズムで考えてみて下さい。

例えば、Lhankor_Mhyさんのコードは配列全体を検索して反転座標を見つけるものでした。100個の座標があれば、100回の処理を行います。
私が提案した渦を描くコードは起点となる座標を求めてから渦を描くように反転座標を求めるコードでした。目的の座標から1マスずれた座標を求めるとするなら、8回の処理を行います。
つまり、単純計算でも「8/100」の時間で完了するわけです。

te2jiさんのコードは目的の座標から起点となる反転座標を求め、上辺/下辺を描いた後に、右辺/左辺を描くコードでした。
私のコードはループ処理が4回ありますが、te2jiさんのコードはループ処理が2回で済みます。
ただし、te2jiさんのコードは次のようになりますが、

  1. 「目的の座標」から「反転座標」を求めて、反転座標の配列を返す
  2. 反転座標の配列を Array#forEach で反復処理し、各座標を反転させる

効率特化で考えるなら、反転座標の配列を返す処理は省くことが可能で、即座に反転処理させる事で効率を向上させることが出来ます。
効率化は「無駄を省くこと」なので、他にも省略出来る処理がないか探してみることをお勧めします。

最終的にはベンチマークを取ることが大切で、自分の想定と異なる結果が返ってきたなら、アルゴリズムを見直してくる事で見えてくるものもあります。

配列を生成しないコード

前述の「処理効率」の下りでは、Lhankor_Mhyさんのコードの効率が悪いニュアンスで説明しましたが、配列の生成する事を踏まえるとそれ程、悪い実装でもありません。
いずれにしても、真っ白なキャンバス(配列)を作る前提であれば、配列を生成するタイミングで文字を初期化すれば、配列全体の走査が1回で済むと考える事も出来ます。

(A) Lhankor_Mhyさんの発想

  1. 配列を作りながら、「〇」「◎」を代入していく
  2. 配列全体を走査し、文字列化する

(B) te2ji さんの発想

  1. 配列を作りながら、ビット列を代入していく
  2. 配列を部分的を走査し、「◎」を代入する
  3. 配列全体を走査し、文字列化する

(A) は (B) よりも処理工数が少なく、効率が良いことが分かります。

ところで、どちらも「二次元配列を生成→二次元配列を文字列化」の手順を踏んでいますが、そもそも、二次元配列を生成する必要はあるでしょうか。
「初めから文字列を生成すればよいのでは」という発想で書いたのが次のコードです。

配列を作る過程がなく、条件を元に文字列を生成していくので、原理上は効率が良いはずです。

ベンチマーク

次の環境において、「キャンバスサイズの最大値: 1010 (※1)」「繰り返し回数: 1000回」の設定値でベンチマークを実行してみました。

名前値
OSWindows 10 Home 64bit
BrowserGoogle Chrome 60.0.3112.113

(※1) テキストボックス入力値は「1000」ですが、関数 benchmark の処理で +10 しています。0x0のキャンバスでは有効値が取れないと思われる為の措置です。
(※2) ベンチマーク処理の都合上、引数の順番等の処理を一部変更しています。特に、raccyさんのコードは設計思想が大きく異なり、rect サイズを指定する為に追加処理を入れています。

回数think49Lhankor_Mhy(初版)te2ji(type1 初版)raccy
1回目10.128173828125ms39301.115966796875ms測定不能(エラー)125472.5986328125ms
2回目1.7138671875ms36288.373779296875ms測定不能(エラー)124575.38696289062ms
3回目1.626953125ms35011.963623046875ms測定不能(エラー)125737.03271484375ms
4回目2.990966796875ms36570.126953125ms測定不能(エラー)131851.31713867188ms
5回目1.56005859375ms39585.26806640625ms測定不能(エラー)128274.21826171875ms

前述の通り、配列を介在せずに直接文字列を生成している為、高速になっているものと思われます。
それから、行単位、列単位で処理を分ける事でまとめて処理を行う工夫もしています。
例えば、次のマップを生成する場合、

〇〇〇〇〇〇〇〇〇〇
〇〇〇〇〇〇〇〇〇〇
〇〇〇〇〇〇〇〇〇〇
〇〇〇◎◎◎〇〇〇〇
〇〇〇◎〇◎〇〇〇〇
〇〇〇◎◎◎〇〇〇〇
〇〇〇〇〇〇〇〇〇〇
〇〇〇〇〇〇〇〇〇〇
〇〇〇〇〇〇〇〇〇〇
〇〇〇〇〇〇〇〇〇〇

まず、種別に行単位で区分けします。

〇〇〇〇〇〇〇〇〇〇
〇〇〇〇〇〇〇〇〇〇
〇〇〇〇〇〇〇〇〇〇
　　　　　＋
〇〇〇◎◎◎〇〇〇〇
　　　　　＋
〇〇〇◎〇◎〇〇〇〇
　　　　　＋
〇〇〇◎◎◎〇〇〇〇
　　　　　＋
〇〇〇〇〇〇〇〇〇〇
〇〇〇〇〇〇〇〇〇〇
〇〇〇〇〇〇〇〇〇〇
〇〇〇〇〇〇〇〇〇〇

先頭の3行と末尾の4行は「〇」か「◎」かを判断する必要はない為、「〇〇〇〇〇〇〇〇〇〇\n」を整数倍した文字列を生成して処理を終えます。
「〇〇〇◎◎◎〇〇〇〇」は「〇〇〇 + ◎◎◎ + 〇〇〇〇」のように3つのブロックに分解してやり、「〇 x 3 の文字列」「◎ x 3 の文字列」「〇 x 4 の文字列」を各々生成して連結します。
続く行も同様で「〇〇〇 + ◎ + 〇 + ◎ + 〇〇〇〇」のように分解して文字列を生成→連結を繰り返します。
なお、文字列の生成には、ES2017 規定の String.prototype.padStart, String.prototype.padEnd を利用しており、一般的な繰り返し構文(for, forEach, for-of 等)を使用していない事も高速化に貢献しているかもしれません。
(padStart, padEnd は IE11- 対策で Polyfill を適用してやります)。

te2ji(type1), te2ji(type2) のコードは生成される文字列は一致せず、te2ji(type1) ではベンチマークを実行する事も出来ませんでしたので、ここでは比較対象が意図しました。
しかし、Lhankor_Mhyさんとte2jiさんのコード比較は気になったので、コードを修正して、ベンチマークをとってみました(次節参照)。

raccyさんのコードが著しく遅いのは、単純に処理ステップが多いためだと思われます。

  • コンストラクタ呼び出し
  • [[Prototype]] のプロパティ参照
  • 分割代入
  • 「コンストラクタ呼び出し(マップ初期化) -> listByDistance -> offMap(マップ全体のフラグ初期化) -> onMap(該当座標のフラグ書き換え) -> join(文字列化)」で合計5回の処理
  • map[y][x].flag で合計3回のプロパティ参照コスト(2次元配列より1回多い)

これだけ処理量が多ければ、遅いのは致し方ありません。

ベンチマーク(2回目)

回数Lhankor_Mhy(初版)Lhankor_Mhy(改訂版1)Lhankor_Mhy(改訂版2)Lhankor_Mhy(改訂版3)te2ji(type1 改訂版1)
1回目39301.115966796875ms12114.286865234375ms12167.263916015625ms13070.504150390625ms17185.240966796875ms
2回目36288.373779296875ms12250.916015625ms12209.571044921875ms13132.1572265625ms16331.541259765625ms
3回目35011.963623046875ms12381.442138671875ms12042.466064453125ms13132.1572265625ms17234.682861328125ms
4回目36570.126953125ms12274.921142578125ms12375.59814453125ms12552.7861328125ms131851.31713867188ms
5回目39585.26806640625ms12051.870849609375ms12160.140869140625ms13023.833984375ms17187.80712890625ms

概ね、「Lhankor_Mhy(改訂版2) > Lhankor_Mhy(改訂版1) > Lhankor_Mhy(改訂版3) > te2ji(type1 改訂版1) > Lhankor_Mhy(初版)」の結果となりました。

Lhankor_Mhy(初版)

  1. Array() で配列を生成
  2. Spread要素で配列を展開(Array() では length プロパティのみの初期化でキーが存在しない為、Array#map で走査出来ません。キーを生成する為にSpread要素で初期化しています。)
  3. Array#map で値を初期化

Lhankor_Mhy(改訂版1)、(改訂版2)

※(改訂版2) は x, y の最小値/最大値を事前に変数にキャッシュしておく

  1. while x 2 で二次元配列を生成し、条件判断で「〇」「◎」を格納していく
  2. 即座に join() して文字列化

Lhankor_Mhy(改訂版3)

  1. 条件を元に「◎」を代入する座標をキャッシュしておく
  2. while x 2 で二次元配列を生成し、条件判断で「〇」「◎」を格納していく
  3. 即座に join() して文字列化

te2ji(type1 改訂版1)

  1. while x 2 で二次元配列を生成し、「〇」で初期化
  2. 配列全体を検索し、条件判断で「〇」「◎」を格納していく
  3. 配列を行検索し、joinで文字列化

実際のところ、te2ji(type1 改訂版1)はLhankor_Mhy(改訂版2)のコードを関数単位で分割しただけなので、どうやってもLhankor_Mhy(改訂版2)に勝てません。
te2ji(type1 改訂版1)のコードをオブジェクト指向で書き直したのがraccyさんのコードともいえます。
ただ、パフォーマンスの観点から見ると、raccyさんのコードには改善の余地があると思います。

まとめ

活用したテクニックをまとめると、次のようになります。

  • 同じプロパティを何度も参照する時には変数にキャッシュする
  • 繰り返し回数を減らす(まとめて処理できるなら、そうする)
  • 配列やオブジェクトのプロパティ参照回数を減らす
  • 配列やオブジェクトの生成回数を減らす
  • if文の条件判定の通過回数を減らす(場合によっては、ネストした方が速い)

更新履歴

  • 2017/09/17 12:30 「左上の起点」を「左下の起点」に修正。「処理効率」の節を追記。
  • 2017/09/20 05:53 「配列を生成しないコード」「ベンチマーク」の節を追記。
  • 2017/09/20 14:12 「ベンチマーク」の節でミスが発覚したので一時取り下げ。
  • 2017/09/20 20:22 「ベンチマーク」の節を書き直し。「ベンチマーク(2回目)」「まとめ」を追加。

Re: bakemon-gogogo さん

投稿2017/09/16 11:37

編集2017/09/20 11:23
think49
think49

総合スコア18162

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

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

bakemon-gogogo
bakemon-gogogo

2017/09/16 13:53 編集

@think49 さん ありがとうございます！ いただいたサンプルでいうと、まず起点を決めて上辺→右辺→下辺→左辺の順に走査するということでしょうか？ プログラミング自体、初心者でして基本的な質問になってしまうかもしれませんが… 時計回り/反時計回りに周回するようにループ走査した方が処理効率やパフォーマンスとして優れている という理解であっておりますか？
think49
think49

2017/09/17 03:34

親記事に追記しました。 コーディングする時には、「アルゴリズムを考える→コードを書く」の手順で行うことをお勧めします。 効率化する時にも同様で優れたアルゴリズムは無駄が少ないものです。 アルゴリズムには特別な技能は必要ないので、「1. ～を行う」「2. ～を行う」のように序列リストで手順化する事で無駄を見つけることが出来ます。
bakemon-gogogo
bakemon-gogogo

2017/09/17 05:12

@think49 さん ご丁寧に補足いただきありがとうございます！ 考え方やコーディングする際のフローなどとても勉強になりました。 > 最終的にはベンチマークを取ることが大切で、自分の想定と異なる結果が返ってきたなら、 > アルゴリズムを見直してくる事で見えてくるものもあります。 think49さん、te2jiさん、Lhankor_Mhyさんにご教示いただいたロジックでベンチマークを取って試してみたいと思います。
think49
think49

2017/09/18 08:09

効率について、もう一つ。 Array#filter や Array#map は新しい配列を生成して返すという特徴があります。 ある配列を別のフォーマットに変換する動作は、配列全体を検索する必要があります。 構造上、配列全体を1回は走査しなければなりませんが、配列全体を走査する回数が2回、3回と増えれば、比例して時間がかかってしまうわけです。 その上、別のフォーマットに変換するとなれば、新しいオブジェクトを生成するコストがかかります。 この過程を省略出来れば、効率は大きく上昇します。 今、別の発想でコードを書いていますが、少し時間がかかりそうです。
think49
think49

2017/09/19 21:54

親記事に追記しました。
退会済みユーザー

退会済みユーザー

2017/09/19 23:33

te2ji(type2)は、桁あふれちゃうんじゃないですかねぇ。 ちゃんと見てないですけど、オリジナルは桁あふれたら、まともに動きません＾＾；
think49
think49

2017/09/20 03:53

To: te2ji さん 昨夜(今朝)はベンチマークだけで力尽きました。 しかし、何故そんな他人事のように…。
退会済みユーザー

退会済みユーザー

2017/09/20 04:11

残念ながら、私のスキルではあれぐらいが限界で＾＾； ２つの私の回答は、晒すには恥ずかしいレベルですが、まぁ概念は伝わるかなぁって感じのサンプルです。 ベンチマークは想定外だったんで、コメントししました。 (type2)のオリジナルは、他にもいろいろヤバイので、実用というよりは、概念を追いかける材料ぐらいにしか使えないです。。。
think49
think49

2017/09/20 05:36

テストしたところ、think49, te2ji(type1), te2ji(type2) でエラーとなりました。 他人の指摘をしている場合ではなかったですね…。 取り急ぎ、v1.0.1で修正しました(要Git Hub参照)。 ベンチマーク結果は変わっていなくてほっとしました。
think49
think49

2017/09/20 11:24

親記事を編集しました。 To: te2ji さん ご希望のものに近いかわかりませんが、(type1) は修正しておきました。
退会済みユーザー

退会済みユーザー

2017/09/20 13:52

修正、ありがとうございます。 今ちょっと時間が取れないので、後日になりますが勉強させていただきます。
guest

0

Lhankor_Mhy さんの言うとおり、まだ BA つけないほうが良いかと。。。
Lhankor_Mhy さんの回答は、配列の全部を走査しているので、効率を求めたというよりは、入力と出力を要件として成立させたサンプル回答だと思います。

効率を求めるのであれば、
・rectSize によって決定される、反転座標の配列を作成
・反転座標の配列を元に入力値にその座標があれば、反転させる
といった操作になると思います。

JavaScript は得意でないので、回答としてコードが書けないのが残念ですが、他にもやり方や書き方がある質問だと思いますよ。

追記
上記の処理を書いてみましたが、php からの移植なので、JavaScript っぽくないです。
あと変数名等、ルールが色々おかしいですが、処理の参考になれば幸いです。

JavaScript
1var map = [];
2var col = 10;    // マップ：列
3var row = 10;    // マップ：行
4var set = {
5    col: 5,    // 基準フラグの位置：6列目
6    row: 3    // 基準フラグの位置：4行目
7};
8
9for (var i=0; i<col; ++i) {
10    map[i] = [];
11    for (var j=0; j<row; ++j) {
12        map[i][j] = '◯';
13    }
14}
15
16function test_array(centerX, centerY, rectSize){
17    let test_array = [];
18    let size_x = rectSize * 2 + 1;
19    for(var i = 0; i < size_x ; ++i) {
20        test_array.push([centerX-rectSize+i, centerY-rectSize]); 
21        test_array.push([centerX-rectSize+i, centerY+rectSize]);
22    }
23    let size_y = rectSize * 2 - 1;
24    for(var j = 0; j < size_y ; ++j) {
25        test_array.push([centerX-rectSize, centerY-rectSize+j+1]); 
26        test_array.push([centerX+rectSize, centerY-rectSize+j+1]);
27    }
28    return test_array;
29}
30function array_reverse(map,arr,size){
31    arr.forEach(function(val){
32        if(val[0] >= 0 && val[0] < size[0] && val[1] >= 0 && val[1] < size[1]){
33            map[val[0]][val[1]] = map[val[0]][val[1]] === '◯' ? '◎' : '◯';
34        }
35    })
36    return map;
37}
38
39arr = test_array(set.col, set.row, 3);//ここの第三引数が反転箇所の半径
40result = array_reverse(map,arr,[col,row]);
41console.log(result);

書いてみて気がついたのですが、反転処理を分ける必要ないですね。。。
test_array の中でやってしまってかまわない気がします。

投稿2017/09/16 08:05

編集2017/09/17 15:43
退会済みユーザー

退会済みユーザー

総合スコア0

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

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

退会済みユーザー

退会済みユーザー

2017/09/16 08:08

他にも2進数で、フラグ操作するとかもあると思います。
bakemon-gogogo
bakemon-gogogo

2017/09/16 08:10

@te2ji さん 今日から勉強の一環で本サービス利用しており、BAつけるタイミングなど理解できておらず恐縮です…
bakemon-gogogo
bakemon-gogogo

2017/09/16 10:52 編集

@te2ji さん ご回答いただきありがとうございます！ > 効率を求めるのであれば、 > ・rectSize によって決定される、反転座標の配列を作成 > ・反転座標の配列を元に入力値にその座標があれば、反転させる > といった操作になると思います。 上記ですが、理解できず申し訳ないのですが… もう少し掘り下げると下記のような解釈でしょうか？ 現状は、Array[0][0] 〜 Array[9][9]まで配列の全てを走査していますが、 図解でいう、6列目・4行目（Array[5][3]）を始点としてそこから rectSize の間に限定した配列を別途用意し判定、 その後上記の判定結果を本配列と同様の箇所と差し替える？ という理解であっておりますでしょうか。
退会済みユーザー

退会済みユーザー

2017/09/16 11:14

伝わりにくかったようなのでコードにしてみました。 どちらかと言うと、ツッコミどころ満載のコードで恐縮ですが、処理が伝われば幸いです。
bakemon-gogogo
bakemon-gogogo

2017/09/16 13:48 編集

@te2ji さん 結論としては、forEachで重複して走査処理を回すことになるので、反転処理を分ける必要がないということでしょうか？ ご丁寧にサンプルコードも記載いただきありがとうございます！
退会済みユーザー

退会済みユーザー

2017/09/16 13:59

> if(val[0] >= 0 && val[0] < size[0] && val[1] >= 0 && val[1] < size[1]) php 脳では配列の存在確認で分かりやすい条件が書けると思っていたのですが、JavaScript での書き方がわからなかったため、かなり汚い書き方になりました。 ので、こんな条件書くぐらいだったら統合しちゃえ。って意味です。 コードとしてはかなり汚いので、ざっと流れが追えれば、いいかな。ぐらいで見てください。正直、回答として晒しているのがかなり恥ずかしいです。。。
bakemon-gogogo
bakemon-gogogo

2017/09/16 14:12 編集

いえ、とんでもないです、プログラム自体が初心者で勉強中の身ですので、とても参考になります！ ご教示くださったコードを詳しく見て理解したいと思います。
bakemon-gogogo
bakemon-gogogo

2017/09/16 14:23

@te2ji さん ご教示いただいたコードを詳しく見てみたのですが、test_array[0][0]からの走査は同じですが、範囲の右下のマスまでの範囲までで走査し、その後forEachでフラグの反転処理を行っている という理解であっておりますか？ 度々の質問になり恐縮です。。
退会済みユーザー

退会済みユーザー

2017/09/17 15:44 編集

全体の走査はしていないです。 コードの概要は、以下の通り。 test_array の２つの for で反転すべき配列を作っています。 ◎◎◎◎◎ ◎○○○◎ ◎○○○◎ ◎○○○◎ ◎◎◎◎◎ 最初の for が四角形の上下（◎◎◎◎◎） 2つ目の for が四角形の左右の配列を作っています。(◎○○○◎) arr = test_array(set.col, set.row, 3); console.log(arr)； とでもしてやると分かりやすいです。 array_reverse では、反転すべき配列の入った arr を forEach しています。 まず、map 範囲内か確認した後、map の arr 座標を反転します。 forEach するのは arr なので、全体を走査することはありません。
bakemon-gogogo
bakemon-gogogo

2017/09/16 14:42

@te2ji さん ご丁寧に補足いただきありがとうございます！ ようやく理解できました。すごく効率が良さそう（初心者目線ですが…）です、ありがとうございます！
bakemon-gogogo
bakemon-gogogo

2017/09/16 15:30 編集

@te2ji さん > 他にも2進数で、フラグ操作するとかもあると思います。 上記ですが、 プログラミングを始めたばかりで引き出しが少なすぎるのと、 色々な書き方の引き出しを増やしたいのですが、参考書籍を見ていても一つの書き方・ロジックしか書いておらず・・・ 大変申し上げにくいのですが、サンプルコードをお願いできないでしょうか？ 勿論差し支え無ければです。。
退会済みユーザー

退会済みユーザー

2017/09/17 06:15

> 他にも2進数で、フラグ操作するとかもあると思います。 初心者向けの参考書には載ってない気がするなぁ。。。 あんまりきれいなコードで書ける気がしないですが、あとでやってみます。 ただ、こういうのは、きれいなコードで見ないと、理解しづらいかも。 あと、今更ですが、今回の回答のコード、console.log で出力すると、x,y が入れ替わっちゃうので、感覚的にわかりにくいですね＾＾； 修正はしませんので、読み替えてくださいｗ
退会済みユーザー

退会済みユーザー

2017/09/17 15:45

関数にスペルミスが有ったので、修正しました。
think49
think49

2017/09/19 22:12 編集

こちらも ReferenceError があったので修正。 ついでに、縦横反転の問題に対処しておきました。 グローバル変数を廃止し、関数の引数で設定値を受け取るようにすると汎用性が上がると思います。 https://jsfiddle.net/bwzw4ds4/5/
退会済みユーザー

退会済みユーザー

2017/09/19 23:25

ありがとうございます＾＾
guest

0

javascript
1function test(centerX, centerY, rectSize, fieldSize){
2  return [...(function* (y){
3    while (y<fieldSize){          
4      yield [...(function* (x){
5        while (x<fieldSize) {
6          yield (
7            ( y == (centerY - rectSize) || y == (centerY + rectSize) ) && (centerX - rectSize) <= x && x <= (centerX + rectSize)
8            ||
9            ( x == (centerX - rectSize) || x == (centerX + rectSize) ) && (centerY - rectSize) <= y && y <= (centerY + rectSize)            
10          );
11          x++;
12        }
13      })(0)];
14      y++;
15    }
16  })(0)]
17}
18
19test(3,5,0,10);
20/*
210000000000
220000000000
230000000000
240000000000
250000000000
260001000000
270000000000
280000000000
290000000000
300000000000
31*/
32
33test(3,5,1,10);
34/*
350000000000
360000000000
370000000000
380000000000
390011100000
400010100000
410011100000
420000000000
430000000000
440000000000
45*/
46
47test(3,5,2,10);
48/*
490000000000
500000000000
510000000000
520111110000
530100010000
540100010000
550100010000
560111110000
570000000000
580000000000
59*/
60//出力結果は見易さのため加工しています。

かっこつけてイテレータを使ってみたものの、普通にmapメソッドを使った方が読みやすいですねえ……

javascript
1function test(centerX, centerY, rectSize, fieldSize){
2  return [...Array(fieldSize)].map( (_, y) => 
3    [...Array(fieldSize)].map( (_, x) => 
4      ( y == (centerY - rectSize) || y == (centerY + rectSize) ) && (centerX - rectSize) <= x && x <= (centerX + rectSize)
5      ||
6      ( x == (centerX - rectSize) || x == (centerX + rectSize) ) && (centerY - rectSize) <= y && y <= (centerY + rectSize)            
7    )
8  );
9}

投稿2017/09/16 05:45

編集2017/09/16 05:53
Lhankor_Mhy
Lhankor_Mhy

総合スコア36100

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

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

bakemon-gogogo
bakemon-gogogo

2017/09/16 06:12

@Lhankor_Mhyさん　ありがとうございます！自分なりに途中までですが…コードを修正してみましたが、やはり上手くできませんでした。。　まだJavaScript初心者で勉強しておりまして、なんだか見たこともない文法ですが、ES2015というものでしょうか？
Lhankor_Mhy
Lhankor_Mhy

2017/09/16 06:31

解決していないならBAにしないほうがいいのでは…… > ES2015というものでしょうか？ そのとおりですが、ここでのキモは ( y == (centerY - rectSize) || y == (centerY + rectSize) ) && (centerX - rectSize) <= x && x <= (centerX + rectSize) || ( x == (centerX - rectSize) || x == (centerX + rectSize) ) && (centerY - rectSize) <= y && y <= (centerY + rectSize) この部分でして、極一般的な真偽値を返す論理式です。
bakemon-gogogo
bakemon-gogogo

2017/09/16 06:54

@Lhankor_Mhyさん ご回答ありがとうございます！ 今日から勉強の一環で本サービス利用しており、理解できておらず恐縮です… ご回答いただいたコードの解釈ですが、 Y軸が基準点から四角形（半径）の範囲に該当する、且つ四角形の範囲内のX軸の場合はtrue、 または X軸が基準点から四角形（半径）の範囲に該当する、且つ四角形の範囲内のY軸の場合はtrue、 であっておりますでしょうか？
Lhankor_Mhy
Lhankor_Mhy

2017/09/16 07:03

おっしゃるとおりです。 それで、「その周囲」にあたる座標にはtrueを返せると思うのですが、いかがでしょうか。 回答のコードは、配列の全範囲をなめて、それぞれその論理式の値を返しているだけです。もちろん、2重for文で書き直すことも可能です。
bakemon-gogogo
bakemon-gogogo

2017/09/16 07:07

@Lhankor_Mhyさん 理解できました。ご教授いただいたコードを参考に再度チャレンジしてみます。 ご丁寧に回答いただきありがとうございました！
guest

0

te2jiさんの「2進数のフラグマップ」というアイディアで書いてみました。

javascript
1function test(centerX, centerY, rectSize, fieldSize){
2  const makeRectRow = x => ( 2**( x*2+1 ) - 1 )
3  const rectRowShift = (n, x) => x > 0 ? n << x : n >>> -x;
4
5  let borderRow = makeRectRow(rectSize); // 一番上と一番下の行
6  const interRow = rectRowShift( borderRow ^ ( makeRectRow(rectSize-1) << 1 ), centerX-rectSize); // 中の行
7 
8  borderRow = rectRowShift(borderRow, centerX-rectSize);
9  
10  return [...Array(fieldSize)].map( (_, y) => {
11    if ( (centerY - rectSize) <= y && y <= (centerY + rectSize) ) {
12      if ( (centerY - rectSize) == y || y == (centerY + rectSize) ) return borderRow;
13      return interRow;
14    }
15    return 0;
16  });
17}
18
19test(3,5,2,10).map(e=>[...Array(10)].map((_,i)=>'◯◎'[e>>>i&1]).join(''));
20
21
22/*
23◯◯◯◯◯◯◯◯◯◯
24◯◯◯◯◯◯◯◯◯◯
25◯◯◯◯◯◯◯◯◯◯
26◯◎◎◎◎◎◯◯◯◯
27◯◎◯◯◯◎◯◯◯◯
28◯◎◯◯◯◎◯◯◯◯
29◯◎◯◯◯◎◯◯◯◯
30◯◎◎◎◎◎◯◯◯◯
31◯◯◯◯◯◯◯◯◯◯
32◯◯◯◯◯◯◯◯◯◯
33*/

まあまあ速いんじゃないかと思うんですが、悲しいかな32マスまでしか使えないので、処理速度が重要になる大きなデータでは使えないという……

投稿2017/09/20 12:18

Lhankor_Mhy
Lhankor_Mhy

総合スコア36100

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

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

think49
think49

2017/09/20 12:50 編集

> 悲しいかな32マスまでしか使えないので ビット演算子を使わなければ、Number.MAX_SAFE_INTEGER.toString(2).length === 53 なので、53マスまでは対応可能…・。 それでも少ないので、32もしくは53bit単位で分割管理するか、フラグマップを文字列で持つ手段が考えられますね。 ただ、実際のところ、必要なビット列のほとんどは「11111111111」と「10000000001」なので、一つの行を生成できれば複製して使いまわす方が手っ取り早いという事情があります。
think49
think49

2017/09/20 13:03

ふと思ったのですが、この方式の場合、1のマス目だけ2進数で覚えておけば、0のマス目は記録しておく必要がないですね。 例えば、Lhankor_Mhy さんが書いたコードの場合、 ◎◎◎◎◎ ◎◯◯◯◎ ◎◯◯◯◎ ◎◯◯◯◎ ◎◎◎◎◎ この部分だけ2進数でフラグマップを作成し、このRectがある座標を記録しておきます。 文字列化する際には上下左右を〇で埋めてやれば、完成します。 33マス以上のフィールドには33マス以上のマス目が存在する可能性がある為、この手法をもってしても32bitを分割管理する等の対策が必要ですが、パフォーマンスは稼げる考え方のように思いました。
退会済みユーザー

退会済みユーザー

2017/09/20 13:50

恥ずかしがりながらも書いてみるもんですね。 今ちょっと時間がないので、後日改めて勉強させていただきます！ ありがとうございます。
Lhankor_Mhy
Lhankor_Mhy

2017/09/21 01:31

> think49さん その考え方は私も思いついたのですが、境界処理とかが面倒になって投げてしまいました（ｗ 　 この質問、当初はUnityタグとかがついていましたので、おそらくゲームに用いたいんだと思ってました。 そうだとすると、おそらく各種処理で参照を行うだろうと思うので、どう処理すればパフォーマンスが向上するのか、について不明な点が多すぎるんですよね…… 　 　 > te2jiさん あまりきれいなコードではないと思うのでお目汚しですが…… 　
guest

0

発想を変えてみました。まず、2次元配列には(プリミティブではない)Objectを置くようにします。そして、最初の初期処理で、距離毎にまとめた配列の配列を別途作成します。カウントが進むときは

  • 前の距離の配列に含まれるオブジェクトはフラグを無効
  • 次の距離に配列に含まれるオブジェクトはフラグを有効

とすることで、最低限のObjectだけ見に行って、フラグの変更処理が実行されます。初期処理は遅くなりますが、カウントアップでは既存の配列の順次処理だけであり、余計な分岐も少なくて済むのでは無いかと思います。

CoffeeScript2で実装してみました。

CoffeeScript
1class Rect
2  constructor: ({@x, @y, size, @width = size, @height = size}) ->
3    @map = ({flag: false, x: x, y: y} for x in [0...@width] \
4        for y in [0...@height])
5    @listByDistance = []
6    for x in [0...@width]
7      for y in [0...@height]
8        distance = Math.max(Math.abs(@x - x), Math.abs(@y - y))
9        @listByDistance[distance] ?= []
10        @listByDistance[distance].push(@map[y][x])
11    @count = 0
12    @onMap()
13
14  countUp: ->
15    @offMap()
16    @count++
17    @onMap()
18
19  onMap: ->
20    return 0 unless @listByDistance[@count]?
21    (point.flag = true for point in @listByDistance[@count]).length
22
23
24  offMap: ->
25    return 0 unless @listByDistance[@count]?
26    (point.flag = false for point in @listByDistance[@count]).length
27
28  reset: ->
29    @offMap()
30    @count = 0
31    @onMap()
32
33  join: ({tStr = 't', fStr = 'f', colSep = '', rowSep = '\n'}) ->
34    (((if point.flag then tStr else fStr) for point in row).join(colSep) \
35        for row in @map).join(rowSep)
36
37rect = new Rect({x: 3, y: 5, size: 10})
38wrap = document.createElement('div')
39document.body.appendChild(wrap)
40render = ->
41  wrap.innerHTML = rect.join({tStr: '◎', fStr: '○', rowSep: '<br>'})
42prevNum = 0
43window.addEventListener 'click', ->
44  prevNum = if prevNum == 0
45    rect.reset()
46  else
47    rect.countUp()
48  render()

CoffeeScript2 -> ES2015+ -> ES5に変換したコードについては下記で確認してください。

https://codepen.io/anon/pen/jGbZRr

欠点として、Objectの数が多くなるためメモリを消費することがあります。速度については、Objectへの変更や参照がどれぐらいになるか次第のため、実測しないとわからないところがあります。

投稿2017/09/17 16:17

raccy
raccy

総合スコア21735

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

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

0

ゴッチャになるので、回答を分けます。
コメントも入れているので、確認してみてください。

条件分けが思ったより面倒くさかったです＾＾；

JavaScript
1var map = [];
2var col = 10;    // マップ：列
3var row = 10;    // マップ：行
4var rectSize = 3;    // 半径
5var set = {
6    col: 5,    // 基準フラグの位置：6列目
7    row: 3,    // 基準フラグの位置：4行目
8};
9
10for (var i=0; i<row; ++i) {
11    map[i] = 0;
12    // map[i] = Math.floor( Math.random() * Math.pow(2, row));
13}
14
15function view(map,col,row){//map表示用の関数。ロジックとはあまり関係ないです。
16    let result = [];
17    let tmp = [];
18    for (var j = 0; j < row; ++j) {
19        result[j] = '';
20        tmp[j] = (Array(col).join('0') + map[j].toString(2)).slice(-col);
21        let n = tmp[j].length;
22        for (var k = 0; k < n; ++k) {//左上を(0,0)とするための処置。ひっくり返してます。
23            result[j] = result[j] + tmp[j][n - k - 1];
24        }
25        result[j] = result[j].replace(/0/g,'●').replace(/1/g,'○')//文字サイズを揃えるため、○と●に変更しました。
26    }
27    return result;
28}
29
30function test_array(map, set, rectSize, col, row){
31    let result_array = [];
32    centerX = set.col;
33    centerY = set.row;
34    console.log(centerX - rectSize,centerX + rectSize)
35    if(centerX - rectSize < 0 && centerX + rectSize > col){//ここの条件は、左上を(0,0)にするため、すべて左右が逆になっていることに注意
36        console.log('left right');
37        //上と下用のマスク用の数値
38        top_bottom = parseInt(Array(col + 1).join('1'), 2);
39        //左右用のマスク用の数値
40        left_right = 0;
41    } else if (centerX - rectSize < 0){
42        console.log('left',centerX + rectSize,col - (rectSize + centerX));
43        top_bottom = parseInt(Array(col - (centerX + rectSize + 2)).join('0') + Array(centerX + rectSize + 2).join('1'), 2);
44        left_right = parseInt(Array(col - (centerX + rectSize + 2)).join('0') + '1' + Array(centerX + rectSize + 1).join('0'), 2);
45    } else {
46        console.log('other');
47        top_bottom = parseInt(Array(centerX - rectSize).join('0') + Array((rectSize + 1) * 2).join('1') + Array(centerX - rectSize + 1).join('0'), 2);
48        left_right = parseInt(Array(centerX - rectSize).join('0') + '1' + Array((rectSize) * 2).join('0') + '1' + Array(centerX - rectSize + 1).join('0'), 2);
49    }
50    map.forEach(function(val, key){
51        if(key === centerY - rectSize || key === centerY + rectSize){//上下
52            result_array[key] = map[key] ^ top_bottom;
53        } else if(key > centerY - rectSize && key < centerY + rectSize){//左右
54            result_array[key] = map[key] ^ left_right;
55        } else {
56            result_array[key] = map[key] ^ 0;//関係ないところ
57        }
58    })
59    return result_array;
60}
61console.log(view(test_array(map, set, rectSize, col, row),col,row));

投稿2017/09/17 11:23

退会済みユーザー

退会済みユーザー

総合スコア0

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

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

退会済みユーザー

退会済みユーザー

2017/09/19 19:24

指摘ありがとうございます。 ただ、それ直したぐらいじゃ、合格点になるようなスクリプトじゃないんですよね＾＾； test_array の中の処理とか、ひどいしｗ あー、だれか分かりやすいキレイなコード、提供してくれないかなぁ~＾＾
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。

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

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

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

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

ただいまの回答率
85.48%

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

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

質問する

関連した質問

トップJavaScriptに関する質問

配列で特定位置の周囲の値を効率よく調べたい アルゴリズム