Menggabungkan dua std::vector metode mana yang lebih efisien dan bagaimana/mengapa?

Pertimbangkan skenario berikut:

std::vector<int> A;
std::vector<int> B;
std::vector<int> AB;

Saya ingin AB memiliki konten A dan kemudian konten B dalam urutan yang sama.

Pendekatan 1:

AB.reserve( A.size() + B.size() ); // preallocate memory
AB.insert( AB.end(), A.begin(), A.end() );
AB.insert( AB.end(), B.begin(), B.end() );

Pendekatan 2:

std::vector<int> AB ( A.begin(), A.end() ); // calling constructor
AB.insert ( AB.end(), B.begin(), B.end() );

Manakah dari metode di atas yang lebih efisien? Mengapa? Apakah ada metode lain yang lebih efisien?


c++ performance concatenation stdvector
person CinCout    schedule 09.10.2014    source sumber
comment
Sudahkah Anda mencoba mengukurnya?   -  person Chris Drew    schedule 09.10.2014
comment
Hal ini sangat bergantung pada ukuran kedua vektor dan implementasi algoritma pengalokasi vektor   -  person EdChum    schedule 09.10.2014
comment
Tidak yakin apakah Anda sudah memeriksanya, tetapi ingat bahwa kinerja adalah sesuatu yang hanya perlu Anda perhatikan setelah Anda menetapkan bahwa itu adalah masalah. Kecuali jika vektor Anda sangat besar, atau item di dalamnya mahal untuk dibuat. /copy, Anda tidak akan melihat banyak perbedaan. Jangan menghabiskan banyak waktu mengurangi operasi 0,2 md menjadi 0,1 md kecuali Anda perlu melakukannya ribuan kali per detik :-)   -  person paxdiablo    schedule 09.10.2014
comment
Jika kinerja tidak menjadi masalah, saya sarankan Anda memilih salah satu yang lebih mudah dibaca untuk Anda. Keterbacaan kode sangat penting setelah Anda kembali ke kode Anda setelah sekian lama.   -  person rozina    schedule 09.10.2014

Jawaban (3)


arrow_upward
1
arrow_downward

Saya pikir yang pertama akan selalu lebih cepat daripada yang kedua karena hanya akan melakukan satu alokasi memori dan yang kedua mungkin harus melakukan realokasi setidaknya sekali. Namun pengukuran saya tampaknya menunjukkan bahwa untuk ukuran kurang dari sekitar 100.000, ini bahkan lebih cepat:

std::vector<int> AB(A.size() + B.size());
std::copy(A.begin(), A.end(), AB.begin());
std::copy(B.begin(), B.end(), AB.begin() + B.size());

Saya kira ini karena, ini tidak hanya melakukan satu alokasi dan tidak ada realokasi, bahkan tidak perlu memeriksa apakah harus melakukan realokasi. Kelemahannya adalah mungkin harus mengosongkan semua memori pada awalnya, tapi menurut saya CPU bagus dalam hal itu.

person Chris Drew    schedule 09.10.2014
comment
kelemahannya adalah ia harus menghilangkan semua memori -- Saya melihat rakitan yang dihasilkan dan saya tidak dapat menjelaskan perbedaan yang begitu besar, tetapi yang jelas adalah pengoptimal menghapus nol dari Penyimpanan. Kode dasar yang dihasilkan untuk yang pertama dan rasa Anda sama, tetapi kode tersebut disusun dengan cara yang sedikit berbeda, sepertinya pengoptimal lebih siap untuk menangani opsi terakhir ini... - person David Rodríguez - dribeas; 11.10.2014
comment
@ DavidRodríguez-dribeas Menarik. Ini bukan pertama kalinya saya terkejut betapa baiknya pendekatan zero-out memori dan penimpaan dibandingkan dengan pendekatan cadangan memori dan penyisipan. Misalnya std::vector<int> A(size); for(size_t i=0;i!=size;++i) A[i]=func(i); berperforma sangat baik. Dan mungkin Anda benar, alasannya adalah pengoptimal menghilangkan zeroing dari memori. - person Chris Drew; 11.10.2014

arrow_upward
8
arrow_downward

Yang pertama mungkin sedikit lebih efisien karena Anda dapat menjamin bahwa hanya satu alokasi memori yang akan dilakukan. Yang kedua, kemungkinannya (sebagian besar implementasi melakukannya) adalah alokasi untuk A.size() akan dilakukan selama konstruksi vektor dan kemudian insert akan memicu alokasi kedua karena perlu bertambah sebanyak B.size() elemen.

person David Rodríguez - dribeas    schedule 09.10.2014

arrow_upward
3
arrow_downward

Pendekatan 1 melakukan tidak realokasi, sedangkan Pendekatan 2 dapat melakukan realokasi beberapa kali, dan dalam praktiknya kemungkinan besar akan melakukan realokasi satu kali. Jadi Pendekatan 1 lebih baik.

person Kerrek SB    schedule 09.10.2014
comment
Rentang iterator yang dimasukkan menggunakan RandomAccessIterators, sehingga jumlah elemen yang dimasukkan dapat dihitung dalam O(1) sehingga tidak ada alasan untuk melakukan realokasi lebih dari sekali dalam pendekatan 2. - person Jonathan Wakely; 09.10.2014
comment
@JonathanWakely: Apakah itu benar-benar dijamin, atau hanya implementasi umum? (Saya tahu ada jaminan sebenarnya untuk konstruktor jangkauan.) - person Kerrek SB; 09.10.2014
comment
@KerrekSB: Ini adalah salah satu hal yang akan dianggap bug meskipun standar tidak menjaminnya. - person David Rodríguez - dribeas; 09.10.2014
comment
Itu tidak dijamin, tapi itu sebabnya saya bilang tidak ada alasan daripada bug jika dialokasikan kembali :-) Anda harus mengeluh kepada vendor Anda jika implementasinya tidak menghitung elemen saat memasukkan RandomAccessIterators. Konstruktor vektor yang menggunakan rentang iterator diperlukan untuk menghitung elemen apa pun kecuali InputIterators, tetapi rentang insert tidak. - person Jonathan Wakely; 09.10.2014
comment
@JonathanWakely: Saya selalu mengeluh kepada vendor saya :-) - person Kerrek SB; 09.10.2014