1brc ObjectPascal
End of Challenge with no oops
นี่คือพื้นที่เก็บข้อมูลที่จะประสานงานความท้าทาย 1 พันล้านแถวสำหรับ Object Pascal
ความท้าทายหนึ่งพันล้านแถว (1BRC) เป็นการสำรวจที่สนุกสนานว่า Pascal วัตถุที่ทันสมัยสามารถผลักดันได้ไกลแค่ไหนในการรวมหนึ่งพันล้านแถวจากไฟล์ข้อความ คว้าเธรดทั้งหมดของคุณเอื้อมมือออกไปที่ SIMD หรือดึงเคล็ดลับอื่น ๆ และสร้างการใช้งานที่เร็วที่สุดสำหรับการแก้ปัญหานี้!
ไฟล์ข้อความมีค่าอุณหภูมิสำหรับช่วงของสถานีอากาศ แต่ละแถวคือการวัดหนึ่งครั้งในรูปแบบ <string: station name>;<double: measurement> ด้วยค่าการวัดที่มีตัวเลขเศษส่วนเดียวที่แน่นอน แถวจะถูกคั่นด้วยฟีดบรรทัดเดียวเท่ากับ LF (ASCII 10) เพื่อความสอดคล้องกับความท้าทายดั้งเดิม - และไม่ใช่ CR+LF (ASCII 13+10) อีกต่อไป ต่อไปนี้แสดงสิบแถวเป็นตัวอย่าง:
Hamburg;12.0
Bulawayo;8.9
Palembang;38.8
St. John's;15.2
Cracow;12.6
Bridgetown;26.9
Istanbul;6.2
Roseau;34.4
Conakry;31.2
Istanbul;23.0
ภารกิจคือการเขียนโปรแกรมวัตถุ Pascal ที่อ่านไฟล์คำนวณค่าต่ำสุดค่าเฉลี่ยและค่าอุณหภูมิสูงสุดต่อสถานีสภาพอากาศและปล่อยผลลัพธ์ของ STDOUT . นี้ (เช่นเรียงลำดับตามตัวอักษรตามชื่อสถานีและค่าผลลัพธ์ <min>/<mean>/<max> สถานีในรูปแบบ ส่วนการปัดเศษหรือใช้งานของคุณเองที่สอดคล้องกับตัวเลือกที่มีให้):
{Abha=-23.0/18.0/59.2, Abidjan=-16.2/26.0/67.3, Abéché=-10.0/29.4/69.0, Accra=-10.1/26.4/66.4, Addis Ababa=-23.7/16.0/67.0, Adelaide=-27.8/17.3/58.5, ...}
การส่งจะผ่าน PR (คำขอดึง) ไปยังที่เก็บนี้
ความท้าทายจะเริ่มตั้งแต่วันที่ 10 มีนาคมจนถึงวันที่ 10 พฤษภาคม 2567
เมื่อสร้างรายการของคุณโปรดทำดังนี้:
entries ที่มีนามสกุลและนามสกุลแรกของคุณเช่นสำหรับ Gustavo Carreno: entries/gcarrenoREADME.md ด้วยเนื้อหาบางอย่างเกี่ยวกับวิธีการของคุณเช่น entries/gcarreno/README.mdentries/<your name>/src , เช่น entries/gcarreno/srcbin ออกจากรูทของที่เก็บนี้.gitignore กำหนดเองสำหรับสิ่งที่ไม่ได้อยู่ในหลักโปรดทำความท้าทายนี้เป็นหลักเพื่อให้เราสามารถเรียนรู้สิ่งใหม่ ๆ ซึ่งหมายความว่าจะอนุญาตให้คัดลอกรหัสจากผู้อื่นภายใต้เงื่อนไขเหล่านี้:
API ของระบบปฏิบัติการใด ๆ หรือไลบรารี C/C++ ภายนอกJedi Project หรือแม้แต่ mORMmot (หรือสิ่งอื่นใด) ถ้ามันคอมไพล์รันข้ามแพลตฟอร์มที่อนุญาตIDE สำคัญ
ความท้าทายนี้สามารถป้อนได้แม้ว่าคุณจะสามารถเข้าถึง RAD Studio รุ่นชุมชนเท่านั้น ฉันมี Windows VM โดยติดตั้ง Rad Studio ซึ่งจะทำการรวบรวม Cross ที่จำเป็นในโฮสต์ Linux ของฉัน
ส่งการดำเนินการของคุณและเป็นส่วนหนึ่งของคณะกรรมการผู้นำ!
ด้วยความช่วยเหลือของชุมชนที่งดงามนี้เราสามารถไปสู่การแก้ปัญหาการปัดเศษที่ใช้งานได้ในที่สุด
ซึ่งหมายความว่าฉันสนับสนุนให้ทุกคนใช้รหัสที่อยู่ในหน่วยพื้นฐาน
ฉันต้องทำให้ Crystal ชัดเจนว่าการใช้รหัสนั้นเป็น ตัวเลือก หนึ่งที่คุณสามารถเลือกไม่ได้
แต่ถ้าคุณเลือกเพียงแค่รวมหน่วยนั้นไว้ในรายการของคุณ
บันทึก
ตอนนี้เรามีทั้งรุ่น Lazarus และรุ่น Delphi ของเครื่องกำเนิดไฟฟ้าสำหรับทั้ง 32B และ 64B
เพื่อที่จะสร้างข้อความหนึ่งพันล้านแถวเรากำลังจัดหาซอร์สโค้ดสำหรับเครื่องกำเนิดอย่างเป็นทางการดังนั้นเราทุกคนจึงมีข้อมูลรายการเดียวกัน
| พารามิเตอร์ | คำอธิบาย |
|---|---|
| -h หรือ -help | เขียนข้อความความช่วยเหลือนี้และออก |
| -v หรือ -Version | เขียนเวอร์ชันและออก |
| -i หรือ--- input-file <filename> | ไฟล์ที่มีสถานีอากาศ |
| -o หรือ -Output-File <Filename> | ไฟล์ที่จะมีบรรทัดที่สร้างขึ้น |
| -n หรือ -line-count <number> | จำนวนบรรทัดที่จะสร้าง (สามารถใช้ 1_000_000_000) |
| -4 หรือ -400STATIONS | มีเพียง 400 สถานีอากาศในไฟล์เอาต์พุต |
บันทึก
นี่ยังคงเป็นฟลักซ์นิดหน่อยยังคงต้องทำเวอร์ชัน Delphi ให้เสร็จ
เพื่อตรวจสอบผลลัพธ์อย่างเป็นทางการเรากำลังจัดทำซอร์สโค้ดสำหรับพื้นฐานอย่างเป็นทางการ
| พารามิเตอร์ | คำอธิบาย |
|---|---|
| -h หรือ -help | เขียนข้อความความช่วยเหลือนี้และออก |
| -v หรือ -Version | เขียนเวอร์ชันและออก |
| -i หรือ--- input-file <filename> | ไฟล์ที่มี 1 พันล้านแถว |
คุณสามารถตรวจสอบ measurements.txt ที่สร้างขึ้น txt ด้วยยูทิลิตี้ SHA256 :
ลินเวกซ์
$ sha256sum ./data/measurements.txtWindows (บรรทัดคำสั่ง)
C:> CertUtil -hashfile .datameasurements.txt SHA256Windows (PowerShell)
Get-FileHash . data measurements.txt - Algorithm SHA256 SHA256 HASH ที่คาดหวัง: 2b48bc2fa0b82d748925a820f43f75df01cc06df7447c7571e52d3962e675960
ขณะนี้มีพื้นฐานของ Delphi ซึ่งหมายความว่าตอนนี้เรามีวิธีการอย่างเป็นทางการในการสร้างผลผลิตที่ถูกต้องทั้งสองด้านของรั้ว
ด้วยสิ่งนี้ตอนนี้เรามีแฮชอย่างเป็นทางการ: 4256d19d3e134d79cc6f160d428a1d859ce961167bd01ca528daca8705163910
นอกจากนี้ยังมีรุ่นพื้นฐานที่เก็บถาวร
เพื่อการเปรียบเทียบที่ง่ายขึ้นกับพื้นฐานนี่คือแฮชสำหรับจำนวนแถวที่สร้างขึ้นที่แตกต่างกัน:
| เส้น | แฮชไฟล์อินพุต | แฮชไฟล์เอาต์พุต |
|---|---|---|
| 1_000 | 0be4844a2417c08a85a44b26509bbe6868a6f65d0e0d087d3f9ceedc02f5ceaa | d42c37ca405f230e91dd0a75e6741dbbbcddd2338963ea0f0e727cf90ecbd7e7 |
| 10_000 | 447380628ca25b1c9901c2e62e01591f2e2f794d2888934a5e9d4a67d72346a5 | b4dd36d80a63fefdccbff50ffaaef7e2092034935c729b3330569c7c7f7351fc |
| 100_000 | dd3a4821e91de82e44f17f65b1951af8a21652b92c20a7e53a1fa02ea6e5fbd2 | c9e50d46bba327727bf4b412ec0401e0c2e59c9035b94b288e15631ca621cb52 |
| 1_000_000 | c2955973c3db29bf544655c11d2d3c7ac902c9f65014026b210bd25eb1876c0c | 5fedbd9811660ee3423f979a0c854ec8b70da3e804170bc39bcc400c94f93bc0 |
| 10_000_000 | 90193d314e991f7789258c8b6b06c493a4d624991e203b12343c2a8ce1d0c7fd | 2f3a6383b3bc83a9ad53fc0773de2da57bd4add8a51662cdb86bfca502d276a3 |
| 100_000_000 | f55384da4646a0c77a1d5dd94a58f8430c5956fe180cedcb17b4425fe5389a39 | 7e8339b5d268fa400a93887b7a1140ac1adf683a8e837e6274fd71e383c26c6b |
ฉันตัดสินใจแล้วว่าฉันจะต้องการให้ความท้าทายนี้หันไปถึง 11!
ซึ่งหมายความว่ามีความแตกต่างบางอย่างจากต้นฉบับ
ผลลัพธ์ดั้งเดิมคำนวณจากสถานีอากาศขนาดเล็ก: 400
ในขณะที่ฉันยังไม่ได้ตารางจำนวนที่อยู่ในไฟล์อินพุต แต่เราไม่ได้ จำกัด หมายเลขใด ๆ ในขณะที่เราใช้สถานีเต็ม ~ 40k ที่มีอยู่ใน data/weather_stations.csv เพื่อสร้างไฟล์อินพุต
ความแตกต่างอีกประการหนึ่งคือเครื่องจักรที่ใช้งานได้
ฉันใช้เครื่องของตัวเองกับรายละเอียดที่กล่าวถึงในส่วนผลลัพธ์ตะโกน
ฉันยังอนุญาตให้ใช้เธรด 32 ฉบับเต็มที่เครื่องของฉันจัดเตรียมไว้ซึ่งความท้าทายดั้งเดิม จำกัด ไว้ที่ 8
ความท้าทายดั้งเดิมยังมีตารางผลลัพธ์ที่สองที่มีสถานี 10K และการใช้เธรดทั้งหมด 64 รายการ
ด้วยทั้งหมดที่กล่าวมาการเปรียบเทียบกับความท้าทายดั้งเดิมควรทำโดยคำนึงถึงสิ่งนี้
นี่คือผลลัพธ์จากการเรียกใช้รายการทั้งหมดในความท้าทายในคอมพิวเตอร์ส่วนบุคคลของฉัน:
| - | ผลลัพธ์ (M: S.MS) | ผู้ประกอบการ | ผู้ส่ง | หมายเหตุ | ใบรับรอง |
|---|---|---|---|---|---|
| 1 | 0: 1.261 | Lazarus-3.99, FPC-3.3.1 | Arnaud Bouchez | ใช้ mORMot2 , 32 เธรด | |
| 2 | 0: 1.950 | Lazarus-3.99, FPC-3.3.1 | o coddo | ใช้ SCL , 32 เธรด | |
| 3 | 0: 2.101 | Lazarus-3.99, FPC-3.3.1 | Hatem Georges | ใช้ mORMot2 , 32 เธรด | |
| 4 | 0: 5.248 | Lazarus-3.99, FPC-3.3.1 | Hartmut Grosser | ใช้ 32 เธรด | |
| 5 | 0: 7.363 | Lazarus-3.99, FPC-3.3.1 | เบนิโตแวนเดอร์แซนเดอร์ | ใช้ 32 เธรด | |
| 6 | 0: 9.627 | Lazarus-3.99, FPC-3.3.1 | G Klark | ใช้ 32 เธรด | |
| 7 | 0: 13.321 | Lazarus-3.99, FPC-3.3.1 | SzékelyBalázs | ใช้ 32 เธรด | |
| 8 | 0: 18.062 | Lazarus-3.99, FPC-3.3.1 | Lurendrejer Aksen | ใช้ 32 เธรด | |
| 9 | 1: 9.354 | Lazarus-3.99, FPC-3.3.1 | ริชาร์ดลอว์สัน | ใช้ 1 เธรด | |
| 10 | 2: 24.787 | Lazarus-3.99, FPC-3.3.1 | Iwan Kelaiah | ใช้ 1 เธรด | |
| 11 | 6: 2.343 | Delphi 12.1 | Brian Fire | ใช้ 8 เธรด | |
| 12 | 6: 53.788 | Delphi 12.1 | David Cornelius | ใช้ 1 เธรด | |
| 13 | 8: 37.975 | Delphi 12.1 | Daniel Töpfl | ใช้ 1 เธรด |
บันทึก
หลังจากการทดสอบบางอย่างดำเนินการโดย @paweld มันก็ไม่สมเหตุสมผลที่จะมีการรัน
HDDฉันได้ลบสิ่งนั้นออกจากผลลัพธ์
คู่แข่งแต่ละคนจะรัน 10 ครั้งติดต่อกันสำหรับทั้ง SSD และ HDD โดยใช้ hyperfine ในขณะที่ใช้เวลา
ค่าเฉลี่ยของการรัน 10 ครั้งเป็นผลลัพธ์สำหรับคู่แข่งนั้นและจะถูกเพิ่มลงในตารางผลลัพธ์ด้านบน
ค่าขั้นต่ำและสูงสุดจะถูกยกเลิกและค่าที่เหลืออีก 8 ค่าจะถูกใช้เพื่อคำนวณค่าเฉลี่ย
ไฟล์ measurements.txt ที่เหมือนกัน. txt ใช้สำหรับการประเมินผู้เข้าแข่งขันทั้งหมด
สิ่งนี้กำลังดำเนินการเพื่อสิทธิในการคุยโม้เท่านั้นและความสนุกของความท้าทายดังกล่าว
ถาม: ฉันสามารถคัดลอกรหัสจากการส่งอื่น ๆ ได้หรือไม่?
ตอบ: ใช่คุณทำได้ จุดสนใจหลักของความท้าทายคือการเรียนรู้สิ่งใหม่ ๆ มากกว่า "ชนะ" เมื่อคุณทำเช่นนั้นโปรดให้เครดิตกับการส่งแหล่งที่เกี่ยวข้อง โปรดอย่าส่งรายการอื่น ๆ อีกครั้งโดยไม่มีการปรับปรุงเล็กน้อยหรือเพียงเล็กน้อย
ถาม: การเข้ารหัสของไฟล์ txt.txt คืออะไร?
ตอบ: ไฟล์ถูกเข้ารหัสด้วย UTF-8
ถาม: ระบบปฏิบัติการใดที่ใช้สำหรับการประเมินผล?
A: Ubuntu 23.10 64b
ฉันอยากจะขอบคุณ @paweld ที่พาเราจากความพยายามที่น่าสังเวช 20m ของฉันไปจนถึง ~ 25s ที่ยิ่งใหญ่ตีสคริปต์ Python ประมาณ 4 นาทีครึ่ง
ฉันอยากจะขอบคุณ @mobius ที่สละเวลาในการจัดหาเครื่องกำเนิดไฟฟ้า Delphi
ฉันอยากจะขอบคุณ @DTPFL สำหรับงานที่มีค่าของเขาในการบำรุงรักษาไฟล์ README.md ให้ทันสมัยกับทุกสิ่ง
ฉันขอขอบคุณSzékelyBalázsที่ให้แพทช์มากมายเพื่อให้ทุกอย่างสอดคล้องกับความท้าทายดั้งเดิม
ฉันอยากจะขอบคุณ @corneliusdavid ที่ให้ข้อมูลบางอย่างไฟล์หนึ่งครั้งและทำให้สิ่งที่ชัดเจนและชัดเจนยิ่งขึ้น
ฉันอยากจะขอบคุณ Mr. Pack Man หรือที่รู้จักกันในชื่อสำหรับการล้างหมอกรอบ ๆ ปัญหาการปัดเศษ
ฉันอยากจะขอบคุณจอร์ชสที่ให้บริการพื้นฐานของ Delphi
ที่เก็บต้นฉบับ: https://github.com/gunnarmorling/1brc
ฉันค้นพบเกี่ยวกับเรื่องนี้โดยดูวิดีโอนี้เกี่ยวกับความพยายามในการเดินทาง: https://www.youtube.com/watch?v=cyng524s-ma
โพสต์บล็อกในคำถาม: https://www.bytesizego.com/blog/one-billion-row-challenge-go
ฐานรหัสนี้มีอยู่ภายใต้ใบอนุญาต MIT
ยอดเยี่ยมซึ่งกันและกัน!
มากกว่าการชนะจุดประสงค์ของความท้าทายนี้คือการมีความสนุกสนานและเรียนรู้สิ่งใหม่ ๆ
