Доступ к элементу массива

@OxomHuK · Регистрация: 11.07.2013

Студворк — интернет-сервис помощи студентам

Здравствуйте! Такой вопрос: для одномерного массива на 100 элементов к какому из элементов быстрее произойдет обращение по индексу – к третьему или к предпоследнему и почему?

Добавлено через 1 час 52 минуты
еще: как можно посмотреть описание устройства массивов в java? (например, откуда берется свойство length)

Добавлено через 5 часов 6 минут
Еще чего не понимаю. Раз массив является ссылочным типом аля обьектом, то какого класса?

Добавлено через 12 минут

Сообщение от OxomHuK

еще: как можно посмотреть описание устройства массивов в java? (например, откуда берется свойство length)
Добавлено через 5 часов 6 минут
Еще чего не понимаю. Раз массив является ссылочным типом аля обьектом, то какого класса?

Вроде немного понял.

Массив является обьектом класса Array (не Arrays). Но этот класс конкретно так 'запечатан' (приватный конструктор и куча native методов)

Но все же, где быстрее обращение по индексу? или это нельзя узнать?

@mutagen · 20.09.2013, 12:05

Сообщение от OxomHuK

Массив является обьектом класса Array

неверно, массив это нативный объект

Java
1
2
3
4
5
6
public class Arr {
    public static void main(String[] args) {
        int [] a = new int[2];
        System.out.println(a.getClass().getName());
    }
}

доступ к любому элементу массива происходит с одинаковой скоростью, так как при этом
происходит такой алгоритм реализованный на С в нативках:
get <адрес_массива_в_памяти> + <индекс_массива> * <размер_типа_данных>

Не по теме:

возможно получение 0 элемента и обгоняет на пару тактов, но это всё )

класс Array это специальный класс для Reflection с нативными методами для реализации поведения как у объекта
примерно как у void

Java
1
2
        Class v = void.class;
        System.out.println(v.isPrimitive());

@tankomaz · 20.09.2013, 12:09

length это некая переменная (поле), которую вы пишите new int[100]
а время доступа, как мне кажется, к любому элементу будет одинаковое, ибо jvm четко понимает в какой области памяти какой номер

@MbICJIuTeJIb_u3 · 21.09.2013, 22:36

Сообщение от mutagen

get <адрес_массива_в_памяти> + <индекс_массива> * <размер_типа_данных>

А как насчёт разрядности ОС?
Вот примерно ваш алгоритм:

C++
1
2
3
4
5
6
        const int size = 5;
 
    int mas [size] = {1,2,3,4,5};
 
    for(int i = 0; i < size; i++) 
        std::cout << *(mas + (i * sizeof(int))) << "\n";

Но работает он не корректно...

@Venzo · 21.09.2013, 22:44

Сообщение от MbICJIuTeJIb_u3

Но работает он не корректно...

потому что складывание указателей само по себе предполагает "умножение на размер типа указателя".
т.е если у вас указатель на int и вы к нему прибавите 1, то реально указатель увеличится на 4 (в 32х)

@MbICJIuTeJIb_u3 · 21.09.2013, 22:54

Сообщение от Venzo

потому что складывание указателей само по себе предполагает "умножение на размер типа указателя".
т.е если у вас указатель на int и вы к нему прибавите 1, то реально указатель увеличится на 4 (в 32х)

C++
1
2
3
for(int i = 0; i < size; i++) 
        cout << *(mas + i) << "\n";
    */

Да это я знаю, я просто подставил под этот алгоритм:
get <адрес_массива_в_памяти> + <индекс_массива> * <размер_типа_данных>

Добавлено через 1 минуту

Сообщение от MbICJIuTeJIb_u3

то реально указатель увеличится на 4 (в 32х)

В вот именно на 4 в (32х) а в 64х ? Поэтому разрядность ос тут тоже играет свою роль.

@Venzo · 21.09.2013, 23:27

Сообщение от MbICJIuTeJIb_u3

Поэтому разрядность ос тут тоже играет свою роль.

Сообщение от MbICJIuTeJIb_u3

<размер_типа_данных>

хоть 16 разрядная, эта формула все равно подойдет)

@kamre · 21.09.2013, 23:51

Сообщение от mutagen

доступ к любому элементу массива происходит с одинаковой скоростью

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

@mutagen · 22.09.2013, 01:49

Сообщение от kamre

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

ОК - окунёмся маленько глубже )
1. Вы совершенно правы по поводу иерархичности памяти, если массив уложится в кеш процессора по своему размеру, то скакать по нему можно будет очень быстро, но если массив настолько велик что он не умещается в кеше проца полностью, то возникнут потери времени на доступ в достаточно медленное ОЗУ по сравнению с кешем.

2. То есть дело не в патернах, а в собственно железе на котором выполняются замеры, поэтому один и тот же код может показать разные результаты на разных системах.

3. последовательный доступ всегда быстрее так как не надо умножать <размер_типа_данных> на индeкс, нужно просто сместиться на 1 шаг вперёд по памяти, естественно операция инкремента указателя происходит быстрее чем умножение.

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

verylazy · 24.09.2013, 12:53

не давала мне эта тема...покоя

и решил провести небольшой тест
Вот два примера, массив или лист размером 10 миллионов, но проходов по элементам в 10 раз больше.
Seed поставил одинаковый, что бы генерировало каждый раз одинаковые последовательности, это можно будет наблюдать по сумме чисел.

Кликните здесь для просмотра всего текста

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Random;
 
public class RandomTestArray {
 
    public static void main(String[] args) {
        long sum = 0;
        int size = 10_000_000;
        Random r = new Random(42); // засеваем_всегда_одинаково
        Integer[] arr = new Integer[size];
        for (int i = 0; i < size; i++) arr[i] = i;
        // банзай!!!
        long start = System.currentTimeMillis();
        for (int i = 0; i < size * 10; i++) {
            int t = r.nextInt(size);
            sum += arr[t].intValue();
        }
        System.out.println("sum=" + sum + "  время " + (System.currentTimeMillis() - start));
    }
}

Кликните здесь для просмотра всего текста

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.ArrayList;
import java.util.Random;
 
public class RandomTestList {
 
    public static void main(String[] args) {
        long sum = 0;
        int size = 10_000_000;
        Random r = new Random(42); // засеваем_всегда_одинаково
        ArrayList<Integer> arr = new ArrayList<Integer>(size);
        for (int i = 0; i < size; i++) arr.add(i);
        // банзай!!!
        long start = System.currentTimeMillis();
        for (int i = 0; i < size * 10; i++) {
            int t = r.nextInt(size);
            sum += arr.get(t).intValue();
        }
        System.out.println("sum=" + sum + "  время " + (System.currentTimeMillis() - start));
    }
}

а вот результаты, числа это время по тесту, делал по 5 измерений

ArrayList 20964 20758 20978 20931 21016
Array 20947 20603 20555 20689 20505

полагаю, время одинаковое потому что использовались объекты, а не примитивные типы, но я не знаю как заполнить ArrayList примитивами

Для ясности я в первом примере вместо Integer сделал массив int - время выполнения в 2 раза быстрее
Выводы оставляю сделать читателям.
Троллинг и конструктивная критика приветствуется.

@MbICJIuTeJIb_u3 · 24.09.2013, 13:07

Не понимаю зачем сверять массивы и Список реализованный на динамически расширяющимся массиве?
Если вы зарание знаете размер , то следовательно нужно использовать массив.

verylazy · 24.09.2013, 13:27

если это массив не примитивных типов то нет разницы что использовать - список или массив, это видно из результата теста, ваш кэп

но мне просто захотелось сравнить, для себя, будет ли разница между ними или нет...вот, сравнил

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 11.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@tankomaz ɐwʎ ɔ vǝmоɔ dиw ɐʚонɔ 443 / 442 / 100 Регистрация: 14.10.2012 Сообщений: 1,146 Записей в блоге: 9
	20.09.2013, 12:09
	length это некая переменная (поле), которую вы пишите new int[100] а время доступа, как мне кажется, к любому элементу будет одинаковое, ибо jvm четко понимает в какой области памяти какой номер 1

@MbICJIuTeJIb_u3 KeM6Pug}I{a 49 / 49 / 1 Регистрация: 23.08.2013 Сообщений: 202
	24.09.2013, 13:07
	Не понимаю зачем сверять массивы и Список реализованный на динамически расширяющимся массиве? Если вы зарание знаете размер , то следовательно нужно использовать массив. 0

verylazy 462 / 462 / 71 Регистрация: 26.02.2013 Сообщений: 1,263
	24.09.2013, 13:27
	если это массив не примитивных типов то нет разницы что использовать - список или массив, это видно из результата теста, ваш кэп но мне просто захотелось сравнить, для себя, будет ли разница между ними или нет...вот, сравнил 0