Стек и хэш-соединение

Question

Я пытаюсь написать структуру данных, которая представляет собой комбинацию Stack и HashSet с быстрым push / pop / членством (я ищу операции с постоянным временем). Подумайте о OrderedDict Python.

Я попробовал несколько вещей, и я получил следующий код: HashInt и SetInt . Мне нужно добавить некоторую документацию к источнику, но в основном я использую хеш с линейным зондированием для хранения индексов в векторе ключей. Поскольку линейное зондирование всегда помещает последний элемент в конец непрерывного диапазона уже заполненных ячеек, pop () может быть реализовано очень просто без сложной операции удаления.

У меня есть следующие проблемы:

• структура данных занимает много памяти (некоторое улучшение очевидно: stackKeys больше, чем нужно).
• некоторые операции выполняются медленнее, чем если бы я использовал fastutil (например, pop (), даже push () в некоторых сценариях). Я попытался переписать классы, используя fastutil и trove4j, но общая скорость моего приложения сократилась вдвое.

Какие улучшения производительности вы бы предложили для моего кода? Какую библиотеку / код с открытым исходным кодом вы знаете, что я могу попробовать?

Answer 1

У вас уже есть довольно хорошая реализация. Единственное улучшение, очевидное для меня, заключается в том, что вы выполняете больше работы, чем нужно, выполняя поиск при всплытии. В стеке следует хранить не сам ключ, а индекс в массиве ключей . Это дает вам тривиально быстрое всплывающее окно за счет только одного косвенного указателя, когда вы хотите посмотреть последний элемент.

Просто увеличьте размер стека до LOAD_FACTOR * (размер массива кучи), и вы получите примерно такую ​​же быструю реализацию, какую ожидаете, с минимальным объемом памяти, каким вы можете управлять, учитывая ваши требования к скорости.

Answer 2

Я думаю, что то, что вы хотите, (почти) уже доступно в библиотеках: LinkedHashSet - это хэш-набор с базовым двусвязным списком (что делает его итеративным). LinkedHashMap даже имеет метод removeEldestEntry, который звучит очень похоже на pop-метод.

Как производительность наивного решения, такого как:

class HashStack<T> {

    private HashMap<T, Integer> counts = new HashMap<T, Integer>();
    private Stack<T> stack = new Stack<T>();

    public void push(T t) {
        stack.push(t);
        counts.put(t, 1 + getCount(t));
    }

    public T pop() {
        T t = stack.pop();
        counts.put(t, counts.get(t) - 1);
        return t;
    }

    private int getCount(T t) {
        return counts.containsKey(t) ? counts.get(t) : 0;
    }

    public boolean contains(T t) {
        return getCount(t) > 0;
    }

    public String toString() {
        return stack.toString();
    }
}

Answer 3

Я бы предложил использовать TreeSet , поскольку он обеспечивает гарантированную стоимость O (log n) для добавления, удаления и хранения.