Эффективное добавление элемента вверху списка

Question

У меня есть такой ENUM, из которого у меня всегда получается то, что у меня 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

Все эти решения работают слишком усердно. Наборы Java довольно эффективны, но простой доступ к массиву в большей степени. Кроме того, построение двух наборов (один со вспомогательной операцией), копирование в ArrayList, то создание нового ArrayList с addAll - это много бесполезной работы и мусора памяти.

Перечисление дает вам массив своих значений по порядку. Используй это! Просто поменяйте локальный элемент на нуль, затем перетасуйте оставшуюся часть массива. Таким образом вы создаете ровно одну структуру данных: 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) 

Answer 2

Как насчет этого? Он избегает любых 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 3

Предполагая, что установленный размер довольно мал, например 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; 
} 

Эти копии всех О (п) где п является количество плодов. Если 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 невелик, вышеупомянутое может быть на самом деле медленнее, чем у вас.

В принципе, вышеупомянутый способ избежать копирования длинных списков в такой ситуации. С большими списками это полезно. С маленькими, не так много.