Я знаю, что доступ к чему-либо из массива занимает O(1) времени, если он одного типа, используя математическую формулу array[n]=(начальный адрес массива + (n * size Of(type)), но предположим, что у вас есть массив объектов. Эти объекты могут иметь любое количество полей, включая вложенные объекты. Можем ли мы считать время доступа постоянным?

Редактирование - я спрашиваю в основном о JAVA, но я хотел бы знать, есть ли разница в случае, если я выберу другой основной язык, такой как python, c++, JavaScript и т.д.

Например, в приведенном ниже коде

class tryInt{
    int a;
    int b;
    String s;
    public tryInt(){
        a=1;
        b=0;
        s="Sdaas";
    }
}

class tryobject{
    public class tryObject1{
        int a;
        int b;
        int c;
    }
    public tryobject(){
        tryObject1 o=new tryObject1();
        sss="dsfsdf";
    }
    String sss;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("Hello World!");
        Object[] arr=new Object[5];
        arr[0]=new tryInt();
        arr[1]=new tryobject();
        System.out.println(arr[0]);
        System.out.println(arr[1]);
    }
}

Я хочу знать, что поскольку объект типа tryInt должен занимать меньше места, чем объект типа tryobject, как теперь массив будет использовать формулу array[n]=(начальный адрес массива + (n * size Of(type)), поскольку тип больше не является одинаковым и, следовательно, эта формула должна/будет не работать.

ImprobMyster

Ответов: 4

Ответы (4)

В Java тип Object - это ссылка на объект, а не сам объект. То есть, переменную типа Object можно рассматривать как указатель, который говорит: "Вот куда вы должны пойти, чтобы найти свой Object", а не "Я - настоящий, честный Object". Важно отметить, что размер этой ссылки - количество используемых байтов - одинаков независимо от того, на какой тип объекта ссылается переменная Object.

В результате, если у вас есть Object[], то стоимость индексации в этом массиве действительно O(1), поскольку все записи в этом массиве имеют одинаковый размер (а именно, размер ссылки на объект). Размеры объектов, на которые указывают, могут быть не одинаковыми, как в вашем примере, но сами указатели всегда имеют одинаковый размер, поэтому приведенная вами математика дает возможность выполнять индексацию массива за постоянное время.

Ответ на ваш вопрос: это зависит.

Если можно получить случайный доступ к массиву, когда вы знаете нужный индекс, то да, это операция O(1).

С другой стороны, если каждый элемент массива имеет разную длину, или если массив хранится в виде связного списка, необходимо начать поиск своего элемента в начале массива, пропуская элементы, пока не будет найден элемент, соответствующий вашему индексу. Это операция O(n).

В реальном мире работающих программистов и коллекций данных, эти O(x) вещи неразрывно связаны со способом представления данных.

Многие люди используют слово массив для обозначения случайно доступной коллекции O(1). Страницы книги - это массив. Если вы знаете номер страницы, вы можете открыть книгу на этой странице. (Переворачивание книги на нужную страницу не обязательно является тривиальной операцией. Возможно, вам придется сначала пойти в библиотеку и найти нужную книгу. Аналогия применима к многоуровневому компьютерному хранилищу... жесткий диск / оперативная память / несколько уровней кэша процессора)

Люди используют список для обозначения последовательно доступной коллекции O(n). Предложения текста на странице книги - это список. Чтобы найти пятое предложение, нужно прочитать первые четыре.

Я упоминаю здесь значение слов список и массив по важной для профессиональных программистов причине. Большая часть нашей работы - это поддержка существующего кода. В нашей оправданной спешке, когда мы торопимся закончить работу, иногда мы хватаем первый попавшийся под руку класс коллекции, и иногда мы берем не тот класс. Например, мы можем взять список O(n), а не массив O(1) или хэш O(1, возможно). Коллекция, которую мы берем, хорошо работает для наших тестов. Но, бум! , производительность падает именно тогда, когда приложение становится успешным и масштабируется до хранения большого количества данных. Это происходит всегда.

Для решения подобной проблемы нам необходимо практическое понимание этих вопросов доступа. Однажды мне достался в наследство проект с самодельным классом хешированного словаря, который потреблял O(n cubed) при вставке большого количества элементов в словарь. Пришлось изрядно покопаться, чтобы разобраться в документации по классу коллекции и понять, что происходит на самом деле.

Ответ зависит от контекста.

В некоторых учебниках действительно принято рассматривать доступ к массиву как O(1), потому что это упрощает анализ. И справедливости ради, в современных архитектурах это O(1) инструкций процессора.

Но:

  • По мере увеличения массива данных, стремящегося к бесконечности, он не помещается в памяти. Если "массив" реализован как структура базы данных, распределенная по нескольким машинам, то в итоге вы получите древовидную структуру и, вероятно, логарифмическое время доступа в худшем случае. Если вы не беспокоитесь о том, что размер данных будет стремиться к бесконечности, то нотация big O может не подойти для вашей ситуации
  • .
  • В реальном оборудовании обращения к памяти не все одинаковы - существует много уровней кэша, и промахи кэша стоят сотни или тысячи циклов. Модель O(1) для доступа к памяти имеет тенденцию игнорировать это
  • В теоретической работе машины со случайным доступом получают доступ к памяти за O(1), но машины Тьюринга не могут. Иерархические эффекты кэша, как правило, игнорируются. Некоторые модели, такие как трансдихотомическая оперативная память, пытаются учесть это.
  • Как правило, иерархические кэш-эффекты игнорируются.

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

В общем случае массив обозначает диапазон памяти фиксированного размера, хранящий элементы одинакового размера. Если рассматривать это обычное понятие массива, то если объекты являются членами массива, то под капотом ваш массив хранит ссылки на объекты, и обращаясь к i-му элементу вашего массива, вы находите ссылку на объект/указатель, который он содержит, со сложностью O(1), а адрес, на который он указывает, язык должен найти.

Однако существуют массивы, которые не соответствуют этому определению. Например, в Javascript вы можете легко добавлять элементы в массив, что заставляет меня думать, что в Javascript массивы несколько отличаются от выделенного диапазона элементов фиксированного размера одного размера/типа. Кроме того, в Javascript вы можете добавлять в массив элементы любых типов. Итак, в целом я бы сказал, что сложность составляет O(1), но есть довольно много важных исключений из этого правила, в зависимости от технологий.

2022 WebDevInsider