Временная сложность операции get на десериализованном объекте Google Protobuf

Question

Предположим, мы создали прото-файл с повторением некоторого типа данных, например.

message DocList{ 
    repeated string docId = 1; 
} 

Теперь мы вставили объекты это объект строитель следующим образом:

DocList.Builder docList = new DocList.newBuilder() 
docList.addAllDocId(docIDlist);   // docIDList is ArrayList<String> 

Теперь мы выполняем следующую операцию GET для извлечения объекта в индексе.

docList.getDocId(i); // Some index i 

Я хочу знать это, получаете ли операция O (1) или O (п)?

Answer 1

Protobuf ListValue опирается на java.util.ArrayList

if (!((mutable_bitField0_ & 0x00000001) == 0x00000001)) { 
     values_ = new java.util.ArrayList<com.google.protobuf.Value>(); 
     mutable_bitField0_ |= 0x00000001; 
} 

, следовательно, это O (1) для Get()

OpenJDK ArrayList

@SuppressWarnings("unchecked") 
E elementData(int index) { 
    return (E) elementData[index]; 
}