java - 是否可以使这个嵌套 for 循环小于 O(N^2)？

Question

我正在使用 Apache Spark 2.1 和 Java 8 开发 Kafka Streaming 服务。我使用嵌套的 for 循环来使用主题/分区对填充 ArrayList。

是否可以使用另一种方法来减少 O(N^2) 的嵌套 for 循环？

这是代码:

    private static List<TopicAndPartition> createTAndPList(List<String> topics, List<String> partitions)
        throws ConsumerException {
    if (topics.size() != partitions.size()) {
        throw new ConsumerException("Cannot create list with unequal number of topics and parititons,");
    }

    List<TopicAndPartition> topicsAndPartitions = new ArrayList<>();
    for (int t = 0; t < topics.size(); t++) {
        for (int p = 0; p < Integer.parseInt(partitions.get(t)); p++) {
            topicsAndPartitions.add(new TopicAndPartition(topics.get(t), p));
        }
    }

    return topicsAndPartitions;
}

仅供引用:由于我无法控制(管理)的权力，我无法使用 Kafka 8 以上版本。

Answer 1

使用您给定的代码，看起来不可能减少订单。

但是，您可以进行两个小的优化。

• 将 topics.get(t) 移出内部 for 循环，

• 不要在每次循环时重新计算内部 for 循环终止条件。

  for (int t = 0; t < topics.size(); t++) {
      String topic = topics.get(t);
      int count = Integer.parseInt(partitions.get(t));    
      for (int p = 0; p < count; p++) {
          topicsAndPartitions.add(new TopicAndPartition(topic, p));
  

您正在调用 topics.get 和 Integer.parseInt(partitions.get(t)) t*p 次，而不是仅仅 t 次。 topic.get() 的更改可能不会有太大作用，但像这样将某些内容移出内循环是一种非常常见的优化。

最后，您真的需要将它们全部放在一个列表中吗？或者您可以在实际需要的地方动态生成它们吗？