Блог

Мне нужно измерить время поиска для LinkedLists для разных значений. Мое решение нелогично, поэтому я не знаю, на правильном ли я пути или нет. Это мое решение;

     LinkedList<Integer> myList = new LinkedList<>();
    for (int i = 1; i <= 1000; i  )
        myList.add(i);
    Collections.shuffle(myList);
    Random rand = new Random();
    myList.contains(rand.nextInt(myList.size()));
    System.out.println(System.nanoTime());

    LinkedList<Integer> myList2 = new LinkedList<>();
    for (int i = 1; i <= 2000; i  )
        myList2.add(i);
    Collections.shuffle(myList2);
    myList.contains(rand.nextInt(myList2.size()));
    System.out.println(System.nanoTime());
 

Это мои результаты

38565758048600

38565759163200

Вы не можете измерить производительность таким образом. Компьютеры ненадежны; не сегодня и не были десятилетиями. Операционные системы упреждают. JVM JITs. Процессоры имеют ядра. Ядра имеют конвейеры и многоуровневые кэши. Вам безнадежно не повезло; нанотайм между синглом contains абсолютно ни о чем не говорит — это все равно, что пытаться измерить эффект от того, что кто-то в Гонолулу помочился в воду, проверяя высоту океана, плещущегося у пирса в Амстердаме. Задействовано около миллиарда других факторов, которые гораздо более впечатляющие по величине.

Обычный принцип измерения производительности состоит в том, чтобы засечь время, сделать то, что нужно, а затем снова засечь время. Разница во времени? Вот сколько времени это заняло. Но вы должны запускать операцию не один раз; но много-много раз (а затем принимать среднее значение) и на самом деле не воспринимать время серьезно, пока оно не будет запущено несколько раз, чтобы убедиться, что строки кэша и процессы JIT стабилизировались. Вам также необходимо убедиться, что движок VM hotspot не будет оптимизировать весь ваш код, поэтому вы также должны фактически использовать результат (вы отбрасываете boolean contains возврат that; это может привести к тому, что движок hotspot поймет, что он может просто исключить весь вызов, поскольку он не может изменить список.

Одним словом, это совершенно невозможно для любого новичка в Java; даже седой старый ветеран, скорее всего, сделает это неправильно, и, поскольку речь идет о времени, очень сложно «проверить», действительно ли работает ваша структура синхронизации.

К счастью, вам не нужно это писать. Он уже существует: JMH. Вы либо используете это, либо являетесь прямым конкурентом этого, либо почти наверняка получаете полную ложь и измышления из своего временного кода.

Обратите внимание, что вовлечение Random — очень плохая идея для синхронизации; вы хотите, чтобы код, который вы синхронизируете, был как можно более надежным. Таким образом, не перетасовывайте список и не запрашивайте случайное число. Каждый раз запрашивайте определенное число или множество чисел, или дублируйте список, перемешивайте его, затем выполняйте поиск по каждому числу — это означает, что все числа во входном списке ищутся ровно один раз, но в произвольном порядке.