การเชื่อม std::vector สองอันเข้าด้วยกัน วิธีใดมีประสิทธิภาพมากกว่า และอย่างไร/เพราะเหตุใด

พิจารณาสถานการณ์ต่อไปนี้:

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

ฉันต้องการให้ AB มีเนื้อหาของ A และเนื้อหาของ B อยู่ในลำดับเดียวกัน

แนวทางที่ 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() );

แนวทางที่ 2:

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

วิธีใดวิธีหนึ่งข้างต้นมีประสิทธิภาพมากกว่า ทำไม มีวิธีอื่นที่มีประสิทธิภาพมากกว่าหรือไม่?


c++ performance concatenation stdvector
person CinCout    schedule 09.10.2014    source แหล่งที่มา
comment
ลองวัดดูหรือยัง?   -  person Chris Drew    schedule 09.10.2014
comment
มันขึ้นอยู่กับขนาดของเวกเตอร์ทั้งสองอย่างหนาแน่นและการใช้งานอัลกอริธึมตัวจัดสรรเวกเตอร์   -  person EdChum    schedule 09.10.2014
comment
ไม่แน่ใจว่าคุณได้ตรวจสอบแล้วหรือไม่ แต่จำไว้ว่าประสิทธิภาพเป็นสิ่งที่คุณควรคำนึงถึงเมื่อคุณสร้างมันขึ้นมาแล้วเท่านั้น ปัญหา เว้นแต่ว่าเวกเตอร์ของคุณมีขนาดใหญ่มาก หรือรายการภายในนั้นมีค่าใช้จ่ายสูงในการสร้าง /copy คุณจะไม่สังเกตเห็นความแตกต่างมากนัก อย่าใช้เวลามากในการลดการดำเนินการ 0.2ms เหลือ 0.1ms เว้นแต่คุณจะต้องทำหลายพันครั้งต่อวินาที :-)   -  person paxdiablo    schedule 09.10.2014
comment
หากประสิทธิภาพไม่ใช่ปัญหา ฉันขอแนะนำให้คุณเลือกอันที่อ่านง่ายกว่าสำหรับคุณ ความสามารถในการอ่านโค้ดนั้นสำคัญมากเมื่อคุณกลับมาที่โค้ดของคุณอีกครั้งหลังจากผ่านไประยะหนึ่ง   -  person rozina    schedule 09.10.2014

คำตอบ (3)


arrow_upward
1
arrow_downward

ฉันคิดว่าอันแรกจะเร็วกว่าอันที่สองเสมอเพราะมันจะทำการจัดสรรหน่วยความจำเพียงครั้งเดียวและอันที่สองอาจจะต้องจัดสรรใหม่อย่างน้อยหนึ่งครั้ง แต่ การวัดของฉัน ดูเหมือนจะบ่งบอกว่าสำหรับขนาดที่น้อยกว่าประมาณ 100,000 การดำเนินการนี้จะยิ่งเร็วกว่า:

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

ฉันเดาว่าเป็นเพราะ ไม่เพียงแต่ดำเนินการจัดสรรเพียงครั้งเดียวและไม่มีการจัดสรรใหม่ แต่ยังไม่จำเป็นต้องตรวจสอบด้วยซ้ำว่าควรทำการจัดสรรใหม่หรือไม่ ข้อเสียคืออาจต้องทำให้หน่วยความจำทั้งหมดเป็นศูนย์ในตอนแรก แต่ฉันคิดว่า CPU ทำได้ดี

person Chris Drew    schedule 09.10.2014
comment
ข้อเสียคือต้องทำให้หน่วยความจำทั้งหมดเป็นศูนย์ -- ฉันดูแอสเซมบลีที่สร้างขึ้นและฉันไม่สามารถอธิบายความแตกต่างอย่างมากได้ แต่สิ่งที่ชัดเจนก็คือเครื่องมือเพิ่มประสิทธิภาพจะลบการทำให้เป็นศูนย์ออกจาก หน่วยความจำ. โค้ดพื้นฐานที่สร้างขึ้นสำหรับโค้ดแรกและรสชาติของคุณเหมือนกัน แต่โค้ดมีโครงสร้างที่แตกต่างกันเล็กน้อย ดูเหมือนว่าเครื่องมือเพิ่มประสิทธิภาพได้รับการเตรียมการไว้ดีกว่าเพื่อจัดการกับตัวเลือกสุดท้ายนี้... - person David Rodríguez - dribeas; 11.10.2014
comment
@DavidRodríguez-dribeas น่าสนใจ นี่ไม่ใช่ครั้งแรกที่ฉันรู้สึกประหลาดใจว่าวิธีการใช้หน่วยความจำและการเขียนทับเป็นศูนย์นั้นดีเพียงใดเมื่อเปรียบเทียบกับวิธีสำรองหน่วยความจำและการแทรก เช่น std::vector<int> A(size); for(size_t i=0;i!=size;++i) A[i]=func(i); ทำงานได้ดีอย่างน่าประหลาดใจ และบางทีคุณอาจพูดถูก เหตุผลก็คือเครื่องมือเพิ่มประสิทธิภาพจะลบค่าศูนย์ออกจากหน่วยความจำ - person Chris Drew; 11.10.2014

arrow_upward
8
arrow_downward

อันแรกน่าจะมีประสิทธิภาพมากกว่าเล็กน้อยเนื่องจากคุณสามารถรับประกันได้ว่าจะมีการจัดสรรหน่วยความจำเพียงครั้งเดียวเท่านั้น ในรูปแบบที่สอง มีโอกาส (การใช้งานส่วนใหญ่) ที่การจัดสรรสำหรับ A.size() จะดำเนินการในระหว่างการสร้างเวกเตอร์ จากนั้น insert จะทริกเกอร์การจัดสรรครั้งที่สอง เนื่องจากจำเป็นต้องเพิ่มองค์ประกอบ B.size()

person David Rodríguez - dribeas    schedule 09.10.2014

arrow_upward
3
arrow_downward

วิธีที่ 1 ดำเนินการ ไม่ การจัดสรรใหม่ ในขณะที่วิธีที่ 2 อาจจัดสรรใหม่หลายครั้ง และในทางปฏิบัติมีแนวโน้มว่าจะจัดสรรใหม่เพียงครั้งเดียว ดังนั้นวิธีที่ 1 ดีกว่า

person Kerrek SB    schedule 09.10.2014
comment
ช่วงตัววนซ้ำที่ถูกแทรกใช้ RandomAccessIterators ดังนั้นจำนวนองค์ประกอบที่ถูกแทรกจึงสามารถนับได้ใน O(1) ดังนั้นจึงไม่มีข้อแก้ตัวสำหรับการจัดสรรใหม่มากกว่าหนึ่งครั้งในแนวทางที่ 2 - person Jonathan Wakely; 09.10.2014
comment
@JonathanWakely: รับประกันจริงหรือเป็นเพียงการใช้งานทั่วไป? (ฉันรู้ว่ามีการรับประกันจริงสำหรับตัวสร้างช่วง) - person Kerrek SB; 09.10.2014
comment
@KerrekSB: มันเป็นหนึ่งในสิ่งที่จะถือเป็นจุดบกพร่องแม้ว่ามาตรฐานจะไม่รับประกันก็ตาม - person David Rodríguez - dribeas; 09.10.2014
comment
มันไม่รับประกัน แต่นั่นเป็นเหตุผลว่าทำไมฉันถึงบอกว่าไม่มีข้อแก้ตัว แทนที่จะเป็นข้อผิดพลาดถ้ามันจัดสรรใหม่ :-) คุณควรร้องเรียนกับผู้จำหน่ายของคุณอย่างแน่นอนหากการใช้งานของพวกเขาไม่นับองค์ประกอบเมื่อทำการแทรก RandomAccessIterators ตัวสร้างเวกเตอร์ที่ใช้ช่วงตัววนซ้ำ จำเป็น เพื่อนับองค์ประกอบสำหรับสิ่งใดๆ ยกเว้น InputIterators แต่ช่วง insert ไม่ใช่ - person Jonathan Wakely; 09.10.2014
comment
@JonathanWakely: ฉันบ่นกับผู้ขายของฉันตลอดเวลา :-) - person Kerrek SB; 09.10.2014