提问人:WastedxBusted 提问时间:11/15/2023 更新时间:11/15/2023 访问量:76
有没有办法以系统的方式将数组中的小块元素复制并移动到 Java 中新增长的数组中的左侧(log(n))?
is there a way to copy and shift small blocks of elements in an array to the left in a new grown array in java in o(log(n)) in a systematic way?
问:
假设我们有一个数组,它充当隐式二进制堆,我们从:
[0, 0, 0]
它慢慢地被填满:
[3, 2, 3]
我们需要通过将其复制到大小为 2n + 1 的新增长数组中来扩展它,其中 n 是旧数组的长度,但这次我们将一些元素块复制到增长数组中的某些位置,例如:
[0, 3, 0, 2, 3, 0, 0]
假设上面的数组被填满了,我们需要再次增长,它看起来像这样:
[5, 3, 5, 2, 3, 4, 5]
|
|
\|/
[0, 5, 0, 3, 5, 0, 0, 2, 3, 4, 5, 0, 0, 0, 0]
我希望你现在明白了转变的模式。
那么有没有办法使用 System.arraycopy() 在 o(log(n)) 中实现这种转换模式的方式?如果没有,您能否建议任何其他替代方案。
答:
"...我们需要通过将其复制到大小为 2n + 1 的新增长数组来扩展它,其中 n 是旧数组的长度,但这次我们将一些元素块复制到增长数组中的某些位置......”
下面是一个没有 arraycopy 的示例。
int[] increase(int[] a) {
int[] na = new int[(a.length * 2) + 1];
for (int i = 1, j = 0, n = na.length; i < n; i += 2, j++)
na[i] = a[j];
return na;
}
输出
a = [3, 2, 3]
na = [0, 3, 0, 2, 0, 3, 0]
评论
这里有几点需要注意。
首先,观察通常的策略,即拥有一个可以有效地向右扩展的数组。
一个例子是 C++。
稍微简化一点,数组具有显式大小和隐式容量。
分配的内存与容量匹配。
使用的内存与大小匹配。
当我们扩展数组并且大小小于容量时,我们开始使用下一个分配的元素 O(1) 成本。
当大小等于容量时,我们创建一个两倍大的副本,将内容移动到那里,然后开始使用新副本。std::vector
请注意,此操作为 O(size)。 但是由于它发生在容量 1、2、4、8、16、32...,因此总运行时间也是 O(大小)。 这称为摊销复杂度 O(1)。 从形式上讲,对于每 k 个操作,前 k 个操作都在 O(k) 时间内完成。 有些手术很昂贵,但很少见。
有一些方法可以创建一个可扩展的数组,其中每个操作的成本是实际的 O(1),而不是摊销,代价是更大的常数因子。 其中一种方法是提前创建下一个数组,同时维护数组的两个副本,并且每增加一个副本,就将另外两个元素复制到下一个数组中。 如果这是重点,那么它值得一个单独的问题。
其次,在扩展底层容器后,无论如何都可以在 O(log n) 中有效地将元素插入二进制堆中。 只需将元素添加为最后一个元素,然后对其进行筛选,直到它停止。 因此,如果我们对每个操作的摊销 O(log n) 感到满意,我们可以只使用上述策略进行扩展和自然堆插入操作。唯一的问题是,如果我们想要真正的 O(log n),而不是摊销,那么它就值得在问题中明确提及。
第三,如果坚持在容器扩容时对元素进行重新排序,其成本与容器扩容成本相同。 请记住,在每次扩展时,我们必须将旧内容复制到新数组中,这需要 O(size) 时间。 好吧,此时此刻,我们可以复制到我们选择的地方,而不是相同的地方。 在您的示例中,我们选择 [0]->[1]、[1,2]->[3,4]、[3,4,5,6]->[7,8,9,10],依此类推。
如果真的需要,就像摊销的 O(1) 被转换为每个元素添加的实际 O(1) 一样,我们可以提前创建下一个数组,并在每次添加时再复制两个元素。 但是,我们必须维护这两个副本,因此,堆操作的 O(log n) 也将具有更大的常数因子。
下一个:我如何获得总成本和要添加的食物
评论
for (int i=0,j=1,k=1; i<len; i+=k,j+=2*k,k*=2) arraycopy(src, i, dst, j, min(k, len-i));
O()