Как создать структуру данных, которая позволяет искать, вставлять и удалять целое число X в O (1) раз - программирование
Подтвердить что ты не робот

Как создать структуру данных, которая позволяет искать, вставлять и удалять целое число X в O (1) раз

Вот упражнение (3-15) в книге "Руководство по разработке алгоритмов".

Создайте структуру данных, которая позволяет искать, вставлять и удалять целое число X в O (1) раз (т.е. постоянное время, независимо от общего количества сохраненных целых чисел). Предположим, что 1 ≤ X ≤ n и что существуют m + n единиц пространства, где m - максимальное количество целых чисел, которое может быть в таблице в любой момент времени. (Подсказка: используйте два массива A [1..n] и B [1..m].) Вам не разрешено инициализировать A или B, так как это займет операции O (m) или O (n). Это означает, что массивы полны случайного мусора, поэтому вы должны быть очень осторожны.

Я действительно не ищу ответа, потому что я даже не понимаю, что это упражнение просит.

Из первого предложения:

Создайте структуру данных, которая позволяет искать, вставлять и удалять целое число X в O (1) время

Я могу легко создать такую ​​структуру данных. Например:

Поскольку 1 <= X <= n, поэтому у меня есть только бит-вектор из n слотов, и пусть X является индексом массива, когда вставка, например, 5, затем a [5] = 1; при удалении, например, 5, затем a [5] = 0; при поиске, например, 5, я могу просто вернуть [5], правильно?

Я знаю, что это упражнение сложнее, чем я себе представляю, но каков ключевой момент этого вопроса?

4b9b3361

ОТВЕТЫ

Ответ 1

В основном вы реализуете мультимножество с ограниченным размером, как в количестве элементов (#elements <= m), так и в допустимом диапазоне для элементов (1 <= elementValue <= n).

  • Поиск: myCollection.search(x) → return True, если x внутри, else False
  • Вставить: myCollection.insert(x) → добавить ровно один x в коллекцию
  • Удалить: myCollection.delete(x) → удалить ровно один x из коллекции

Рассмотрим, что произойдет, если вы попытаетесь сохранить 5 дважды, например

myCollection.insert(5)
myCollection.insert(5)

Вот почему вы не можете использовать бит-вектор. Но в нем говорится "единицы" пространства, поэтому разработка вашего метода состояла бы в том, чтобы вести подсчет каждого элемента. Например, у вас может быть [_,_,_,_,1,_,...], затем [_,_,_,_,2,_,...].

Почему это не работает? Кажется, что это работает отлично, например, если вы вставляете 5, а затем удаляете 5... но что произойдет, если вы делаете .search(5) в неинициализированном массиве? Вам определенно сказано, что вы не можете его инициализировать, поэтому вы не можете сказать, действительно ли значение, которое вы найдете в этом фрагменте памяти e.g. 24753, на самом деле означает "существует 24753 экземпляра 5" или если он мусор.

ПРИМЕЧАНИЕ. Вы должны разрешить себе пространство инициализации O(1), или проблема не может быть решена. (В противном случае a .search() не сможет отличить случайный мусор в вашей памяти от фактических данных, потому что вы всегда можете найти случайный мусор, похожий на фактические данные.) Например, вы можете подумать о наличии логического значения, которое означает "I начали использовать мою память", которую вы инициализируете до False, и установите значение True в тот момент, когда вы начнете писать свои слова памяти m.

Если вам нужно полное решение, вы можете навести курсор на серый блок, чтобы показать тот, с которым я столкнулся. Это всего лишь несколько строк кода, но доказательства немного длиннее:

СПОЙЛЕР: ПОЛНОЕ РЕШЕНИЕ  
 
  Настройка:  
 Используйте N слов в качестве таблицы рассылки: locationOfCounts[i] - это массив размера N со значениями в диапазоне location=[0,M]. Это место, где будет храниться счетчик i, но мы можем доверять только этому значению, если мы можем доказать, что это не мусор. > !
 (sidenote: Это эквивалентно массиву указателей, но массив указателей предоставляет вам возможность поиска мусора, поэтому вам придется кодировать эту реализацию с помощью проверок диапазона указателей.)  
 
 Чтобы узнать, сколько i есть в коллекции, вы можете посмотреть вверху значение counts[loc]. Мы используем M-слова как сами счетчики: counts - это массив размера N с двумя значениями для каждого элемента. Первое значение - это число, которое представляет, а второе значение - это количество (в диапазоне [1, м]). Например, значение (5,2) означает, что в коллекции хранятся 2 экземпляра числа 5.  
 (M слов достаточно места для всех отсчетов. Доказательство. Мы знаем, что никогда не может быть больше, чем M элементов, поэтому в худшем случае мы имеем M counts value = 1. QED)  
 (Мы также хотим отслеживать только counts >= 1, иначе нам не хватило бы памяти.)  
 
 Используйте номер с именем numberOfCountsStored, который инициализируется до 0, но обновляется всякий раз, когда изменяется количество типов элементов. Например, это число будет 0 для {}, 1 для {5:[1 times]}, 1 для {5:[2 times]} и 2 для {5:[2 times],6:[4 times]}.  
 
                           1  2  3  4  5  6  7  8...  
 locationOfCounts[<N]: [☠, ☠, ☠, ☠, ☠, 0, 1, ☠, ...]  
 counts[<M]:           [(5,⨯2), (6,⨯4), ☠, ☠, ☠, ☠, ☠, ☠, ☠, ☠..., ☠]  
 numberOfCountsStored:          2  
 
 Ниже мы очищаем детали каждой операции и доказываем, почему это правильно:  
 
  Алгоритм:  
 Существуют две основные идеи: 1) мы никогда не сможем позволить себе читать память, не проверяя, что это не мусор в первую очередь, или если мы это сделаем, мы должны быть в состоянии доказать, что это мусор, 2) нам нужно иметь возможность доказать в O(1) время инициализации фрагмента памяти counter с пробелом O(1). Чтобы обойти это, используемое нами пространство O(1) numberOfItemsStored. Каждый раз, когда мы выполняем операцию, мы вернемся к этому номеру, чтобы доказать, что все было правильно (например, см. Ниже). Инвариант представления состоит в том, что мы всегда будем хранить counts в counts, идущем слева направо, поэтому numberOfItemsStored всегда будет максимальным индексом массива, который действителен.  
 
  .search(e)- Проверьте locationsOfCounts[e]. Предположим теперь, что значение правильно инициализировано и может быть доверено. Мы переходим к проверке counts[loc], но сначала проверяем, была ли инициализирована counts[loc]: она инициализируется, если 0 <= loc < numberOfCountsStored (если нет, данные являются бессмысленными, поэтому мы возвращаем False). После проверки, мы посмотрим counts[loc], который дает нам пару number,count. Если number!= e, мы попали сюда, следуя рандомизированному мусору (бессмысленно), поэтому мы возвращаем False (опять как указано выше)... но если действительно number == e, это доказывает, что счет (доказательство ★: numberOfCountsStored является свидетелем того, что этот конкретный counts[loc] действителен, а counts[loc].number является свидетелем того, что locationOfCounts[number] действителен, и, следовательно, наш первоначальный поиск не был мусором.), поэтому мы вернемся Правда.  
 
  .insert(e). Выполните шаги в .search(e). Если он уже существует, нам нужно только увеличить счет на 1. Однако, если он не существует, мы должны применить новую запись справа от подматрицы counts. Сначала мы увеличиваем numberOfCountsStored, чтобы отразить тот факт, что этот новый счет действителен: loc = numberOfCountsStored++. Затем мы применим новую запись: counts[loc] = (e,⨯1). Наконец, мы добавим ссылку на нее в нашу таблицу рассылки, чтобы быстро найти ее locationOfCounts[e] = loc.  
 
  .delete(e). Выполните шаги в .search(e). Если он не существует, введите ошибку. Если счетчик = 2, все, что нам нужно сделать, это уменьшить счет на 1. В противном случае счет будет равен 1, а трюк здесь, чтобы обеспечить неизменность целого numberOfCountsStored - counts[...] (т.е. Все остается сохраненным слева часть counts) - выполнять свопы. Если удаление удалит последний элемент, мы потеряем пару counts, оставив отверстие в нашем массиве: [countPair0, countPair1, _hole_, countPair2, countPair{numberOfItemsStored-1}, ☠, ☠, ☠..., ☠]. Мы заменяем это отверстие последним countPair, уменьшаем numberOfCountsStored, чтобы аннулировать отверстие, и обновляем locationOfCounts[the_count_record_we_swapped.number], чтобы теперь он указывал на новое местоположение записи счетчика.

Ответ 2

Вот идея:

рассмотрите массив B [1..m] как стек и сделайте указатель p, чтобы указать на вершину стека (пусть p = 0, чтобы указать, что никакие элементы не были вставлены в структуру данных). Теперь, чтобы вставить целое число X, используйте следующую процедуру:

p++;
A[X] = p;
B[p] = X;

Поиск здесь довольно легко увидеть (пусть X '- целое число, которое вы хотите найти, а затем просто проверьте, что 1 <= A [X'] <= p, и что B [A [X ' ]] == X '). Удаление более сложное, но все же постоянное время. Идея состоит в том, чтобы найти элемент, чтобы подтвердить, что он есть, а затем переместить что-то на свое место в B (хороший выбор - B [p]). Затем обновите A, чтобы отразить значение указателя замещающего элемента и вытащите верхнюю часть стека (например, установите B [p] = -1 и декремент p).

Ответ 3

Легче понять вопрос, как только вы узнаете ответ: целое число находится в наборе, если A[X]<total_integers_stored && B[A[X]]==X.

Вопрос действительно спрашивает, можете ли вы понять, как создать структуру данных, которая может использоваться с минимальной инициализацией.

Ответ 4

Я впервые увидел в Cameron идею ответа в "Jon Bentley Programming Pearls".

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

remove-member(i):
    if not is-member(i): return
    j = dense[n-1];
    dense[sparse[i]] = j;
    sparse[j] = sparse[i];
    n = n - 1