Самый быстрый способ найти индекс дочернего элемента node в родительском

Я хочу найти индекс дочернего div, который имеет id 'whereami'.

<div id="parent">
   <div></div>
   <div></div>
   <div id="whereami"></div>
   <div></div>
</div>

В настоящее время я использую эту функцию для поиска индекса дочернего элемента.

function findRow(node){
    var i=1;
    while(node.previousSibling){
        node = node.previousSibling;
        if(node.nodeType === 1){
            i++;
        }
    }
    return i; //Returns 3
}

var node = document.getElementById('whereami'); //div node to find
var index = findRow(node);

скрипт: http://jsfiddle.net/grantk/F7JpH/2/

Проблема
Когда есть тысячи узлов div, цикл while должен проходить через каждый div, чтобы подсчитать их. Это может занять некоторое время.

Есть ли более быстрый способ справиться с этим?

* Обратите внимание, что идентификатор изменится на разные divs node, поэтому он должен будет иметь возможность пересчитать.

Ответы

Ответ 1

Из любопытства я запустил ваш код против jQuery .index() и моего нижеследующего кода:

function findRow3(node)
{
    var i = 1;
    while (node = node.previousSibling) {
        if (node.nodeType === 1) { ++i }
    }
    return i;
}

Перейти к результатам jsperf

Оказывается, что jQuery примерно на 50% медленнее, чем ваша реализация (на Chrome/Mac), а моя, возможно, превысила ее на 1%.

Edit

Нельзя допустить этого, поэтому я добавил еще два подхода:

Использование Array.indexOf

[].indexOf.call(node.parentNode.children, node);

Улучшение моего предыдущего экспериментального кода, как показано в HBP answer, DOMNodeList рассматривается как массив и использует Array.indexOf() для определения позиции внутри его .parentNode.children, которые являются всеми элементами. Моя первая попытка заключалась в использовании .parentNode.childNodes, но это дает неправильные результаты из-за текстовых узлов.

Использование previousElementSibling

Вдохновленный user1689607 answer, последние браузеры имеют еще одно свойство помимо .previousSibling. previousElementSibling, который делает оба оригинальных оператора в одном. IE <= 8 не обладает этим свойством, но .previousSibling уже действует как таковой, поэтому функция будет работать.

(function() {
    // feature detection
    // use previousElementSibling where available, IE <=8 can safely use previousSibling
    var prop = document.body.previousElementSibling ? 'previousElementSibling' : 'previousSibling';

    getElementIndex = function(node) {
        var i = 1;
        while (node = node[prop]) { ++i }
        return i;
    }

Заключение

Использование Array.indexOf() не поддерживается в IE <= 8 браузерах, и эмуляция просто недостаточно быстро; однако это дает 20% улучшение производительности.

Использование функции обнаружения и .previousElementSibling дает 7-кратное улучшение (в Chrome), мне еще предстоит проверить его на IE8.

Ответ 2

Кооптируя Array indexOf, вы можете использовать:

  var wmi = document.getElementById ('whereami');
  index = [].indexOf.call (wmi.parentNode.children, wmi);

[Проверено только в браузере Chrome]

Ответ 3

Я добавил два теста в jsPerf test. Оба используют previousElementSibling, а второй - код совместимости для IE8 и ниже.

Оба из них очень хорошо работают в современных браузерах (которые в настоящее время используются большинством браузеров), но в старых браузерах они будут иметь небольшой успех.

Здесь первый, который не содержит исправления совместимости. Он будет работать в IE9 и выше, а также почти во всех Firefox, Chrome и Safari.

function findRow6(node) {
    var i = 1;
    while (node = node.previousElementSibling)
        ++i;
    return i;
}

Здесь версия с исправлением совместимости.

function findRow7(node) {
    var i = 1,
        prev;
    while (true)
        if (prev = node.previousElementSibling) {
            node = prev;
            ++i;
        } else if (node = node.previousSibling) {
            if (node.nodeType === 1) {
                ++i;
            }
        } else break;
    return i;
}

Поскольку он автоматически захватывает братья и сестры, для nodeType не требуется никаких тестов, а цикл короче в целом. Это объясняет большой рост производительности.

Я также добавил одну последнюю версию, которая петлирует .children и сравнивает node с каждым.

Это не так быстро, как версии previousElementSibling, но все же быстрее других (по крайней мере, в Firefox).

function findRow8(node) {
    var children = node.parentNode.children,
        i = 0,
        len = children.length;
    for( ; i < len && children[i] !== node; i++)
        ; // <-- empty statement

    return i === len ? -1 : i;
}

Возвращаясь к версии previousElementSibling, вот настройка, которая может немного повысить производительность.

function findRow9(node) {
    var i = 1,
        prev = node.previousElementSibling;

    if (prev) {
        do ++i;
        while (prev = prev.previousElementSibling);
    } else {
        while (node = node.previousSibling) {
            if (node.nodeType === 1) {
                ++i;
            }
        }
    }
    return i;
}

~~Я не тестировал его в jsPerf, но~~, разбивая его на два разных цикла, основанные на присутствии previousElementSibling, только помогло бы мне подумать.

~~Возможно, я немного добавлю его.~~

Я пошел вперед и добавил его к тесту, связанному в верхней части этого ответа. Это немного помогает, поэтому я думаю, что это, вероятно, стоит того сделать.

Ответ 4

Поскольку вы используете jQuery. индекс должен сделать трюк

jQuery('#whereami').index()

но как вы собираетесь использовать индекс позже?

Ответ 5

Попробуйте следующее:

function findRow(node) {
    var i = 1;
    while ((node = node.previousSibling) != null) {
        if (node.nodeType === 1) i++;
    }
    return i; //Returns 3
}

Ответ 6

Небольшое улучшение по сравнению с решением Джека, улучшение на 3%. Очень странно.

function findRow5(node)
{
    var i = 2;
    while (node = node.previousSibling)
        i += node.nodeType ^ 3;
    return i >> 1;
}

Поскольку в этом случае (и в большинстве случаев) существует только два возможных nodeType:

Node.ELEMENT_NODE == 1
Node.TEXT_NODE == 3

Итак, xor 3 с nodeType, даст 2 и 0.

http://jsperf.com/sibling-index/4

Ответ 7

Вообще говоря, небольшая разница в производительности имеет незначительный эффект, если код не выполняется в цикле. Необходимость запуска кода один раз, а не каждый раз будет значительно быстрее.

Выполните одно из следующих действий:

var par = document.getElementById('parent');
var childs = par.getElementsByTagName('*');
for (var i=0, len = childs.length;i < len;i++){
  childs[i].index = i;
}

Впоследствии найти индекс так же просто, как:

document.getElementById('findme').index

Похоже, что все, что вы делаете, может быть полезно благодаря более чистым отношениям между DOM и javascript. Рассмотрим обучение Backbone.js, маленькую библиотеку MVC javascript, которая упрощает управление веб-приложениями.

edit: Я удалил используемый jQuery. Обычно я не использую его, но там предпочтение отдается SO, поэтому я предположил, что он все равно будет использоваться. Здесь вы можете увидеть очевидную разницу: http://jsperf.com/sibling-index/8

Ответ 8

Самый быстрый способ - выполнить двоичный поиск, сравнив позиции документа элементов. Чем больше элементов у вас есть, тем выше потенциал для производительности. Например, если у вас было 256 элементов, то (оптимально) вам нужно было бы проверить только 16 из них! Для 65536 всего 256! Производительность возрастает до 2! См. Больше номеров/статистики. Посетите Wikipedia.

(function(constructor){
   'use strict';
    Object.defineProperty(constructor.prototype, 'parentIndex', {
      get: function() {
        var searchParent = this.parentElement;
        if (!searchParent) return -1;
        var searchArray = searchParent.children,
            thisOffset = this.offsetTop,
            stop = searchArray.length,
            p = 0,
            delta = 0;

        while (searchArray[p] !== this) {
            if (searchArray[p] > this)
                stop = p + 1, p -= delta;
            delta = (stop - p) >>> 1;
            p += delta;
        }

        return p;
      }
    });
})(window.Element || Node);

Затем способ, которым вы его используете, - получить свойство parentIndex любого элемента. Например, ознакомьтесь со следующей демонстрацией.

(function(constructor){
   'use strict';
    Object.defineProperty(constructor.prototype, 'parentIndex', {
      get: function() {
        var searchParent = this.parentNode;
        if (searchParent === null) return -1;
        var childElements = searchParent.children,
            lo = -1, mi, hi = childElements.length;
        while (1 + lo !== hi) {
            mi = (hi + lo) >> 1;
            if (!(this.compareDocumentPosition(childElements[mi]) & 0x2)) {
                hi = mi;
                continue;
            }
            lo = mi;
        }
        return childElements[hi] === this ? hi : -1;
      }
    });
})(window.Element || Node);

output.textContent = document.body.parentIndex;
output2.textContent = document.documentElement.parentIndex;

Body parentIndex is <b id="output"></b><br />
documentElements parentIndex is <b id="output2"></b>