ความสุขเล็กๆ ของการเขียนโปรแกรม

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

ฉันมีตัวอย่างสองสามตัวอย่างล่าสุดที่สามารถให้รสชาติของประสบการณ์เหล่านี้ได้

แอป ที่ฉันกำลังดำเนินการอยู่นั้น ด้วยเหตุผลหลายประการ บางครั้งจำเป็นต้องใช้รหัสบล็อกการสำรวจสำมะโนประชากร — สตริงอักขระ 15 ตัว — และแมปรหัสดังกล่าวกับรหัสของเขตลงคะแนนเสียงที่รวมรหัสดังกล่าว — 9–12 สายอักขระ กรมสำรวจสำมะโนเผยแพร่ข้อมูลนี้และเผยแพร่บนเว็บไซต์ของตนได้อย่างอิสระ เรานำเข้าข้อมูลนี้และจัดเก็บไว้ในการแสดง JSON/JavaScript ที่ง่ายที่สุดเท่าที่คุณจะจินตนาการได้ — เพียงออบเจ็กต์ที่มีรหัสบล็อกเป็นคีย์และรหัสเขตลงคะแนนเป็นค่า การประมวลผลที่จำเป็นในการแมปจะโหลดไฟล์ JSON จากนั้นใช้ออบเจ็กต์เพื่อทำการแมปจากคีย์ไปยังค่า

ไฟล์เหล่านี้ถูกจัดเก็บตามรัฐ ดังนั้น เพื่อเลือกกรณีที่เลวร้ายที่สุด เท็กซัสมีบล็อกการสำรวจสำมะโนประชากรเกือบหนึ่งล้านบล็อก และโครงสร้างนี้มีขนาดเกือบ 30 เมกะไบต์เมื่อจัดเก็บไว้ในดิสก์ ในหน่วยความจำจะขยายเป็น 50 MB JSON (สัญลักษณ์วัตถุ JavaScript - วิธีหนึ่งในการนำวัตถุ JavaScript และส่งผ่านเป็นสตริงหรือเก็บไว้ในไฟล์) อาจใช้คำค่อนข้างมาก ดังนั้นบางครั้งอาจมีขนาดเล็กลงเมื่อนำเข้า แต่ในกรณีนี้ ไฟล์ส่วนใหญ่จะเป็นเพียงสตริง ดังนั้นจริงๆ แล้ว ขยายเมื่อแยกวิเคราะห์และจัดเก็บไว้ในหน่วยความจำ

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

เมื่อดูที่เท็กซัสอีกครั้ง ไฟล์ JSON ขนาด 30 MB นั้นจริงๆ แล้วมีขนาดเพียง 4 MB เมื่อบีบอัด ซึ่งเป็นวิธีจัดเก็บและส่งไฟล์ การบีบอัดข้อมูลเป็นวิธีที่ดีในการทำความเข้าใจว่าเนื้อหาข้อมูล "จริง" ของบล็อกข้อมูลบางส่วนคืออะไรอย่างรวดเร็ว แบบฟอร์มที่บีบอัดอาจไม่อยู่ในรูปแบบที่ดีที่สุดสำหรับการประมวลผล แต่จะทำให้คุณทราบได้ว่าข้อมูลมีความซ้ำซ้อนมากน้อยเพียงใด ในกรณีนี้ มีความซ้ำซ้อน ตัน ความซ้ำซ้อนนั้นค่อนข้างชัดเจนเมื่อคุณคิดถึงเนื้อหา เขตการเลือกตั้งแต่ละเขตประกอบด้วยบล็อกการสำรวจสำมะโนประชากรประมาณ 65 บล็อก ดังนั้นแต่ละค่า (รหัสเขตการเลือกตั้งที่มีอักขระ 9 ถึง 12 ตัว) จะถูกทำซ้ำโดยเฉลี่ย 65 ครั้ง รหัสบล็อกจริง ๆ แล้วอยู่ในรูปแบบที่มีโครงสร้างมาก โดยอักขระ 2 ตัวแรกคือรหัสสถานะ (ดังนั้นจะเหมือนกันสำหรับค่าทั้งหมดในไฟล์ที่จัดระเบียบตามรัฐ) อักขระ 3 ตัวถัดไปคือรหัสเขต จากนั้นระบบสำรวจสำมะโนประชากร กลุ่มบล็อกการสำรวจสำมะโนประชากร และสุดท้ายคือหมายเลขบล็อกแต่ละรายการ

เมื่อพิจารณาถึงความซ้ำซ้อนทั้งหมดนี้ สำหรับฉันแล้วดูเหมือนว่าเราจะสามารถสร้างโครงสร้างข้อมูลที่หนาแน่นขึ้นมาก ซึ่งสามารถจัดเก็บ ส่ง โหลด และใช้งานโดยตรงในการนำเสนอที่มีความหนาแน่นสูงนี้ โดยไม่ต้องระเบิดข้อมูลในหน่วยความจำ ฉันเพิ่งกลายเป็นแฟนตัวยงในการเขียนโปรแกรม JavaScript ของฉันเมื่อต้องการเร่งความเร็วหรือลดการใช้หน่วยความจำ (มักจะเป็นสิ่งเดียวกัน) ในการระบุว่าการแสดงข้อมูล JavaScript ไร้เดียงสานั้นป่องโดยไม่จำเป็นและแทนที่จะใช้การแสดงไบนารี่ขนาดกะทัดรัดแทน อาจเป็นราก C/C++ ของฉัน

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

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

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

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

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

ตัวอย่างที่สองของฉันแตกต่างออกไปเล็กน้อย ในกรณีนี้ การเรียนรู้สิ่งใหม่ๆ และนำไปใช้อย่างมีประสิทธิภาพเป็นเรื่องสนุก

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

วิธีพื้นฐานที่สุดในการปรับปรุงประสิทธิภาพคือการใช้รูปร่างที่มีความละเอียดสูงที่กรมสำรวจสำมะโนมอบให้และทำให้ง่ายขึ้นโดยการลบคะแนนออก สิ่งนี้ช่วยได้ทุกที่ (ในการใช้หน่วยความจำและในทุกขั้นตอนของการประมวลผล) ดังนั้นสิ่งที่ต้องให้ความสำคัญจึงชัดเจน คะแนนพิเศษอาจไม่สร้างความแตกต่างในการมองเห็นเมื่อแสดงบนหน้าจอคอมพิวเตอร์ หรือไม่สร้างความแตกต่างที่มีประสิทธิภาพ เนื่องจากไม่ได้เปลี่ยนวิธีที่ผู้ใช้โต้ตอบกับแอปพลิเคชัน รูปแบบการสำรวจสำมะโนประชากรพื้นฐานจำเป็นต้องแยกแยะว่าบ้านเดี่ยวอยู่ในกลุ่มการสำรวจสำมะโนกลุ่มเดียวหรืออีกกลุ่มหนึ่ง แต่สำหรับจุดประสงค์ของเรา การประมาณค่าดังกล่าวก็ใช้ได้ดี เนื่องจากไม่มีข้อมูลอื่นๆ ของเรา (การสำรวจสำมะโนประชากรและการเลือกตั้ง) ที่ความละเอียดดังกล่าว

ดังนั้นการทำให้รูปร่างง่ายขึ้นคือปัญหาแรกของเรา

ปัญหาที่สองคือการรวมชุดของรูปร่างให้เป็นรูปร่างเดียวหรือโดยทั่วไปคือ "การรวมรูปหลายเหลี่ยม" ประเด็นหลักที่เราพบปัญหานี้คือการนำชุดของรูปแบบเขตลงคะแนนเสียงมารวมไว้ในรูปแบบรัฐสภาเดียว (หรือสภานิติบัญญัติของรัฐ) Polygon union เป็นปัญหาที่ได้รับการศึกษามาเป็นอย่างดีในคอมพิวเตอร์กราฟิก แต่วิธีแก้ปัญหาโดยทั่วไปคือต้องใช้ทั้งหน่วยความจำและการประมวลผลสูง และเมื่อเรารวมโซลูชันโอเพ่นซอร์สเข้ากับแอปของเรา ก็ทำให้เกิดภาระอย่างมากต่อประสิทธิภาพเชิงโต้ตอบของแอปพลิเคชัน ฉันต้องสร้างกลไกการแบ่งงานแบบอะซิงโครนัสที่ซับซ้อนไว้ด้านบนเพื่อป้องกันไม่ให้ล็อกแอปของเราทีละวินาที

ปัญหาที่สามคือจะทราบได้อย่างไรว่ารูปร่างสองรูปอยู่ติดกันหรือไม่ นี่เป็นหัวใจหลักในการวิเคราะห์แผนการกำหนดเขตใหม่ ในแอปพลิเคชันของเรา สิ่งนี้จะเกิดขึ้น "ออฟไลน์" เพื่อสร้างกราฟที่ต่อเนื่องกัน ไม่จำเป็นต้องรวดเร็วเป็นพิเศษ แต่เดิมได้รับการแก้ไขด้วยชุดเครื่องมือที่แยกออกจากชุดเครื่องมือหลักของเรา ดังนั้นเราจึงมีแรงจูงใจที่จะพยายามรวมสิ่งนี้เข้าด้วยกัน

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

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

ในการค้นคว้าเรื่องนี้ ฉันได้พบกับไลบรารี TopoJSON ที่เขียนโดย Mike Bostock Mike ค่อนข้างเป็นที่รู้จักในชุมชนการแสดงภาพข้อมูล โดยก่อนหน้านี้เคยทำงานด้านนวัตกรรมที่ New York Times และเป็นผู้เขียนร่วมของไลบรารีการแสดงภาพแบบโอเพ่นซอร์สที่สำคัญ d3.js การสืบสวนนี่คือจุดที่ฉันได้เรียนรู้สิ่งใหม่ๆ

ไลบรารี TopoJSON ใช้แนวทางที่แตกต่างออกไปในการแก้ไขปัญหาที่ฉันเผชิญอยู่ ความเข้าใจหลักก็คือ เมื่อคุณมีชุดของรูปร่าง เช่น โครงร่างของรัฐในสหรัฐฯ หรือเขตลงคะแนนเสียงของรัฐ รูปร่างเหล่านี้จริงๆ แล้วมีลักษณะเฉพาะที่สำคัญในการแบ่งพื้นผิว — รูปร่างเหล่านี้ไม่ทับซ้อนกันและครอบคลุมพื้นที่ทั้งหมด ส่วนหนึ่งของพื้นผิวที่คุณใส่ใจ คุณมี โทโพโลยี จริงๆ (จึงเป็นชื่อของแพ็คเกจ) และรูปหลายเหลี่ยมแบ่งส่วนของเส้นตรงหรือ ส่วนโค้งของโทโพโลยีนี้

ข้อมูลเชิงลึกหลักก็คือ แทนที่จะคิดว่าข้อมูลของคุณเป็นชุดของรูปร่าง คุณจะมีชุดของส่วนโค้งทอพอโลยีที่แบ่งพื้นผิวของคุณจริงๆ สิ่งนี้กลายเป็นกุญแจสำคัญในการประมวลผลที่ตามมา นี่มันเจ๋งมาก!

รูปแบบการทะลุทะลวงนี้เกิดขึ้นบ่อยครั้ง คุณมีปัญหาทั่วไปบางอย่างที่ “ยากในทางทฤษฎี” แต่การระบุข้อมูลเชิงลึกที่สำคัญจะทำให้คุณสามารถแก้ไขปัญหาที่แตกต่างและง่ายกว่าด้วยวิธีที่ตัดผ่านความซับซ้อนด้วยประสิทธิภาพที่ดีกว่ามาก

ขั้นตอนแรกของการประมวลผลคือนำรูปหลายเหลี่ยมของคุณมาแยกเป็นส่วนโค้งที่จุดที่รูปหลายเหลี่ยมตัดกัน จากนั้นคุณกำจัดส่วนโค้งที่ซ้ำกันโดยระบุรูปหลายเหลี่ยมทั้งหมดที่ใช้ส่วนโค้งร่วมกันและให้พวกมันอ้างอิงส่วนโค้งเดียวกัน

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

ทีนี้ เมื่อคุณลดรูปลง คุณจะลดรูปลงตามรายละเอียดของส่วนโค้งที่ใช้ร่วมกันเหล่านี้ สิ่งนี้รับประกันโดยอัตโนมัติว่ารูปหลายเหลี่ยมสองรูปที่ใช้ขอบร่วมกันจะตัดสินใจลดความซับซ้อนเหมือนกันทั้งสองด้านของขอบ ขอบนั้นถูกระบุโดยส่วนโค้งแบบง่ายที่ใช้ร่วมกัน

ปัญหาสหภาพจะง่ายยิ่งขึ้น เมื่อพิจารณาชุดของรูปหลายเหลี่ยมที่อธิบายว่าเป็นชุดของส่วนโค้ง คุณเพียงแค่ลบส่วนโค้งใดๆ ที่อ้างอิงโดยรูปหลายเหลี่ยมมากกว่าหนึ่งรูปออก ส่วนโค้งที่ยังคงอธิบายขอบเขตของรูปร่างที่ผสาน (มีรายละเอียดปลีกย่อยบางประการในการจัดการกับรูปร่างและรูที่ไม่ต่อเนื่องกันเมื่อสร้างรูปร่างสุดท้ายขึ้นมาใหม่)

ปัญหาความต่อเนื่องกันยังเป็นเรื่องเล็กน้อยในการนำเสนอนี้ รูปร่างสองรูปจะต่อเนื่องกันหากมีส่วนโค้งร่วมกัน

อีกสิ่งหนึ่งที่ฉันพบว่าน่าทึ่งคือฟังก์ชันทั้งหมดนี้ (และฟีเจอร์อื่น ๆ ที่ฉันข้ามไป) ได้รับการปรับใช้ด้วยโค้ดไม่กี่ร้อยบรรทัด ชิ้นงานเรียบร้อยมาก ฉันคุ้นเคยกับโค้ดเบสอย่าง Microsoft Office มากกว่า ซึ่งคุณอาจมีโค้ดกว่า 100,000 บรรทัดที่เกี่ยวข้องกับการคัดลอก/วาง (ซึ่งพูดตามตรงแล้ว มันเป็นปัญหาที่ซับซ้อนทางความหมายจริงๆ — ให้ฉันบอกคุณเกี่ยวกับการคัดลอกและวางใน HTML ดีกว่า) ตารางบ้าง)

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

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

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

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

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

กระบวนการพัฒนามีการพลิกผันเล็กน้อย ฉันจะประมวลผลรูปทรงหลายสิบล้านรูปแบบที่ครอบคลุมสหรัฐอเมริกา และไม่กี่ร้อยรูปแบบก็จะทำให้ฉันเดือดร้อน รูปร่างเหล่านี้เป็นอย่างไร? ดังนั้น ฉันจะเดินทางไปยังจุดหนึ่งตามท่าเรือบอสตัน ซึ่งส่วนใหญ่เป็นรูปสี่เหลี่ยมผืนผ้าและมีนิ้วเรียวยาวคลุมท่าเทียบเรือ หรือชุดรูปทรงในโคโลราโดที่นักภูมิศาสตร์วาดอย่างปราณีตเพื่อปกคลุมลำธารที่คดเคี้ยวแคบๆ สำหรับรัฐมินนิโซตา ซึ่งใช้รูปทรงมากกว่าที่คุณคิดไว้มาก ได้วาดภาพรอบๆ แหล่งน้ำทั้งหมดอย่างระมัดระวัง ดินแดนแห่งทะเลสาบนับหมื่น ฉันต้องติดตามข้อผิดพลาดทั่วไปด้วยอัลกอริธึมการผสาน TopoJSON เมื่อต้องจัดการกับรูปหลายเหลี่ยมที่มีรูที่สัมผัสได้เอง (ลองนึกถึงรูปที่แปด) เหตุใดจึงเกิดขึ้นเพียงไม่กี่สิบครั้งทั่วทั้งสหรัฐอเมริกา? จากนั้นฉันก็เห็นรูชุดหนึ่ง — แถวไข่มุก — วาดอย่างระมัดระวังรอบๆ แนวเกาะกลางแม่น้ำ

ปัญหาที่สองคือการแทน TopoJSON ที่ใช้สำหรับจุดและลำดับบรรทัดนั้นสอดคล้องกับแพ็คเกจและรูปแบบ JavaScript อื่น ๆ สำหรับการประมวลผลทางภูมิศาสตร์ (โดยพื้นฐานแล้วจุดหนึ่งถูกแสดงโดยอาร์เรย์สององค์ประกอบและลำดับบรรทัดถูกแสดงเป็นอาร์เรย์ของจุด) แต่เป็น หน่วยความจำไม่มีประสิทธิภาพอย่างน่ากลัว โปรแกรมเมอร์ C คิดว่าอาร์เรย์อาจเป็นโครงสร้างข้อมูลที่ง่ายและกะทัดรัดที่สุด แต่ JavaScript ถือว่าอาร์เรย์เป็นรูปแบบพิเศษของวัตถุทั่วไปหรือตารางแฮช เพียงใช้สตริงคีย์พิเศษในรูปแบบ "0", "1" ฯลฯ ผลที่สุดคือการแสดงลำดับจุด / เส้นอย่างง่ายใช้หน่วยความจำจำนวนมากและครอบงำการใช้งานหน่วยความจำของเราจริงๆ สิ่งนี้เป็นจริงแม้ว่า TopoJSON จะเริ่มต้นด้วยชัยชนะครั้งใหญ่เกือบ 50% เหนือรูปแบบที่จัดโดยรูปหลายเหลี่ยมโดยการเข้ารหัสจุดบนขอบที่ใช้ร่วมกันเพียงครั้งเดียว

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

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

เมื่อรวมเข้าด้วยกันในที่สุด งานที่เสร็จสมบูรณ์จะลดการใช้หน่วยความจำของแอปของเราลง 100 เมกะไบต์ และขจัดปัญหาส่วนที่ต้องใช้การประมวลผลและหน่วยความจำมากที่สุดของแอปพลิเคชันแบบโต้ตอบของเราออกไป ระหว่างทาง ฉันได้เรียนรู้เกี่ยวกับเทคโนโลยีที่น่าสนใจ และสำรวจความแปลกประหลาดบางประการในภูมิศาสตร์ของสหรัฐอเมริกา สนุกจริงๆ!