Какая структура данных лучше подойдет для случайного удаления из коллекции?

Question

[SergeySerge11]

В общем частенько заметил, трачу время на кривые велосипеды.
Есть ли оригинальное решение для такой задачи.
Нужна структура данных, в которую:
- Идут запросы на вставку с случайным ключом.
- Идут запросы на удаления, при том без ключа. Просто какой-то узел удалить.

Какое-то дерево скорей всего должно быть с узлами, а как удалить случ. узел

Comments

[Everything_is_not_so_bad]

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

Возьми Memcached/Redis и не морочь себе голову.

Answer 1

[Wataru]

Обычно во всяких кешах удаляют не случайный элемент, а какой-то особенный. Например, самый старый. Или как можно реже использующийся.

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

При вставке - просто добавляйте в вектор ключ и вставляйте в дерево значение {значение, последний индекс в векторе}. При удалении по ключу - в известном месте вектора пропишите последний элемент и укоротите вектор на 1. Не забудьте обновить ссылку на вектор у того ключа, который с последнего места переехал.

Или можно вместе с вектором поддерживать список пустых мест в векторе. Тогда при удалении не надо перемещать ключ и обновлять ссылку, а при добавлении не расширяйте вектор, если есть пустые места.

При удалении случайного - берите случайный ключ из вектора и его удаляйте.

Answer 2

[dollar]

Удаление без ключа - это как вообще? Как структура узнает, что именно удалять? Что-то же должно быть ключом, аргументом функции удаления! То есть "какой-то узел" должен содержать какие-то свойства, по которым происходит идентификация, хотя бы иметь адрес в памяти, и вот тогда этот адрес уже можно считать ключом.

Честно говоря, не понятно, зачем вообще ключ (из вопроса), если он не используется. Складывается ощущение, что нужно не подстраиваться под эти условия, а менять их.

В общем случае решением будет хеш-таблица, в которой в качестве ключа может быть, что угодно (т.е. любой тип данных, кроме разве что всяких null и т.п.). Возможно, потребуется пара таких структур: по "ключу" (из вопроса), по адерсу и т.д., - потому что у вас по сути получается несколько ключей.

Comments

[Алексей Уколов]

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

[SergeySerge11]

@dollar
Не структура , а функция к ней, там много решений я использовал. Но просто вопрос задал, может есть какое базовое по учебнику решение.
Так же есть запросы поиск по ключу.
Так же могу быть запросы на удаление по ключу.
Наглядный пример. Есть колода Карт Уникальных, карты случайно достаются, случайно добавляются. Так же есть орбитр, допустим, который знает в каждый момент где карта.
Доступ O(1) - 100% условие
Задача протестить множество, постоянно удаляя, добавляя.
И удаления в произвольных местах.
Тут несколько решений, к примеру создать генератор запросов, то есть подготовленный список с ключами которые надо удалить.

Я просто думаю, что есть какая-то структура в Дерьевьях и списках, с быстрым удалением, с каким-то хитрым компаратором, который будет линейное множество 1,2,3,4,5 транслировать в другое множество.
Или там к примеру, присматриваюсь к структуре Куча, которая поддерживает индексацию, но пока только ознакамливаюсь. с теорией.

[dollar]

SergeySerge11, ну, этой задаче соответствует и обычный массив, получается:

• Доступ по ключу, то есть по индексу, - O(1)
  
• Случайное удаление - случайный индекс, - снова O(1), потому что можно без сдвига, на место удалённого переставляем последний элемент массива. Ведь про сортировку речи не было.
  
• Добавление, очевидно, тупо в конец - снова O(1). А если нужно запутывание для какой-то игры - добавляем в случайное место, вместо какого-то элемента, который перемещается в конец. Для "игрока" это равносильно случайному добавлению, т.к. он не будет знать, где какая карта, сколько бы чего ни добавлял.
  

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

Однако если, как сказали в другом ответе, вам нужно что-то типа удаления "самого старого элемента", то есть это какой-то выбор и сравнение, то это уже намёк на сортировку и порядок, и нужен совсем другой подход. Просто в вопросе об этом не было ни слова. "Просто какой-то узел удалить" - подразумевает, что у вас уже есть функция, определяющая самый нужный для удаления узел, и её менять/придумывать не требуется.

В общем, если задачу нужно сделать честно, и нет возможности срезать углы, перемешивать карты в любой момент, когда нам вздумается, и нужно вставлять чётко "со сдвигом" и иметь определённый порядок, пусть даже известный только арбитру, то придётся чем-то жертвовать - процессором или памятью, например, или ускорением где-то по цене замедления где-то ещё. Но всё же у вас, скорее всего, специфичная задача, где нужен конкретный результат, а значит, скорее всего, возможна оптимизация, типа игнорирования порядка, удобные преставления, ещё какие-то допущения и упрощения. Это всё зависит от конкретных условий задачи, наличия/отсутствия в ней конкретных ограничений.

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

[SergeySerge11]

dollar, супер. Так легко.
Самое забавное, что я вообще для других целей, такой массив реализовывал. И знаю. Но блин, не дошло, что он он подходит и для этой задачи. Эх как бы научиться прям машинально, понимать, что, где применить

[Василий Банников]

SergeySerge11, практикой)