1

ユーザーが n 要素の行を持つ小さな Web アプリをコーディングしています。ユーザーは、独自の基準に従って、各要素を true/false に切り替える必要があります。

ユーザーが要素を切り替えるたびに、切り替えられた要素が含まれている可能性のある真の要素の「チェーン」の長さを確認する必要があります。例:

0 0 0 0 1 0 1 1 1 ? //if user selects '1', the chain length is 4
0 ? 1 1 0 1 1 0 0 0 //if user selects '1', the chain length is 3
0 0 1 1 1 ? 1 1 0 0 //if user selects '1', the chain length is 6

これを行う最善の方法を考えています。

すべての要素は、JSON オブジェクトと DOM オブジェクト (s など) の両方で表現されます<div>。

1 つのオプションは、クリックするたびに配列全体を単純に実行することです。要素の最大数は約 1000 になるため、これで問題ありません。しかし、これは最も効率的な方法ではないようです。

別のオプションは、クリックされた要素を取得し、false 要素に到達するまで、追加の true 要素をそれぞれカウントしながら後退することです。次に、クリックした要素から同じことを行います。これは私には良いように思えますが、不必要な面倒かもしれません。

この問題に最も適した方法を判断するのに助けが必要です。要因は（驚くべきことではありませんが）-

  1. パフォーマンス - クライアント側で遅延が発生してはなりません - チェーンの長さは即座に決定される必要があります。
  2. 保守性。

この質問は少し主観的に思えるかもしれませんが、おそらくそうかもしれませんが、これは私が気付いていないおなじみの解決策を持つおなじみの問題であるに違いないと考えました。

私はjQueryを使用します。

4

3 に答える 3

2

最初に最も長いチェーンを見つけます。これには、要素を 1 回反復処理する必要があります。

その後、変更された各要素の位置から外側に放射し、最長のチェーンを見つけます。

$('.box').click(function() {
    $('.selected').removeClass('selected');

    var $this = $(this);
    $this.toggleClass('active');

    var $next = $this.nextUntil(':not(.active)');
    var $prev = $this.prevUntil(':not(.active)');

    if ($this.hasClass('active')) {
        var $chain = $next.add($prev).add($this);
    } else {
        var $chain = $next.length > $prev.length ? $next : $prev;
    }

    $chain.addClass('selected');
});

そのチェーンが最長のチェーンよりも長い場合、新しい最長のチェーンが見つかりました。

デモ: http://jsfiddle.net/EDVvN/4/

于 2013-01-31T06:31:05.743 に答える
1

テスト中にブラウザに遅延がなかったという点で、「十分に効率的」と思われるソリューションを思いつきました。1000 個の要素は、ブラウザが処理できる量に比べれば大した量ではありませんが、ユーザーにとっては大した量です (物理的な痛みを感じる前に、約 100 個の要素をクリックすることしかテストできませんでした)。

これは整数の単純な配列で機能し、クリックされたときの個々の入力要素を除いて、DOM の大部分には触れません。整数配列の操作は、並べ替えと集計で得られる速度とほぼ同じであると思います。

//record an array of selected indices
var items = [];

//Delegation will speed things up (hopefully)
$("body").on('change', 'input', function () {
    var $this = $(this);
    var index = $this.index();

    //`items` should only ever contain clicked elements
    //We only have to worry about the one item with each click for now
    if ($this.prop('checked')) {
        items.push(index);
    }
    else {
        items.splice(items.indexOf(index), 1);
    }
    items.sort(function (a, b) { return a - b; });
    var chains = [1];
    var chain = 0;
    try {
        //iterate over the items array.  This should be fast even for 100 items
        items.reduce(function (prev, next) {
            //items are out of order; record currently found chain
            if (next - 1 !== prev) {
                chain++;
                chains.push(1);
            }
            else {
                chains[chain]++;
            }
            return next;
        });
    }
    catch (err) {
        //handle TypeError thrown by `.reduce` on empty array
        //this also accounts for the "0" case (no elements selected)
        chains = [0];
    }
    //Get the longest found chain
    console.log(Math.max.apply(undefined, chains));
});

http://jsfiddle.net/ExplosionPIlls/svUrs/2/

于 2013-01-31T07:01:41.433 に答える
0

クリックされた要素からゼロに到達するまで後方に移動してから前方に移動するというアイデアは、効率的で特に複雑ではないように聞こえます。ただし、これは時期尚早の最適化と見なされる場合があります。1000個の要素をチェックしても、ブラウザーの応答性に影響を与える可能性は低いため（これはテストするのに十分簡単です）、効率の低いアルゴリズムのコーディングが高速であるか、保守が容易であると思われる場合は、間違いなく最良の解決策です。

于 2013-01-31T06:22:33.613 に答える