Ответы пользователя по тегу Алгоритмы
  • как лучше организовать контейнер для хранения IP адресов (1-3Mb)

    @Dervish66
    Вряд ли найдется контейнер, который обеспечивал бы эффективный доступ к данным сразу по двум индексам. Зато вместо std::map можно использовать что угодно, например, сбалансированные деревья, тем более что код будет писаться на С. Главная идея моего предложения — разнести индексы и сами данные. Тогда издержки на поиск слотов, вставки слотов и апдейтов индексов можно постараться свести к минимуму.

    Вытеснение тоже реализуется довольно просто: по индексу времени доступа находим слот с самым минимальным значением времени доступа (самый давнишний) и заменяем в нем все поля. При этом, конечно, придется обновить оба индекса.

    Обновление индекса можно сделать через удаление индексной записи и добавление новой.
    Ответ написан
    5 комментариев
  • как лучше организовать контейнер для хранения IP адресов (1-3Mb)

    @Dervish66
    К одним и тем же данным Вам нужно обращаться двумя способами. Один способ — по IP, второй — по времени доступа. При этом необходимо чтобы поиск изменения в данных (смена IP в слоте данных и смена времени доступа) выполнялись быстро и эффективно.

    Я бы решал эту задачу отделив сами данные (массив слотов) от индексов, через которые нужно обращаться. Если брать реализацию на С++ то примерно вот так:

    // Описатель слота данных
    struct CDataItem {
        __int64 accessTime; // Любое представление времени
        DWORD ip;
        BYTE  userData [64];
    };
    
    // Индекс по IP
    std::map<DWORD, CDataItem *> ipIndex;
    
    // Индекс по времени доступа
    std::map<__int64, CDataItem *> accessIndex;
    
    // Память для хранения массива слотов
    CDataItem * dataArray = new CDataItem[32000];
    

    При этом, конечно, после каждого изменения (обновления) слота придется обновлять индексы.
    Ответ написан
    1 комментарий