Saya ingin mencari indeks suatu himpunan secara efisien. Saya menggunakan unordered_map dan membuat peta terbalik seperti ini
std::unordered_map <int, int> myHash (size);
Int i = 0;
for (it = someSet.begin(); it != someSet.end(); it++)
{
myHash.insert({*it , i++});
}
Ini berfungsi tetapi tidak efisien. Saya melakukan ini sehingga kapan pun saya membutuhkan indeks, saya dapat mengaksesnya O(1). Analisis kinerja menunjukkan kepada saya bahwa bagian ini menjadi hotspot kode saya.
VTune memberi tahu saya bahwa operator new
adalah hotspot saya. Saya kira ada sesuatu yang terjadi di dalam unordered_map. Menurut saya kasus ini harus ditangani secara efisien. Saya belum dapat menemukan cara yang baik. Apakah ada solusi yang lebih baik? konstruktor yang benar? Mungkin saya harus menyampaikan lebih banyak info ke konstruktor. Saya mencari daftar inisialisasi tetapi bukan itu yang saya inginkan.
Pembaruan: Izinkan saya menambahkan beberapa informasi lebih lanjut. Himpunannya tidak terlalu penting; Saya menyimpan set ke dalam array (diurutkan). Nanti saya perlu mencari indeks nilai yang unik. Saya bisa melakukannya di logn tetapi tidak cukup cepat. Itu sebabnya saya memutuskan untuk menggunakan hash. Ukuran himpunan (kolom submatriks) tidak berubah setelah titik ini.
Ini muncul dari perhitungan matriks renggang yang saya perlukan untuk mencari indeks submatriks dalam matriks yang lebih besar. Oleh karena itu ukuran dan pola pencarian bergantung pada matriks masukan. Ini berfungsi dengan baik pada masalah yang lebih kecil. Saya bisa menggunakan tabel pencarian tetapi ketika saya berencana melakukannya secara paralel, tabel pencarian untuk setiap thread bisa mahal. Saya memiliki ukuran hash yang tepat pada saat pembuatan. Saya pikir dengan mengirimkannya ke konstruktor itu berhenti mengalokasikan ulang. Saya benar-benar tidak mengerti mengapa realokasi sebanyak ini.
Int
? Maksudmuint
? - person tadman   schedule 31.10.2020std::distance()
adalah O(n). - person Eugene   schedule 31.10.2020std::distance()
. Di mana lagi Anda akan menggunakan indeks? - person Eugene   schedule 31.10.2020pmr
untuk alokasi diunordered_map
. Jika Anda hanya menambahkan elemen, mungkin Anda bisa membuat reservasi dalam jumlah besar dan meletakkan elemen satu demi satu - person ALX23z   schedule 31.10.2020SomeSet
dia mengatakan bahwa dia menyimpan indeks dari sebuah array. - person ALX23z   schedule 31.10.2020