O(1)在非连续内存中查找？

Question

是否有任何已知的数据结构提供O(1)随机访问,而不使用大小为O(N)或更大的连续内存块？这是受到这个答案的启发,并且被要求出于好奇而不是任何特定的实际用例,尽管它可能在一个严重碎片堆的情况下有用.

Answer 1

Yes, here's an example in 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
};

The main difference from std::deque is this has O(n) push_front instead of O(1), and in fact there's a bit of a problem implementing std::deque to have all of:

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

Perhaps I misinterpreted "without using a contiguous block of memory of size O(N) or greater", which seems awkward. Could you clarify what you want? I've interpreted as "no single allocation that contains one item for every item in the represented sequence", such as would be helpful to avoid large allocations. (Even though I do have a single allocation of size N/B for the vector.)

If my answer doesn't fit your definition, then nothing will, unless you artificially limit the container's max size. (I can limit you to LONG_MAX items, store the above blocks in a tree instead, and call that O(1) lookup, for example.)

Answer 2

您可以使用键长度有限的trie 。由于在键长度为 的 trie 中查找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]);
        }
    }
}