効率的な方法ですべての一致を見つけ、ある配列を別の配列と比較することはできません

Question

私はknockoutJSを使ってタグシステムを使ってリストシステムを作っています。アイデアは、異なるタグを持つ複数のリストを持っているし、任意のマッチを表示することであるタグ（0、1または複数のタグ）の独自のセットを持つ各

-

「アイテム」の中央リストがあります。例えば

： -

item 1 - tags 1,3 
item 2 - tags 2,4 
item 3 - tags 4 
item 4 - tags NONE 

とシステム、アイテムを拾うために「いいえリスト」（のための「いいえタグ」の1と1で生成され

List 1 - tags 1,2 
List 2 - tags 3 

プラス2余分なリストタグとリストにそれぞれ一致しないアイテムはありません）。

これはにつながる： -

List NO TAGS = item 4 
List NO LIST = item 3 
List 1  = item 1, item 2 
List 2  = item 1 

私は複数のループを実行し、各リストで開催された項目をリセットしています現時点ではと私が午前問題は、リストに項目をソートするための効率的な方法であります変更が行われるたびに

次のコードは、私が知っている醜いです、それは参照のためのより多くのですが、私は質問が下

UGLY WORKING例

に示すデータ構造にタグを比較するための最も効率的な方法とは何かあるとし

ko.computed(function() { 
//clear all items in arrays 
ko.utils.arrayForEach(self.lists(), function (list) { 
    list.items([]); 
}); 
var onList; //does this item appear on a list yet 
//loop through all items and then all lists to see if an item matches any tags on that list and if so add it. 
ko.utils.arrayForEach(self.items(), function (item) { 
    onList = 0; //reset whether found - used for adding to 'No List' 
    ko.utils.arrayForEach(self.lists(), function (list) { 


      //if an item has no tasks then add to list id - 2 'No Tags' List 
      if (item.tags().length == 0 && list.id() == -2) { 
       list.items.push(item); 
       onList = 1; //found a list 
      } else { 
       //now for each item loop through tags and then loop through lists tags and find any matches 
       ko.utils.arrayFirst(item.tags(), function (tag) { 
        var found = 0; 

        ko.utils.arrayFirst(list.tags(), function (listTag) { 

         console.log(listTag, tag); 
         if (parseInt(listTag) == parseInt(tag)) { 
          list.items.push(item); 
          found = 1; 
          onList = 1; 
          //at least one tag matches, so exit 
          return 1; 
         } 
        }); 

        if (found == 1) { 
         //at least one tag matches, so exit 
         return 1; 
        } 
       }); 
      } 
     }); 
     //there were no matches in any of the lists so add this to the list 'No List' 
     if(onList == 0 && self.lists().length > 1){ 
       self.lists()[1].items.push(item); 
     } 

    }); 
}); 

データ構造

///4 lists - the first 2 are system generated 'catch' lists 
var listData = [ 
    {id: -2, name: "NO TAGS", tags: [ 
      //NOT APPLICABLE AS HANDLED BY CODE 
     ] 
    }, 
    {id: -1, name: "NO LIST", tags: [ 
      //NOT APPLICABLE AS HANDLED BY CODE 
     ] 
    }, 
    {id: 1, name: "List 1", tags: [ 
      2 
     ] 
    }, 
    {id: 2, name: "List 2", tags: [ 
      1, 3 
     ] 
    } 
]; 

//2 sets of items 
var itemData = [ 
    {id: 1, name: "Item 1", addedBy: 1, tags: [ 
      1 
     ]}, 
    {id: 2, name: "Item 2", addedBy: 1, tags: [ 
      2, 3 
     ]} 
]; 

Answer 1

私は明確な答えを得ておらず、あなたがhttps://codereview.stackexchange.com/にもっと多くの回答を得るかもしれないのだろうかと疑問に思います。

これはコメントでは少し長いですが、それほど答えはありません。それはとにかく便利だと思います。

私はあなたのアプローチがあまりにも悪いとは思わない - 問題を解決するための不可欠なコードブロックとして、明らかに仕事をしている。おそらく、list.tags（）とitem.tags（）の共通部分を計算して、それらのうちの1つをハッシュに変換することができます。しかし、一致が見つかると直ちに両方のループを終了するためにarrayFirstをうまく利用します。

現代JS &ブラウザでは、時間のかかる大きなリストのためにおそらくこのことが起こります。この問題は、特にKOの場合、おそらくブラウザーでリストを表示することによって発生します。既にパフォーマンスの問題に気づいたことがありますか、より学術的な観点からこの問題について疑問に思っていますか？

これは、KOがDOMで物事を作成するのがかなり遅いためです.1000項目のリストは、1000項目のHTML文字列を作成してから挿入すると目立ちますそれはコンテナのinnerHTMLプロパティを使用してDOMに1回で移動します。あなたは1で、リスト1に項目を追加する場合は、

list.items.push(item); 

と

self.lists()[1].items.push(item); 

これに伴う問題は、ここで便利なブログの記事で説明されていて、あなたのコード内で行うように、これは、特にそうです。

http://www.knockmeout.net/2012/04/knockoutjs-performance-gotcha.html

ブログ記事は、その後、repopulaそのアプローチの中ので、一度にそれぞれのリストをクリアして、あなたのコードをあなたのobservableArraysを設定することをお勧めしますあなたが一時的な配列にあなたのマッチを格納するためにそれを少し書き直している限り、それはうまくいくでしょう、そして、一度にobservableにそれらを入れてください。

もう1つ注意すべき点は、4つのリストがあることです。上記を実行しても、各リストが読み込まれるとUIを再描画するための4つの通知が生成されます。あなたは延期アップデートを利用することによってこの問題を回避できます。

http://knockoutjs.com/documentation/deferred-updates.html

あなたのアルゴリズムは、リスト上のアイテムをループしてアイテムが与えられたリストに属している場合ワークアウトして、各リストを構築するアプローチを採用しています。リストを破壊しない別の方法は、アイテムをループしてリストを作成する方法です。リストからアイテムを追加または削除する必要がある場合は、各アイテムをワークアウトします。アルゴリズム的には、アイテムとすべてのリストをループして、その中でリストフィルタとアイテムタグの共通部分を計算する必要があるので、それがもっとうまくいくとは思えません。 KOの観点から見ると、リストからアイテムを追加または削除するたびにobservableArrayが変更されるため、そこではもっと高速になるとは思われません。

KOはプログラミングの機能的スタイルを促進する傾向があり、その観点からは、あなたのコードが醜いと主張することができます。機能スタイルを使用すると、ko.computed関数からリストの一致を生成できます。何か変更があるたびに明示的に各リストを空にする必要はありません。おそらくこれは、KOの依存関係追跡が、DOMを再レンダリングしないという点でリストが変化しないときに何かを巧妙にすることを可能にするでしょうか？この例として、私はこのバイオリンを書いた：

https://jsfiddle.net/325gp71a/3/

いくつかのことをそれがない：

は私が述べているハッシュを利用することがdeferUpdates

// Using deferUpdates=true will help performance when altering the lists. 
// - When true, all lists will be recalculated before UI redrawing 
// - When false, as each list changes the UI will redraw 
// In my browser ,the time taken to add lots of items when clicking the test 
// button is: 
// - deferUpdates=false takes approx 10 seconds 
// - deferUpdated=true takes approx 4 seconds 
// 
ko.options.deferUpdates = true; 

をご利用くださいタグ/フィルタの交点を少し速くする：

// Reduce the filter to a hash to remove one loop from the matching process. 
// The filter [2,3] will become the hash {2: true, 3: true} 
this.hash = {} 
ko.utils.arrayForEach(this.filter, function(f) { 
    this.hash[f] = true 
}.bind(this)) 

....skip a bit of code, then.... 

match = ko.utils.arrayFirst(tags, function(tag) { 
    return this.hash.hasOwnProperty(tag) 
}.bind(this)) 

observableArraysはむしろobservableArrayにアイテム一つ一つを追加するよりも、単に一度に設定されていることを確認：項目については

：

// Once all the new items are ready, put them into the observableArray 
    // on one go. 
    new_items = this.items().concat(new_items) 
    this.items(new_items) 

リストの一致、このそれはko.computedであることを通じて行われます。このリストが変更されていないため場合、計算の値は変更しないでください、とKOはDOMのこのビット再レンダリングする必要はありません。最後に

// Find the matches for this list. 
this.matches = ko.computed(function() { 
    var matches = [] 

    ... do the logic ... 

    // Done. 
    return matches 
}, this) 

を、私は評価するために、テストボタンのカップルを追加しましたパフォーマンス。 1つのボタンは、さまざまなランダムタグを持つ1000個のアイテムを追加し、私のブラウザには4秒かかっています。これは、KOがDOMを操作するまで完全にダウンしています。 deferUpdates=trueここで助けてください。それがなければ、約10秒かかります。これは、deferUpdatesがDOMを描画する前にすべての計算結果が評価されることを保証するためです。それがなければ、DOMはより頻繁に再描画されます。

もう1つのテストではアイテムの1つが変更され、あるリストから別のリストに素早く再描画されます。変更はブラウザ内で瞬時に表示されます。各計算はこの変更によって再評価されますが、KOの依存関係追跡はリスト全体を再描画せずにその差を再描画できるため、速くなります。