从 LinkedList 中获取 entry/node 最快

Question

从 LinkedList.java 我找到了这个获取条目的方法。

/**
 * Returns the indexed entry.
 */
private Entry<E> entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

让我烦恼的是：

    if (index < (size >> 1))

这里为什么要做位移操作？这样的东西不是最优的吗？

if (index < (size / 2)) {
    for (int i = 0; i <= index; i++)
        e = e.next;
} else {
    for (int i = size; i > index; i--)
        e = e.previous;
}

自

if (index < (size / 2))

保证我们请求的索引在列表的前半部分。

Answer 1

没有理由在代码示例中将位移位右移一位：除以二将具有相同的性能，并且可能比位移位具有更好的可读性。这种微优化在过去的 C 语言中很常见，但现在每个称职的优化器都会为您做这种替代。

Answer 2

实际上没有。如果硬件级别非常快，则移位操作。这就像连接电线（位）并丢弃移位的电线。这仅适用于整数运算和 "for base 2 divisions" 所以请注意。

从 LinkedList 中获取 entry/node 最快

Get entry/node from LinkedList fastest

java

optimization

doubly-linked-list