Может ли структура данных иметь O (1) время доступа без использования каких-либо массивов?

Question

Я беру вводный класс CS, и один из первых проектов имел следующие ограничения:

Вы не можете:

• Сделать вашу программу частью пакет.
• Добавьте дополнительные методы или переменные publi c.
• Используйте любые встроенные классы Java Collections Framework в любом месте вашей программы (например, без ArrayList, LinkedList, HashSet, et c.).
• Используйте любые массивы в любом месте вашей программы.
• Добавьте любые дополнительные операторы import (или используйте «полное имя», чтобы обойти добавление import операторов).

Видя ограничения для этого проекта, я задался вопросом, что еще можно сделать в этих ограничениях. Основным ограничением, которое я увидел, было предложение «без массивов».

Можно ли спроектировать структуру данных с учетом этих ограничений, которая имитирует характеристики производительности массива? В частности, структура данных должна представлять последовательность фиксированной длины, поддерживающую операции «get» или «set» по индексу, и эти операции должны занимать O (1) время, независимо от длины последовательности.

Хотя было бы возможно построить графоподобные структуры, такие как связанные списки и деревья, операции «get» и «set» для этих структур данных потребовали бы O (n) или O (log n) времени соответственно. Единственное, о чем я могу думать, это класс с несколькими тысячами закрытых полей и оператором switch для «get» или «set» по индексу, но это будет работать только для последовательностей до фиксированной длины.

Answer 1

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

Пусть D будет (максимальным) числом элементов данных, которое содержит объект, а F будет (максимальным) числом опорных полей, которые содержит объект. Для ясности, D подсчитывает поля, используемые для хранения фактических данных «массива», а F подсчитывает поля, которые используются для самой структуры данных.

Если время доступа равно O (1), тогда вы можете для доступа к ячейке следует не более O (1) ссылок, что означает, что размер вашего «массива» ограничен O (D * F ^ R), где R - это фиксированное ограничение на количество ссылок, которым вы можете следовать для выполнения. одна операция. Если все три из D, F и R являются постоянными, то размер вашего «массива» будет таким же. Из этого следует, что эмуляция характеристик производительности структуры данных массива произвольного размера невозможна с учетом ограничений.

Этот аргумент можно расширить еще немного, чтобы доказать, что R должно быть не менее O (log n) в порядок достижения n отдельных элементов данных; то есть, чтобы получить доступ к элементу, вы должны следовать как минимум за O (log n) ссылками. Вы можете использовать полное двоичное дерево для фактического достижения этой границы.

---

Тем не менее, есть по крайней мере один способ следовать букве правил, не следуя их духу.

Вам строго запрещено использовать массивы или библиотечные классы JCF, но единственные правила в отношении сторонних библиотечных классов заключаются в том, что вы не можете импортировать их или ссылаться на них по полному имени. Вы можете использовать метод ClassLoader.loadClass, чтобы загрузить класс коллекции из сторонней библиотеки, создать его экземпляр с помощью отражения, присвоить его переменной типа Object, а затем вызвать его методы с помощью отражения. Это технически разрешено, потому что loadClass принимает "двоичное имя", а не "полностью определенное имя" класса, который вы хотите загрузить. (Я оставлю это на усмотрение адвокатов, чтобы выяснить, нужно ли вам загружать класс, двоичное имя которого также не полностью квалифицированное имя.)

Для педантов: я интерпретирую правило о массивах гласит, что у вас не должно быть массивов в вашем коде (кроме, предположительно, String[] args в основном методе), а не в массивах в чужих кодах, которые ваш код звонки; в противном случае, например, вашей программе запрещено печатать любые выходные данные, потому что данные, записанные в System.out, буферизуются в массиве. Я думаю, что вряд ли это правило предназначено для запрета на печать любого вывода.

Answer 2

Без какого-либо адресуемого пространства это оставляет вас с древовидной структурой, где каждый узел содержит потенциальное значение и количество дочерних элементов. Один дочерний элемент на узел сделает его связанным списком , два дочерних - двоичное дерево , и чем больше дочерних элементов на узел вы разрешите, тем быстрее будет доступ - в конечном итоге O (1), когда количество дочерних элементов на узел соответствует или превышает размер массива.

Операции для массива:

• инициализация с начальным числом слотов
• получение длины массива
• получение элемента по индексу
• установить элемент в индекс

Я пришел к следующему решению (двоичное дерево, пакет и модификатор publi c для методов, опущенных по запросу, что делает его пригодным для использования только из значений по умолчанию пакет):

public class Array<T> {

    private final int length;
    private final Cell<T> root = new Cell<>();

    Array(int length) {
        if (length < 0) {
            throw new IllegalArgumentException("Array length must be >=0")
        }
        this.length = length;
    }

    T get(int index) {
        return cell(index).value;
    }

    void set(int index, T value) {
        cell(index).value = value;
    }

    int length() {
        return length;
    }

    private Cell<T> cell(int index) {
        if (index < 0 || index >= length) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        Cell<T> pointer = root;
        while (index > 0) {
            pointer = (index & 1) == 0 ? pointer.left() : pointer.right();
            index >>= 1;
        }
        return pointer;
    }

    private class Cell<T> {

        private Cell<T> left;
        private Cell<T> right;
        private T value;

        Cell<T> left() {
            return left = left != null ? left : new Cell<>();
        }

        Cell<T> right() {
            return right = right != null ? right : new Cell<>();
        }
    }
}