Какие структуры данных следует использовать при хранении нескольких объектов с несколькими критериями запроса?

Ответ 1

Для получения номера пространства для хранения я использовал метод минимальной кучи, PriorityQueue. Это работает в O (log n) времени, удалении и вставке.

Я использовал 2 BiMaps, самодвижущиеся структуры данных, для хранения сопоставления между UIN, цветом и номером пространства памяти. Эти BiMaps использовали внутри HashMap и массив размера N.

В первом BiMap (BiMap1) a HashMap<color, Set<StorageSpace>> сохраняет отображение цвета в список пространств хранения. И массив String String[] colorSpace, который сохраняет цвет в индексе пространства хранения.

Во втором BiMap (BiMap2) a HashMap<UIN, storageSpace> stores the mapping between UIN and storageSpace. And a string array String [] uinSpace` хранит UIN в индексе пространства хранения.

Выполнение запроса выполняется с помощью этого подхода:

• Когда цвет ввода, покажите все UIN, связанные с этим цветом.    Получите список пространств хранения из BiMap1, поскольку эти пространства используют массив в BiMap2 для получения соответствующих UIN.
• Когда цвет ввода, покажите все номера, на которых размещены эти пакеты (номер пространства памяти). Используйте BiMap1 HashMap для получения списка.
• Показать, где находится элемент с заданным UIN, т.е. номер пространства памяти. Использовать BiMap2 для получения значений из HashMap.

Теперь, когда нам предоставляется место для хранения, необходимо обновить BiMaps. В BiMap1 получить запись из массива, получить соответствующий ответ и удалить номер пробела из этого набора. Из BiMap2 получите UIN из массива, удалите его и удалите из HashMap.

Для обоих BiMaps удаление и операции вставки - это O (1). И Min heap работает в O (Log n), поэтому общая временная сложность - O (Log N)

Ответ 2

Вы упомянули три запроса, которые хотите сделать. Позвольте обрабатывать их один за другим.

Я не могу представить ни одной структуры данных, которая может помочь вам со всеми тремя запросами одновременно. Поэтому я дам ответ, который содержит три структуры данных, и вам нужно будет поддерживать все три состояния DS, чтобы приложение работало должным образом. Подумайте, что в качестве стоимости получения очень высокой производительности из вашего приложения для желаемой функциональности.

Когда цвет ввода, покажите все UIN, связанные с этим цветом.

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

• Добавлен

• - Посмотрите, присутствует ли цвет в HashMap. Если да, добавьте этот UIN в set else, создайте новую запись с новым набором и затем добавьте UIN.

• удален. Найдите набор для этого цвета и удалите этот UIN из набора. Если набор теперь пуст, вы можете полностью удалить эту запись.

Когда цвет ввода, укажите все номера, на которых расположены эти пакеты.

Поддерживать HashMap, который отображает UIN на номер, где размещается входящий пакет. Из HashMap, который мы создали в предыдущем случае, вы можете получить список всех UIN, связанных с данным цветом. Затем, используя этот HashMap, вы можете получить номер для каждого UIN, который присутствует в наборе для этого цвета.

Итак, теперь, когда пакет должен быть добавлен, вам нужно будет добавить запись в предыдущую HashMap в конкретном цветовом ведре и в эту HashMap. При удалении вам потребуется .Remove() запись отсюда.

Наконец,

Показывает, где размещается элемент с заданным UIN.

Если вы сделали предыдущее, у вас уже есть HashMap, отображающий UINs для чисел. Эта проблема является только суб-проблемой предыдущего.

Третий DS, как я упоминал выше, будет Min-Heap из ints. Куча будет инициализирована с первыми N целыми числами в начале. Затем, когда пакеты придут, куча будет опрошена. Возвращаемое число будет представлять собой пространство для хранения, в которое должен быть установлен этот пакет. Если блок хранения заполнен, куча будет пустой. Всякий раз, когда пакет будет удален, его номер будет добавлен обратно в кучу. Поскольку это минимальная куча, минимальное число будет пузыриться до вершины, удовлетворяя вашему случаю, когда 4 и 2 пустые, следующее заполняемое пространство будет 4.

Сделайте завершение Big O анализа этого решения.

• Время для инициализации: из этой установки будет O (N), потому что нам придется инициализировать кучу N. Другие два HashMaps будут пустыми для начала и, следовательно, не будут иметь временных затрат.

• Время для добавления пакета: будет включать время, чтобы получить номер, а затем сделать соответствующие записи в HashMaps. Чтобы получить число из кучи, время O (Log N) будет приниматься макс. Добавление записей в HashMaps будет O (1). Следовательно, в худшем случае общее время O (Log N).

• Время для удаления пакета: в худшем случае будет O (Log N), потому что время для удаления из HashMaps будет O (1) только тогда, когда время для добавления освобожденного номера обратно в min- куча будет ограничена сверху O (Log N).

Ответ 3

Это пахнет домашней работой или действительно плохим управлением.

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

Tl; DR - для решения вашей проблемы я используйте PriorityQueue, Array, HashMap и ArrayListMultimap (из guava, общей внешней библиотеки), каждая из которых может решить другую проблему.

Следующий раздел - это рабочий код, который просматривает несколько простых вставок, запросов и удалений. Этот следующий бит на самом деле не является Java, поскольку я уничтожил большую часть импорта, объявление класса и т.д. Кроме того, он ссылается на другой класс под названием "Packg". Это просто простая структура данных, которую вы должны иметь возможность выяснить только из сделанных ей вызовов.

Объяснение ниже кода

import com.google.common.collect.ArrayListMultimap;

private PriorityQueue<Integer> openSlots;
private Packg[] currentPackages;
Map<Long, Packg> currentPackageMap;
private ArrayListMultimap<String, Packg> currentColorMap;
private Object $outsideCall;


public CrazyDataStructure(int howManyPackagesPossible) {
    $outsideCall = new Object();
    this.currentPackages = new Packg[howManyPackagesPossible];
    openSlots = new PriorityQueue<>();
    IntStream.range(0, howManyPackagesPossible).forEach(i -> openSlots.add(i));//populate the open slots priority queue
    currentPackageMap = new HashMap<>();
    currentColorMap = ArrayListMultimap.create();
}

/*
 * args[0] = integer, maximum # of packages
 */
public static void main(String[] args)
{
    int howManyPackagesPossible = Integer.parseInt(args[0]);
    CrazyDataStructure cds = new CrazyDataStructure(howManyPackagesPossible);
    cds.addPackage(new Packg(12345, "blue"));
    cds.addPackage(new Packg(12346, "yellow"));
    cds.addPackage(new Packg(12347, "orange"));
    cds.addPackage(new Packg(12348, "blue"));
    System.out.println(cds.getSlotsForColor("blue"));//should be a list of {0,3}
    System.out.println(cds.getSlotForUIN(12346));//should be 1 (0-indexed, remember)
    System.out.println(cds.getSlotsForColor("orange"));//should be a list of {2}
    System.out.println(cds.removePackage(2));//should be the orange one
    cds.addPackage(new Packg(12349, "green"));
    System.out.println(cds.getSlotForUIN(12349));//should be 2, since that open
}

public int addPackage(Packg packg)
{
    synchronized($outsideCall)
    {
        int result = openSlots.poll();
        packg.setSlot(result);
        currentPackages[result] = packg;
        currentPackageMap.put(packg.getUIN(), packg);
        currentColorMap.put(packg.getColor(), packg);
        return result;
    }
}

public Packg removePackage(int slot)
{
    synchronized($outsideCall)
    {
        if(currentPackages[slot] == null)
            return null;
        else
        {
            Packg packg = currentPackages[slot];
            currentColorMap.remove(packg.getColor(), packg);
            currentPackageMap.remove(packg.getUIN());
            currentPackages[slot] = null;
            openSlots.add(slot);//return slot to priority queue
            return packg;
        }
    }
}

public List<Packg> getUINsForColor(String color)
{
    synchronized($outsideCall)
    {
        return currentColorMap.get(color);
    }
}

public List<Integer> getSlotsForColor(String color)
{
    synchronized($outsideCall)
    {
        return currentColorMap.get(color).stream().map(packg -> packg.getSlot()).collect(Collectors.toList());
    }
}

public int getSlotForUIN(long uin)
{
    synchronized($outsideCall)
    {
        if(currentPackageMap.containsKey(uin))
            return currentPackageMap.get(uin).getSlot();
        else
            return -1;
    }
}

Я использую 4 разных структуры данных в своем классе.

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

Массив Я использую обычный массив для отслеживания по слоту #. Это линейно для памяти и константа для вставки и удаления. Если вам нужно больше гибкости в количестве слотов, которые у вас есть, вам, возможно, придется отключить это для ArrayList или что-то в этом роде, но тогда вам нужно будет найти лучший способ отслеживать "пустые" слоты.

HashMap ah, HashMap, золотой ребенок сложности BigO. В обмен на некоторые издержки памяти и раздражающую заглавную букву "M", это потрясающая структура данных. Вставки являются разумными, а запросы постоянны. Я использую его для сопоставления между UID и слотом для Packg.

ArrayListMultimap единственная структура данных, в которой я использую эту неровную Java. Это происходит от Guava (Google, в основном), и это просто приятный небольшой ярлык для написания собственной карты списков. Кроме того, он отлично играет с нулями, и это бонус для меня. Это, пожалуй, наименее эффективный из всех структур данных, но и тот, который обрабатывает самую сложную задачу, поэтому... не могу винить его. это позволяет нам захватить список Packg по цвету, в постоянное время относительно количества слотов и в линейном времени относительно количества возвращаемых объектов Packg.

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

Ответ 4

Запрос 3. Используйте хэш-карту, ключ UIN, значение - это объект (номер пространства памяти, цвет) (и больше информации о пакете). Стоимость - O (1) для запроса, вставки или удаления. Пространство равно O (k), где k - текущее число UIN.

Запрос 1 и 2: используйте хэш-карту + несколько списков ссылок

Карта хэша, ключ - цвет, значение - указатель (или ссылка в Java), чтобы связать список соответствующих UIN для этого цвета.

Каждый список ссылок содержит UIN.

Для запроса 1: спросите хэш-карту, затем верните соответствующий список ссылок. Стоимость O (k1), где k1 - количество UIN для цвета запроса. Пространство равно O (m + k1), где m - количество уникального цвета.

Для запроса 2: выполните запрос 1, затем примените запрос 3. Стоимость - O (k1), где k1 - количество UIN для цвета запроса. Пространство равно O (m + k1), где m - количество уникального цвета.

Вставить: заданный цвет, число и UIN, вставить в хэш-карту запроса 3 объект (num, color); hash (color), чтобы перейти в соответствующий список ссылок и вставить UIN.

Чтобы удалить:, учитывая UIN, спросите запрос 3 для цвета, затем попросите запрос 1 удалить UIN в списке ссылок. Затем удалите UIN в хэш-карте запроса 3.

Бонус: для управления дисковым пространством ситуация такая же, как и управление памятью в ОС: читать дальше

Ответ 5

Это очень просто сделать с SegmentTree. Просто сохраните позицию в каждом месте и запросите мин, она будет соответствовать свободному месту, когда вы захватите место, просто назначьте 0 этому месту. Информация о пакете возможна в отдельном массиве.

• Initiall имеет следующие значения:
• 1 2 3 4
• После захвата он будет выглядеть следующим образом:
• 0 2 3 4
• После захвата еще один выглядит следующим образом:
• 0 0 3 4
• После захвата еще один выглядит следующим образом:
• 0 0 0 4
• После очистки 2 он будет выглядеть следующим образом:
• 0 2 0 4
• После захвата еще один выглядит следующим образом:
• 0 0 0 4

ans и так далее.

Если у вас есть дерево сегментов для извлечения min on range, это можно сделать в O (LogN) для каждой операции.

Здесь моя реализация в С#, это легко перевести на С++ Java.

public class SegmentTree
{
    private int Mid;
    private int[] t;

    public SegmentTree(int capacity)
    {
        this.Mid = 1;
        while (Mid <= capacity) Mid *= 2;
        this.t = new int[Mid + Mid];


        for (int i = Mid; i < this.t.Length; i++) this.t[i] = int.MaxValue;
        for (int i = 1; i <= capacity; i++) this.t[Mid + i] = i;
        for (int i = Mid - 1; i > 0; i--) t[i] = Math.Min(t[i + i], t[i + i + 1]);
    }

    public int Capture()
    {
        int answer = this.t[1];
        if (answer == int.MaxValue)
        {
            throw new Exception("Empty space not found.");
        }

        this.Update(answer, int.MaxValue);

        return answer;
    }

    public void Erase(int index)
    {
        this.Update(index, index);
    }

    private void Update(int i, int value)
    {
        t[i + Mid] = value;
        for (i = (i + Mid) >> 1; i >= 1; i = (i >> 1))
            t[i] = Math.Min(t[i + i], t[i + i + 1]);
    }
}

Здесь пример использования:

    int n = 4;
    var st = new SegmentTree(n);

    Console.WriteLine(st.Capture());
    Console.WriteLine(st.Capture());
    Console.WriteLine(st.Capture());
    st.Erase(2);
    Console.WriteLine(st.Capture());
    Console.WriteLine(st.Capture());