unordered_map เพื่อค้นหาดัชนีของอาร์เรย์

ฉันต้องการค้นหาดัชนีของชุดอย่างมีประสิทธิภาพ ฉันใช้ unordered_map และสร้างแผนที่ผกผันเช่นนี้

std::unordered_map <int, int> myHash (size); 
Int i = 0;
for (it = someSet.begin(); it != someSet.end(); it++)
{
    myHash.insert({*it , i++});
 }

มันใช้งานได้แต่มันไม่มีประสิทธิภาพ ฉันทำสิ่งนี้ทุกครั้งที่ต้องการดัชนีที่ฉันสามารถเข้าถึงได้ O(1) การวิเคราะห์ประสิทธิภาพแสดงให้ฉันเห็นว่าส่วนนี้กลายเป็นฮอตสปอตของโค้ดของฉัน

VTune บอกฉันว่าตัวดำเนินการ new คือฮอตสปอตของฉัน ฉันเดาว่ามีบางอย่างเกิดขึ้นภายใน unordered_map สำหรับฉันดูเหมือนว่าคดีนี้ควรได้รับการจัดการอย่างมีประสิทธิภาพ ฉันยังหาวิธีที่ดีไม่ได้เลย มีวิธีแก้ไขที่ดีกว่านี้หรือไม่? ตัวสร้างที่ถูกต้อง? บางทีฉันควรส่งข้อมูลเพิ่มเติมไปให้ตัวสร้าง ฉันค้นหารายการเริ่มต้นแล้ว แต่มันไม่ใช่สิ่งที่ฉันต้องการเลย

อัปเดต: ให้ฉันเพิ่มข้อมูลเพิ่มเติม ฉากนี้ไม่สำคัญเท่าไหร่ ฉันบันทึกชุดลงในอาร์เรย์ (เรียงลำดับ) ต่อมาฉันต้องค้นหาดัชนีของค่าที่ไม่ซ้ำใคร ฉันสามารถทำได้ในการเข้าสู่ระบบแต่มันไม่เร็วพอ นี่คือเหตุผลที่ฉันตัดสินใจใช้แฮช ขนาดของเซต (คอลัมน์ของเมทริกซ์ย่อย) จะไม่เปลี่ยนแปลงหลังจากจุดนี้

มันเกิดขึ้นจากการคำนวณเมทริกซ์แบบกระจาย ซึ่งฉันต้องค้นหาดัชนีของเมทริกซ์ย่อยในเมทริกซ์ที่ใหญ่กว่า ดังนั้นขนาดและรูปแบบของการค้นหาจึงขึ้นอยู่กับเมทริกซ์อินพุต มันใช้งานได้สมเหตุสมผลกับปัญหาเล็กๆ น้อยๆ ฉันสามารถใช้ตารางการค้นหาได้ แต่ในขณะที่ฉันกำลังวางแผนที่จะทำแบบคู่ขนาน ตารางการค้นหาสำหรับแต่ละเธรดอาจมีราคาแพง ฉันมีขนาดแฮชที่แน่นอนในเวลาที่สร้าง ฉันคิดว่าการส่งมันไปที่ตัวสร้างจะหยุดการจัดสรรใหม่ ฉันไม่เข้าใจจริงๆ ว่าทำไมมันถึงจัดสรรมากขนาดนี้


c++ set performance unordered-map
person Aznaveh    schedule 30.10.2020    source แหล่งที่มา
comment
Int? คุณหมายถึง int?   -  person tadman    schedule 31.10.2020
comment
คุณกำลังแปลงองค์ประกอบกี่รายการ? คุณกำลังค้นหากี่รายการ? ค่าใช้จ่ายในการสร้างตารางตรวจสอบอาจเกินเงินออมที่คุณได้รับ ดังนั้นจึงอาจเป็นการปรับให้เหมาะสมที่ผิดพลาด มีค่าเกณฑ์บางค่าที่จำนวนองค์ประกอบ › N และจำนวนการค้นหา › M ให้ผลลัพธ์ที่เป็นบวก แต่ค่าที่ต่ำกว่านั้นเป็นค่าลบสุทธิ   -  person tadman    schedule 31.10.2020
comment
@tadman ฉันเพิ่งคัดลอกโค้ดของฉันและทำให้ง่ายขึ้นที่นี่ ลืมเปลี่ยนส่วนนี้ ไม่สำคัญอยู่แล้ว int เป็น int แบบยาว   -  person Aznaveh    schedule 31.10.2020
comment
@tadman มันเป็นส่วนหนึ่งของโครงการขนาดใหญ่ มันทำงานได้ดีสำหรับอินพุตขนาดเล็ก แต่จะใช้งานไม่ได้เมื่อขนาดเพิ่มขึ้น   -  person Aznaveh    schedule 31.10.2020
comment
คุณจะต้องสำรวจว่าผลตอบแทนของกลยุทธ์นี้คืออะไรตามที่ฉันได้อธิบายไว้ก่อนหน้านี้ ฉันจะเขียนคลาส wrapper เกี่ยวกับสิ่งนี้ซึ่งจะทำการเพิ่มประสิทธิภาพ ถ้า มันคิดว่ามันจะมีประสิทธิผล และเพียงแต่ทำด้วยวิธีเริ่มต้นเท่านั้น นั่นทำให้ปรับแต่งได้ง่ายขึ้น   -  person tadman    schedule 31.10.2020
comment
ทำไมคุณถึงต้องการดัชนีขององค์ประกอบ set? แม้ว่าคุณจะมีมันก็ตาม การเข้าถึงองค์ประกอบ (โดยใช้ std::distance() คือ O(n)   -  person Eugene    schedule 31.10.2020
comment
@Eugene มันเป็นส่วนหนึ่งของโครงการที่ใหญ่กว่า ในที่สุดฉันก็เก็บชุดไว้ในอาร์เรย์   -  person Aznaveh    schedule 31.10.2020
comment
ดูเหมือนจะไม่สมเหตุสมผลกับโปรเจ็กต์ขนาดใดๆ หากคุณถามเกี่ยวกับประสิทธิภาพ คุณจะต้องอธิบายด้วยว่าทำไมคุณถึงต้องการดัชนี โปรดทราบว่าการค้นหาองค์ประกอบในชุดดั้งเดิมนั้นเร็วกว่า: มันคือ O(log(n)) ในขณะที่การใช้ดัชนีของคุณคือ O(n)   -  person Eugene    schedule 31.10.2020
comment
@Eugene hash ทำให้ O (ยาว) เป็น O (1) ฉันไม่เข้าใจว่า O(n) มาจากไหน   -  person Aznaveh    schedule 31.10.2020
comment
ใช่ การเข้าถึงแผนที่แบบไม่เรียงลำดับเพื่อรับดัชนีคือ O(1) ฉันนึกภาพไม่ออกว่าการมีดัชนีจะเป็นประโยชน์กับสิ่งใด จากประสบการณ์ C++ กว่า 20 ปี ฉันไม่เคยรู้สึกว่าจำเป็นต้องใช้ดัชนีขององค์ประกอบชุด (การจัดเก็บตัววนซ้ำแทนอาจมีประโยชน์) ฉันจึงขอยกตัวอย่างว่าคุณจะใช้ดัชนีนี้อย่างไร และได้เปรียบด้านความเร็วเท่าใด   -  person Eugene    schedule 31.10.2020
comment
O(n) มาจากการใช้ std::distance() คุณจะใช้ดัชนีที่ไหนอีก   -  person Eugene    schedule 31.10.2020
comment
เว้นแต่ว่าคุณมีแฮชที่สมบูรณ์แบบ คุณไม่รับประกันว่าจะได้รับ O(1) และในกรณีที่เลวร้ายที่สุด คุณจะได้รับ O(N)   -  person Surt    schedule 31.10.2020
comment
ไม่ชัดเจนสำหรับฉันว่าค่าใดคือดัชนีของแต่ละค่าในชุดตามลำดับการวนซ้ำ ไม่มีวิธีการชุดที่จะส่งกลับค่าที่มีดัชนีที่กำหนด ดูเหมือนเป็นวิธีแก้ปัญหาในการค้นหาปัญหา   -  person Sam Varshavchik    schedule 31.10.2020
comment
@Eugene การค้นหาดัชนีนั้นสมเหตุสมผลดีเนื่องจากตัววนซ้ำจะใช้งานไม่ได้เมื่อปรับขนาด   -  person ALX23z    schedule 31.10.2020
comment
@ ALX23z std::set ทำให้การปรับขนาดใช้ไม่ได้ แต่ไม่มีการปรับขนาด ...   -  person Surt    schedule 31.10.2020
comment
ปัญหาน่าจะเกิดจากขนาดของอาร์เรย์ การค้นหาที่มีขนาดใหญ่เกินไปย่อมทำให้เกิดปัญหาเนื่องจากการจัดสรรแบบกระจัดกระจายที่มีขนาดใหญ่เกินไป พิจารณาการใช้อัลกอริทึมสำหรับโครงการของคุณ ลองค้นหาดัชนีด้วยวิธีอื่นหรือใช้ pmr สำหรับการจัดสรรใน unordered_map หากคุณเพียงแค่เพิ่มองค์ประกอบ บางทีคุณอาจจองจำนวนมากและใส่องค์ประกอบต่างๆ ลงไป   -  person ALX23z    schedule 31.10.2020
comment
@Surt ในขณะที่เขาเขียน SomeSet เขาบอกว่าเขาเก็บดัชนีของ อาร์เรย์   -  person ALX23z    schedule 31.10.2020

คำตอบ (2)


arrow_upward
1
arrow_downward

ปัญหาคือ std::unordered_map ซึ่งส่วนใหญ่ใช้งานเป็นรายการเวกเตอร์ นั้นไม่เป็นมิตรกับแคชอย่างยิ่ง และจะทำงานได้ไม่ดีเป็นพิเศษเมื่อใช้คีย์/ค่าขนาดเล็ก (เช่น int,int ในกรณีของคุณ) ไม่ต้องพูดถึงการจัดสรร (ใหม่) มากมาย

อีกทางเลือกหนึ่ง คุณสามารถลองใช้แผนที่แฮชของบุคคลที่สามที่ใช้ ที่อยู่แบบเปิด ด้วย การซักถามเชิงเส้น (แค่คำหนึ่ง แต่โครงสร้างพื้นฐานเป็นเพียงเวกเตอร์ กล่าวคือ เป็นมิตรกับแคชมากกว่ามาก) ตัวอย่างเช่น dense_hash_map ของ Google หรือสิ่งนี้: flat_hash_map ทั้งสองสามารถใช้เป็นการแทนที่แบบดรอปอินสำหรับ unordered_map และจำเป็นต้องกำหนดค่า int เพิ่มเติมเพียงค่าเดียวเป็นคีย์ว่าง

person rustyx    schedule 31.10.2020
comment
std::unordered_map ไม่มีปัญหาใดๆ กับการจัดสรรใหม่ บางทีตารางการค้นหาอาจต้องการองค์ประกอบดังกล่าว แต่ไม่ใช่องค์ประกอบพื้นฐาน มันทำการจัดสรรจำนวนมาก ดังนั้นจึงขอแนะนำสำหรับแฮชขนาดใหญ่ - person ALX23z; 31.10.2020
comment
ฉันลงเอยด้วยการใช้แฮชของตัวเองโดยใช้การตรวจวัดเชิงเส้น มันมีประสิทธิภาพมากขึ้น - person Aznaveh; 08.11.2020

arrow_upward
1
arrow_downward

std::unordered_map‹int, int› มักจะถูกนำมาใช้ราวกับว่ามันเป็น

std::vector<std::list<std::par<int, int>>>

ซึ่งทำให้เกิดการจัดสรรและการจัดสรรคืนจำนวนมากของแต่ละโหนด แต่ละโหนด (de-)allocation ใช้การล็อคซึ่งทำให้เกิดความขัดแย้ง

คุณสามารถช่วยได้เล็กน้อยโดยใช้ emplace แทนการแทรก หรือคุณสามารถกระโดดออกไปสู่โลกใหม่อันน่าอัศจรรย์ของตัวจัดสรร pmr หากการสร้างและการทำลาย pmr::unordered_map ของคุณเป็นแบบเธรดเดียว คุณควรจะได้รับประสิทธิภาพพิเศษมากมายจากมัน ดู Jason Turners C++ Weekly - ตอนที่ 222 - คอนเทนเนอร์มาตรฐานเร็วขึ้น 3.5 เท่าพร้อม PMR! ตัวอย่างของเขาแม้จะเล็กน้อยแต่คุณสามารถเข้าใจแนวคิดทั่วไปได้

person Surt    schedule 30.10.2020
comment
คำอธิบายของปัญหานั้นถูกต้อง แต่ฉันไม่แน่ใจเหมือนกันว่า PMR จะเป็นคำแนะนำที่ดีที่สุด ตารางแฮชของ Google มีการใช้กันอย่างแพร่หลาย และมีตัวเลือกอื่นที่เร็วกว่า - probabildance.com/2017/02/26/i-wrote-the-fastest-hashtable เป็นการอ่านที่ดี - person Tony Delroy; 31.10.2020