当我尝试更新一个元素时，整个 ArrayList 正在更新 Java 21

Question

我在空闲时间做了一些算法，遇到了一个奇怪的问题。我不明白为什么会发生这种情况。我有两个列表，并且我在两个列表中以完全相同的方式更新元素，但在“惰性”列表中，当我更新一个元素时，所有元素都会更新。

这是代码的重要部分：

public class SegmentTree {
    public static void main(String[] args) {

        List<Integer> a = List.of(1,2,3,4,5,6,7,8);

        SegmentTreeObject segmentTreeObject = new SegmentTreeObject(a);

        segmentTreeObject.build(a);

 segmentTreeObject.list.forEach(s->{
            System.out.println(s.leftPosition + " " + s.rightPosition + " " + s.value);
        });


        segmentTreeObject.updateLazy(new Point(0,7),5);



        segmentTreeObject.lazy.forEach(s->{
            System.out.println(s.leftPosition + " " + s.rightPosition + " " + s.value);
        });

}
}

class SegmentTreeObject{

    List<Node> list;
    List<Integer> original;

    //Lazy tree
    List<Node> lazy;

    int size;

    SegmentTreeObject(List<Integer> obj){
        this.list = new ArrayList<>(Collections.nCopies(4*obj.size(),new Node(100,100,0)));
        this.lazy = new ArrayList<>(Collections.nCopies(4*obj.size(), new Node(0,0,0)));
        this.original = new ArrayList<>(obj);
        this.size = obj.size();
    }

 void updateLazyTree(int start, int end, int left,int right, int node, int newValue){
        if(left>end || right<start){
            return;
        }
        if(start>=left && end<=right){
            this.list.get(node)
                    .updateNode(
                            this.list.get(node).value + (end-start+1) * newValue);

            this.lazy.get(2*node+1)
                    .updateNode(
                            this.lazy.get(2*node+1).value + newValue);


            this.lazy.get(2*node+2)
                    .updateNode(
                            this.lazy.get(2*node+2).value + newValue);

            return;
        }

        int mid = start + (end-start)/2;
        updateLazyTree(start,mid,left,right,2*node+1,newValue);
        updateLazyTree(mid+1,end,left,right,2*node+2,newValue);
    }
void updateLazy(Point range, int value){
        updateLazyTree(0,this.size-1,range.x,range.y,0,value);
    }

}
class Node{
    int leftPosition;
    int rightPosition;
    int value;

    Node(int leftPosition, int rightPosition, int value){
        this.leftPosition = leftPosition;
        this.rightPosition = rightPosition;
        this.value = value;
    }

    public void updateNode (int value){
        this.value = value;
    }

}

lazy 的输出是这样的：

0 0 10
0 0 10
0 0 10
0 0 10
0 0 10
0 0 10
0 0 10

我还检查了调试器，是的，“惰性”列表在一次“updateNode”调用后正在更新实体。

感谢您的宝贵时间！

如果您有任何想法请告诉我；我创建“懒惰”列表可能是错误的。

Answer 1

数一下

new

。这就是您拥有的对象数量。因此，在：

this.list = new ArrayList<>(Collections.nCopies(4*obj.size(),new Node(100,100,0)));

我数..1

new

.

因此，您有一个包含大量条目的列表，但是，只有一个

Node

对象。怎么可能？在本例中，您如何拥有一个

.size()

报告为 32（

obj

是 8 大，然后将其乘以 4）的数组列表 - 但只有一个

Node

对象？

好吧，想象一下这种情况：

我建了一栋房子。

然后我从商店购买了一本地址簿。它有 32 页。我在每一页上写下相同的地址。我盖的那一栋房子的地址。

多田！ 32栋房子！

不完全是。当然，我有 32 个地址。而且它们都是一样的。 1 栋房子，32 页。

同样的情况也发生在这里。您有一个节点对象，以及一个包含 32 个引用的数组列表，全部指向该一个节点对象。改变一个，你就改变了所有的，就像如果你拿着那本有 32 页的地址簿，随机选择一页，走到房子里，从窗户扔一块砖头，然后：无论你打开哪一页，都是同样的原因你的地址簿，如果你走到那里找到的地址，你猜怎么着？窗户坏了。

您需要 32 个节点对象。

this.list = new ArrayList<>();
for (int i = 0; i < 4 * obj.size()) this.list.add(new Node(100, 100, 0));

如果我计算

new

现在被执行的次数，我最终会得到 32 次。事实上，这段代码会做得很好（当然，你还必须修复

this.lazy

）。

如果您觉得这在某种程度上破坏了一切的清洁度，那么，这种方法可以存在于

j.u.Collections

：

public static <T> nTimes(int n, Supplier<T> supplier) {
  if (n < 0) throw new IllegalArgumentException("" + n);
  var list = new ArrayList<T>(n);
  for (int i = 0; i < n; i++) list.add(supplier.get());
  return list;
}

但这种方法根本不存在。它可能永远不会：在很大程度上，

nCopies

根本存在，因为它允许相当令人印象深刻的优化：它可以代表一百万个条目，几乎没有记忆，它只记住一个引用以及数字“一百万” 。

nCopies

就像一本神奇的地址簿，只有 2 页，所以非常小：一页上有一个号码，第二页上有一个地址。出于所有目的，该地址簿就像一本大地址簿（与第一个数字一样多的页数），每一页上都有相同的地址。这听起来不像是一个非常有用的地址簿，而且事实上，

nCopies

很少被使用。但这就是它的目的。 如果你需要这个奇怪的“有很多相同条目的地址簿”东西，

nCopies

非常擅长。

但这根本不是您想要的。所以，真的，只写一个循环。