Создайте карту на основе времени в C

Итак, у меня есть карта из Key -> Struct

Мой ключ будет IP-адресом устройства, а значение (структура) будет содержать IP-адрес устройства и время, которое по истечении этого времени приведет к истечению срока действия пары ключ-значение и, следовательно, будет удалено с карты.

Я довольно новичок в этом, поэтому мне было интересно, что было бы хорошим способом сделать это.

Я погуглил и, кажется, нашел много на картах, основанных на времени, только на Java.

ИЗМЕНИТЬ

Наткнувшись на это, я думаю, что могу нужно создать карту с элементами в ней, а затем иметь параллельную очередь со ссылками на каждый элемент. Затем периодически вызывайте clean и, если он находился там дольше x времени, удаляйте его.

Это корректор? Может ли кто-нибудь предложить более оптимальный способ сделать это?


c keyvaluepair
person cxzp    schedule 22.07.2013    source источник
comment
Может быть достаточно очистить список при доступе (или даже при вставке и просто пропустить недопустимые записи в операциях чтения).   -  person urzeit    schedule 22.07.2013

Ответы (1)


arrow_upward
1
arrow_downward

Я использовал три подхода для решения такой проблемы.

  1. Используйте периодический таймер. Каждый раз в квант получайте все элементы с истекающим сроком действия и истекайте их сроком действия. Храните элементы в колесах таймера, см. схему 7 в этом бумага для идей. Накладные расходы здесь в том, что периодический таймер срабатывает, когда ему нечего делать, а у сегментов есть постоянные накладные расходы памяти, но это самая эффективная вещь, которую вы можете сделать, если вы добавляете и удаляете вещи из карту гораздо чаще, чем вы истекаете элементы из нее.

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

  3. Каждый раз, когда вы получаете доступ к карте, проверяйте, не истек ли срок действия элемента, к которому вы обращаетесь. Если это так, просто выбросьте его и притворитесь, что его вообще не было. Это может быть довольно неэффективно из-за всех вызовов проверки временной метки при каждом доступе и не работает, если вам нужно выполнить какое-либо действие по истечении срока действия.

person Art    schedule 22.07.2013