Python或Javascript如何管理调整数组大小？

Question

这两种语言如何调整数组的大小？ 所以，假设我创建了一个包含10个索引的数组，然后我需要添加一个元素。在java中，我会将数组的大小增加一倍并不断添加。在JS和Python这样的语言中，它们使用什么机制来调整数组的大小？你知道吗

它们是否也将内存中数组的大小增加了一倍？你知道吗

Answer 1

CPython的相关代码是here：

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

所以不，它的尺寸不会增加一倍。如果追加/扩展将导致列表的长度为newsize，则支持数组的分配内存将增长到大约该长度加上八分之一。你知道吗

对于Java OpenJDK 7 ArrayLists：

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

所以需要额外的一半容量。你知道吗

请使用ArrayList而不是管理自己的调整大小数组。你知道吗