Редактирование: ПОД (3 поток), Ответы
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 322 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 433: | Строка 433: | ||
В современных компьютерах многоуровневая структура кэша, которая позволяет очень быстро выполнять обход массива. Попадание кэша настолько быстрая операция, что можно учитывать только промахи. Если строка кэша имеет размер B, то колличество промахов в массиве равно n/B. Если рассматривать связный список, то в худшем случае на доступ к каждому узлу будет приходится промах. Но даже в лучшем случае, когда узлы списка расположенны последовательно, из-за того, что узел у списка больше, может потребоваться в несколько раз больше кэша для прохода по списку. | В современных компьютерах многоуровневая структура кэша, которая позволяет очень быстро выполнять обход массива. Попадание кэша настолько быстрая операция, что можно учитывать только промахи. Если строка кэша имеет размер B, то колличество промахов в массиве равно n/B. Если рассматривать связный список, то в худшем случае на доступ к каждому узлу будет приходится промах. Но даже в лучшем случае, когда узлы списка расположенны последовательно, из-за того, что узел у списка больше, может потребоваться в несколько раз больше кэша для прохода по списку. | ||
- | Пусть у нас есть массив из 60 миллионов элементов и мы хотим вставить элементы в середину. Несмотря на преимущества, которые дает кэш, эта операция займет недели | + | Пусть у нас есть массив из 60 миллионов элементов и мы хотим вставить элементы в середину. Несмотря на преимущества, которые дает кэш, эта операция займет недели. |
Поэтому в программах, где вставка и удаление элементов является частой операцией, массивы неприменимы. Также недостатком массивов явлеется то, что они медленно увеличиваются и фрагментируют память. | Поэтому в программах, где вставка и удаление элементов является частой операцией, массивы неприменимы. Также недостатком массивов явлеется то, что они медленно увеличиваются и фрагментируют память. | ||