O (1) поиск в памяти, состоящей из нескольких несмежных участков?
Там кто-либо - известная структура данных, которая обеспечивает O (1) произвольный доступ, не используя непрерывный блок памяти размера O (N) или больше? Это вдохновил этот ответ и просят относительно пользы любопытства, а не относительно любого определенного случая практического применения, хотя это могло бы гипотетически быть полезно в случаях сильно фрагментированной "кучи".
4 ответа
Да, вот пример в C ++:
template<class T>
struct Deque {
struct Block {
enum {
B = 4*1024 / sizeof(T), // use any strategy you want
// this gives you ~4KiB blocks
length = B
};
T data[length];
};
std::vector<Block*> blocks;
T& operator[](int n) {
return blocks[n / Block::length]->data[n % Block::length]; // O(1)
}
// many things left out for clarity and brevity
};
Основное отличие от STD :: deque имеет o (n) push_front вместо o (1), и на самом деле есть немного Проблема, реализующего STD :: DECE, чтобы иметь все из:
- o (1) push_front
- o (1) push_back
- o (1) op []
Возможно я Неверно истолковывается «без использования смежного блока памяти размером O (N) или большее», что кажется неловким. Не могли бы вы уточнить, что вы хотите? Я интерпретировал как «Нет единого распределения, которое содержит один элемент для каждого элемента в представленной последовательности», например, было бы полезно, чтобы избежать больших выделений. (Хотя у меня есть одно выделение размера N / B для вектора.)
Если мой ответ не соответствует вашему определению, то ничто не будет, если вы не пределируете максимальный размер контейнера. (Я могу ограничить вам элементы long_max, вместо этого храните вышеуказанные блоки на дереве, а также вызовите, что O (1) поиск, например.)
Ну, поскольку я потратил время, думая об этом, и это может утверждаться, что все Hashtables являются либо смежным блоком размера> n или имеют список ведров Пропорциональна на массиве верхнего уровня Roger из блока S (N) с коэффициентом менее 1, и я предложил починить это в комментариях к его вопросу, здесь идет:
int magnitude( size_t x ) { // many platforms have an insn for this
for ( int m = 0; x >>= 1; ++ m ) ; // return 0 for input 0 or 1
return m;
}
template< class T >
struct half_power_deque {
vector< vector< T > > blocks; // max log(N) blocks of increasing size
int half_first_block_mag; // blocks one, two have same size >= 2
T &operator[]( size_t index ) {
int index_magnitude = magnitude( index );
size_t block_index = max( 0, index_magnitude - half_first_block_mag );
vector< T > &block = blocks[ block_index ];
size_t elem_index = index;
if ( block_index != 0 ) elem_index &= ( 1<< index_magnitude ) - 1;
return block[ elem_index ];
}
};
template< class T >
struct power_deque {
half_power_deque forward, backward;
ptrdiff_t begin_offset; // == - backward.size() or indexes into forward
T &operator[]( size_t index ) {
ptrdiff_t real_offset = index + begin_offset;
if ( real_offset < 0 ) return backward[ - real_offset - 1 ];
return forward[ real_offset ];
}
};
half_power_deque реализует стирание всех, кроме последнего блока, изменяя half_first_block_mag соответственно. Это позволяет O (MAX со временем N) использованием памяти, амортизированные вставки O (1) на обоих концах, а не недействительными ссылками, а O (1) поиска.
Как насчет карты / словаря? Последний я проверил, это выступление (1).
Вы можете использовать TRIE , где длина ключа ограничена. Как поиск в три с ключом длина m o (m) o (m) , если мы связали длину клавиш, тогда мы связаны m и теперь поиск O (1) .
Так что думайте о TRIE, где ключи являются строками на алфавите {0, 1} (то есть, мы думаем о ключах как двоичное представление целых чисел). Если мы связали длину клавиш, чтобы сказать, что 32 буквы, у нас есть структура, которую мы можем подумать о том, что они проиндексируются 32-битными целыми числами и являются случайным образом доступными в O (1) время.
Вот реализация в C #:
class TrieArray<T> {
TrieArrayNode<T> _root;
public TrieArray(int length) {
this.Length = length;
_root = new TrieArrayNode<T>();
for (int i = 0; i < length; i++) {
Insert(i);
}
}
TrieArrayNode<T> Insert(int n) {
return Insert(IntToBinaryString(n));
}
TrieArrayNode<T> Insert(string s) {
TrieArrayNode<T> node = _root;
foreach (char c in s.ToCharArray()) {
node = Insert(c, node);
}
return _root;
}
TrieArrayNode<T> Insert(char c, TrieArrayNode<T> node) {
if (node.Contains(c)) {
return node.GetChild(c);
}
else {
TrieArrayNode<T> child = new TrieArray<T>.TrieArrayNode<T>();
node.Nodes[GetIndex(c)] = child;
return child;
}
}
internal static int GetIndex(char c) {
return (int)(c - '0');
}
static string IntToBinaryString(int n) {
return Convert.ToString(n, 2);
}
public int Length { get; set; }
TrieArrayNode<T> Find(int n) {
return Find(IntToBinaryString(n));
}
TrieArrayNode<T> Find(string s) {
TrieArrayNode<T> node = _root;
foreach (char c in s.ToCharArray()) {
node = Find(c, node);
}
return node;
}
TrieArrayNode<T> Find(char c, TrieArrayNode<T> node) {
if (node.Contains(c)) {
return node.GetChild(c);
}
else {
throw new InvalidOperationException();
}
}
public T this[int index] {
get {
CheckIndex(index);
return Find(index).Value;
}
set {
CheckIndex(index);
Find(index).Value = value;
}
}
void CheckIndex(int index) {
if (index < 0 || index >= this.Length) {
throw new ArgumentOutOfRangeException("index");
}
}
class TrieArrayNode<TNested> {
public TrieArrayNode<TNested>[] Nodes { get; set; }
public T Value { get; set; }
public TrieArrayNode() {
Nodes = new TrieArrayNode<TNested>[2];
}
public bool Contains(char c) {
return Nodes[TrieArray<TNested>.GetIndex(c)] != null;
}
public TrieArrayNode<TNested> GetChild(char c) {
return Nodes[TrieArray<TNested>.GetIndex(c)];
}
}
}
Вот использование образца:
class Program {
static void Main(string[] args) {
int length = 10;
TrieArray<int> array = new TrieArray<int>(length);
for (int i = 0; i < length; i++) {
array[i] = i * i;
}
for (int i = 0; i < length; i++) {
Console.WriteLine(array[i]);
}
}
}