O (1) поиск в несмежной памяти?

Question

Существует ли какая-либо известная структура данных, которая обеспечивает O (1) произвольный доступ, без использования непрерывного блока памяти размером O (N) или больше? Это было вдохновлено этим ответом и его спрашивают ради любопытства, а не для какого-либо конкретного практического использования, хотя это может гипотетически быть полезным в случаях сильно фрагментированной кучи.

Answer 1

Да, вот пример на 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 :: deque, чтобы all :

1. O (1) push_front
2. O (1) push_back
3. O (1) op []

---

Возможно, я неверно истолковал «не используя непрерывный блок памяти размером O (N) или больше», что кажется неудобным. Не могли бы вы уточнить, что вы хотите? Я интерпретировал как «нет единого распределения, которое содержит один элемент для каждого элемента в представленной последовательности», что было бы полезно, чтобы избежать больших распределений. (Хотя у меня есть одно распределение размера N / B для вектора.)

Если мой ответ не соответствует вашему определению, то ничего не подойдет, если вы не искусственно ограничите максимальный размер контейнера. (Я могу ограничить вас элементами LONG_MAX, вместо этого сохранить вышеупомянутые блоки в дереве и вызвать этот поиск O (1), например.)

Answer 2

Вы можете использовать три , где длина ключа ограничена. Так как поиск в дереве с ключом длины m равен O(m), если мы ограничиваем длину ключей, тогда мы ограничиваем m, и теперь поиск равен O(1).

Итак, представьте, что ключи - это строки в алфавите { 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]);
        }
    }
}

Answer 3

Ну, так как я потратил время на размышления об этом, и можно утверждать, что все хеш-таблицы являются либо непрерывным блоком размером> N, либо имеют список блоков, пропорциональный N, и вершину Роджера -уровень массива Block s равен O (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 (максимум за время N) памяти, амортизированные вставки O (1) на обоих концах, никогда не отменять ссылки и искать O (1).

Answer 4

Как насчет карты / словаря?Последнее, что я проверил, это производительность O (1).