有效地将元素添加到列表的顶部

Question

我有一个像这样的枚举，我总是从中得到我的 localFruit ，它可以是 APPLE 或 ORANGE 或 BANANA.

public enum Fruits {
    // it can have more elements here
    APPLE, ORANGE, BANANA;

    // some code
}

那么假设如果 APPLE 是我的 localFruit，那么 ORANGE 和 BANANA 将是我的 remoteFruits。我需要打乱我的 remoteFruits，然后确保我的 localFruit 位于我列表的顶部，然后是 remoteFruits。

下面是我的代码，我在其中进行洗牌并添加原始 result 列表：在下面的代码中，CURRENT_FRUIT 可以是 APPLE 或 ORANGE 或 BANANA.

private static List<Fruits> getFruitsInOrder() {
    EnumSet<Fruits> localFruit = EnumSet.of(CURRENT_FRUIT);
    EnumSet<Fruits> remoteFruits = EnumSet.complementOf(localFruit);

    List<Fruits> result = new ArrayList<Fruits>(remoteFruits);
    Collections.shuffle(result);

    // first element in the list will always be the local fruit
    result.addAll(0, new ArrayList<Fruits>(localFruit));
    return result;
}

由于这段代码会被调用很多次，所以想看看我在做的事情是否有问题，这可能是性能瓶颈？我的代码在性能方面是否还可以？

我的主要目标是让 localFruit 位于列表的顶部，然后是 remoteFruits（但是我需要在将它们添加到结果列表之前将它们打乱）。

Answer 1

这个呢？它通过在第一次正确调整大小来避免任何 ArrayList 调整大小的性能影响，并且它避免了您通过在列表中插入而受到的影响。它还完全支持多个localFruit。我认为你的版本已经是 O(n)，所以无论哪种方式都不是什么大问题。

private static List<Fruits> getFruitsInOrder() {
    EnumSet<Fruits> localFruit = EnumSet.of(CURRENT_FRUIT);
    EnumSet<Fruits> remoteFruits = EnumSet.complementOf(localFruit);

    List<Fruits> result = new ArrayList<Fruits>(localFruit.size() + remoteFruits.size());
    result.addAll(localFruit);
    result.addAll(remoteFruit);
    Collections.shuffle(result.subList(localFruit.size(), result.size()));
    return result;
}

Answer 2

假设集合大小相当小，例如 3 或 4 个值，这可能没问题。与优化一样，最好分析您的代码，然后进行优化。话虽如此，该代码看起来相当合理，但您正在制作大量列表副本，其中大部分都可以避免。这是您的代码，带有注释，指示您每次制作副本时：

private static List<Fruits> getFruitsInOrder() {
    EnumSet<Fruits> localFruit = EnumSet.of(CURRENT_FRUIT);
    // Creates a new set copying all the fruits from the enum
    EnumSet<Fruits> remoteFruits = EnumSet.complementOf(localFruit);

    // Copies the set above
    List<Fruits> result = new ArrayList<Fruits>(remoteFruits);
    Collections.shuffle(result);

    // Will allocate a new array, copy the remote fruits, then add
    // another copy of the local fruit
    result.addAll(0, new ArrayList<Fruits>(localFruit));
    return result;
}

那些副本都是O(n) 其中n是水果的数量。如果 n 小于 10 左右（甚至可能小于 100 左右），这还不错。还有分配和释放所有这些对象的成本。同样，不可怕但也不是很好。这是仅制作一个副本的替代实现：

private static List<Fruits> getFruitsInOrder() {
    // Makes one copy of all the fruits, that's it.
    ArrayList<Fruits> allFruits = new ArrayList<>(Fruits.values());
    // move the current fruit to the front. Assumes that the value of the
    // fruit is its array index: if not, you'll have to maintain that 
    // explicitly in a Map<Fruits, int>
    int curFruitIdx = CURRENT_FRUIT.value();
    Fruits curFruit = allFruits.get(curFruitIdx);
    allFruits.set(curFruitIdx, allFruits.get(0));
    allFruits.set(0, curFruit);
    // Now get a **view**, not a copy, of the rest of the list and shuffle it
    List<Fruits> toShuffle = allFruits.subList(1, allFruits.size());
    Collections.suffle(toShuffle);
    return allFruits;
}

如果事情不需要是线程安全的，即使是方法顶部的单个副本也可以删除：您可以只在静态的某个地方粘贴一个副本并继续对其进行操作。同样，如果 n 很小，上面的实际上可能比你得到的慢。

基本上，以上是一种避免在这种情况下复制长列表的方法。对于大列表，这很有帮助。对于小的，没那么多。

Answer 3

所有这些解决方案都太难了。 Java 集非常有效，但简单的数组访问更是如此。此外，构建两个集合（一个具有补码操作），复制到 ArrayList，然后使用 addAll 创建一个新的 ArrayList 是大量无用的工作和内存垃圾。

枚举按顺序为您提供其值的数组。用它！只需将本地元素交换到位置零，然后打乱数组的其余部分。这样您就创建了一个数据结构：您想要 return 的 ArrayList。剩下的只是重新排序它的元素。

当然，除非你有一个巨大的枚举或者正在调用这个函数数百万次，否则这个讨论是学术性的。您不会注意到性能差异。

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

enum Fruit { APPLE, PEAR, PEACH, PLUM, BANANA }

public class Hack {

    static List<Fruit> getFruitInOrder(Fruit local) {
        List<Fruit> list = Arrays.asList(Fruit.values());
        Collections.swap(list, 0, local.ordinal());
        Collections.shuffle(list.subList(1, list.size()));
        return list;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.println(getFruitInOrder(Fruit.PLUM));
        }
    }
}

在我的 MacBook 上：

run:
[PLUM, BANANA, PEAR, APPLE, PEACH]
[PLUM, PEACH, PEAR, APPLE, BANANA]
[PLUM, PEACH, BANANA, PEAR, APPLE]
[PLUM, PEAR, BANANA, APPLE, PEACH]
[PLUM, PEAR, APPLE, BANANA, PEACH]
[PLUM, BANANA, APPLE, PEACH, PEAR]
[PLUM, APPLE, BANANA, PEACH, PEAR]
[PLUM, APPLE, PEACH, PEAR, BANANA]
[PLUM, APPLE, PEAR, PEACH, BANANA]
[PLUM, PEACH, APPLE, PEAR, BANANA]
BUILD SUCCESSFUL (total time: 0 seconds)

有效地将元素添加到列表的顶部

Efficiently adding element to the top of the list

java

enums

linked-list

list

arraylist