teratail
回答率
85.30%
teratail header banner
teratail header banner
質問するログイン新規登録
トップJavaScriptに関する質問配列で特定位置の周囲の値を効率よく調べたい アルゴリズム

編集履歴

回答編集履歴

7

「ベンチマーク」の節を書き直し。「ベンチマーク\(2回目\)」「まとめ」を追加。

2017/09/20 11:23

投稿

think49
think49

スコア18194

answer CHANGED
@@ -60,13 +60,137 @@
60
60
 
61
61
  ### ベンチマーク
62
62
 
63
- ミスが発覚したので一時取り下げます。
63
+ 次の環境において、「キャンバスサイズの最大値: 1010 (※1)」「繰り返し回数: 1000回」の設定値でベンチマークを実行してみました。
64
- 遂行後に投稿予定となります。
65
64
 
65
+ - [benchmark - create-square-aa-1.0.1.js - JSFiddle](https://jsfiddle.net/u313fm02/2/)
66
+
67
+ |名前|値|
68
+ |:--|:--|
69
+ |OS|Windows 10 Home 64bit|
70
+ |Browser|Google Chrome 60.0.3112.113|
71
+
72
+ (※1) テキストボックス入力値は「1000」ですが、関数 benchmark の処理で +10 しています。0x0のキャンバスでは有効値が取れないと思われる為の措置です。
73
+ (※2) ベンチマーク処理の都合上、引数の順番等の処理を一部変更しています。特に、raccyさんのコードは設計思想が大きく異なり、`rect` サイズを指定する為に追加処理を入れています。
74
+
75
+ |回数|think49|Lhankor_Mhy(初版)|te2ji(type1 初版)|raccy|
76
+ |:--|:--|:--|:--|:--|
77
+ |1回目|10.128173828125ms|39301.115966796875ms|測定不能(エラー)|125472.5986328125ms|
78
+ |2回目|1.7138671875ms|36288.373779296875ms|測定不能(エラー)|124575.38696289062ms|
79
+ |3回目|1.626953125ms|35011.963623046875ms|測定不能(エラー)|125737.03271484375ms|
80
+ |4回目|2.990966796875ms|36570.126953125ms|測定不能(エラー)|131851.31713867188ms|
81
+ |5回目|1.56005859375ms|39585.26806640625ms|測定不能(エラー)|128274.21826171875ms|
82
+
83
+ 前述の通り、配列を介在せずに直接文字列を生成している為、高速になっているものと思われます。
84
+ それから、行単位、列単位で処理を分ける事でまとめて処理を行う工夫もしています。
85
+ 例えば、次のマップを生成する場合、
86
+
87
+ ```
88
+ 〇〇〇〇〇〇〇〇〇〇
89
+ 〇〇〇〇〇〇〇〇〇〇
90
+ 〇〇〇〇〇〇〇〇〇〇
91
+ 〇〇〇◎◎◎〇〇〇〇
92
+ 〇〇〇◎〇◎〇〇〇〇
93
+ 〇〇〇◎◎◎〇〇〇〇
94
+ 〇〇〇〇〇〇〇〇〇〇
95
+ 〇〇〇〇〇〇〇〇〇〇
96
+ 〇〇〇〇〇〇〇〇〇〇
97
+ 〇〇〇〇〇〇〇〇〇〇
98
+ ```
99
+
100
+ まず、種別に行単位で区分けします。
101
+
102
+ ```
103
+ 〇〇〇〇〇〇〇〇〇〇
104
+ 〇〇〇〇〇〇〇〇〇〇
105
+ 〇〇〇〇〇〇〇〇〇〇
106
+ 　　　　　＋
107
+ 〇〇〇◎◎◎〇〇〇〇
108
+ 　　　　　＋
109
+ 〇〇〇◎〇◎〇〇〇〇
110
+ 　　　　　＋
111
+ 〇〇〇◎◎◎〇〇〇〇
112
+ 　　　　　＋
113
+ 〇〇〇〇〇〇〇〇〇〇
114
+ 〇〇〇〇〇〇〇〇〇〇
115
+ 〇〇〇〇〇〇〇〇〇〇
116
+ 〇〇〇〇〇〇〇〇〇〇
117
+ ```
118
+
119
+ 先頭の3行と末尾の4行は「〇」か「◎」かを判断する必要はない為、「〇〇〇〇〇〇〇〇〇〇\n」を整数倍した文字列を生成して処理を終えます。
120
+ 「〇〇〇◎◎◎〇〇〇〇」は「〇〇〇 + ◎◎◎ + 〇〇〇〇」のように3つのブロックに分解してやり、「〇 x 3 の文字列」「◎ x 3 の文字列」「〇 x 4 の文字列」を各々生成して連結します。
121
+ 続く行も同様で「〇〇〇 + ◎ + 〇 + ◎ + 〇〇〇〇」のように分解して文字列を生成→連結を繰り返します。
122
+ なお、文字列の生成には、ES2017 規定の `String.prototype.padStart`, `String.prototype.padEnd` を利用しており、一般的な繰り返し構文(`for`, `forEach`, `for-of` 等)を使用していない事も高速化に貢献しているかもしれません。
123
+ (padStart, padEnd は IE11- 対策で Polyfill を適用してやります)。
124
+
125
+ - [String.prototype.padStart, String.prototype.padEnd の Polyfill (ECMAScript 2017 / ECMA-262 8th edition)](https://gist.github.com/think49/d0e01c82c12bda2d27d8)
126
+
127
+ te2ji(type1), te2ji(type2) のコードは生成される文字列は一致せず、te2ji(type1) ではベンチマークを実行する事も出来ませんでしたので、ここでは比較対象が意図しました。
128
+ しかし、Lhankor_Mhyさんとte2jiさんのコード比較は気になったので、コードを修正して、ベンチマークをとってみました(次節参照)。
129
+
130
+ raccyさんのコードが著しく遅いのは、単純に処理ステップが多いためだと思われます。
131
+ - コンストラクタ呼び出し
132
+ - [[Prototype]] のプロパティ参照
133
+ - 分割代入
134
+ - 「コンストラクタ呼び出し(マップ初期化) -> listByDistance -> offMap(マップ全体のフラグ初期化) -> onMap(該当座標のフラグ書き換え) -> join(文字列化)」で合計5回の処理
135
+ - `map[y][x].flag` で合計3回のプロパティ参照コスト(2次元配列より1回多い)
136
+ これだけ処理量が多ければ、遅いのは致し方ありません。
137
+
138
+ ### ベンチマーク(2回目)
139
+
140
+ |回数|Lhankor_Mhy(初版)|Lhankor_Mhy(改訂版1)|Lhankor_Mhy(改訂版2)|Lhankor_Mhy(改訂版3)|te2ji(type1 改訂版1)|
141
+ |:--|:--|:--|:--|:--|:--|
142
+ |1回目|39301.115966796875ms|12114.286865234375ms|12167.263916015625ms|13070.504150390625ms|17185.240966796875ms|
143
+ |2回目|36288.373779296875ms|12250.916015625ms|12209.571044921875ms|13132.1572265625ms|16331.541259765625ms|
144
+ |3回目|35011.963623046875ms|12381.442138671875ms|12042.466064453125ms|13132.1572265625ms|17234.682861328125ms|
145
+ |4回目|36570.126953125ms|12274.921142578125ms|12375.59814453125ms|12552.7861328125ms|131851.31713867188ms|
146
+ |5回目|39585.26806640625ms|12051.870849609375ms|12160.140869140625ms|13023.833984375ms|17187.80712890625ms|
147
+
148
+ 概ね、「Lhankor_Mhy(改訂版2) > Lhankor_Mhy(改訂版1) > Lhankor_Mhy(改訂版3) > te2ji(type1 改訂版1) > Lhankor_Mhy(初版)」の結果となりました。
149
+
150
+ #### Lhankor_Mhy(初版)
151
+
152
+ 1. `Array()` で配列を生成
153
+ 2. Spread要素で配列を展開(`Array()` では `length` プロパティのみの初期化でキーが存在しない為、`Array#map` で走査出来ません。キーを生成する為にSpread要素で初期化しています。)
154
+ 3. `Array#map` で値を初期化
155
+
156
+ #### Lhankor_Mhy(改訂版1)、(改訂版2)
157
+
158
+ ※(改訂版2) は x, y の最小値/最大値を事前に変数にキャッシュしておく
159
+
160
+ 1. while x 2 で二次元配列を生成し、条件判断で「〇」「◎」を格納していく
161
+ 2. 即座に join() して文字列化
162
+
163
+ #### Lhankor_Mhy(改訂版3)
164
+
165
+ 1. 条件を元に「◎」を代入する座標をキャッシュしておく
166
+ 2. while x 2 で二次元配列を生成し、条件判断で「〇」「◎」を格納していく
167
+ 3. 即座に join() して文字列化
168
+
169
+ #### te2ji(type1 改訂版1)
170
+
171
+ 1. while x 2 で二次元配列を生成し、「〇」で初期化
172
+ 2. 配列全体を検索し、条件判断で「〇」「◎」を格納していく
173
+ 3. 配列を行検索し、joinで文字列化
174
+
175
+ 実際のところ、te2ji(type1 改訂版1)はLhankor_Mhy(改訂版2)のコードを関数単位で分割しただけなので、どうやってもLhankor_Mhy(改訂版2)に勝てません。
176
+ te2ji(type1 改訂版1)のコードをオブジェクト指向で書き直したのがraccyさんのコードともいえます。
177
+ ただ、パフォーマンスの観点から見ると、raccyさんのコードには改善の余地があると思います。
178
+
179
+ ### まとめ
180
+
181
+ 活用したテクニックをまとめると、次のようになります。
182
+
183
+ - 同じプロパティを何度も参照する時には変数にキャッシュする
184
+ - 繰り返し回数を減らす(まとめて処理できるなら、そうする)
185
+ - 配列やオブジェクトのプロパティ参照回数を減らす
186
+ - 配列やオブジェクトの生成回数を減らす
187
+ - if文の条件判定の通過回数を減らす(場合によっては、ネストした方が速い)
188
+
66
189
  ### 更新履歴
67
190
 
68
191
  - 2017/09/17 12:30 「左上の起点」を「左下の起点」に修正。「処理効率」の節を追記。
69
192
  - 2017/09/20 05:53 「配列を生成しないコード」「ベンチマーク」の節を追記。
70
193
  - 2017/09/20 14:12 「ベンチマーク」の節でミスが発覚したので一時取り下げ。
194
+ - 2017/09/20 20:22 「ベンチマーク」の節を書き直し。「ベンチマーク(2回目)」「まとめ」を追加。
71
195
 
72
196
  Re: bakemon-gogogo さん

6

「ベンチマーク」の節でミスが発覚したので一時取り下げ

2017/09/20 11:23

投稿

think49
think49

スコア18194

answer CHANGED
@@ -60,96 +60,13 @@
60
60
 
61
61
  ### ベンチマーク
62
62
 
63
- というわけで、実際にベンチマークをとってみました。
63
+ ミスが発覚したので一時取り下げます。
64
+ 遂行後に投稿予定となります。
64
65
 
65
- - [benchmark - create-aa-square.js - JSFiddle](https://jsfiddle.net/u313fm02/)
66
-
67
- |回数|think49|Lhankor_Mhy|te2ji(type2)|raccy|
68
- |:--|:--|:--|:--|:--|
69
- |1回目|25.2119140625ms|38196.677001953125ms|23589.571044921875ms|129957.9169921875ms|
70
- |2回目|13.60009765625ms|36981.338134765625ms|23589.571044921875ms|129957.9169921875ms|
71
- |3回目|19.122802734375ms|36985.7021484375ms|23666.81005859375ms|130607.10815429688ms|
72
- |4回目|12.8232421875ms|36823.884033203125ms|22614.092041015625ms|125199.45922851562ms|
73
- |5回目|8.265869140625ms|38262.90087890625ms|23925.908935546875ms|129177.49096679688ms|
74
-
75
- 次の環境において、「キャンバスサイズの最大値: 1010 (※1)」「繰り返し回数: 1000回」の設定値で実行しています。
76
-
77
- |名前|値|
78
- |:--|:--|
79
- |OS|Windows 10 Home 64bit|
80
- |Browser|Google Chrome 60.0.3112.113|
81
-
82
- (※1) テキストボックス入力値は「1000」ですが、関数 benchmark の処理で +10 しています。0x0のキャンバスでは有効値が取れないと思われる為の措置です。
83
- (※2) ベンチマーク処理の都合上、引数の順番等の処理を一部変更しています。特に、raccyさんのコードは設計思想が大きく異なり、`rect` サイズを指定する為に追加処理を入れています。
84
-
85
- 自画自賛になりますが、私のコードが段違いに速い結果となりました。
86
- 中間オブジェクトを経由していない設計が功を奏したものと思われます。
87
- また、私のコードでは反転座標が存在しない行をキャッシュして複製する事で計算コストを下げる工夫をしています。
88
- 例えば、次のマップを生成する場合、
89
-
90
- ```
91
- 〇〇〇〇〇〇〇〇〇〇
92
- 〇◎◎◎〇〇〇〇〇〇
93
- 〇◎〇◎〇〇〇〇〇〇
94
- 〇◎◎◎〇〇〇〇〇〇
95
- 〇〇〇〇〇〇〇〇〇〇
96
- 〇〇〇〇〇〇〇〇〇〇
97
- 〇〇〇〇〇〇〇〇〇〇
98
- 〇〇〇〇〇〇〇〇〇〇
99
- 〇〇〇〇〇〇〇〇〇〇
100
- 〇〇〇〇〇〇〇〇〇〇
101
- ```
102
-
103
- 1行目及び5～10行目には「◎」が存在しない為、「〇〇〇〇〇〇〇〇〇〇」を流し込むだけで済むと考えられます。
104
- 「◎」が存在しない行は「〇〇〇〇〇〇〇〇〇〇\n」をN行数分だけN倍化して流し込めば、1文字ごとにしていた演算を大幅に省略することが出来ます。
105
- 2行目の「〇◎◎◎〇〇〇〇〇〇」についても、「〇 + ◎◎◎ + 〇〇〇〇〇〇」のように3回に分けて処理するようにしており、座標一つに付き、1回ずつ処理するよりも効率が上がる事が期待できます。
106
- なお、私のコードでは、ES2017 規定の `String.prototype.padStart`, `String.prototype.padEnd` を利用している為、IE11- の為に Polyfill が必要です。
107
-
108
- - [String.prototype.padStart, String.prototype.padEnd の Polyfill (ECMAScript 2017 / ECMA-262 8th edition)](https://gist.github.com/think49/d0e01c82c12bda2d27d8)
109
-
110
- Lhankor_Mhyさんのコードとte2jiさんのコードでは、若干ながらte2jiさんのコードが速い結果となりました。
111
- 前述の説明((A) は (B) よりも処理工数が少なく、効率が良い)と矛盾しますが、実はte2jiさんのコードは二種類あり、今回は後から作成されたコード(ここではtype2とします)を使用している事からアルゴリズムが違います。
112
-
113
- (Lhankor_Mhy さんのコード)
114
-
115
- 1. `Array()` で配列を生成
116
- 2. Spread要素で配列を展開(`Array()` では `length` プロパティのみの初期化でキーが存在しない為、`Array#map` で走査出来ません。キーを生成する為にSpread要素で初期化しています。)
117
- 3. `Array#map` で値を初期化
118
-
119
- (te2ji さんのコード)
120
-
121
- 1. 行の配列を 0 で初期化
122
- 2. 各行を forEach で走査し、ビット列となる数値を代入
123
- 3. 各行を for 文で走査し、2進数文字列に変換後、0 と 1 をそれぞれ対応する記号に置換する
124
-
125
- Lhankor_Mhy さんのコードでは配列を初期化するステップが3回存在しますが、te2ji さんのコードでは、二次元配列ではない上に初期化ステップは2回だけです。
126
- しかし、te2ji さんのコードでは前述の通り、配列を生成後に配列を全検索して文字列化している為、全検索のステップが2回ある事となり、そこに付け入る隙があります。
127
- Lhankor_Mhy さんのコードを改善して、再度、ベンチマークをとってみました。
128
-
129
- - [benchmark - Lhankor_Mhy(改訂版) vs te2ji(type2) - JSFiddle](https://jsfiddle.net/u313fm02/1/)
130
-
131
- |回数|Lhankor_Mhy|Lhankor_Mhy(改訂版)|te2ji(type2)|
132
- |:--|:--|:--|:--|
133
- |1回目|37858.259033203125ms|12281.44287109375ms|23761.200927734375ms|
134
- |2回目|39205.093994140625ms|12562.913818359375ms|24098.187744140625ms|
135
- |3回目|36470.593017578125ms|13279.234375ms|24565.427978515625ms|
136
-
137
- 概ね、想像通りの結果となりました。
138
- Lhankor_Mhy(改訂版)では配列初期化後に即時値を代入し、`join()`している為、処理完了までに配列全体を1回だけ走査しますが、te2ji(type2)では配列全体を2回走査しています。
139
-
140
- raccyさんのコードが著しく遅いのは、単純に処理ステップが多いためだと思われます。
141
-
142
- - コンストラクタ呼び出し
143
- - [[Prototype]] のプロパティ参照
144
- - 分割代入
145
- - 「コンストラクタ呼び出し(マップ初期化) -> listByDistance -> offMap(マップ全体のフラグ初期化) -> onMap(該当座標のフラグ書き換え) -> join(文字列化)」で合計5回の処理
146
- - `map[y][x].flag` で合計3回のプロパティ参照コスト(2次元配列より1回多い)
147
-
148
- これだけ処理量が多ければ、遅いのは致し方ありません。
149
-
150
66
  ### 更新履歴
151
67
 
152
68
  - 2017/09/17 12:30 「左上の起点」を「左下の起点」に修正。「処理効率」の節を追記。
153
69
  - 2017/09/20 05:53 「配列を生成しないコード」「ベンチマーク」の節を追記。
70
+ - 2017/09/20 14:12 「ベンチマーク」の節でミスが発覚したので一時取り下げ。
154
71
 
155
72
  Re: bakemon-gogogo さん

5

markdown修正

2017/09/20 05:12

投稿

think49
think49

スコア18194

answer CHANGED
@@ -129,7 +129,7 @@
129
129
  - [benchmark - Lhankor_Mhy(改訂版) vs te2ji(type2) - JSFiddle](https://jsfiddle.net/u313fm02/1/)
130
130
 
131
131
  |回数|Lhankor_Mhy|Lhankor_Mhy(改訂版)|te2ji(type2)|
132
- |:--|:--|:--|:--|:--|
132
+ |:--|:--|:--|:--|
133
133
  |1回目|37858.259033203125ms|12281.44287109375ms|23761.200927734375ms|
134
134
  |2回目|39205.093994140625ms|12562.913818359375ms|24098.187744140625ms|
135
135
  |3回目|36470.593017578125ms|13279.234375ms|24565.427978515625ms|

4

「配列を生成しないコード」「ベンチマーク」の節を追記

2017/09/19 22:01

投稿

think49
think49

スコア18194

answer CHANGED
@@ -33,8 +33,123 @@
33
33
 
34
34
  最終的にはベンチマークを取ることが大切で、自分の想定と異なる結果が返ってきたなら、アルゴリズムを見直してくる事で見えてくるものもあります。
35
35
 
36
+ ### 配列を生成しないコード
37
+
38
+ 前述の「処理効率」の下りでは、Lhankor_Mhyさんのコードの効率が悪いニュアンスで説明しましたが、配列の生成する事を踏まえるとそれ程、悪い実装でもありません。
39
+ いずれにしても、真っ白なキャンバス(配列)を作る前提であれば、配列を生成するタイミングで文字を初期化すれば、配列全体の走査が1回で済むと考える事も出来ます。
40
+
41
+ (A) Lhankor_Mhyさんの発想
42
+
43
+ 1. 配列を作りながら、「〇」「◎」を代入していく
44
+ 2. 配列全体を走査し、文字列化する
45
+
46
+ (B) te2ji さんの発想
47
+
48
+ 1. 配列を作りながら、ビット列を代入していく
49
+ 2. 配列を部分的を走査し、「◎」を代入する
50
+ 3. 配列全体を走査し、文字列化する
51
+
52
+ (A) は (B) よりも処理工数が少なく、効率が良いことが分かります。
53
+
54
+ ところで、どちらも「二次元配列を生成→二次元配列を文字列化」の手順を踏んでいますが、そもそも、二次元配列を生成する必要はあるでしょうか。
55
+ 「初めから文字列を生成すればよいのでは」という発想で書いたのが次のコードです。
56
+
57
+ - [create-square-aa.js: 四角形のASCII Artを生成する](https://gist.github.com/think49/2a30b4e865f3dca4043440fb9b99a448)
58
+
59
+ 配列を作る過程がなく、条件を元に文字列を生成していくので、原理上は効率が良いはずです。
60
+
61
+ ### ベンチマーク
62
+
63
+ というわけで、実際にベンチマークをとってみました。
64
+
65
+ - [benchmark - create-aa-square.js - JSFiddle](https://jsfiddle.net/u313fm02/)
66
+
67
+ |回数|think49|Lhankor_Mhy|te2ji(type2)|raccy|
68
+ |:--|:--|:--|:--|:--|
69
+ |1回目|25.2119140625ms|38196.677001953125ms|23589.571044921875ms|129957.9169921875ms|
70
+ |2回目|13.60009765625ms|36981.338134765625ms|23589.571044921875ms|129957.9169921875ms|
71
+ |3回目|19.122802734375ms|36985.7021484375ms|23666.81005859375ms|130607.10815429688ms|
72
+ |4回目|12.8232421875ms|36823.884033203125ms|22614.092041015625ms|125199.45922851562ms|
73
+ |5回目|8.265869140625ms|38262.90087890625ms|23925.908935546875ms|129177.49096679688ms|
74
+
75
+ 次の環境において、「キャンバスサイズの最大値: 1010 (※1)」「繰り返し回数: 1000回」の設定値で実行しています。
76
+
77
+ |名前|値|
78
+ |:--|:--|
79
+ |OS|Windows 10 Home 64bit|
80
+ |Browser|Google Chrome 60.0.3112.113|
81
+
82
+ (※1) テキストボックス入力値は「1000」ですが、関数 benchmark の処理で +10 しています。0x0のキャンバスでは有効値が取れないと思われる為の措置です。
83
+ (※2) ベンチマーク処理の都合上、引数の順番等の処理を一部変更しています。特に、raccyさんのコードは設計思想が大きく異なり、`rect` サイズを指定する為に追加処理を入れています。
84
+
85
+ 自画自賛になりますが、私のコードが段違いに速い結果となりました。
86
+ 中間オブジェクトを経由していない設計が功を奏したものと思われます。
87
+ また、私のコードでは反転座標が存在しない行をキャッシュして複製する事で計算コストを下げる工夫をしています。
88
+ 例えば、次のマップを生成する場合、
89
+
90
+ ```
91
+ 〇〇〇〇〇〇〇〇〇〇
92
+ 〇◎◎◎〇〇〇〇〇〇
93
+ 〇◎〇◎〇〇〇〇〇〇
94
+ 〇◎◎◎〇〇〇〇〇〇
95
+ 〇〇〇〇〇〇〇〇〇〇
96
+ 〇〇〇〇〇〇〇〇〇〇
97
+ 〇〇〇〇〇〇〇〇〇〇
98
+ 〇〇〇〇〇〇〇〇〇〇
99
+ 〇〇〇〇〇〇〇〇〇〇
100
+ 〇〇〇〇〇〇〇〇〇〇
101
+ ```
102
+
103
+ 1行目及び5～10行目には「◎」が存在しない為、「〇〇〇〇〇〇〇〇〇〇」を流し込むだけで済むと考えられます。
104
+ 「◎」が存在しない行は「〇〇〇〇〇〇〇〇〇〇\n」をN行数分だけN倍化して流し込めば、1文字ごとにしていた演算を大幅に省略することが出来ます。
105
+ 2行目の「〇◎◎◎〇〇〇〇〇〇」についても、「〇 + ◎◎◎ + 〇〇〇〇〇〇」のように3回に分けて処理するようにしており、座標一つに付き、1回ずつ処理するよりも効率が上がる事が期待できます。
106
+ なお、私のコードでは、ES2017 規定の `String.prototype.padStart`, `String.prototype.padEnd` を利用している為、IE11- の為に Polyfill が必要です。
107
+
108
+ - [String.prototype.padStart, String.prototype.padEnd の Polyfill (ECMAScript 2017 / ECMA-262 8th edition)](https://gist.github.com/think49/d0e01c82c12bda2d27d8)
109
+
110
+ Lhankor_Mhyさんのコードとte2jiさんのコードでは、若干ながらte2jiさんのコードが速い結果となりました。
111
+ 前述の説明((A) は (B) よりも処理工数が少なく、効率が良い)と矛盾しますが、実はte2jiさんのコードは二種類あり、今回は後から作成されたコード(ここではtype2とします)を使用している事からアルゴリズムが違います。
112
+
113
+ (Lhankor_Mhy さんのコード)
114
+
115
+ 1. `Array()` で配列を生成
116
+ 2. Spread要素で配列を展開(`Array()` では `length` プロパティのみの初期化でキーが存在しない為、`Array#map` で走査出来ません。キーを生成する為にSpread要素で初期化しています。)
117
+ 3. `Array#map` で値を初期化
118
+
119
+ (te2ji さんのコード)
120
+
121
+ 1. 行の配列を 0 で初期化
122
+ 2. 各行を forEach で走査し、ビット列となる数値を代入
123
+ 3. 各行を for 文で走査し、2進数文字列に変換後、0 と 1 をそれぞれ対応する記号に置換する
124
+
125
+ Lhankor_Mhy さんのコードでは配列を初期化するステップが3回存在しますが、te2ji さんのコードでは、二次元配列ではない上に初期化ステップは2回だけです。
126
+ しかし、te2ji さんのコードでは前述の通り、配列を生成後に配列を全検索して文字列化している為、全検索のステップが2回ある事となり、そこに付け入る隙があります。
127
+ Lhankor_Mhy さんのコードを改善して、再度、ベンチマークをとってみました。
128
+
129
+ - [benchmark - Lhankor_Mhy(改訂版) vs te2ji(type2) - JSFiddle](https://jsfiddle.net/u313fm02/1/)
130
+
131
+ |回数|Lhankor_Mhy|Lhankor_Mhy(改訂版)|te2ji(type2)|
132
+ |:--|:--|:--|:--|:--|
133
+ |1回目|37858.259033203125ms|12281.44287109375ms|23761.200927734375ms|
134
+ |2回目|39205.093994140625ms|12562.913818359375ms|24098.187744140625ms|
135
+ |3回目|36470.593017578125ms|13279.234375ms|24565.427978515625ms|
136
+
137
+ 概ね、想像通りの結果となりました。
138
+ Lhankor_Mhy(改訂版)では配列初期化後に即時値を代入し、`join()`している為、処理完了までに配列全体を1回だけ走査しますが、te2ji(type2)では配列全体を2回走査しています。
139
+
140
+ raccyさんのコードが著しく遅いのは、単純に処理ステップが多いためだと思われます。
141
+
142
+ - コンストラクタ呼び出し
143
+ - [[Prototype]] のプロパティ参照
144
+ - 分割代入
145
+ - 「コンストラクタ呼び出し(マップ初期化) -> listByDistance -> offMap(マップ全体のフラグ初期化) -> onMap(該当座標のフラグ書き換え) -> join(文字列化)」で合計5回の処理
146
+ - `map[y][x].flag` で合計3回のプロパティ参照コスト(2次元配列より1回多い)
147
+
148
+ これだけ処理量が多ければ、遅いのは致し方ありません。
149
+
36
150
  ### 更新履歴
37
151
 
38
152
  - 2017/09/17 12:30 「左上の起点」を「左下の起点」に修正。「処理効率」の節を追記。
153
+ - 2017/09/20 05:53 「配列を生成しないコード」「ベンチマーク」の節を追記。
39
154
 
40
155
  Re: bakemon-gogogo さん

3

更新履歴

2017/09/19 21:53

投稿

think49
think49

スコア18194

answer CHANGED
@@ -1,3 +1,5 @@
1
+ ### 渦を描くアルゴリズム
2
+
1
3
  下記スレッドを想起させる質問ですね。
2
4
 
3
5
  - [JavaScript - html/css/jsでグルグルアニメーションの仕方について(ローディングじゃないよ！)(82926)｜teratail](https://teratail.com/questions/82926)
@@ -5,11 +7,15 @@
5
7
  起点となる座標を一つ設定し、時計回り/反時計回りに周回すれば効率よく走査できます。
6
8
  例えば、X座標/Y座標をそれぞれ -N (※N は自然数) すれば、左下の起点を求める事が可能です。
7
9
 
10
+ **(2017/09/17 12:30追記)**
11
+ 「左上の起点」と書いていましたが、正しくは「左下の起点」でしたので、訂正しました。
12
+
8
13
  ### 処理効率
9
14
 
10
15
  > 時計回り/反時計回りに周回するようにループ走査した方が処理効率やパフォーマンスとして優れているという理解であっておりますか？
16
+
11
17
  処理効率は何かのコードと比較して出るものなので、漠然と優れていると判断する事は出来ません。
12
- 処理効率はコードではなく、アルゴリズムで考えてみて下さい。
18
+ 処理効率を考える時には、はコードではなく、アルゴリズムで考えてみて下さい。
13
19
 
14
20
  例えば、Lhankor_Mhyさんのコードは配列全体を検索して反転座標を見つけるものでした。100個の座標があれば、100回の処理を行います。
15
21
  私が提案した渦を描くコードは起点となる座標を求めてから渦を描くように反転座標を求めるコードでした。目的の座標から1マスずれた座標を求めるとするなら、8回の処理を行います。
@@ -17,5 +23,18 @@
17
23
 
18
24
  te2jiさんのコードは目的の座標から起点となる反転座標を求め、上辺/下辺を描いた後に、右辺/左辺を描くコードでした。
19
25
  私のコードはループ処理が4回ありますが、te2jiさんのコードはループ処理が2回で済みます。
26
+ ただし、te2jiさんのコードは次のようになりますが、
20
27
 
28
+ 1. 「目的の座標」から「反転座標」を求めて、反転座標の配列を返す
29
+ 2. 反転座標の配列を `Array#forEach` で反復処理し、各座標を反転させる
30
+
31
+ 効率特化で考えるなら、反転座標の配列を返す処理は省くことが可能で、即座に反転処理させる事で効率を向上させることが出来ます。
32
+ 効率化は「無駄を省くこと」なので、他にも省略出来る処理がないか探してみることをお勧めします。
33
+
34
+ 最終的にはベンチマークを取ることが大切で、自分の想定と異なる結果が返ってきたなら、アルゴリズムを見直してくる事で見えてくるものもあります。
35
+
36
+ ### 更新履歴
37
+
38
+ - 2017/09/17 12:30 「左上の起点」を「左下の起点」に修正。「処理効率」の節を追記。
39
+
21
40
  Re: bakemon-gogogo さん

2

処理効率

2017/09/17 03:30

投稿

think49
think49

スコア18194

answer CHANGED
@@ -3,6 +3,19 @@
3
3
  - [JavaScript - html/css/jsでグルグルアニメーションの仕方について(ローディングじゃないよ！)(82926)｜teratail](https://teratail.com/questions/82926)
4
4
 
5
5
  起点となる座標を一つ設定し、時計回り/反時計回りに周回すれば効率よく走査できます。
6
- 例えば、X座標/Y座標をそれぞれ -N (※N は自然数) すれば、左上の起点を求める事が可能です。
6
+ 例えば、X座標/Y座標をそれぞれ -N (※N は自然数) すれば、左下の起点を求める事が可能です。
7
7
 
8
+ ### 処理効率
9
+
10
+ > 時計回り/反時計回りに周回するようにループ走査した方が処理効率やパフォーマンスとして優れているという理解であっておりますか？
11
+ 処理効率は何かのコードと比較して出るものなので、漠然と優れていると判断する事は出来ません。
12
+ 処理効率はコードではなく、アルゴリズムで考えてみて下さい。
13
+
14
+ 例えば、Lhankor_Mhyさんのコードは配列全体を検索して反転座標を見つけるものでした。100個の座標があれば、100回の処理を行います。
15
+ 私が提案した渦を描くコードは起点となる座標を求めてから渦を描くように反転座標を求めるコードでした。目的の座標から1マスずれた座標を求めるとするなら、8回の処理を行います。
16
+ つまり、単純計算でも「8/100」の時間で完了するわけです。
17
+
18
+ te2jiさんのコードは目的の座標から起点となる反転座標を求め、上辺/下辺を描いた後に、右辺/左辺を描くコードでした。
19
+ 私のコードはループ処理が4回ありますが、te2jiさんのコードはループ処理が2回で済みます。
20
+
8
21
  Re: bakemon-gogogo さん

1

typo修正

2017/09/17 03:03

投稿

think49
think49

スコア18194

answer CHANGED
@@ -3,6 +3,6 @@
3
3
  - [JavaScript - html/css/jsでグルグルアニメーションの仕方について(ローディングじゃないよ！)(82926)｜teratail](https://teratail.com/questions/82926)
4
4
 
5
5
  起点となる座標を一つ設定し、時計回り/反時計回りに周回すれば効率よく走査できます。
6
- 例えば、X座標/Y座標をそれぞれ -N (※N は自然数) すれば、左上の起点が求める事が可能です。
6
+ 例えば、X座標/Y座標をそれぞれ -N (※N は自然数) すれば、左上の起点を求める事が可能です。
7
7
 
8
8
  Re: bakemon-gogogo さん