Collections

Показатели производительности

Language

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

    Показатели производительности на последовательностях:

      head tail apply update prepend append insert
    Не изменяемые              
    List C C L L C L -
    LazyList C C L L C L -
    ArraySeq C L C L L L -
    Vector eC eC eC eC eC eC -
    Queue aC aC L L C C -
    Range C C C - - - -
    String C L C L L L -
    Изменяемые              
    ArrayBuffer C L C C L aC L
    ListBuffer C L L L C C L
    StringBuilder C L C C L aC L
    Queue C L L L C C L
    ArraySeq C L C C - - -
    Stack C L L L C L L
    Array C L C C - - -
    ArrayDeque C L C C aC aC L

    Показатели производительности на множествах и мапах:

      lookup add remove min
    Не изменяемые        
    HashSet/HashMap eC eC eC L
    TreeSet/TreeMap Log Log Log Log
    BitSet C L L eC1
    VectorMap eC eC aC L
    ListMap L L L L
    Изменяемые        
    HashSet/HashMap eC eC eC L
    WeakHashMap eC eC eC L
    BitSet C aC C eC1
    TreeSet Log Log Log Log

    Примечание: 1 Предполагаем, что биты плотно упакованы.

    Объяснение записей:

       
    C Операция занимает (быстрое) постоянное время.
    eC Операция занимает практически постоянное время, но может зависеть от некоторых допущений, таких как максимальная длина вектора или распределение ключей хэширования.
    aC Операция занимает постоянное амортизированное время. Некоторые вызовы операции могут занять больше времени, но если в среднем выполняется много операций, то на одну операцию приходится постоянное время.
    Log Операция занимает время, пропорциональное логарифму от размера коллекции.
    L Операция линейная, т.е. занимает время, пропорциональное размеру коллекции.
    - Операция не поддерживается.

    В первой таблице рассматриваются типы последовательностей - как изменяемые, так и неизменяемые - со следующими операциями:

       
    head Выбор первого элемента последовательности.
    tail Создание новой последовательности, состоящей из всех элементов, кроме первого.
    apply Работа с индексом.
    update Функционал обновления (с updated) для неизменяемых последовательностей и через сайд эффекты обновление (с update) для изменяемых последовательностей.
    prepend Добавление элемента спереди последовательности. В неизменяемых последовательностях происходит создание новой последовательности. В изменяемых - модифицируется исходная.
    append Добавление элемента в конец последовательности. В неизменяемых последовательностях происходит создание новой последовательности. В изменяемых - модифицируется исходная.
    insert Вставка элемента в любом месте последовательности. Поддерживается только в изменяемых последовательностях.

    Во второй таблице показаны изменяемые и неизменяемые множества и мапы со следующими операциями:

       
    lookup Проверка наличия элемента во множестве или получение значения, связанного с ключом в мапе.
    add Добавление нового элемента во множество или пару ключ/значение в мапу .
    remove Удаление элемента из множества или ключа из мапы.
    min Наименьший элемент множества, или наименьший ключ в мапе.
    ← previous next →

    Contributors to this page:

    Contents
    Problem with this page?
         Please help us fix it!