Обычные контейнеры для сбора должны избегать ям

Java контейнер
Обычные контейнеры для сбора должны избегать ям

предисловие

Не так давно я помог коллегеreviewОдинjobКогда реализация идет медленно, я обнаружил, что многим друзьям все еще нужно обращать внимание на детали при кодировании, чтобы реализовать функцию, поэтому у меня есть эта статья.

Шаги ArrayList на яме

List<String> temp = new ArrayList() ;

//获取一批数据
List<String> all = getData();
for(String str : all) {
	temp.add(str);
}

Прежде всего, что не так с этим кодом?

На самом деле в большинстве случаев это не проблема, это не что иное, как циклArrayListТолько записывайте данные.

Но в особых случаях, как здесьgetData()Последующие действия, когда возвращаемые данные очень великиtemp.add(str)Будут проблемы.

Например, мыreviewКогда я кодирую, я обнаруживаю, что возвращаемые здесь данные иногда достигают 2000 Вт.ArrayListОбостряется проблема письма.

Руководство по заполнению ямы

Всем известно, что ArrayList реализован массивом, а длина данных ограничена, массив нужно расширять в нужный момент.

Вот пример вставки в хвост add(E e).

ArrayList<String> temp = new ArrayList<>(2) ;
temp.add("1");
temp.add("2");
temp.add("3");

Когда мы инициализируем длину 2ArrayList, и запишите в него три части данныхArrayListЕго нужно расширить, то есть скопировать предыдущие данные в новый массив длины 3.

Причина, по которой это 3, заключается в том, что новая длина = исходная длина * 1,5.

Из исходного кода мы можем знатьArrayListДлина по умолчанию — 10.

Но на самом деле он не создается при инициализации.DEFAULT_CAPACITY = 10массив .

но иду внутрьaddПервые данные будут расширены до 10.

Теперь, когда мы знаем, что длина по умолчанию равна 10, это означает, что после записи девятого элемента он расширится до10*1.5 =15. Этот шаг заключается в копировании массива, то есть повторном открытии нового пространства памяти для хранения 15 массивов.

Если мы будем писать часто и в больших количествах, это вызовет много копий массива, что крайне неэффективно.

Но если мы заранее предскажем, сколько фрагментов данных может быть записано, мы сможем заранее избежать этой проблемы.

Например, когда мы записываем в него 1000W кусков данных, возникает огромный разрыв в производительности между заданной длиной массива и длиной по умолчанию 10 при инициализации.

Я проверил тест JMH следующим образом:

@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
public class CollectionsTest {

    private static final int TEN_MILLION = 10000000;

    @Benchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.MICROSECONDS)
    public void arrayList() {

        List<String> array = new ArrayList<>();

        for (int i = 0; i < TEN_MILLION; i++) {
            array.add("123");
        }

    }

    @Benchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.MICROSECONDS)
    public void arrayListSize() {
        List<String> array = new ArrayList<>(TEN_MILLION);

        for (int i = 0; i < TEN_MILLION; i++) {
            array.add("123");
        }

    }


    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(CollectionsTest.class.getSimpleName())
                .forks(1)
                .build();


        new Runner(opt).run();
    }
}

По результатам видно, что эффективность предустановленной длины будет намного выше, чем при использовании по умолчанию (здесьScoreотносится ко времени, которое требуется для выполнения функции).

Так что тут всем настоятельно рекомендуется: когда пишется большой объем данныхArrayList, обязательно инициализируйте указанную длину.

Опять же, будьте осторожныadd(int index, E element)Запишите данные в указанное место.

Из исходного кода видно, что каждая запись будет перемещать данные после индекса обратно, собственно, суть в том, чтобы скопировать массив;

Но это отличается от записи данных в конец массива обычным способом, он будет каждый раз копировать массив, что крайне неэффективно.

LinkedList

упомянулArrayListя должен поговоритьLinkedListЭтот брат-близнец; хотя обаListконтейнер, но основная реализация совершенно другая.

LinkedListОн состоит из связанного списка, и каждый узел имеет два узла, головной и хвостовой, которые относятся к переднему и заднему узлам соответственно; следовательно, это также двусвязный список.

Так что в теории его запись очень эффективна, не будет копирования массива, что крайне неэффективно в ArrayList, и каждый раз нужно перемещать только указатель.

Я не буду рисовать тут картинки, если мне лень, каждый сам наверстает.

Сравнительный тест

Ходили слухи, что:

Эффективность записи LinkedList выше, чем у ArrayList, поэтому он очень подходит для LinkedList, когда запись больше, чем чтение.

    @Benchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.MICROSECONDS)
    public void linkedList() {
        List<String> array = new LinkedList<>();

        for (int i = 0; i < TEN_MILLION; i++) {
            array.add("123");
        }

    }

Вот тест, чтобы увидеть, если вывод последователен; то же самое верноLinkedListнаписать1000WВторичные данные, через результаты, чтобы увидеть длину инициализированного массиваArrayListЭффективность явно вышеLinkedList.

Но предпосылка здесь заключается в том, чтобы заранее установитьArrayListДлина массива, чтобы избежать расширения массива, чтобыArrayListЭффективность записи очень высока, в то время какLinkedListХотя ему не нужно копировать память, ему необходимо создавать объекты, преобразовывать указатели и выполнять другие операции.

И вопрос, разумеется,ArrayListМожет поддерживаться произвольный доступ по подписке, и эффективность очень высока.

LinkedListПоскольку нижний слой не является массивом, доступ по индексу не поддерживается, но необходимо решить, следует ли проходить с начала или с конца в соответствии с позицией индекса запроса.

Но независимо от того, какой, вам нужно перемещать указатель, чтобы пройти один за другим, особенноindexЭто будет очень медленно ближе к середине.

Суммировать

Как упоминалось здесь, высокопроизводительные приложения строятся из мелких деталей.ArrayListКак и в случае с ямами данных, в повседневном использовании нет больших проблем.Как только объем данных станет большим, все маленькие проблемы станут большими проблемами.

Итак, подведем итог:

  • При повторном использовании ArrayList, если вы можете заранее предсказать размер данных, вы должны указать его длину, когда она станет больше.
  • Избегайте, насколько это возможноadd(index,e)api, что приведет к копированию массива и снижению эффективности.
  • Еще один момент, другой обычно используетсяMapконтейнерHashMapТакже рекомендуется инициализировать длину, чтобы избежать расширения.

Весь тестовый код в этой статье:

GitHub.com/crossover J я…

Ваши лайки и репост - лучшая поддержка для меня

Категории