เพิ่มประสิทธิภาพความท้าทาย "ค้นหาความแตกต่างที่ยิ่งใหญ่ที่สุด"

ฉันได้รับโจทย์โค้ดให้แก้ใน JavaScript และมันกลายเป็นโจทย์ข้อหนึ่งที่คุณไม่จำเป็นต้องแก้ แต่คุณต้องแก้ให้ดีด้วย

เคารพ.

ความท้าทายคือคุณได้รับค่าเป็นอาร์เรย์ของตัวเลข และจำเป็นต้องค้นหาความแตกต่างเชิงบวกที่ยิ่งใหญ่ที่สุดระหว่างสองรายการที่มีดัชนี i และ j ในอาร์เรย์ เงื่อนไขคือ j ‹ i และ nums[i] › nums[j] ตัวอย่างเช่น ถ้า nums = [4, 5, 3, 5, 7, 8, 1] โดยที่ i = 4 และ j = 2 คุณจะมี 7 - 3 = 4 อย่างไรก็ตาม ค่าสูงสุดจะอยู่ที่ i = 5 และ j = 2, nums[i] = 8 และ nums[j] = 3 โดยให้ผลต่าง 5

ปัญหาง่ายๆ ในการแก้ปัญหาการใช้กำลังดุร้าย โดยมีเนื้อหาดังนี้:

นี่จะให้ผลการแก้ปัญหาเวลา O(n²) เนื่องจากเป็นการวนซ้ำซ้อนสองเท่า ทำงานได้ดีสำหรับอาร์เรย์อินพุตขนาดเล็ก แต่ความท้าทายคือป้อนอาร์เรย์สองสามขนาด › 100,000 นิ้วโดยเฉพาะ ดังนั้น ประสิทธิภาพจึงเป็นสิ่งสำคัญ

ฉันตระหนักว่าสำหรับทุกค่าของ i (วงนอกสุด) มีวิธีระบุได้ทันทีว่า เป็นไปได้ ที่จะหาค่าสูงสุดใหม่ได้หรือไม่ โดยพื้นฐานแล้ว สำหรับทุกค่าของ i คุณจะต้องติดตามค่าต่ำสุดที่พบจนถึงจุดนั้นด้วย เรียกว่าเล็กที่สุด จากนั้น สำหรับค่า i นั้น ก่อนที่จะเข้าสู่ลูปที่สอง คุณจะต้องพิจารณาว่า nums[i]-smallestNum น้อยกว่าค่า GreatestDiff ในปัจจุบันหรือไม่ หากเป็นเช่นนั้น หมายความว่าไม่มีค่าที่เป็นไปได้สำหรับ nums[j] สำหรับค่า i ที่อาจให้ค่าที่มากกว่าค่าความแตกต่างที่ยิ่งใหญ่ที่สุด ดังนั้นคุณจึงดำเนินการวนซ้ำครั้งถัดไป

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

(ฉันยังแอบฟังฟังก์ชันจับเวลาบางอย่างด้วย เนื่องจากการเปรียบเทียบนั้นได้ผลดีมาก)

ดังนั้นเวลาทำงาน

เพื่อให้กระบวนการง่ายขึ้น ฉันเขียนฟังก์ชันใหม่เพื่อส่งคืนเฉพาะเวลาทำงานเท่านั้น ฉันยังสร้างฟังก์ชันตัวช่วยต่อไปนี้:

สิ่งที่น่าสนใจคือฉันพบข้อผิดพลาดแปลกๆ ซึ่งทำให้ฉันรู้สึกงุนงงจนถึงจุดที่ฉันโพสต์ "คำถามใน StackOverflow" เมื่อฉันเขียนฟังก์ชันใหม่เพื่อส่งคืนเวลาการทำงานเท่านั้น V1 จะทำงานอย่างต่อเนื่องเกือบจะทันทีและส่งคืนเวลาการทำงาน 0 วินาที ในขณะที่ V2 จะทำงานตามที่คาดไว้ รหัสของพวกเขานอกเหนือจากค่าที่ส่งคืนเหมือนกัน และฉันไม่สามารถหาสาเหตุที่แท้จริงได้

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

กลับ [((วันที่ใหม่().getTime() — เริ่มต้น) / 1,000.0), GreatestDiff]

มันเริ่มส่งคืนเวลาทำงานที่ถูกต้องอีกครั้ง

ดังนั้น ต่อไปนี้คือเวลารันสำหรับทั้งสองฟังก์ชันสำหรับขนาดอาร์เรย์ต่างๆ และขนาดสูงสุดแต่ละรายการ:

ตามที่คาดไว้ ฟังก์ชัน V2 ที่ได้รับการปรับปรุงให้ดีขึ้นจะเร็วขึ้นอย่างมาก ประมาณสิบเท่า และเมื่อขนาดสูงสุดที่เป็นไปได้ขององค์ประกอบในอาเรย์เพิ่มขึ้น มันก็จะมีประสิทธิภาพมากขึ้น เนื่องจากจะคอยดูค่าต่ำสุดในปัจจุบันและความแตกต่างที่ยิ่งใหญ่ที่สุดที่เป็นไปได้ในปัจจุบัน และด้วยช่วงค่าแต่ละค่าที่กว้างกว่า ทำให้สามารถข้ามค่าเหล่านั้นได้มากขึ้นอย่างมาก ในทางกลับกัน เวลาดำเนินการของวิธี brute-force ส่วนใหญ่ไม่ขึ้นอยู่กับขนาดสูงสุดขององค์ประกอบอินพุตแต่ละรายการ ซึ่งก็เป็นไปตามที่คาดไว้เช่นกัน

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