Последовательный доступ означает, что стоимость доступа к 5-му элементу в 5 раз превышает стоимость доступа к первому элементу, или, по крайней мере, увеличивается стоимость, связанная с позицией элементов в наборе. Это связано с тем, что для доступа к 5-му элементу набора необходимо сначала выполнить операцию по поиску 1-го, 2-го, 3-го и 4-го элементов, поэтому для доступа к 5-му элементу требуется 5 операций.
Произвольный доступ означает, что доступ к любому элементу набора имеет ту же стоимость, что и доступ к любому другому элементу набора. Поиск 5-го элемента множества по-прежнему является единственной операцией.
Таким образом, доступ к случайному элементу в структуре данных с произвольным доступом будет иметь стоимость O (1), тогда как доступ к случайному элементу в последовательной структуре данных будет иметь стоимость O (n/2) -> O (n) . n/2 исходит из того, что если вы хотите получить доступ к случайному элементу в наборе 100 раз, средняя позиция этого элемента будет примерно на полпути через набор. Таким образом, для набора из n элементов получается n/2 (что в большой нотации O можно просто приблизить к n).
Что-то, что вы можете найти интересным:
Хеш-карты — это пример структуры данных, реализующей произвольный доступ. Интересно отметить, что при коллизиях хэшей в хеш-карте два столкнувшихся элемента сохраняются в последовательном связанном списке в этом сегменте на хэш-карте. Это означает, что если у вас есть 100% коллизий для хеш-карты, вы фактически получаете последовательное хранилище.
Вот изображение хэш-карты, иллюстрирующее то, что я описываю:
Это означает, что наихудший сценарий для хэш-карты на самом деле равен O(n) для доступа к элементу, так же, как и средний случай для последовательного хранения, или, говоря более правильно, поиск элемента в хэш-карте равен Ω(n), O(1). ) и Θ(1). Где Ω — наихудший случай, Θ — наилучший случай, а O — средний случай.
So:
Последовательный доступ: поиск случайного элемента в наборе из n элементов равен Ω(n), O(n/2) и Θ(1), что для очень больших чисел становится Ω(n), O (n) и Θ(1).
Произвольный доступ: поиск случайного элемента в наборе из n элементов равен Ω(n/2), O(1) и Θ(1), что для очень больших чисел становится Ω(n), O (1) и Θ(1)
Таким образом, произвольный доступ обеспечивает более высокую производительность при доступе к элементам, однако последовательные структуры данных хранения обеспечивают преимущества в других областях.
Второе редактирование для @sumsar1812:
Я хочу начать с того, как я понимаю преимущества/варианты использования последовательного хранилища, но я не так уверен в своем понимании преимуществ последовательных контейнеров, как в своем ответе выше. Поэтому, пожалуйста, поправьте меня, где я ошибаюсь.
Последовательное хранение полезно, потому что данные будут храниться в памяти последовательно.
На самом деле вы можете получить доступ к следующему элементу последовательно сохраненного набора данных, сместив указатель на предыдущий элемент этого набора на количество байтов, необходимое для хранения одного элемента этого типа.
Итак, поскольку для хранения подписанного int требуется 8 байтов, если у вас есть фиксированный массив целых чисел с указателем, указывающим на первое целое число:
int someInts[5];
someInts[1] = 5;
someInts — это указатель, указывающий на первый элемент этого массива. Добавление 1 к этому указателю просто смещает место, на которое он указывает в памяти, на 8 байт.
(someInts+1)* //returns 5
Это означает, что если вам нужно получить доступ к каждому элементу в вашей структуре данных в этом конкретном порядке, это будет намного быстрее, поскольку каждый поиск последовательного хранилища просто добавляет постоянное значение к указателю.
Для хранилища с произвольным доступом нет гарантии, что каждый элемент хранится даже рядом с другими элементами. Это означает, что каждый поиск будет дороже, чем простое добавление постоянной суммы.
Контейнеры хранения с произвольным доступом по-прежнему могут имитировать то, что выглядит как упорядоченный список элементов, с помощью итератора. Однако, пока вы разрешаете поиск элементов с произвольным доступом, нет никакой гарантии, что эти элементы будут храниться в памяти последовательно. Это означает, что хотя контейнер может демонстрировать поведение как контейнера с произвольным доступом, так и последовательного контейнера, он не будет демонстрировать преимущества последовательного контейнера.
Таким образом, если порядок элементов в вашем контейнере должен быть значимым или вы планируете выполнять итерации и работать с каждым элементом в наборе данных, вам может быть полезен последовательный контейнер.
По правде говоря, все еще становится немного сложнее, потому что связанный список, который является последовательным контейнером, на самом деле не хранится последовательно в памяти, в отличие от вектора, другого последовательного контейнера. Вот хорошая статья, в которой варианты использования каждого конкретного контейнера объясняются лучше, чем я.
person
echochamber
schedule
10.06.2014
