1

我正在编写一个小型 Web 应用程序，其中用户将有一行 n 个元素，并且他需要根据自己的标准将每个元素切换为真/假。

每次用户切换元素时，我都必须检查切换元素可能属于的真实元素“链”的长度。例子：

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 对象（例如<div>s）中具有表示形式。

一种选择是每次单击都简单地遍历整个阵列。这没关系，因为元素的最大数量约为 1000。但这似乎不是最有效的方法。

另一种选择是获取单击的元素并在计算每个额外的真实元素时后退一步，直到到达虚假元素。然后从单击的元素开始执行相同的操作。这对我来说似乎更好，但也许这是不必要的麻烦。

我需要帮助来决定哪种方法最适合这个问题。因素是（不足为奇） -

  1. 性能 - 它不能在客户端造成任何滞后 - 必须立即确定链长度。
  2. 可维护性。

我意识到这个问题可能看起来有点主观，也许确实如此，但我认为这一定是一个熟悉的问题，有一个我不知道的熟悉的解决方案。

我将使用 jQuery。

4

3 回答 3

2

我会先找到最长的链。这将需要遍历您的元素一次。

之后，从每个变化元素的位置向外辐射，找到最长的链。

$('.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 回答