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

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

ただいまの
回答率

90.61%

  • JavaScript

    16003questions

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

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

受付中

回答 6

投稿 編集

  • 評価
  • クリップ 2
  • VIEW 803

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

前提・実現したいこと

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

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

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

図解

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

   ↓↓↓↓

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

   ↓↓↓↓

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

コード

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

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

<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="utf-8">
<style>
body {
    text-align: center;
    cursor: pointer;
}
div {
    margin: 50px auto;
    font-size: 30px;
    letter-spacing: .5em;
    user-select: none;
}
</style>
<script>

var map = [];
var col = 10;    // マップ:列
var row = 10;    // マップ:行
var set = {
    col: 5,    // 基準フラグの位置:6列目
    row: 3    // 基準フラグの位置:4行目
};
var count = 0;
var wrap; 

// 初期化
function init () {

    // HTML出力枠 生成
    wrap = document.createElement('div');
    document.body.appendChild(wrap);

    // 配列のマップ生成(縦×横:10マス)
    for (var i=0; i<col; ++i) {
        map[i] = [];
        for (var j=0; j<row; ++j) {
            map[i][j] = '◯';
        }
    }

    test(count);

    // クリックイベント
    window.addEventListener('click', function() { 
        count = check('◎') ? (count + 1) : 0;
        test(count);
    });

}

// 基準フラグの周囲を調査
function test (size) {

    // 縦横最小・最大範囲4点を求める
    var rect = {
        xmin: set.row - size,
        xmax: set.row + size,
        ymin: set.col - size,
        ymax: set.col + size
    };

    // マップ全体から基準フラグの周囲を走査
    for (var i=0; i<col; ++i) {
        for (var j=0; j<row; ++j) {

            // 該当するマス目にフラグ付与
            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)) ? '◎' : '◯';

        }
    }

    draw();

}

// マップ全体からフラグを検索
function check (string) {

    for(var i in map){
        for(var j in map[i]){
            if (map[i][j] == string) {
                return true;
                break;
            }
        }
    }
    return false;

}

// HTMLに描画
function draw () {

    var html = '';

    for (var i=0, l=map.length; i<l; ++i) {
        for (var j=0, m=map[i].length; j<m; ++j) {
            html += map[i][j];
        }
        html += '<br>';
    }

    wrap.innerHTML = html;

}

document.addEventListener('DOMContentLoaded', init);

</script>
</head><body></body></html>
  • 気になる質問をクリップする

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • bakemon-gogogo

    2017/09/16 13:19 編集

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

    キャンセル

  • te2ji

    2017/09/16 13:32

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

    キャンセル

  • bakemon-gogogo

    2017/09/16 15:31 編集

    @te2ji さん すみません。自分なりに途中まで書いたコードですが…掲載いたしました。https://codepen.io/bakemon-gogogo/pen/zEvObR

    キャンセル

回答 6

+4

 渦を描くアルゴリズム

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

起点となる座標を一つ設定し、時計回り/反時計回りに周回すれば効率よく走査できます。
例えば、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回」の設定値でベンチマークを実行してみました。

名前
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.padStartString.prototype.padEnd を利用しており、一般的な繰り返し構文(forforEachfor-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(初版)

  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 22:50 編集

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

    キャンセル

  • 2017/09/17 12:34

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

    キャンセル

  • 2017/09/17 14:12

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

    キャンセル

  • 2017/09/18 17:09

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

    今、別の発想でコードを書いていますが、少し時間がかかりそうです。

    キャンセル

  • 2017/09/20 06:54

    親記事に追記しました。

    キャンセル

  • 2017/09/20 08:33

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

    キャンセル

  • 2017/09/20 12:53

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

    キャンセル

  • 2017/09/20 13:11

    残念ながら、私のスキルではあれぐらいが限界で^^;

    2つの私の回答は、晒すには恥ずかしいレベルですが、まぁ概念は伝わるかなぁって感じのサンプルです。
    ベンチマークは想定外だったんで、コメントししました。

    (type2)のオリジナルは、他にもいろいろヤバイので、実用というよりは、概念を追いかける材料ぐらいにしか使えないです。。。

    キャンセル

  • 2017/09/20 14:36

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

    キャンセル

  • 2017/09/20 20:24

    親記事を編集しました。

    To: te2ji さん
    ご希望のものに近いかわかりませんが、(type1) は修正しておきました。

    キャンセル

  • 2017/09/20 22:52

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

    キャンセル

+3

function test(centerX, centerY, rectSize, fieldSize){
  return [...(function* (y){
    while (y<fieldSize){          
      yield [...(function* (x){
        while (x<fieldSize) {
          yield (
            ( y == (centerY - rectSize) || y == (centerY + rectSize) ) && (centerX - rectSize) <= x && x <= (centerX + rectSize)
            ||
            ( x == (centerX - rectSize) || x == (centerX + rectSize) ) && (centerY - rectSize) <= y && y <= (centerY + rectSize)            
          );
          x++;
        }
      })(0)];
      y++;
    }
  })(0)]
}

test(3,5,0,10);
/*
0000000000
0000000000
0000000000
0000000000
0000000000
0001000000
0000000000
0000000000
0000000000
0000000000
*/

test(3,5,1,10);
/*
0000000000
0000000000
0000000000
0000000000
0011100000
0010100000
0011100000
0000000000
0000000000
0000000000
*/

test(3,5,2,10);
/*
0000000000
0000000000
0000000000
0111110000
0100010000
0100010000
0100010000
0111110000
0000000000
0000000000
*/
//出力結果は見易さのため加工しています。


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

function test(centerX, centerY, rectSize, fieldSize){
  return [...Array(fieldSize)].map( (_, y) => 
    [...Array(fieldSize)].map( (_, x) => 
      ( y == (centerY - rectSize) || y == (centerY + rectSize) ) && (centerX - rectSize) <= x && x <= (centerX + rectSize)
      ||
      ( x == (centerX - rectSize) || x == (centerX + rectSize) ) && (centerY - rectSize) <= y && y <= (centerY + rectSize)            
    )
  );
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/09/16 15:12

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

    キャンセル

  • 2017/09/16 15: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)

    この部分でして、極一般的な真偽値を返す論理式です。

    キャンセル

  • 2017/09/16 15:54

    @Lhankor_Mhyさん

    ご回答ありがとうございます!
    今日から勉強の一環で本サービス利用しており、理解できておらず恐縮です…

    ご回答いただいたコードの解釈ですが、

    Y軸が基準点から四角形(半径)の範囲に該当する、且つ四角形の範囲内のX軸の場合はtrue、
    または
    X軸が基準点から四角形(半径)の範囲に該当する、且つ四角形の範囲内のY軸の場合はtrue、

    であっておりますでしょうか?

    キャンセル

  • 2017/09/16 16:03

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

    キャンセル

  • 2017/09/16 16:07

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

    キャンセル

+2

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

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

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

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

var map = [];
var col = 10;    // マップ:列
var row = 10;    // マップ:行
var set = {
    col: 5,    // 基準フラグの位置:6列目
    row: 3    // 基準フラグの位置:4行目
};

for (var i=0; i<col; ++i) {
    map[i] = [];
    for (var j=0; j<row; ++j) {
        map[i][j] = '◯';
    }
}

function test_array(centerX, centerY, rectSize){
    let test_array = [];
    let size_x = rectSize * 2 + 1;
    for(var i = 0; i < size_x ; ++i) {
        test_array.push([centerX-rectSize+i, centerY-rectSize]); 
        test_array.push([centerX-rectSize+i, centerY+rectSize]);
    }
    let size_y = rectSize * 2 - 1;
    for(var j = 0; j < size_y ; ++j) {
        test_array.push([centerX-rectSize, centerY-rectSize+j+1]); 
        test_array.push([centerX+rectSize, centerY-rectSize+j+1]);
    }
    return test_array;
}
function array_reverse(map,arr,size){
    arr.forEach(function(val){
        if(val[0] >= 0 && val[0] < size[0] && val[1] >= 0 && val[1] < size[1]){
            map[val[0]][val[1]] = map[val[0]][val[1]] === '◯' ? '◎' : '◯';
        }
    })
    return map;
}

arr = test_array(set.col, set.row, 3);//ここの第三引数が反転箇所の半径
result = array_reverse(map,arr,[col,row]);
console.log(result);


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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/09/16 17:08

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

    キャンセル

  • 2017/09/16 17:10

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

    キャンセル

  • 2017/09/16 19:25 編集

    @te2ji さん
    ご回答いただきありがとうございます!

    > 効率を求めるのであれば、
    > ・rectSize によって決定される、反転座標の配列を作成
    > ・反転座標の配列を元に入力値にその座標があれば、反転させる
    > といった操作になると思います。
    上記ですが、理解できず申し訳ないのですが…
    もう少し掘り下げると下記のような解釈でしょうか?

    現状は、Array[0][0] 〜 Array[9][9]まで配列の全てを走査していますが、
    図解でいう、6列目・4行目(Array[5][3])を始点としてそこから rectSize の間に限定した配列を別途用意し判定、
    その後上記の判定結果を本配列と同様の箇所と差し替える?

    という理解であっておりますでしょうか。

    キャンセル

  • 2017/09/16 20:14

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

    キャンセル

  • 2017/09/16 22:30 編集

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

    キャンセル

  • 2017/09/16 22:59

    > if(val[0] >= 0 && val[0] < size[0] && val[1] >= 0 && val[1] < size[1])
    php 脳では配列の存在確認で分かりやすい条件が書けると思っていたのですが、JavaScript での書き方がわからなかったため、かなり汚い書き方になりました。
    ので、こんな条件書くぐらいだったら統合しちゃえ。って意味です。

    コードとしてはかなり汚いので、ざっと流れが追えれば、いいかな。ぐらいで見てください。正直、回答として晒しているのがかなり恥ずかしいです。。。

    キャンセル

  • 2017/09/16 23:09 編集

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

    キャンセル

  • 2017/09/16 23:23

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

    キャンセル

  • 2017/09/16 23:36 編集

    全体の走査はしていないです。

    コードの概要は、以下の通り。

    test_array の2つの for で反転すべき配列を作っています。
    ◎◎◎◎◎
    ◎○○○◎
    ◎○○○◎
    ◎○○○◎
    ◎◎◎◎◎

    最初の for が四角形の上下(◎◎◎◎◎)
    2つ目の for が四角形の左右の配列を作っています。(◎○○○◎)

    arr = test_array(set.col, set.row, 3);
    console.log(arr);
    とでもしてやると分かりやすいです。

    array_reverse では、反転すべき配列の入った arr を forEach しています。
    まず、map 範囲内か確認した後、map の arr 座標を反転します。
    forEach するのは arr なので、全体を走査することはありません。

    キャンセル

  • 2017/09/16 23:42

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

    キャンセル

  • 2017/09/17 00:29 編集

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

    キャンセル

  • 2017/09/17 15:15

    > 他にも2進数で、フラグ操作するとかもあると思います。
    初心者向けの参考書には載ってない気がするなぁ。。。
    あんまりきれいなコードで書ける気がしないですが、あとでやってみます。
    ただ、こういうのは、きれいなコードで見ないと、理解しづらいかも。

    あと、今更ですが、今回の回答のコード、console.log で出力すると、x,y が入れ替わっちゃうので、感覚的にわかりにくいですね^^;

    修正はしませんので、読み替えてくださいw

    キャンセル

  • 2017/09/18 00:45

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

    キャンセル

  • 2017/09/20 06:59 編集

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

    キャンセル

  • 2017/09/20 08:25

    ありがとうございます^^

    キャンセル

0

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

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

var map = [];
var col = 10;    // マップ:列
var row = 10;    // マップ:行
var rectSize = 3;    // 半径
var set = {
    col: 5,    // 基準フラグの位置:6列目
    row: 3,    // 基準フラグの位置:4行目
};

for (var i=0; i<row; ++i) {
    map[i] = 0;
    // map[i] = Math.floor( Math.random() * Math.pow(2, row));
}

function view(map,col,row){//map表示用の関数。ロジックとはあまり関係ないです。
    let result = [];
    let tmp = [];
    for (var j = 0; j < row; ++j) {
        result[j] = '';
        tmp[j] = (Array(col).join('0') + map[j].toString(2)).slice(-col);
        let n = tmp[j].length;
        for (var k = 0; k < n; ++k) {//左上を(0,0)とするための処置。ひっくり返してます。
            result[j] = result[j] + tmp[j][n - k - 1];
        }
        result[j] = result[j].replace(/0/g,'●').replace(/1/g,'○')//文字サイズを揃えるため、○と●に変更しました。
    }
    return result;
}

function test_array(map, set, rectSize, col, row){
    let result_array = [];
    centerX = set.col;
    centerY = set.row;
    console.log(centerX - rectSize,centerX + rectSize)
    if(centerX - rectSize < 0 && centerX + rectSize > col){//ここの条件は、左上を(0,0)にするため、すべて左右が逆になっていることに注意
        console.log('left right');
        //上と下用のマスク用の数値
        top_bottom = parseInt(Array(col + 1).join('1'), 2);
        //左右用のマスク用の数値
        left_right = 0;
    } else if (centerX - rectSize < 0){
        console.log('left',centerX + rectSize,col - (rectSize + centerX));
        top_bottom = parseInt(Array(col - (centerX + rectSize + 2)).join('0') + Array(centerX + rectSize + 2).join('1'), 2);
        left_right = parseInt(Array(col - (centerX + rectSize + 2)).join('0') + '1' + Array(centerX + rectSize + 1).join('0'), 2);
    } else {
        console.log('other');
        top_bottom = parseInt(Array(centerX - rectSize).join('0') + Array((rectSize + 1) * 2).join('1') + Array(centerX - rectSize + 1).join('0'), 2);
        left_right = parseInt(Array(centerX - rectSize).join('0') + '1' + Array((rectSize) * 2).join('0') + '1' + Array(centerX - rectSize + 1).join('0'), 2);
    }
    map.forEach(function(val, key){
        if(key === centerY - rectSize || key === centerY + rectSize){//上下
            result_array[key] = map[key] ^ top_bottom;
        } else if(key > centerY - rectSize && key < centerY + rectSize){//左右
            result_array[key] = map[key] ^ left_right;
        } else {
            result_array[key] = map[key] ^ 0;//関係ないところ
        }
    })
    return result_array;
}
console.log(view(test_array(map, set, rectSize, col, row),col,row));

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/09/20 01:09

    Strict Mode にすると、ReferenceError が4つ程、発生するようです。
    https://jsfiddle.net/ew9kghm4/
    let で宣言したコードがこちら。
    https://jsfiddle.net/ew9kghm4/1/

    キャンセル

  • 2017/09/20 04:24

    指摘ありがとうございます。

    ただ、それ直したぐらいじゃ、合格点になるようなスクリプトじゃないんですよね^^;
    test_array の中の処理とか、ひどいしw

    あー、だれか分かりやすいキレイなコード、提供してくれないかなぁ~^^

    キャンセル

0

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

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

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

CoffeeScript2で実装してみました。

class Rect
  constructor: ({@x, @y, size, @width = size, @height = size}) ->
    @map = ({flag: false, x: x, y: y} for x in [0...@width] \
        for y in [0...@height])
    @listByDistance = []
    for x in [0...@width]
      for y in [0...@height]
        distance = Math.max(Math.abs(@x - x), Math.abs(@y - y))
        @listByDistance[distance] ?= []
        @listByDistance[distance].push(@map[y][x])
    @count = 0
    @onMap()

  countUp: ->
    @offMap()
    @count++
    @onMap()

  onMap: ->
    return 0 unless @listByDistance[@count]?
    (point.flag = true for point in @listByDistance[@count]).length


  offMap: ->
    return 0 unless @listByDistance[@count]?
    (point.flag = false for point in @listByDistance[@count]).length

  reset: ->
    @offMap()
    @count = 0
    @onMap()

  join: ({tStr = 't', fStr = 'f', colSep = '', rowSep = '\n'}) ->
    (((if point.flag then tStr else fStr) for point in row).join(colSep) \
        for row in @map).join(rowSep)

rect = new Rect({x: 3, y: 5, size: 10})
wrap = document.createElement('div')
document.body.appendChild(wrap)
render = ->
  wrap.innerHTML = rect.join({tStr: '◎', fStr: '○', rowSep: '<br>'})
prevNum = 0
window.addEventListener 'click', ->
  prevNum = if prevNum == 0
    rect.reset()
  else
    rect.countUp()
  render()

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

function test(centerX, centerY, rectSize, fieldSize){
  const makeRectRow = x => ( 2**( x*2+1 ) - 1 )
  const rectRowShift = (n, x) => x > 0 ? n << x : n >>> -x;

  let borderRow = makeRectRow(rectSize); // 一番上と一番下の行
  const interRow = rectRowShift( borderRow ^ ( makeRectRow(rectSize-1) << 1 ), centerX-rectSize); // 中の行

  borderRow = rectRowShift(borderRow, centerX-rectSize);

  return [...Array(fieldSize)].map( (_, y) => {
    if ( (centerY - rectSize) <= y && y <= (centerY + rectSize) ) {
      if ( (centerY - rectSize) == y || y == (centerY + rectSize) ) return borderRow;
      return interRow;
    }
    return 0;
  });
}

test(3,5,2,10).map(e=>[...Array(10)].map((_,i)=>'◯◎'[e>>>i&1]).join(''));


/*
◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◎◎◎◎◎◯◯◯◯
◯◎◯◯◯◎◯◯◯◯
◯◎◯◯◯◎◯◯◯◯
◯◎◯◯◯◎◯◯◯◯
◯◎◎◎◎◎◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
◯◯◯◯◯◯◯◯◯◯
*/


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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/09/20 21:49 編集

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

    キャンセル

  • 2017/09/20 22:03

    ふと思ったのですが、この方式の場合、1のマス目だけ2進数で覚えておけば、0のマス目は記録しておく必要がないですね。
    例えば、Lhankor_Mhy さんが書いたコードの場合、

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

    この部分だけ2進数でフラグマップを作成し、このRectがある座標を記録しておきます。
    文字列化する際には上下左右を〇で埋めてやれば、完成します。
    33マス以上のフィールドには33マス以上のマス目が存在する可能性がある為、この手法をもってしても32bitを分割管理する等の対策が必要ですが、パフォーマンスは稼げる考え方のように思いました。

    キャンセル

  • 2017/09/20 22:50

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

    キャンセル

  • 2017/09/21 10:31

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

    キャンセル

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

  • ただいまの回答率 90.61%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • JavaScript

    16003questions

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