algorithm - 如何在两个集合之间交换数据时降低运行时复杂性

Question

有这样的任务。有 2 个集合，List类型（集合可以是不同的类型），但目前 List 被接受为起点。

• 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>

有2个对象：

• 节点新数据
• 节点

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;

对于每个对象，都有一个集合，它是处理请求的输入。

List集合将包含3000条记录。

List集合将包含10 - 100条记录（很少1000条）。

你需要 List 中的数据（即只有NodePosition），更新List中的每个节点，当然要按照每个节点的idNode。

例如，我使用了 2 个嵌套循环

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())
                    );
        });
    }
    
}

• 测试电路

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);
    }
}

该算法的时间复杂度（在两个集合之间更新数据）是 O (n^2)，正如我所假设的（由于2 个嵌套循环）。

我必须说这些集合以List格式出现（作为一种实现，值得 - ArrayList）。

您能否建议此任务的优化算法以降低执行时间的复杂性？

在这种情况下 filter() 有什么好处，即它会影响执行时间的复杂度吗？

建议使用较小的作为主要集合。执行时间的复杂性会改变吗？（在我看来，它会更长）？

在这种情况下使用 parallelsStream() 有多合适？

更新。

所以。我决定听从建议并做了以下事情：

1. 首先，我将最大的集合移至地图。

2. 然后我开始浏览集合，它只包含需要更新的节点。

3. 所以运行时复杂度将是 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;
    }

将集合传递给 map 时，需要确保没有重复错误。相反，如果您想在处理流时看到集合中有重复项，则使用该方法

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

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

标签： algorithmjava-streamjava-11