如何在C++中優化我的查詢？

在我的應用程序中，我在對象列表（即對象數組）中保存了數千條記錄。我喜歡根據記錄中的特定場景（如日期，名稱等）檢索數據。如何在C++中優化我的查詢？

我的想法是，在for循環我與每一個記錄進行數據和retrive記錄併發送給用戶。

，但我覺得這不是好主意。

我需要任何建議。

問候，

KARTHIK

來源

2011-03-22 karthik

「過早的優化是所有罪惡的根源（或至少大部分）在編程。」 --Knuth。您是否遇到「我的應用程序」的速度問題？ – Johnsyweb 2011-03-22 11:11:42

當然，如果我比較每條記錄，那麼時間複雜性如何克服這一點？ – karthik 2011-03-22 11:16:44

既然你提到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++; 
    }

然後，你必須通過各自領域的指針數組排序，所有剩下的就是做對他們的二進制搜索...

我用這一切的時候，我們需要通過快速查找時間大量數據的不同字段。

來源

2011-03-22 12:05:42 DavidMFrey

如果你在一個領域比較（如姓名），你可以在維持有序的數組，並使用binary search檢索每個記錄。

看起來你是由多個字段（日期，姓名等）訂貨。您可以保留多個排序的副本（使用指針，以便您沒有多個副本），然後使用這些來檢索它們。把它隔離到適當的類後面，你總是可以改變想法到另一個選擇（比如內存數據庫）。

也許最好的解決辦法是保持多個地圖的使用不同的密鑰

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

等。這通常在引擎蓋下使用二進制搜索樹。

來源

2011-03-22 11:12:15

當然受限於當記錄數很少時（如Johnsyweb所指出的），線性搜索可能足夠好。 – 2011-03-22 11:13:09

就我而言，記錄的數量是巨大的。 – karthik 2011-03-22 11:15:06

創建多個排序的副本是不公平的。請您提供一些其他技術來解決這個問題？ – karthik 2011-03-22 11:17:58

你有沒有想過使用散列表？ ...實際上你可能有兩個不同的散列表，每個存儲一個指向堆上實際記錄的指針，根據要查詢的數據在每個表中散列指針。這會給你持續的複雜性（即，O（1））。

因此，例如，你會在堆上創建一個記錄，並得到指針指向的記錄。然後，如果您對記錄中的日期或名稱感興趣，那麼有兩個哈希表，一個用於日期，另一個用於名稱。將散列函數應用於名稱的記錄，並根據散列函數的結果將指針存儲在適當的表格插槽中。然後在存儲指向原始記錄的指針的單獨散列表中對日期執行相同操作，但根據日期字段進行散列處理。你應該快速查找一下。插入也應該非常快，以及你的散列函數也應該在不變的時間執行（假設你有一個足夠大的散列表）。

如果你沒有興趣做一個你自己，你可以得到一個在C哈希表++ 0x中使用std::unordered_map。否則，你可以做一個基本的包裝類與插入等。函數使用std::vector<std::list<RECORD_TYPE*> >作爲基本容器（在使用它之前先將其大小調整爲適當的大小...最好是大於您計劃插入的記錄數的質數）。

希望這有助於

傑森

來源

2011-03-25 04:53:56 Jason

如何在C++中優化我的查詢？

回答

相關問題