为什么创建一个对象的副本仍然会改变原始对象的实例变量？

Question

我有两个 class。 Class Algorithm 实现了一个方法 findIntersections()，它是一个 sweep line algorithm 在 O(nLogN) 时间内检查交叉点的方法。

它还实现了一个函数addSegments，它根据x坐标将Segment类型的对象（两点）添加到一个优先级队列中。

public class Algorithm {
 
    public PriorityQueue pQueue = new PriortiyQueue();

    //This function adds objects of type Segments to a priority queue
    public void addSegments(List<Segment> segments) {
        pQueue.add(segments);
        //do something
    }

    //This function implements a sweep line algorithm to check for Intersections.
    public void findIntersection() {
        while (!pQueue.isEmpty()) {
            p.poll(); //removes element from Queue
            // do something
        }
    }
}

另一个class Model 将CSV 文件中的数据加载到优先级队列中。这是一个密集的过程，我只想做一次。

另一方面，checkForCollissions 被调用了数百万次。

我想检查提供的段与 csv 文件中添加到优先级队列中的其余段之间的冲突

我不想每次都从头开始向优先级队列添加元素。这不可行。

 public class Model  {
     public Algorithm algoObj = new Algorithm();
     public ArrayList<Segment> algoObj = new ArrayList<>();
     public ArrayList<Segment> segments = new ArrayList<>();
     public ArrayList<Segment> single_segment = new ArrayList<>();

     public boolean loadCSV() {
         //read csv file
         while ((strLine = br.readLine()) != null) {
           segments.add(new Segment()); //Add all segments in CSV file to ArrayLisyt
           algo.addSegments(segments);  //Adds 4000 objects of type segment to priority Queue
         }
     }

     //This function is called millions of times
     public boolean checkForCollisions(segment_to_check) {
         single_segment.add(segment_to_check);    //Add 1 segment. 
         algoObj.addSegments(single_segment);     //Adds 1 object of type segment to priority Queue
         algoObj.findIntersection();
         single_segment.remove(new Segment()); //Remove above segment to get back to original data
     }
 }

TL;DR

我遇到的问题是，在第一次调用 checkForCollisions 之后，优先级队列发生了变化，因为 findIntersection() 通过轮询队列中的元素来工作，从而改变了队列。

如何防止由 algoObj.addSegments() 创建的优先级队列在函数调用之间发生变化？

这是否必须像 here 所解释的那样进行浅拷贝和深拷贝？

我尝试在函数开头创建队列副本，然后更改副本：

        public boolean checkForCollisions(segment_to_check) {
            Algorithm copy = algoObj;
            single_segment.add(segment_to_check);    //Add 1 segment. 
            copy.addSegments(single_segment);     //Adds 1 object of type segment to priority Queue
            copy.findIntersection();
            single_segment.remove(new Segment()); //Remove above segment to get back to original data
        }
    }

然而，这不起作用，因为它仍然改变了原始 algoObj 的优先级队列。

我认为这是一个初学者的问题，源于我在使用 OO 语言时缺乏正确的理解。任何帮助将不胜感激。

Answer 1

首先，重要的是要知道将现有对象分配给另一个变量不会创建原始对象的副本：

MyObject a = new MyObject();
MyObject b = a; // does NOT create a copy!
// now a and b "point" to the same single instance of MyObject!

关于你的实际问题的一些想法：

您的优先级队列只是一个用于交集算法的工作数据结构，就在算法处于运行ning 时。完成后（因此找到了交集），它是空的或至少已更改，正如您已经写的那样。因此必须为每个算法重新创建优先级队列运行.

那么你应该怎么做：

将 CSV 文件中的段加载到您的 ArrayList，但不要将其传递到优先级队列。

每次调用 findIntersection() 之前重新填充（或重新创建）优先级队列。这最好通过将所有段传递给该方法并从头开始创建一个新的优先级队列来完成：

public void findIntersection(Collection<Segment> segments) {
    PriorityQueue<Segment> pQueue = new PrioerityQueue<Segment>(segments);
    while (!pQueue.isEmpty()) {
        p.poll(); //removes element from Queue
        // do something
    }
}

提示：正如我在开头所写的那样，这不会复制各个片段或片段集合。它只是传递一个引用。当然，优先级队列在构造时必须创建内部结构，所以如果段集合很大，这可能需要一些时间。

如果此解决方案对于您的需求来说太慢，您将不得不改进您的算法。您真的需要如此频繁地检查路口吗？如果您只将一个段添加到列表中，那么检查与其他段的交叉点应该就足够了，但如果其他段彼此相交则不需要。也许您可以将您的段存储在类似于 Bentley–Ottmann 算法所使用的二叉搜索树中。每当一个新的段“到达”时，它可以根据搜索树进行检查，这应该是可行的，时间复杂度约为 O(log n)。之后，如果需要，可以将该段插入树中。

或者您可以先添加所有线段，然后只检查一次交叉点。

为什么创建一个对象的副本仍然会改变原始对象的实例变量？

Why does creating a copy of an object still alter instance variables of original object?

java

queue

priority-queue