CODEWITHSUNDEEP
c++cmfcvisual-c++
karthik
karthik

Reputation: 17842

How to optimize my query in c++?

In My Application , I saved thousands of records in list of objects(i.e.,object array).I like to retrieve the data on the basis of particular scenario like date , name ., etc in record.

My idea is that in the for loop i am comparing the data with each record and retrive the record and send to the user.

but I felt that this is not good idea.

I am in need of any suggestions.

Regards,

Karthik

Upvotes: 0

Views: 185

Answers (3)

Jason
Jason

Reputation: 32510

Have you thought about using a hash-table? ... You could actually have a couple different hash-tables, each one storing a pointer to the actual record in question on the heap, and the pointers hashed in each table according to the data you want to query. That would give you constant complexity (i.e., O(1)) for each look-up.

So for instance, you would create one record on the heap and get the pointer to that record. Then if you were interested in the date or name in the record have two hash-tables, one for date, and one for names. Apply a hash function to the record for the name, and store the pointer to that record in the appropriate table slot based on the result from the hash function. Then do the same for the date in a separate hash-table storing pointers to the original record, but hashed according to the date field. You should then get some very quick look-ups. Insertions should also be very fast as well as your hash-functions should perform in constant time as well (assuming you have a large-enough hash-table).

If you're not interested in making one yourself, you can get a hash-table in c++0x using std::unordered_map. Otherwise you can make a basic wrapping a class with insertion, etc. functions using std::vector<std::list<RECORD_TYPE*> > as the basic container (resize it to the appropriate size first before using it ... preferably to a prime number larger than the number of records you're planning on inserting).

Hope this helps,

Jason

Upvotes: 0

DavidMFrey
DavidMFrey

Reputation: 1668

Since you mentioned c also, you can implement sorted arrays of pointers if your list is static. 

    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);

Then assign each pointer to a record.

    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++;
    }

Then you have to sort the pointer arrays by their respective fields and all that's left is to do a binary search on them...

I use this all the time when we need fast lookups by different fields for large amounts of data.

Upvotes: 1

Jeff Foster
Jeff Foster

Reputation: 44706

If you were comparing on a single field (such as name) you could maintain the array in sorted order and use a binary search to retrieve each record.

It looks like you are ordering by multiple fields (date, name etc). You could keep multiple sorted copies (using pointers so that you don't have multiple copies) and then use these to retrieve them. Insulate this behind an appropriate class and you can always change your mind to another alternative (like an in-memory database).

Perhaps the best solution is to keep multiple map's with different keys

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;
}

And so on. This typically uses a binary searched tree under the hood.

Upvotes: 4

Related Questions