読者です 読者をやめる 読者になる 読者になる

kkana's blog

新米コーダーの忘れそうなことメモ

大量のオブジェクトを処理するときに考えた事(3)(連結リストについて)

大量のオブジェクトを処理するときに考えた事(1)(イテレーターパターンについて) - kkana's blogこれを書いているときに勘違いしていたこと2つめは イレテータパターンと連結リストは同じものだと思っていたこと。

前回

tuitui.hatenablog.com

これでイテレーターパターンはできたかな、と思っていたところ

「結局配列でデータにアクセスしてるんじゃ速さがでないんじゃない??indexふり直さないといけないし・・・」 という指摘をもらえたのでまた考え直しました。

連結リストを使う!

できたもの↓

See the Pen ぶつからないように動くビークル(2) by kanaparty (@kanaparty) on CodePen.

連結リストとは?

連結リスト - Wikipedia

gihyo.jp (このサイト前にも見てるんですが・・今度こそなにやってるかわかった気がする!)

FN1010001 - 連結リスト(linked list) - Flash : テクニカルノート
Action Scriptですが参考にしました。とってもわかりやすい(ありがとうございます)

実際書いた連結リスト

連結リストは

  • 最初と最後がある
  • 結合リストで扱う中身は自分自身の前後の参照をもっている(それ以外は知らない)
  • 全部の中身の処理をするときは次の参照からその次の参照へ、ドミノだおし的な感じでつなげていく

ということで、今回かきなおしたのは上記の機能に

  • 結合リストに中身を追加する
    (中身が空であれば最初と最後を加えられたものに設定、空でなければ前後への参照を設定し、最後を上書きする)
  • 結合リストの中身を削除する
    (前の参照をその前の前のリストの中身の参照に置き換え、後の参照もその後の後の中身に置き換え つなぎ直す。あと自分自身を削除する)

というのを加えました。

  // 連結リストのエレメントを納めて操作する
  var LinkedList = function(){
    this.first = null;
    this.last = null;
  };
  LinkedList.prototype = {
    //LinkedList追加する
    push : function(data){
      var newElm = new Element(data);
      //初めて追加されたのではなければ
      if (this.last){
        //前のelementの次へ参照を持たせる
        this.last.next = newElm;
        //新しいelementの前へlastへの参照をもたせる
        newElm.prev = this.last;
        //最後を上書き
        this.last = newElm;
      }
      //はじめて追加されたら
      else {
        //最初と最後に追加
        this.first = this.last = newElm;
      }
    },
    //取り除く
    remove: function(elm){
      //LinkedListが空でなければ
      if(this.first){
        var removeElm = elm;
        //最初だったら
        if(removeElm === this.first){
          removeElm.next.prev = null;
          this.first = removeElm.next;
        }
        //最後だったら
        else if(removeElm === this.last){
          removeElm.prev.next = null;
          this.last = removeElm.prev;
        }
        else{
          removeElm.prev.next = removeElm.next;
          removeElm.next.prev = removeElm.prev;
        }
        //参照先を空にする
        removeElm = null;
      }
      //空だったら何もしない
      else{
        return;
      }
    }
  }

使ってみる

  var l = new LinkedList();
  for (var i = 0; i < 10; i++) {
    l.push(i);
  }
  var targetElm = l.first;
  while (targetElm) {
  //7番目は削除する
    if(targetElm.data === 7){
      l.remove(targetElm);
    }
    targetElm = targetElm.next;
  }

  var targetElm = l.first;
  while (targetElm) {
    console.log(targetElm);
    targetElm = targetElm.next;
  }
//7番目以外が表示される

粒子系は死ぬ

一般的に粒子系はエミッター(寿命)が設定されているらしいです。
じゃないと増え続ける。 なので今回書き直したものには粒子クラスにisDeadというプロパティを作って 画面の外に出たら死ぬことにしています。

死んだら連結リストから削除します。

前回かいたものnature of code:今日の練習「仲間とぶつからないように動こうとする粒子」 - kkana's blogでは増えれば増える一方だったため
しばらくドラックして粒子を増やしているとすぐカクカクした動きになってしまったんですが
今回書いたものはドラックし続けても画面外に消えたら処理をしないようにしたのでカクカクしにくくなった気がします。