问在列表中给出一百万个数字。如何以最小的时间复杂度将每个元素乘以一个常量

EN

(致谢@STaefi)将输入值列表乘以一个常量值的时间复杂度为O(n)。这种复杂性与多线程实现无关。

你的程序:将一列数字乘以一个常量，就属于所谓的"Embarrassingly Parallel"问题：

"...几乎不需要任何努力就可以将问题分成多个并行任务……“

输入列表中的每一项都可以与常量相乘，而无需考虑任何其他输入项或全局状态。

有多种方法可以并行化给定的任务。请注意，在此特定示例中，设置线程的开销对于少量的输入值或根本不值得。

使用Java 8 streams的示例：

 mynumbers.parallelStream()
          .map(in -> in * MUTIPLY_ELEMENT)
          .collect(Collectors.toList());

如果您有一百万个元素，并且需要将每个元素乘以一个常量，那么您将需要执行一百万次操作。没有办法绕过它--它是O(n)。

也就是说，创建列表可以是O(1) (恒定时间)，如果您对延迟计算的列表没有意见的话。芭乐的Lists.transform就是这样做的：

List<Integer> myNumbers = ...
List<Integer> myNewNumbers = Lists.transform(myNumbers, i -> i * MULTIPLY_ELEMENT);

这不会减少完成所有乘法所需的总时间；实际上，总体上可能需要更多的时间，因为JVM更难优化。如果您多次访问相同的元素，速度也会变慢，因为每次访问时都会应用转换。也就是说，它不太可能慢到你会注意到的程度。

这种方法还存在一些限制，即不能向转换后的列表中添加新元素(如JavaDocs中所述)。但是，根据您的场景，快速创建初始列表可能还有其他好处。

这是一个100%的过早优化，在这种情况下很可能没有值得进行的优化。

HOWEVER..purely“从学术上讲”，你需要在这里问自己一个问题，也就是说，结果的顺序重要吗？

如果不是，那么对于Streams，这很简单，下面是一个包含100个数字的示例：

    Integer MUTIPLY_ELEMENT = 2;
    List<Integer> resultNumbers = IntStream.range(0,100)
            .parallel()
            .map(i->i*MUTIPLY_ELEMENT)
            .boxed()
            .collect(Collectors.toList());

如果您确实关心排序，但仍然希望获得并行处理的好处，那么您可以利用这样一个事实，即您的操作(乘以2)足够简单，结果数字仍然是相同的相对“自然”顺序，并且只需在map()调用之后在流上调用sorted()。但是，排序操作的时间可能与单线程的时间一样长。

另外，要知道这绝不是一个“真实世界”的场景，你几乎不会遇到像这样的实际问题。希望您只是想了解总体上的并行性，因为在尝试单线程模型并证明其不足之前，您永远不会真正想要进行这种类型的优化。