How to reduce runtime complexity when exchanging data between two collections

Question

There is such a task. There are 2 collections, the List type (collections can be of different types), but at the moment the List is accepted as the starting point.

• pom.xml

  <properties>
    <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
    <maven.compiler.source>11</maven.compiler.source>
    <maven.compiler.target>11</maven.compiler.target>
  </properties>

  <dependencies>
    <dependency>
      <groupId>org.junit.jupiter</groupId>
      <artifactId>junit-jupiter-engine</artifactId>
      <version>5.7.1</version>
      <scope>test</scope>
    </dependency>

    <dependency>
      <groupId>org.jeasy</groupId>
      <artifactId>easy-random-core</artifactId>
      <version>5.0.0</version>
      <scope>test</scope>
    </dependency>

  </dependencies>

There are 2 objects :

• NodeNewData
• Node

public class Node {

    private String idNode;
    
    private NodePosition nodePosition;
    
    private String nameNode;

//getters and setters
}

public class NodePosition {

    private double xPos;
    private double yPos;
    private double zPos;
//getters and setters

}

public class NodeNewData {

    private String idNode;

    private NodePosition nodePosition;

For each object, there is a collection, which is the input for processing the request.

the List collection will consist of 3000 records.

the List collection will consist of 10 - 100 records (rarely 1000).

You need data from List( namely, only NodePosition ), update each node in List, of course, in accordance with the idNode for each node.

As an example, I used 2 nested loops

public class CollectionChange {

    private List<Node> nodeList;

    private List<NodeNewData> nodePositionList;

    public CollectionChange(List<Node> nodeList, List<NodeNewData> nodePositionList) {
        this.nodeList = nodeList;
        this.nodePositionList = nodePositionList;
    }

    public void runChangeBetweenCollectionON2(){
        
        nodeList.forEach(nodeTarget -> {

            nodePositionList
                    .stream()
                    .filter(nodeWithNewPosition -> nodeWithNewPosition.getIdNode()
                            .equals(nodeTarget.getIdNode()))
                    .forEach(
                            nodeWithNewPosition -> nodeTarget.setNodePosition(nodeWithNewPosition.getNodePosition())
                    );
        });
    }
    
}

• a test circuit

class CollectionChangeTest {

    private static CollectionChange collectionChange;

    @BeforeAll
    static void setup() {

        int countObjects = 3000;
        final List<Node> nodeList = fillList(Node.class, countObjects);

        countObjects = 100;
        final List<NodeNewData> nodePositionList = fillList(NodeNewData.class, countObjects);

        collectionChange = new CollectionChange(nodeList, nodePositionList);
    }

    private static <T> List<T>  fillList (Class<T> clazz, int countObjects){

        EasyRandom generator = new EasyRandom();

        return generator
                .objects(clazz, countObjects)
                .collect(Collectors.toList());
    }

    @Test
    void runChangeBetweenCollectionON2() {

        Instant startProcessRequest = Instant.now();

        collectionChange.runChangeBetweenCollectionON2();

        Instant finishProcessRequest = Instant.now();

        long resultTimeOfProcessRequest = Duration
                .between(startProcessRequest,finishProcessRequest)
                .toSeconds();

        outputResult(resultTimeOfProcessRequest);
        
    }

    private void outputResult(long resultTimeOfProcessRequest){
        String messageInfoFirst = "Request processing time";
        String messageInfoSecond = " seconds.";

        final String formatMessageInfo = String.format("%s : %d %s", messageInfoFirst,
                resultTimeOfProcessRequest, messageInfoSecond);

        System.out.println(formatMessageInfo);
    }
}

The time complexity of this algorithm (updating data between two collections) is O (n^2), as I assume (due to 2 nested loops).

I must say that the collections come in the List format ( as an implementation , it is worth - ArrayList).

Can you suggest optimization algorithms for this task to reduce the complexity of the execution time ?

What is the benefit of filter () in this case, that is, does it affect the complexity of the execution time ?

It was suggested to use the smaller one as the leading collection. Will the complexity of the execution time change ? ( In my opinion-it will be longer)?

How appropriate is the use of parallelsStream() in this case ?

Update.

So. I decided to follow the advice and did the following:

1. First, I moved the largest collection to map.

2. Then I started going through the collection, which contains only the nodes that need to be updated.

3. So the runtime complexity would be O(n).

/**
     * O (n)
     */
    public List<Node> runChangeBetweenCollectionON(){

        final Map<String, Node> nodesInMap = convertListToMapWDuplicates(nodeList);

        nodePositionList
                .stream()
                .filter(nodeNewData -> {

                    final String idNode = nodeNewData.getIdNode();
                    final Node node = nodesInMap.get(idNode);

                    if(node != null) return idNode.equals(node.getIdNode());
                    return false;
                })
                .forEach(nodeNewData -> {
                    final Node nodeTarget = nodesInMap.get(nodeNewData.getIdNode());
                    nodeTarget.setNodePosition(nodeNewData.getNodePosition());
                });

        final List<Node> nodeList = nodesInMap
                .values()
                .stream()
                .collect(toList());

        return nodeList;

    }

    public Map<String, Node> convertListToMapWDuplicates(List<Node> list) {

        Map<String, Node> map = list.stream()
                .collect(Collectors.toMap(Node::getIdNode, node -> node, (nodeFirst, nodeSecond) -> nodeSecond));
        return map;
    }

When passing a collection to map, you need to make sure that there is no duplicate error. If, on the contrary, you want to see that you have duplicates in the collection when processing the stream, then use the method

  public Map<String, Node> convertListToMap(List<Node> list) {

        Map<String, Node> map = list.stream()
                .collect(Collectors.toMap(Node::getIdNode, node -> node));
        return map;
    }