Какая структура данных лучше всего сочетает сильные стороны словаря и списка

Question

A вопрос Я недавно спросил, заставил меня задуматься о следующем:

Какова структура данных для хранения пары (ключ, значение) такой, что:

• его элементы упорядочены
• d[key] -> val имеет сложность O(dict)
• d(index) -> (key, val) имеет сложность O(list)
• обеспечивает обратный поиск d{val} -> (index, key) со сложностью O(dict)
• использует наименьшее возможное хранилище

Когда я набираю O(type), я имею в виду ту же сложность операции, что и структура данных type.

Например, если упорядоченная коллекция:

c = {key_1:val_1, key_2:val_2, key_3:val_3}

Я бы хотел получить

 c[key_1] # returns val_1, as in a dictionary
 c(1)     # returns val_2, as in a list
 c{val_3} # returns (2, key_3) as in a sort of "indexed dictionary"

Answer 1

Вы не упомянули стоимость вставки, что также является важной проблемой.Вы можете сделать это с помощью лексически упорядоченного словаря и обрабатывать запросы, используя двоичный поиск (который равен log(n)).Однако вам нужно будет поддерживать две такие структуры: одну идущую клавишу -> val и одну идущую val-> key, поэтому стоимость вставки будет удвоена, а необходимость вставлять элементы в середину означает, что O(n)(т. е. так же, как для списка).

Answer 2

У меня была такая же проблема. Поэтому я взял исходный код java.util.TreeMap и написал IndexedTreeMap . Он реализует мою собственную IndexedNavigableMap :

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

Реализация основана на обновлении весов узлов в красно-черном дереве при его изменении. Вес - это количество дочерних узлов под данным узлом, плюс один - «я». Например, когда дерево поворачивается влево:

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

updateWeight просто обновляет вес до корня:

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

И когда нам нужно найти элемент по индексу, вот реализация, которая использует весовые коэффициенты:

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

Также очень удобно находить индекс ключа:

    public int keyIndex(K key) {
    if (key == null) {
        throw new NullPointerException();
    }
    Entry<K, V> e = getEntry(key);
    if (e == null) {
        throw new NullPointerException();
    }
    if (e == root) {
        return getWeight(e) - getWeight(e.right) - 1;//index to return
    }
    int index = 0;
    int cmp;
    if (e.left != null) {
        index += getWeight(e.left);
    }
    Entry<K, V> p = e.parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        while (p != null) {
            cmp = cpr.compare(key, p.key);
            if (cmp > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        while (p != null) {
            if (k.compareTo(p.key) > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    }
    return index;
}

Результат этой работы вы можете найти на http://code.google.com/p/indexed-tree-map/

Answer 3

Вы запрашиваете поиск O (1) по ключу и индексу, а также поиск значений O (1). Вы можете сделать это, поддерживая хеш-структуру данных для ключа / значений, вторую хеш-структуру для обратного просмотра и структуру данных списка для упорядоченных списков-> сопоставлений клавиш. Вы все равно будете иметь O (n) вставок и удалений, и ваша сложность пространства будет в 3 раза больше, чем обычно.

Если вы хотите пойти на компромисс в отношении скорости, вы можете сэкономить место, есть множество заданных структур данных, основанных на деревьях (например, TreeSet в Java), операции которых имеют сложность log (n).

Это всегда компромисс