В Java supppose мне нужно получить доступ к array1[index] много раз в коде.Сложность доступа к массиву
Даже для чрезвычайно больших массивов, могу ли я предположить, что каждый доступ к одному массиву занимает постоянное время?
Может ли это отличаться от языков или базовой архитектуры?
Для больших значений array1 size N можно предположить, что каждый доступ к одному массиву (array1 [index]) занимает постоянное время?
В Java, да. Также в C, C++ и C#, запрещающие проблемы подкачки на уровне OS, которые предположительно выходят за рамки.
Зависит ли это время доступа от языка (java vs C++) или базовой архитектуры?
Это может быть, если рассматриваемый язык называет вещи «массивами», которые на самом деле не являются массивами в обычном смысле «непрерывного блока памяти». (JavaScript делает это: Array ([]) тип is really a map; PHP использует термин «массив» как сокращенное выражение для «ассоциативного массива» [например, map].) Поэтому для данной среды/языка стоит проверить, что термин isn ' т злоупотребления или использования свободно.
Поиск в массиве всегдаO(1). Он не зависит от размера массива. Основная идея массивов состоит в том, что он содержит объекты/ссылки с фиксированным размером, поэтому вы можете просто сделать size * index, чтобы иметь позицию объекта, который вы ищете.
Так что не как LinkedList (который O(n) ни HashMap что O(1) амортизируется.
Я думаю, что это имеет место в большинстве языков. Исключение может быть Javascript поэтому убедитесь, что вы проверить документацию для язык, который вы используете.
Размер массива определенно играет роль, учитывая, что более крупные массивы могут не помещаться на странице памяти. – Dukeling
Это не то же самое на каждом языке - один из других ответов упоминает javascript, например. –
Это проблема подкачки памяти, а не проблема языка. –
Доступ к элементу в массиве постоянное время (он просто вычисляет смещение адреса). Это поведение согласовано для всех языков, которые вы указали. Хотя это не следует предполагать для всех языков, это будет применяться к большинству.
Существуют некоторые сложности с точки зрения промаха/удара кеша, конвейеров и т. Д., Но по существу его постоянное время.
Это не тот случай, если для списка. Некоторые реализации списков дают разные характеристики производительности для разных операций.
Для расширения сложности:
Вопрос был «будут большие массивы получить медленный доступ». Правильный ответ «да».
Он останется О (1) с точки зрения порядка доступа, но фактический доступ потенциально может занять значительно больше времени. Например, он будет медленнее, если размер массива заставит вас получить пропуски кэша (поэтому данные нужны для извлечения из основной памяти в кэш процессора) и/или проблемы подкачки памяти (так что данные требуют выборки с диска), хотя это является свойством любого большого набора данных, а не только массивов.
Для большинства случаев разница не стоит беспокоиться. Мы говорим о довольно большой оптимизации, прежде чем вы начнете беспокоиться о таких вещах, как промахи в кеше. Однако стоит быть в курсе этих вещей, как этот вопрос иллюстрирует:
Why is it faster to process a sorted array than an unsorted array?
А, казалось бы, несущественных деталей (предварительной сортировки массива) на код, который на лице его всегда должны занимать то же время побежал в пять раз быстрее, чем детализация работы процессора.
http://array-arraylist-linkedlist.blogspot.co.uk/ – christopher