Какая польза от этой пустой полки RandomAccess?

задняя часть алгоритм API модульный тест

изучениеJavaСобираясь, первое, что нужно усвоить, этоListсерединаArrayListиLinkedList, Ключом к изучению коллекции является изучение ее исходного кода и понимание лежащего в основе метода реализации, поэтому сегодня я расскажу об этом.ArrayListреализует интерфейсRandomAccess.

поколение любопытства

ПроверятьArrayListИсходный код обнаружил, что он реализуетRandomAccessВ этот интерфейс из любопытства зашел, посмотрел, и обнаружил, что этот интерфейс пустой, что, конечно, возбудило еще большее любопытство: какой прок от этой пустой полки?

Глубокое погружение

Официальная документация JDK — незаменимый инструмент, давайте посмотрим, что там написано:RandomAccessдаListреализация используетсяинтерфейс маркера, чтобы показать, что егоПоддерживает быстрый (обычно фиксированное время) произвольный доступ. Основная цель этого интерфейса — позволить общему алгоритму изменить свое поведение, чтобы обеспечить хорошую производительность при применении к спискам случайного или последовательного доступа.

Интерфейс маркера (Marker): Это объясняетRandomAccessПоскольку он пуст, функция этого интерфейса служит только маркером.

Это не связано с интерфейсом сериализацииSerializableПочти? Пока вы внимательно смотрите, это не просто интерфейс маркера, на самом делеArrayListТакже реализованы два других пустых интерфейса, подобных этому:

Cloneableинтерфейс: реализованCloneableинтерфейс для указанияObject.clone()методы могут законно выполнять операции над экземплярами этого классаКопировать по полю. если не реализованоCloneableВызывается для экземпляра интерфейсаObjectизcloneМетод приведет кCloneNotSupportedExceptionаномальный.

SerializableИнтерфейс: Класс реализованjava.io.Serializableинтерфейс свключить его сериализацию. Класс, который не реализует этот интерфейс, не сможет сериализовать или десериализовать какое-либо свое состояние.

продолжать исследовать

Что делает интерфейс маркера? Продолжайте обсуждать роль RandomAccess, две другие здесь обсуждаться не будут.

еслиListподкласс реализуетRandomAccessинтерфейс, что означает, что он может быстро получить доступ к сохраненным элементам в случайном порядке.В настоящее время вы можете думать о массиве через индексindexaccess, который реализует интерфейсArrayListБазовая реализация представляет собой массив, доступ к которому также осуществляется через индексы, но нам нужно использоватьget()форма метода,ArrayListНижний слой по-прежнему является формой доступа к массиву.

Вы также должны подумать о списке,LinkedListБазовая реализация представляет собой связанный список,LinkedListне реализованыRandomAccessИнтерфейс, и найти его — ключ к преодолению проблемы.

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

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

Списки произвольного доступа обрабатываются с помощью циклов, а списки последовательного доступа обрабатываются с помощью итераторов.

Первый взглядRandomAccessкак пользоваться

import java.util.*;
public class RandomAccessTest {
    public static void traverse(List list){

        if (list instanceof RandomAccess){
            System.out.println("实现了RandomAccess接口，不使用迭代器");

            for (int i = 0;i < list.size();i++){
                System.out.println(list.get(i));
            }

        }else{
            System.out.println("没实现RandomAccess接口，使用迭代器");

            Iterator it = list.iterator();
            while(it.hasNext()){
                System.out.println(it.next());
            }

        }
    }
    public static void main(String[] args) {
        List<String> arrayList = new ArrayList<>();
        arrayList.add("a");
        arrayList.add("b");
        traverse(arrayList);

        List<String> linkedList = new LinkedList<>();
        linkedList.add("c");
        linkedList.add("d");
        traverse(linkedList);
    }
}

Ниже мы добавляем большое количество данных для тестирования производительности:

import java.util.*;
public class RandomAccessTimeTest {

    //使用for循环遍历
    public static long traverseByLoop(List list){
        long startTime = System.currentTimeMillis();
        for (int i = 0;i < list.size();i++){
            list.get(i);
        }
        long endTime = System.currentTimeMillis();
        return endTime-startTime;
    }

    //使用迭代器遍历
    public static long traverseByIterator(List list){
        Iterator iterator = list.iterator();
        long startTime = System.currentTimeMillis();
        while (iterator.hasNext()){
            iterator.next();
        }
        long endTime = System.currentTimeMillis();
        return endTime-startTime;
    }

    public static void main(String[] args) {
        //加入数据
        List<String> arrayList = new ArrayList<>();
        for (int i = 0;i < 30000;i++){
            arrayList.add("" + i);
        }
        long loopTime = RandomAccessTimeTest.traverseByLoop(arrayList);
        long iteratorTime = RandomAccessTimeTest.traverseByIterator(arrayList);
        System.out.println("ArrayList:");
        System.out.println("for循环遍历时间:" + loopTime);
        System.out.println("迭代器遍历时间:" + iteratorTime);

        List<String> linkedList = new LinkedList<>();
        //加入数据
        for (int i = 0;i < 30000;i++){
            linkedList.add("" + i);
        }
        loopTime = RandomAccessTimeTest.traverseByLoop(linkedList);
        iteratorTime = RandomAccessTimeTest.traverseByIterator(linkedList);
        System.out.println("LinkedList:");
        System.out.println("for循环遍历时间:" + loopTime);
        System.out.println("迭代器遍历时间:" + iteratorTime);
    }
}

результат:

Список массивов: для времени прохождения цикла: 3 Время обхода итератора: 7

Связанный список: для времени прохождения цикла: 2435 Время обхода итератора: 3

в заключении

По результатам можем сделать вывод:ArrayListОбход с помощью цикла for лучше, чем обход с помощью итератораLinkedListИтераторы лучше, чем циклы

Согласно сделанным выше выводам, его можно использоватьRandomAccessСудить перед траверсом, поListРазличные подклассы выбирают разные методы обхода для повышения производительности алгоритма.

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

Категории