Как оптимизировать мой запрос в C ++?

Question

В Моем приложении я сохранил тысячи записей в списке объектов (т.е. массив объектов). Мне нравится извлекать данные на основе определенного сценария, такого как дата, имя и т. Д. В записи.

Моя идея состоит в том, что в цикле for я сравниваю данные с каждой записью, извлекаю запись и отправляю пользователю.

но я чувствовал, что это не очень хорошая идея.

Мне нужны любые предложения.

С уважением,

Karthik

Answer 1

Если вы сравниваете одно поле (например, имя), вы можете поддерживать массив в отсортированном порядке и использовать двоичный поиск для извлечения каждой записи.

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

Возможно, лучшее решение - сохранить несколько карт с разными ключами

class MyDatabase {
  private:
    std::map<date,Record*> indexedByRecord;
    std::map<name,Record*> indexedByName;
  public:
    Record* getByName(const name& name) const;
    Record* getByDate(const date& date) const;
}

и так далее.Обычно это использует двоичное дерево поиска под капотом.

Answer 2

Поскольку вы также упомянули c, вы можете реализовать отсортированные массивы указателей, если ваш список статичен.

    int num_records = number_of_records_in_array;
    Record **Records_by_name = malloc(sizeof(Record *)*num_records);
    Record **Records_by_date = malloc(sizeof(Record *)*num_records);

Затем назначьте каждый указатель на запись.

    Record **by_name = Records_by_name;
    Record **by_date = Records_by_date;

//not sure how your records are stored in memory but you need to copy a
//pointer to both by_name and by_date
    for(int i=0; i<num_records; i++) { 
      *by_name = Records_array+i;
      *by_date = *by_name;
      by_name++;
      by_date++;
    }

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

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

Answer 3

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

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

Если вы не заинтересованы в том, чтобы создать его самостоятельно, вы можете получить хеш-таблицу в c ++ 0x, используя std::unordered_map. В противном случае вы можете сделать базовую упаковку класса с функциями вставки и т. Д., Используя std::vector<std::list<RECORD_TYPE*> > в качестве базового контейнера (сначала измените его размер до соответствующего размера, прежде чем использовать его ... желательно, чтобы простое число было больше, чем количество записей, которые вы '' повторно планирую вставить).

Надеюсь, это поможет,

Jason