ในสถานการณ์เช่นฟอรัมและห้องสนทนาเพื่อให้แน่ใจว่าประสบการณ์ผู้ใช้เรามักจะต้องปิดกั้นคำที่ไม่ดีมากมาย สำหรับการค้นหาคำหลักเดียวจะมีประสิทธิภาพมากขึ้นในดัชนีและวิธีการปกติ อย่างไรก็ตามหากมีคำหลักจำนวนมากหากคุณเรียกดัชนีหรือคำทั่วไปซ้ำ ๆ เพื่อให้ตรงกับข้อความเต็มการใช้ประสิทธิภาพจะสูงมาก เนื่องจากสตริงเป้าหมายมักจะมีขนาดใหญ่จึงจำเป็นต้องตรวจสอบให้แน่ใจว่าได้ผลลัพธ์ในการเดินทางครั้งเดียว ตามความต้องการดังกล่าวมันเป็นเรื่องง่ายที่จะคิดวิธีที่จะจับคู่ตัวละครแต่ละตัวในข้อความทั้งหมดตามลำดับ ตัวอย่างเช่นสำหรับข้อความนี้: "ไมค์จอร์แดนพูดว่า" แค่ทำมัน "ดังนั้นมาร์คจึงเป็นผู้เขียนโค้ด" หากคำหลักของเราคือ "ไมค์" และ "มาร์ค" คุณสามารถสำรวจประโยคทั้งหมดได้ เมื่อคุณพบ "M" จากนั้นดูว่าคุณสามารถจับคู่ "ฉัน" หรือ "A" ได้หรือไม่ หากคุณสามารถจับคู่ได้จนถึงที่สุดคุณจะพบคำหลักได้สำเร็จมิฉะนั้นคุณจะเดินทางต่อไป จากนั้นโครงสร้างของคำหลักควรเป็นเช่นนี้:
var keywords = {m: {i: {k: {e: {end: true}}}}, a: {r: {k: {end: true}}}}}}}}}จากด้านบนเราจะเห็นว่าข้อมูลนี้เป็นโครงสร้างต้นไม้และยังคงใช้เวลานานในการสร้างโครงสร้างต้นไม้ตามกลุ่มคำหลักในขณะที่คำหลักได้รับแล้วดังนั้นคุณสามารถสร้างโครงสร้างข้อมูลล่วงหน้าก่อนที่จะจับคู่ รหัสมีดังนี้:
ฟังก์ชั่น buildtree (คำหลัก) {var tblcur = {}, คีย์, str_key, ความยาว, j, i; var tblroot = tblcur; สำหรับ (j = keywords.length - 1; j> = 0; j - = 1) {str_key = คำหลัก [j]; ความยาว = str_key.length; สำหรับ (i = 0; i <length; i += 1) {key = str_key.charat (i); if (tblcur.hasownproperty (คีย์)) {tblcur = tblcur [คีย์]; } else {tblcur = tblcur [key] = {}; }} tblcur.end = true; // คำหลักสุดท้าย tblcur = tblroot; } ส่งคืน tblroot;}รหัสนี้ใช้คำสั่งต่อเนื่อง: tblcur = tblcur [คีย์] = {} คำสั่งดำเนินการที่นี่คือคำสั่งการดำเนินการของคำสั่ง เนื่องจากระดับการทำงานของ [] สูงกว่า = สิ่งแรกคือการสร้างแอตทริบิวต์คีย์ในวัตถุ TBLCUR รวมกับ tblroot = tblcur = {} ลำดับการดำเนินการคือ:
var tblroot = tblcur = {}; tblroot = tblcur; tblcur ['คีย์'] = ไม่ได้กำหนด; // ตอนนี้ tblroot = {คีย์: undefined} tblcur ['key'] = {}; tblcur = tblcur ['key'];ผ่านรหัสข้างต้นข้อมูลการสืบค้นที่ต้องการจะถูกสร้างขึ้น มาดูวิธีการเขียนของอินเตอร์เฟสแบบสอบถาม
สำหรับแต่ละคำของสตริงเป้าหมายเราเริ่มจากด้านบนของคำหลักนี้ อันดับแรกคำหลัก [a] หากมีให้ดูที่คำหลัก [a] [b] หากคำหลักสุดท้าย [a] [b] … [x] = จริงหมายความว่าการจับคู่นั้นสำเร็จ หากคำหลัก [a] [b] … [x] = ไม่ได้กำหนดการจับคู่จะถูกรีสตาร์ทจากตำแหน่งถัดไป
การค้นหาฟังก์ชั่น (เนื้อหา) {var tblcur, p_star = 0, n = content.length, p_end, จับคู่, // ไม่ว่าจะหา match_key, match_str, arrmatch = [], // ที่เก็บข้อมูล arrlength ผลลัพธ์ = 0; // ดัชนีความยาวของ arrmatch ในขณะที่ (p_star <n) {tblcur = tblroot; // การติดตามกลับไปที่รูท p_end = p_star; match_str = ""; จับคู่ = เท็จ; ทำ {match_key = content.charat (p_end); if (! (tblcur = tblcur [match_key])) {// จุดสิ้นสุดของการจับคู่นี้ p_star += 1; หยุดพัก; } else {match_str += match_key; } p_end += 1; if (tblcur.end) // ว่าจะตรงกับหาง {match = true; }} ในขณะที่ (จริง); if (match) {// maximum match arrmatch [arrlength] = {key: match_str, เริ่มต้น: p_star - 1, สิ้นสุด: p_end}; arrlength += 1; p_star = p_end; }} return arrmatch;}ข้างต้นเป็นแกนหลักของระบบการจับคู่คำหลักทั้งหมด ที่นี่เราใช้คุณสมบัติภาษาของ JS เป็นอย่างดีและประสิทธิภาพสูงมาก ฉันใช้ "Soushen Ji" 500,000 คำเพื่อทดสอบและพบว่า 300 สำนวนที่ได้รับ เอฟเฟกต์การจับคู่ประมาณ 1 วินาที ที่สำคัญเนื่องจากข้อความเป้าหมายถูกสำรวจในครั้งเดียวความยาวของข้อความเป้าหมายมีผลเพียงเล็กน้อยต่อเวลาในการสืบค้น จำนวนคำหลักที่มีผลกระทบมากขึ้นต่อเวลาในการสืบค้นคือจำนวนคำหลัก แต่ละคำในข้อความเป้าหมายจะผ่านคำหลักดังนั้นจึงมีผลกระทบต่อการสืบค้น
การวิเคราะห์อย่างง่าย
ฉันเดาว่าคุณกำลังสงสัยเมื่อคุณอ่านบทความข้างต้น คุณสามารถสำรวจคำหลักทั้งหมดสำหรับแต่ละคำ แม้ว่าคำหลักบางคำจะเหมือนกันบางส่วน แต่ก็ค่อนข้างใช้เวลานานในการสำรวจพวกเขาอย่างสมบูรณ์ อย่างไรก็ตามคุณสมบัติของวัตถุใน JS ถูกสร้างขึ้นโดยใช้ตารางแฮช ข้อมูลของโครงสร้างนี้แตกต่างจากการสำรวจอาร์เรย์แบบง่าย ๆ และประสิทธิภาพสูงกว่าการสำรวจอาเรย์ตามคำสั่งซื้อ นักเรียนบางคนอาจไม่คุ้นเคยกับโครงสร้างข้อมูลดังนั้นฉันจะพูดคุยสั้น ๆ เกี่ยวกับเนื้อหาที่เกี่ยวข้องของตารางแฮช
ก่อนอื่นมาดูการจัดเก็บข้อมูล
การจัดเก็บข้อมูลในหน่วยความจำประกอบด้วยสองส่วนส่วนหนึ่งคือค่าและอีกอันคือที่อยู่ คิดว่าหน่วยความจำเป็นพจนานุกรม Xinhua คำอธิบายของคำคือค่าและไดเรกทอรีคือที่อยู่ พจนานุกรมถูกจัดเรียงโดยพินอินเช่น "Ni" ที่มีการออกเสียงเดียวกันนั้นจัดเรียงในชิ้นส่วนเดียวกันนั่นคืออาร์เรย์จะถูกจัดเรียงอย่างเรียบร้อยในพื้นที่หน่วยความจำ โครงสร้างนี้เป็นอาร์เรย์คุณสามารถระบุ "Ni" หมายเลข 1 และ 10 เพื่อเข้าถึงได้ แผนภาพโครงสร้างมีดังนี้:
ข้อได้เปรียบของอาร์เรย์คือมันง่ายที่จะสำรวจและพวกเขาสามารถเข้าถึงข้อมูลที่เกี่ยวข้องโดยตรงผ่านตัวห้อย แต่มันยากมากที่จะเพิ่มหรือลบรายการที่แน่นอน ตัวอย่างเช่นหากคุณต้องการลบรายการ 6 ข้อมูลหลังจากรายการ 5 จะต้องถูกเลื่อนไปข้างหน้าโดยตำแหน่งเดียว หากคุณต้องการลบบิตแรกอาร์เรย์ทั้งหมดจะต้องย้ายซึ่งใช้มาก
เพื่อแก้ปัญหาการเพิ่มอาร์เรย์และการลบรายการที่เชื่อมโยงจะปรากฏขึ้น หากเราแบ่งค่าออกเป็นสองส่วนชิ้นส่วนจะใช้ในการจัดเก็บค่าดั้งเดิมและส่วนอื่น ๆ จะใช้เพื่อจัดเก็บที่อยู่ซึ่งชี้ไปที่โครงสร้างเดียวกันและอื่น ๆ ในรูปแบบรายการที่เชื่อมโยง โครงสร้างมีดังนี้:
สามารถมองเห็นได้อย่างชัดเจนจากรูปด้านบนว่าการเพิ่มและการลบรายการที่เชื่อมโยงนั้นง่ายมาก เพียงแค่เขียนรายการเป้าหมายและรายการถัดไปของรายการก่อนหน้าและจะเสร็จสิ้น อย่างไรก็ตามมันยากมากที่จะสอบถามมูลค่าของรายการ คุณต้องสำรวจมันเพื่อเข้าถึงตำแหน่งเป้าหมาย
เพื่อรวมข้อดีของโครงสร้างทั้งสองนี้คุณต้องคิดถึงโครงสร้างต่อไปนี้
โครงสร้างข้อมูลนี้เป็นโครงสร้างตารางแฮช ที่อยู่ส่วนหัวของรายการที่เชื่อมโยงจะถูกเก็บไว้ในอาร์เรย์และสามารถสร้างตารางข้อมูลสองมิติได้ สำหรับวิธีการกระจายข้อมูลนี่เป็นอัลกอริทึมการแฮชและการแปลปกติควรเป็นอัลกอริทึมการแฮช แม้ว่าโดยหลักการแล้วจะมีอัลกอริทึมหลายประเภท แต่พวกเขาก็แก้ปัญหาคีย์ผ่านฟังก์ชั่นแล้ววางข้อมูลตามผลลัพธ์ที่ได้จากการแก้ปัญหา กล่าวอีกนัยหนึ่งการแมปจะเกิดขึ้นระหว่างคีย์และที่อยู่จริงดังนั้นในเวลานี้เราไม่สามารถเข้าถึงอาร์เรย์ได้อีกต่อไปโดยการย่อยอาร์เรย์หรือเพียงแค่ผ่าน แต่แทนที่จะค้นหาข้อมูลโดยฟังก์ชั่นผกผันของฟังก์ชันแฮช วัตถุใน JS คือโครงสร้างแฮช ตัวอย่างเช่นเรากำหนด OBJ obj.name ผ่านการแฮชและตำแหน่งในหน่วยความจำอาจเป็น 90 ในรูปด้านบน เมื่อเราต้องการใช้งาน obj.name เลเยอร์พื้นฐานจะช่วยให้เราค้นหาตำแหน่ง 90 ผ่านอัลกอริทึมแฮชซึ่งหมายความว่าเราเริ่มค้นหารายการที่เชื่อมโยงโดยตรงจาก 12 รายการของอาร์เรย์แทนที่จะสำรวจบล็อกหน่วยความจำทั้งหมดจาก 0
กำหนดวัตถุ obj {key: value} ใน js คีย์จะถูกแปลงเป็นสตริงแล้วแฮชเพื่อรับที่อยู่หน่วยความจำแล้วใส่ค่าลงไป สิ่งนี้ช่วยให้เราเข้าใจว่าทำไมเราสามารถเพิ่มและลบแอตทริบิวต์ได้ตามความประสงค์และทำไมเราถึงสามารถกำหนดแอตทริบิวต์ให้กับอาร์เรย์ใน JS และไม่มีอาร์เรย์ข้ามพรมแดนที่เรียกว่า
ในสถานการณ์ที่ปริมาณข้อมูลมีขนาดใหญ่ตารางแฮชมีข้อได้เปรียบที่ชัดเจนมากเพราะจะช่วยลดการคำนวณที่ไม่จำเป็นจำนวนมากผ่านอัลกอริทึมแฮช การเพิ่มประสิทธิภาพประสิทธิภาพที่เรียกว่าจริง ๆ แล้วทำให้คอมพิวเตอร์มีคอมพิวเตอร์น้อยลง การเพิ่มประสิทธิภาพที่ใหญ่ที่สุดคือการไม่คำนวณ!
การเพิ่มประสิทธิภาพของอัลกอริทึม
ตอนนี้คุณเข้าใจการใช้อัลกอริทึมพื้นฐานแล้วคุณสามารถพิจารณาเพิ่มประสิทธิภาพอัลกอริทึมในการหวนกลับ อย่างไรก็ตามก่อนที่จะปรับให้เหมาะสมคุณควรเน้นสิ่งหนึ่ง: อย่าไล่ตามการแสดงอย่างสุ่มสี่สุ่มห้า! ตัวอย่างเช่นในกรณีนี้เราสามารถจับคู่ได้มากถึง 5,000 คำมากที่สุดดังนั้นอัลกอริทึมที่มีอยู่จึงเพียงพอและการเพิ่มประสิทธิภาพทั้งหมดไม่จำเป็น เหตุผลที่ฉันยังคงพูดถึงการเพิ่มประสิทธิภาพคือการปรับปรุงความเข้าใจของฉันเกี่ยวกับอัลกอริทึมและโปรแกรมแทนที่จะทำการเพิ่มประสิทธิภาพ 1MS จริงๆ
เราพบว่าไม่มีคำหลักของเราที่มีคำเดียวดังนั้นมันจะเป็นการสิ้นเปลืองสำหรับเราในการสำรวจคำหลักตามหน่วยของคำเดียว การเพิ่มประสิทธิภาพที่นี่คือการแสดงล่วงหน้าความยาวสูงสุดและต่ำสุดของคำหลักและค้นหาหน่วยที่มีความยาวต่ำสุดในแต่ละครั้ง ตัวอย่างเช่นคำหลักในกรณีทดสอบของฉันคือสำนวนและสั้นที่สุดคือ 4 อักขระดังนั้นทุกครั้งที่ฉันจับคู่ฉันจับคู่อักขระ 4 ตัวเข้าด้วยกัน ถ้าฉันตีให้ค้นหาในเชิงลึกเพื่อค้นหาความยาวสูงสุด กล่าวอีกนัยหนึ่งเมื่อเราสร้างต้นไม้เป็นครั้งแรกมันจะถูกสร้างขึ้นครั้งแรกด้วยความยาวขั้นต่ำจากนั้นจะถูกเพิ่มคำต่อคำ
ทำการคำนวณอย่างง่าย ตามกรณีทดสอบของเราสำหรับ 300 สำนวนเราต้องเปรียบเทียบหนึ่งคำหนึ่งครั้งและสำหรับการสืบค้นคำเดียวเราต้องเปรียบเทียบ 4 ครั้งและการเปรียบเทียบแต่ละครั้งเราต้องเข้าถึงโครงสร้างต้นไม้ของเราซึ่งเป็นการใช้ประสิทธิภาพที่หลีกเลี่ยงได้ ที่สำคัญการเปรียบเทียบที่นี่ไม่ใช่การเปรียบเทียบสตริง คำหลักของเราที่นี่ทั้งหมดมีอยู่เป็นคีย์และเอฟเฟกต์ก็เหมือนกับคีย์ใน OBJ ซึ่งถูกแฮชคีย์แล้วเข้าถึงที่อยู่ที่เกี่ยวข้อง! ดังนั้นไม่ต้องกังวลเกี่ยวกับความแตกต่างระหว่างการเปรียบเทียบหนึ่งคำและเปรียบเทียบสี่คำ เราไม่ได้เปรียบเทียบสตริง!
นั่นคือทั้งหมดที่เกี่ยวกับการจับคู่คำหลักหลายคำ ฉันจะไม่โพสต์รหัสเวอร์ชันที่เหมาะสมเพราะโดยทั่วไปจะไม่มีให้บริการ