Q&A
ご自身で書かれたコードを質問文に追記されたほうが回答を得られやすいと思います。
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
補足願います。『どのように書けば効率がよいのか』←この場合の効率とは、計算量と考えてよいですか？ また、どの程度の効率のコードをお求めなのか不明ですので、効率がよくないコードの例をご提示いただけますか？
言葉足らずで申し訳ありません。『どのように書けば効率がよいのか』というのは議題のような場合、方程式なるものがあるのかなと思い、「効率的なコード＝アルゴリズム」と記載いたしました。コード例を掲載できればよいのですが、どのように求めるのかも皆目検討がつかない状況でして・・・。
丸投げですね。。。高々25の項の調査なので、べた書きでも良いです。まず、それが書けてからかと。
@te2ji さん
すみません。。自分なりにもう少し考えてコード書いてみます。
ちなみにですが、今のままだと「何を調査するのか？」「配列はどのようなフォーマットか？」等の仕様が明確でないので、コードの提示をすることは出来ません。そのあたりも考慮したご自身のコードがあれば、回答がつきやすいかと。
@te2ji さん すみません。自分なりに途中まで書いたコードですが…掲載いたしました。https://codepen.io/bakemon-gogogo/pen/zEvObR
回答6件
0
渦を描くアルゴリズム
下記スレッドを想起させる質問ですね。
起点となる座標を一つ設定し、時計回り/反時計回りに周回すれば効率よく走査できます。
例えば、X座標/Y座標をそれぞれ -N (※N は自然数) すれば、左下の起点を求める事が可能です。
(2017/09/17 12:30追記)
「左上の起点」と書いていましたが、正しくは「左下の起点」でしたので、訂正しました。
処理効率
時計回り/反時計回りに周回するようにループ走査した方が処理効率やパフォーマンスとして優れているという理解であっておりますか？
処理効率は何かのコードと比較して出るものなので、漠然と優れていると判断する事は出来ません。
処理効率を考える時には、はコードではなく、アルゴリズムで考えてみて下さい。
例えば、Lhankor_Mhyさんのコードは配列全体を検索して反転座標を見つけるものでした。100個の座標があれば、100回の処理を行います。
私が提案した渦を描くコードは起点となる座標を求めてから渦を描くように反転座標を求めるコードでした。目的の座標から1マスずれた座標を求めるとするなら、8回の処理を行います。
つまり、単純計算でも「8/100」の時間で完了するわけです。
te2jiさんのコードは目的の座標から起点となる反転座標を求め、上辺/下辺を描いた後に、右辺/左辺を描くコードでした。
私のコードはループ処理が4回ありますが、te2jiさんのコードはループ処理が2回で済みます。
ただし、te2jiさんのコードは次のようになりますが、
- 「目的の座標」から「反転座標」を求めて、反転座標の配列を返す
- 反転座標の配列を
Array#forEachで反復処理し、各座標を反転させる
効率特化で考えるなら、反転座標の配列を返す処理は省くことが可能で、即座に反転処理させる事で効率を向上させることが出来ます。
効率化は「無駄を省くこと」なので、他にも省略出来る処理がないか探してみることをお勧めします。
最終的にはベンチマークを取ることが大切で、自分の想定と異なる結果が返ってきたなら、アルゴリズムを見直してくる事で見えてくるものもあります。
配列を生成しないコード
前述の「処理効率」の下りでは、Lhankor_Mhyさんのコードの効率が悪いニュアンスで説明しましたが、配列の生成する事を踏まえるとそれ程、悪い実装でもありません。
いずれにしても、真っ白なキャンバス(配列)を作る前提であれば、配列を生成するタイミングで文字を初期化すれば、配列全体の走査が1回で済むと考える事も出来ます。
(A) Lhankor_Mhyさんの発想
- 配列を作りながら、「〇」「◎」を代入していく
- 配列全体を走査し、文字列化する
(B) te2ji さんの発想
- 配列を作りながら、ビット列を代入していく
- 配列を部分的を走査し、「◎」を代入する
- 配列全体を走査し、文字列化する
(A) は (B) よりも処理工数が少なく、効率が良いことが分かります。
ところで、どちらも「二次元配列を生成→二次元配列を文字列化」の手順を踏んでいますが、そもそも、二次元配列を生成する必要はあるでしょうか。
「初めから文字列を生成すればよいのでは」という発想で書いたのが次のコードです。
配列を作る過程がなく、条件を元に文字列を生成していくので、原理上は効率が良いはずです。
ベンチマーク
次の環境において、「キャンバスサイズの最大値: 1010 (※1)」「繰り返し回数: 1000回」の設定値でベンチマークを実行してみました。
| 名前 | 値 |
|---|---|
| OS | Windows 10 Home 64bit |
| Browser | Google Chrome 60.0.3112.113 |
(※1) テキストボックス入力値は「1000」ですが、関数 benchmark の処理で +10 しています。0x0のキャンバスでは有効値が取れないと思われる為の措置です。
(※2) ベンチマーク処理の都合上、引数の順番等の処理を一部変更しています。特に、raccyさんのコードは設計思想が大きく異なり、rect サイズを指定する為に追加処理を入れています。
| 回数 | think49 | Lhankor_Mhy(初版) | te2ji(type1 初版) | raccy |
|---|---|---|---|---|
| 1回目 | 10.128173828125ms | 39301.115966796875ms | 測定不能(エラー) | 125472.5986328125ms |
| 2回目 | 1.7138671875ms | 36288.373779296875ms | 測定不能(エラー) | 124575.38696289062ms |
| 3回目 | 1.626953125ms | 35011.963623046875ms | 測定不能(エラー) | 125737.03271484375ms |
| 4回目 | 2.990966796875ms | 36570.126953125ms | 測定不能(エラー) | 131851.31713867188ms |
| 5回目 | 1.56005859375ms | 39585.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.115966796875ms | 12114.286865234375ms | 12167.263916015625ms | 13070.504150390625ms | 17185.240966796875ms |
| 2回目 | 36288.373779296875ms | 12250.916015625ms | 12209.571044921875ms | 13132.1572265625ms | 16331.541259765625ms |
| 3回目 | 35011.963623046875ms | 12381.442138671875ms | 12042.466064453125ms | 13132.1572265625ms | 17234.682861328125ms |
| 4回目 | 36570.126953125ms | 12274.921142578125ms | 12375.59814453125ms | 12552.7861328125ms | 131851.31713867188ms |
| 5回目 | 39585.26806640625ms | 12051.870849609375ms | 12160.140869140625ms | 13023.833984375ms | 17187.80712890625ms |
概ね、「Lhankor_Mhy(改訂版2) > Lhankor_Mhy(改訂版1) > Lhankor_Mhy(改訂版3) > te2ji(type1 改訂版1) > Lhankor_Mhy(初版)」の結果となりました。
Lhankor_Mhy(初版)
Array()で配列を生成- Spread要素で配列を展開(
Array()ではlengthプロパティのみの初期化でキーが存在しない為、Array#mapで走査出来ません。キーを生成する為にSpread要素で初期化しています。) Array#mapで値を初期化
Lhankor_Mhy(改訂版1)、(改訂版2)
※(改訂版2) は x, y の最小値/最大値を事前に変数にキャッシュしておく
- while x 2 で二次元配列を生成し、条件判断で「〇」「◎」を格納していく
- 即座に join() して文字列化
Lhankor_Mhy(改訂版3)
- 条件を元に「◎」を代入する座標をキャッシュしておく
- while x 2 で二次元配列を生成し、条件判断で「〇」「◎」を格納していく
- 即座に join() して文字列化
te2ji(type1 改訂版1)
- while x 2 で二次元配列を生成し、「〇」で初期化
- 配列全体を検索し、条件判断で「〇」「◎」を格納していく
- 配列を行検索し、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
総合スコア18189
@think49 さん
ありがとうございます！
いただいたサンプルでいうと、まず起点を決めて上辺→右辺→下辺→左辺の順に走査するということでしょうか？
プログラミング自体、初心者でして基本的な質問になってしまうかもしれませんが…
時計回り/反時計回りに周回するようにループ走査した方が処理効率やパフォーマンスとして優れている
という理解であっておりますか？
親記事に追記しました。
コーディングする時には、「アルゴリズムを考える→コードを書く」の手順で行うことをお勧めします。
効率化する時にも同様で優れたアルゴリズムは無駄が少ないものです。
アルゴリズムには特別な技能は必要ないので、「1. ～を行う」「2. ～を行う」のように序列リストで手順化する事で無駄を見つけることが出来ます。
@think49 さん
ご丁寧に補足いただきありがとうございます！
考え方やコーディングする際のフローなどとても勉強になりました。
> 最終的にはベンチマークを取ることが大切で、自分の想定と異なる結果が返ってきたなら、
> アルゴリズムを見直してくる事で見えてくるものもあります。
think49さん、te2jiさん、Lhankor_Mhyさんにご教示いただいたロジックでベンチマークを取って試してみたいと思います。
効率について、もう一つ。
Array#filter や Array#map は新しい配列を生成して返すという特徴があります。
ある配列を別のフォーマットに変換する動作は、配列全体を検索する必要があります。
構造上、配列全体を1回は走査しなければなりませんが、配列全体を走査する回数が2回、3回と増えれば、比例して時間がかかってしまうわけです。
その上、別のフォーマットに変換するとなれば、新しいオブジェクトを生成するコストがかかります。
この過程を省略出来れば、効率は大きく上昇します。
今、別の発想でコードを書いていますが、少し時間がかかりそうです。
親記事に追記しました。
te2ji(type2)は、桁あふれちゃうんじゃないですかねぇ。
ちゃんと見てないですけど、オリジナルは桁あふれたら、まともに動きません＾＾；
To: te2ji さん
昨夜(今朝)はベンチマークだけで力尽きました。
しかし、何故そんな他人事のように…。
残念ながら、私のスキルではあれぐらいが限界で＾＾；
２つの私の回答は、晒すには恥ずかしいレベルですが、まぁ概念は伝わるかなぁって感じのサンプルです。
ベンチマークは想定外だったんで、コメントししました。
(type2)のオリジナルは、他にもいろいろヤバイので、実用というよりは、概念を追いかける材料ぐらいにしか使えないです。。。
テストしたところ、think49, te2ji(type1), te2ji(type2) でエラーとなりました。
他人の指摘をしている場合ではなかったですね…。
取り急ぎ、v1.0.1で修正しました(要Git Hub参照)。
ベンチマーク結果は変わっていなくてほっとしました。
親記事を編集しました。
To: te2ji さん
ご希望のものに近いかわかりませんが、(type1) は修正しておきました。
修正、ありがとうございます。
今ちょっと時間が取れないので、後日になりますが勉強させていただきます。
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
他にも2進数で、フラグ操作するとかもあると思います。
@te2ji さん
今日から勉強の一環で本サービス利用しており、BAつけるタイミングなど理解できておらず恐縮です…
@te2ji さん
ご回答いただきありがとうございます！
> 効率を求めるのであれば、
> ・rectSize によって決定される、反転座標の配列を作成
> ・反転座標の配列を元に入力値にその座標があれば、反転させる
> といった操作になると思います。
上記ですが、理解できず申し訳ないのですが…
もう少し掘り下げると下記のような解釈でしょうか？
現状は、Array[0][0] 〜 Array[9][9]まで配列の全てを走査していますが、
図解でいう、6列目・4行目（Array[5][3]）を始点としてそこから rectSize の間に限定した配列を別途用意し判定、
その後上記の判定結果を本配列と同様の箇所と差し替える？
という理解であっておりますでしょうか。
伝わりにくかったようなのでコードにしてみました。
どちらかと言うと、ツッコミどころ満載のコードで恐縮ですが、処理が伝われば幸いです。
@te2ji さん
結論としては、forEachで重複して走査処理を回すことになるので、反転処理を分ける必要がないということでしょうか？
ご丁寧にサンプルコードも記載いただきありがとうございます！
> if(val[0] >= 0 && val[0] < size[0] && val[1] >= 0 && val[1] < size[1])
php 脳では配列の存在確認で分かりやすい条件が書けると思っていたのですが、JavaScript での書き方がわからなかったため、かなり汚い書き方になりました。
ので、こんな条件書くぐらいだったら統合しちゃえ。って意味です。
コードとしてはかなり汚いので、ざっと流れが追えれば、いいかな。ぐらいで見てください。正直、回答として晒しているのがかなり恥ずかしいです。。。
いえ、とんでもないです、プログラム自体が初心者で勉強中の身ですので、とても参考になります！
ご教示くださったコードを詳しく見て理解したいと思います。
@te2ji さん
ご教示いただいたコードを詳しく見てみたのですが、test_array[0][0]からの走査は同じですが、範囲の右下のマスまでの範囲までで走査し、その後forEachでフラグの反転処理を行っている
という理解であっておりますか？
度々の質問になり恐縮です。。
全体の走査はしていないです。
コードの概要は、以下の通り。
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 なので、全体を走査することはありません。
@te2ji さん
ご丁寧に補足いただきありがとうございます！
ようやく理解できました。すごく効率が良さそう（初心者目線ですが…）です、ありがとうございます！
@te2ji さん
> 他にも2進数で、フラグ操作するとかもあると思います。
上記ですが、
プログラミングを始めたばかりで引き出しが少なすぎるのと、
色々な書き方の引き出しを増やしたいのですが、参考書籍を見ていても一つの書き方・ロジックしか書いておらず・・・
大変申し上げにくいのですが、サンプルコードをお願いできないでしょうか？
勿論差し支え無ければです。。
> 他にも2進数で、フラグ操作するとかもあると思います。
初心者向けの参考書には載ってない気がするなぁ。。。
あんまりきれいなコードで書ける気がしないですが、あとでやってみます。
ただ、こういうのは、きれいなコードで見ないと、理解しづらいかも。
あと、今更ですが、今回の回答のコード、console.log で出力すると、x,y が入れ替わっちゃうので、感覚的にわかりにくいですね＾＾；
修正はしませんので、読み替えてくださいｗ
関数にスペルミスが有ったので、修正しました。
こちらも ReferenceError があったので修正。
ついでに、縦横反転の問題に対処しておきました。
グローバル変数を廃止し、関数の引数で設定値を受け取るようにすると汎用性が上がると思います。
https://jsfiddle.net/bwzw4ds4/5/
ありがとうございます＾＾
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総合スコア36946
@Lhankor_Mhyさん ありがとうございます！自分なりに途中までですが…コードを修正してみましたが、やはり上手くできませんでした。。 まだJavaScript初心者で勉強しておりまして、なんだか見たこともない文法ですが、ES2015というものでしょうか？
解決していないなら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)
この部分でして、極一般的な真偽値を返す論理式です。
@Lhankor_Mhyさん
ご回答ありがとうございます！
今日から勉強の一環で本サービス利用しており、理解できておらず恐縮です…
ご回答いただいたコードの解釈ですが、
Y軸が基準点から四角形（半径）の範囲に該当する、且つ四角形の範囲内のX軸の場合はtrue、
または
X軸が基準点から四角形（半径）の範囲に該当する、且つ四角形の範囲内のY軸の場合はtrue、
であっておりますでしょうか？
おっしゃるとおりです。
それで、「その周囲」にあたる座標にはtrueを返せると思うのですが、いかがでしょうか。
回答のコードは、配列の全範囲をなめて、それぞれその論理式の値を返しているだけです。もちろん、2重for文で書き直すことも可能です。
@Lhankor_Mhyさん
理解できました。ご教授いただいたコードを参考に再度チャレンジしてみます。
ご丁寧に回答いただきありがとうございました！
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
総合スコア36946
> 悲しいかな32マスまでしか使えないので
ビット演算子を使わなければ、Number.MAX_SAFE_INTEGER.toString(2).length === 53 なので、53マスまでは対応可能…・。
それでも少ないので、32もしくは53bit単位で分割管理するか、フラグマップを文字列で持つ手段が考えられますね。
ただ、実際のところ、必要なビット列のほとんどは「11111111111」と「10000000001」なので、一つの行を生成できれば複製して使いまわす方が手っ取り早いという事情があります。
ふと思ったのですが、この方式の場合、1のマス目だけ2進数で覚えておけば、0のマス目は記録しておく必要がないですね。
例えば、Lhankor_Mhy さんが書いたコードの場合、
◎◎◎◎◎
◎◯◯◯◎
◎◯◯◯◎
◎◯◯◯◎
◎◎◎◎◎
この部分だけ2進数でフラグマップを作成し、このRectがある座標を記録しておきます。
文字列化する際には上下左右を〇で埋めてやれば、完成します。
33マス以上のフィールドには33マス以上のマス目が存在する可能性がある為、この手法をもってしても32bitを分割管理する等の対策が必要ですが、パフォーマンスは稼げる考え方のように思いました。
恥ずかしがりながらも書いてみるもんですね。
今ちょっと時間がないので、後日改めて勉強させていただきます！
ありがとうございます。
> think49さん
その考え方は私も思いついたのですが、境界処理とかが面倒になって投げてしまいました（ｗ
この質問、当初はUnityタグとかがついていましたので、おそらくゲームに用いたいんだと思ってました。
そうだとすると、おそらく各種処理で参照を行うだろうと思うので、どう処理すればパフォーマンスが向上するのか、について不明な点が多すぎるんですよね……
> te2jiさん
あまりきれいなコードではないと思うのでお目汚しですが……
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
総合スコア21737
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
Strict Mode にすると、ReferenceError が4つ程、発生するようです。
https://jsfiddle.net/ew9kghm4/
let で宣言したコードがこちら。
https://jsfiddle.net/ew9kghm4/1/
指摘ありがとうございます。
ただ、それ直したぐらいじゃ、合格点になるようなスクリプトじゃないんですよね＾＾；
test_array の中の処理とか、ひどいしｗ
あー、だれか分かりやすいキレイなコード、提供してくれないかなぁ~＾＾
あなたの回答
tips
プレビュー
