Bitmap indexes in Go: ស្វែងរកក្នុងល្បឿនព្រៃ

ការណែនាំ

ខ្ញុំបានផ្ដល់របាយការណ៍នេះជាភាសាអង់គ្លេសនៅក្នុងសន្និសីទ GopherCon Russia 2019 នៅទីក្រុងមូស្គូ និងជាភាសារុស្សីនៅឯកិច្ចប្រជុំមួយនៅ Nizhny Novgorod ។ យើងកំពុងនិយាយអំពីសន្ទស្សន៍ផែនទី - ធម្មតាតិចជាង B-tree ប៉ុន្តែមិនគួរឱ្យចាប់អារម្មណ៍តិចជាងនេះទេ។ ការចែករំលែក ការថត សុន្ទរកថានៅក្នុងសន្និសីទជាភាសាអង់គ្លេស និងប្រតិចារឹកអត្ថបទជាភាសារុស្សី។

យើងនឹងពិនិត្យមើលថាតើលិបិក្រមផែនទីដំណើរការដោយរបៀបណា នៅពេលដែលវាប្រសើរជាង នៅពេលដែលវាអាក្រក់ជាងសន្ទស្សន៍ផ្សេងទៀត ហើយក្នុងករណីណាដែលវាលឿនជាងពួកវាខ្លាំង។ សូមមើល DBMSs ដ៏ពេញនិយមមួយណាដែលមានលិបិក្រមផែនទីប៊ីតរួចហើយ។ តោះព្យាយាមសរសេររបស់យើងនៅក្នុង Go ។ ហើយ "សម្រាប់បង្អែម" យើងនឹងប្រើបណ្ណាល័យដែលត្រៀមរួចជាស្រេចដើម្បីបង្កើតមូលដ្ឋានទិន្នន័យឯកទេសលឿនរហ័សផ្ទាល់ខ្លួនរបស់យើង។

ខ្ញុំពិតជាសង្ឃឹមថាស្នាដៃរបស់ខ្ញុំនឹងមានប្រយោជន៍ និងគួរឱ្យចាប់អារម្មណ៍សម្រាប់អ្នក។ ទៅ!

សេចក្តីណែនាំ

http://bit.ly/bitmapindexes
https://github.com/mkevac/gopherconrussia2019

សួស្តី​អ្នក​ទាំងអស់គ្នា! ម៉ោងប្រាំមួយល្ងាច ហើយយើងទាំងអស់គ្នានឿយហត់ណាស់។ ពេលវេលាដ៏ល្អដើម្បីនិយាយអំពីទ្រឹស្ដីសន្ទស្សន៍មូលដ្ឋានទិន្នន័យគួរឱ្យធុញមែនទេ? កុំបារម្ភ ខ្ញុំនឹងមានកូដប្រភពពីរបីជួរនៅទីនេះ និងទីនោះ។ 🙂

រឿងកំប្លែងទាំងអស់ក្រៅពីនេះ របាយការណ៍គឺពោរពេញដោយព័ត៌មាន ហើយយើងមិនមានពេលច្រើនទេ។ ដូច្នេះសូមចាប់ផ្តើម។

ថ្ងៃនេះខ្ញុំនឹងនិយាយអំពីរឿងដូចខាងក្រោមៈ

• តើអ្វីទៅជាសន្ទស្សន៍;
• អ្វី​ទៅ​ជា​សន្ទស្សន៍​ផែនទី;
• កន្លែងដែលវាត្រូវបានគេប្រើ និងកន្លែងដែលវាមិនត្រូវបានប្រើ និងហេតុអ្វី;
• ការអនុវត្តសាមញ្ញនៅក្នុង Go និងការតស៊ូតិចតួចជាមួយអ្នកចងក្រង;
• សាមញ្ញតិចជាងបន្តិច ប៉ុន្តែការអនុវត្តប្រកបដោយផលិតភាពច្រើននៅក្នុង Go assembler;
• "បញ្ហា" នៃសន្ទស្សន៍ផែនទីប៊ីត;
• ការអនុវត្តដែលមានស្រាប់។

ដូច្នេះតើសន្ទស្សន៍គឺជាអ្វី?

សន្ទស្សន៍គឺជារចនាសម្ព័ន្ធទិន្នន័យដាច់ដោយឡែកដែលយើងរក្សា និងធ្វើបច្ចុប្បន្នភាពបន្ថែមលើទិន្នន័យចម្បង។ វាត្រូវបានប្រើដើម្បីបង្កើនល្បឿនការស្វែងរក។ ដោយគ្មានលិបិក្រម ការស្វែងរកនឹងតម្រូវឱ្យឆ្លងកាត់ទិន្នន័យទាំងស្រុង (ដំណើរការហៅថាការស្កេនពេញលេញ) ហើយដំណើរការនេះមានភាពស្មុគស្មាញនៃក្បួនដោះស្រាយលីនេអ៊ែរ។ ប៉ុន្តែមូលដ្ឋានទិន្នន័យជាធម្មតាផ្ទុកទិន្នន័យយ៉ាងច្រើន ហើយភាពស្មុគស្មាញលីនេអ៊ែរគឺយឺតពេក។ តាមឧត្ដមគតិ យើងនឹងទទួលបានលោការីត ឬថេរមួយ។

នេះគឺជាប្រធានបទដ៏ស្មុគ្រស្មាញ ពោរពេញទៅដោយ subtleties និងការដោះដូរ ប៉ុន្តែបន្ទាប់ពីសម្លឹងមើលការវិវឌ្ឍន៍ និងការស្រាវជ្រាវជាច្រើនទស្សវត្សរ៍នៃមូលដ្ឋានទិន្នន័យ ខ្ញុំមានឆន្ទៈក្នុងការនិយាយថាមានវិធីសាស្រ្តប្រើប្រាស់យ៉ាងទូលំទូលាយមួយចំនួនដើម្បីបង្កើតលិបិក្រមមូលដ្ឋានទិន្នន័យ។

វិធីសាស្រ្តដំបូងគឺកាត់បន្ថយលំហស្វែងរកតាមឋានានុក្រម ដោយបែងចែកទំហំស្វែងរកទៅជាផ្នែកតូចៗ។

ជាធម្មតាយើងធ្វើបែបនេះដោយប្រើប្រភេទដើមឈើផ្សេងៗ។ ឧទាហរណ៍មួយអាចជាប្រអប់ធំនៃសម្ភារៈនៅក្នុងទូរបស់អ្នកដែលមានប្រអប់តូចៗនៃសម្ភារៈដែលបែងចែកទៅជាប្រធានបទផ្សេងៗគ្នា។ ប្រសិនបើអ្នកត្រូវការសម្ភារៈ អ្នកប្រហែលជាស្វែងរកពួកវានៅក្នុងប្រអប់ដែលនិយាយថា "សម្ភារៈ" ជាជាងមួយដែលនិយាយថា "ខូគី" មែនទេ?

វិធីសាស្រ្តទីពីរគឺជ្រើសរើសធាតុដែលចង់បានភ្លាមៗឬក្រុមនៃធាតុ។ យើង​ធ្វើ​វា​ក្នុង​ផែនទី​សញ្ញា ឬ​សន្ទស្សន៍​បញ្ច្រាស។ ការប្រើប្រាស់ផែនទី hash គឺស្រដៀងគ្នាទៅនឹងឧទាហរណ៍មុន ប៉ុន្តែជំនួសឱ្យប្រអប់មួយ អ្នកមានប្រអប់តូចៗនៃធាតុចុងក្រោយនៅក្នុងទូរបស់អ្នក។

វិធីសាស្រ្តទីបីគឺដើម្បីលុបបំបាត់តម្រូវការសម្រាប់ការស្វែងរក។ យើងធ្វើវាដោយប្រើតម្រង Bloom ឬតម្រង cuckoo ។ អ្នកទីមួយផ្តល់ចម្លើយភ្លាមៗ ដោយជួយសង្រ្គោះអ្នកពីការស្វែងរក។

វិធីសាស្រ្តចុងក្រោយគឺប្រើប្រាស់ថាមពលពេញលេញដែលផ្នែករឹងទំនើបផ្តល់ឱ្យយើង។ នេះ​ជា​អ្វី​ដែល​យើង​ធ្វើ​ក្នុង​លិបិក្រម​ផែនទី​ប៊ីត។ បាទ/ចាស ពេលប្រើពួកវា ជួនកាលយើងត្រូវឆ្លងកាត់លិបិក្រមទាំងមូល ប៉ុន្តែយើងធ្វើវាយ៉ាងមានប្រសិទ្ធភាពខ្ពស់។

ដូចដែលខ្ញុំបាននិយាយ ប្រធានបទនៃលិបិក្រមមូលដ្ឋានទិន្នន័យគឺធំធេង និងពោរពេញទៅដោយការសម្របសម្រួល។ នេះមានន័យថា ពេលខ្លះយើងអាចប្រើវិធីសាស្រ្តជាច្រើនក្នុងពេលតែមួយ៖ ប្រសិនបើយើងត្រូវការបង្កើនល្បឿនការស្វែងរកកាន់តែច្រើន ឬប្រសិនបើយើងត្រូវការគ្របដណ្តប់គ្រប់ប្រភេទការស្វែងរកដែលអាចធ្វើបាន។

ថ្ងៃនេះខ្ញុំនឹងនិយាយអំពីវិធីសាស្រ្តដែលគេស្គាល់តិចបំផុតនៃទាំងនេះ - សន្ទស្សន៍ផែនទីប៊ីត។

តើ​ខ្ញុំ​ជា​នរណា​ដើម្បី​និយាយ​លើ​ប្រធានបទ​នេះ?

ខ្ញុំធ្វើការជាអ្នកដឹកនាំក្រុមនៅ Badoo (ប្រហែលជាអ្នកស្គាល់ផលិតផលផ្សេងទៀតរបស់យើង Bumble)។ យើងមានអ្នកប្រើប្រាស់ច្រើនជាង 400 លាននាក់នៅជុំវិញពិភពលោក និងមុខងារជាច្រើនដែលជ្រើសរើសការផ្គូផ្គងដ៏ល្អបំផុតសម្រាប់ពួកគេ។ យើងធ្វើដូចនេះដោយប្រើសេវាកម្មផ្ទាល់ខ្លួន រួមទាំងសន្ទស្សន៍ផែនទីប៊ីត។

ដូច្នេះតើសន្ទស្សន៍ផែនទីប៊ីតគឺជាអ្វី?

Bitmap indexes ដូចដែលឈ្មោះបានបង្ហាញ ប្រើ bitmap ឬ bitsets ដើម្បីអនុវត្តលិបិក្រមស្វែងរក។ តាមទិដ្ឋភាពភ្នែករបស់បក្សី លិបិក្រមនេះមានរូបភាពមួយ ឬច្រើនដែលតំណាងឱ្យអង្គភាពណាមួយ (ដូចជាមនុស្ស) និងលក្ខណៈសម្បត្តិ ឬប៉ារ៉ាម៉ែត្ររបស់វា (អាយុ ពណ៌ភ្នែក។ល។) និងក្បួនដោះស្រាយដោយប្រើប្រតិបត្តិការប៊ីត (AND, OR, NOT ) ដើម្បីឆ្លើយសំណួរស្វែងរក។

យើងត្រូវបានគេប្រាប់ថា សន្ទស្សន៍ផែនទីប៊ីតគឺសមបំផុត និងមានប្រសិទ្ធភាពបំផុតសម្រាប់ករណីដែលមានការស្វែងរកដែលរួមបញ្ចូលគ្នានូវសំណួរនៅទូទាំងជួរតម្លៃទាបជាច្រើន (គិតថា "ពណ៌ភ្នែក" ឬ "ស្ថានភាពអាពាហ៍ពិពាហ៍" ធៀបនឹងអ្វីមួយដូចជា "ចម្ងាយពីកណ្តាលទីក្រុង")។ ប៉ុន្តែ​ខ្ញុំ​នឹង​បង្ហាញ​ពេល​ក្រោយ​ថា​ពួក​វា​ដំណើរការ​ល្អ​សម្រាប់​ជួរ​ឈរ cardinality ខ្ពស់​ផង​ដែរ។

សូមក្រឡេកមើលឧទាហរណ៍សាមញ្ញបំផុតនៃសន្ទស្សន៍ផែនទីប៊ីត។

ស្រមៃថាយើងមានបញ្ជីភោជនីយដ្ឋាននៅទីក្រុងម៉ូស្គូដែលមានទ្រព្យសម្បត្តិគោលពីរដូចនេះ:

• នៅជិតរថភ្លើងក្រោមដី;
• មានកន្លែងចតរថយន្តឯកជន;
• មាន veranda (មានរាបស្មើរ);
• អ្នកអាចកក់តុ (ទទួលយកការកក់ទុក);
• សមរម្យសម្រាប់អ្នកបួស (vegan friendly);
• ថ្លៃ (ថ្លៃ) ។

ចូរផ្តល់ឱ្យភោជនីយដ្ឋាននីមួយៗនូវលេខលំដាប់ដែលចាប់ផ្តើមពី 0 ហើយបែងចែកអង្គចងចាំសម្រាប់ 6 bitmap (មួយសម្រាប់លក្ខណៈនីមួយៗ)។ បន្ទាប់​មក យើង​នឹង​បញ្ចូល​ផែនទី​ប៊ីត​ទាំងនេះ អាស្រ័យ​លើ​ថាតើ​ភោជនីយដ្ឋាន​មាន​ទ្រព្យសម្បត្តិ​នេះ​ឬ​អត់។ ប្រសិនបើភោជនីយដ្ឋាន 4 មាន veranda នោះលេខ 4 នៅក្នុងផែនទី "មាន veranda" នឹងត្រូវបានកំណត់ទៅ 1 (ប្រសិនបើមិនមាន veranda បន្ទាប់មកទៅ 0) ។

ឥឡូវនេះយើងមានលិបិក្រមរូបភាពសាមញ្ញបំផុតដែលអាចធ្វើទៅបាន ហើយយើងអាចប្រើវាដើម្បីឆ្លើយសំណួរដូចជា៖

• “បង្ហាញខ្ញុំនូវភោជនីយដ្ឋានដែលស័ក្តិសមសម្រាប់បួស”;
• "បង្ហាញខ្ញុំនូវភោជនីយដ្ឋានដែលមានតំលៃថោកជាមួយ veranda ដែលអ្នកអាចកក់តុបាន។"

យ៉ាងម៉េច? តោះមើល។ សំណើដំបូងគឺសាមញ្ញណាស់។ អ្វី​ដែល​យើង​ត្រូវ​ធ្វើ​គឺ​យក​ផែនទី "អ្នក​បួស​ជា​មិត្ត" ហើយ​ប្រែក្លាយ​វា​ទៅ​ជា​បញ្ជី​ភោជនីយដ្ឋាន​ដែល​ប៊ីត​ត្រូវ​បាន​លាតត្រដាង។


សំណើទីពីរគឺស្មុគស្មាញបន្តិច។ យើងត្រូវប្រើ NOT bitmap នៅលើផែនទី "ថ្លៃ" ដើម្បីទទួលបានបញ្ជីភោជនីយដ្ឋានដែលមានតំលៃថោក បន្ទាប់មក និងវាជាមួយនឹង "តើខ្ញុំអាចកក់តុបាន" និងលទ្ធផលជាមួយនឹងផែនទី "មាន veranda" ។ ផែនទី​ប៊ីត​លទ្ធផល​នឹង​មាន​បញ្ជី​គ្រឹះស្ថាន​ដែល​បំពេញ​តាម​លក្ខណៈ​វិនិច្ឆ័យ​របស់​យើង​ទាំងអស់។ ក្នុងឧទាហរណ៍នេះ នេះគ្រាន់តែជាភោជនីយដ្ឋាន Yunost ប៉ុណ្ណោះ។


មានទ្រឹស្តីជាច្រើនពាក់ព័ន្ធ ប៉ុន្តែកុំបារម្ភ យើងនឹងឃើញកូដក្នុងពេលឆាប់ៗនេះ។

តើសន្ទស្សន៍ផែនទីប៊ីតត្រូវបានប្រើនៅឯណា?

ប្រសិនបើអ្នកធ្វើលិបិក្រម Google bitmap នោះ 90% នៃចម្លើយនឹងទាក់ទងទៅនឹង Oracle DB តាមមធ្យោបាយមួយឬផ្សេងទៀត។ ប៉ុន្តែ DBMSs ផ្សេងទៀតប្រហែលជាគាំទ្ររឿងត្រជាក់បែបនេះមែនទេ? មិន​ប្រាកដ​ទេ។

ចូរយើងឆ្លងកាត់បញ្ជីជនសង្ស័យសំខាន់ៗ។

MySQL មិន​ទាន់​គាំទ្រ​លិបិក្រម​ផែនទី​ទេ ប៉ុន្តែ​មាន​សំណើ​ស្នើ​បន្ថែម​ជម្រើស​នេះ (https://dev.mysql.com/worklog/task/?id=1524).

PostgreSQL មិន​គាំទ្រ​លិបិក្រម​ផែនទី​ប៊ីត​ទេ ប៉ុន្តែ​ប្រើ​ផែនទី​ប៊ីត​សាមញ្ញ និង​ប្រតិបត្តិការ​ប៊ីត ដើម្បី​បញ្ចូល​លទ្ធផល​ស្វែងរក​តាម​លិបិក្រម​ផ្សេង​ទៀត។

Tarantool មានលិបិក្រម bitset និងគាំទ្រការស្វែងរកសាមញ្ញនៅលើពួកវា។

Redis មាន bitfields សាមញ្ញ (https://redis.io/commands/bitfield) ដោយគ្មានសមត្ថភាពក្នុងការស្វែងរកពួកគេ។

MongoDB មិន​ទាន់​គាំទ្រ​លិបិក្រម​ផែនទី​ប៊ីត​នៅ​ឡើយ​ទេ ប៉ុន្តែ​ក៏​មាន​សំណើ​ដែល​ស្នើ​ថា​ជម្រើស​នេះ​ត្រូវ​បាន​បន្ថែម https://jira.mongodb.org/browse/SERVER-1723

Elasticsearch ប្រើផែនទីប៊ីតនៅខាងក្នុង (https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmap).

• ប៉ុន្តែអ្នកជិតខាងថ្មីបានបង្ហាញខ្លួននៅក្នុងផ្ទះរបស់យើង: Pilosa ។ នេះគឺជាមូលដ្ឋានទិន្នន័យថ្មីដែលមិនទាក់ទងគ្នាដែលបានសរសេរនៅក្នុង Go ។ វា​មាន​តែ​លិបិក្រម​ផែនទី​ប៊ីត​ប៉ុណ្ណោះ ហើយ​ផ្អែក​លើ​អ្វី​គ្រប់​យ៉ាង​នៅ​លើ​ពួកវា។ យើងនឹងនិយាយអំពីវាបន្តិចក្រោយមក។

ការអនុវត្តនៅក្នុង Go

ប៉ុន្តែ​ហេតុអ្វី​បាន​ជា​លិបិក្រម​ផែនទី​ប៊ីត​កម្រ​ប្រើ​ម្ល៉េះ? មុននឹងឆ្លើយសំណួរនេះ ខ្ញុំចង់បង្ហាញអ្នកពីរបៀបអនុវត្តលិបិក្រមរូបភាពសាមញ្ញបំផុតនៅក្នុង Go ។

ផែនទីប៊ីតគឺគ្រាន់តែជាបំណែកនៃទិន្នន័យប៉ុណ្ណោះ។ នៅក្នុង Go សូមប្រើប៊ីតចំណិតសម្រាប់ការនេះ។

យើង​មាន​ផែនទី​ប៊ីត​មួយ​សម្រាប់​លក្ខណៈ​ភោជនីយដ្ឋាន​មួយ ហើយ​ប៊ីត​នីមួយៗ​ក្នុង​ផែនទី​ប៊ីត​បង្ហាញ​ថា​តើ​ភោជនីយដ្ឋាន​ជាក់លាក់​មាន​ទ្រព្យសម្បត្តិ​នេះ​ឬ​អត់។

យើងនឹងត្រូវការមុខងារជំនួយពីរ។ មួយនឹងត្រូវបានប្រើដើម្បីបំពេញរូបភាពផែនទីរបស់យើងជាមួយនឹងទិន្នន័យចៃដន្យ។ ចៃដន្យ ប៉ុន្តែជាមួយនឹងប្រូបាប៊ីលីតេជាក់លាក់ដែលភោជនីយដ្ឋានមានទ្រព្យសម្បត្តិនីមួយៗ។ ជាឧទាហរណ៍ ខ្ញុំជឿថាមានភោជនីយដ្ឋានតិចតួចណាស់នៅទីក្រុងមូស្គូ ដែលអ្នកមិនអាចកក់តុបាន ហើយវាហាក់ដូចជាខ្ញុំថាប្រហែល 20% នៃគ្រឹះស្ថានគឺសមរម្យសម្រាប់អ្នកបួស។

មុខងារទីពីរនឹងបំប្លែងរូបភាពផែនទីទៅជាបញ្ជីភោជនីយដ្ឋាន។


ដើម្បីឆ្លើយសំណួរ "បង្ហាញខ្ញុំនូវភោជនីយដ្ឋានដែលមានតម្លៃថោកដែលមានទីធ្លា និងអាចធ្វើការកក់ទុកបាន" យើងត្រូវការប្រតិបត្តិការប៊ីតពីរ៖ មិនមែន និង AND ។

យើង​អាច​សម្រួល​កូដ​របស់​យើង​បន្តិច​ដោយ​ប្រើ​ប្រតិបត្តិករ​ដែល​ស្មុគស្មាញ​ជាង​នេះ​ហើយ​មិន​ប្រើ។

យើងមានមុខងារសម្រាប់ប្រតិបត្តិការនីមួយៗ។ ពួកគេទាំងពីរឆ្លងកាត់ចំណិតយកធាតុដែលត្រូវគ្នាពីគ្នាបញ្ចូលគ្នាជាមួយប្រតិបត្តិការបន្តិចហើយដាក់លទ្ធផលចូលទៅក្នុងចំណិតលទ្ធផល។

ហើយឥឡូវនេះ យើងអាចប្រើផែនទី និងមុខងាររបស់យើង ដើម្បីឆ្លើយសំណួរស្វែងរក។

ការអនុវត្តគឺមិនខ្ពស់នោះទេ ទោះបីជាមុខងារគឺសាមញ្ញណាស់ ហើយយើងសន្សំប្រាក់បានច្រើនដោយការមិនត្រលប់មកវិញនូវលទ្ធផលថ្មីរាល់ពេលដែលមុខងារត្រូវបានហៅ។

បន្ទាប់ពីធ្វើ profileing បន្តិចជាមួយ pprof ខ្ញុំបានកត់សម្គាល់ឃើញថា Go compiler បាត់ការបង្កើនប្រសិទ្ធភាពដ៏សាមញ្ញ ប៉ុន្តែសំខាន់ខ្លាំងណាស់៖ មុខងារ inlining ។

ការពិតគឺថាកម្មវិធីចងក្រង Go មានការភ័យខ្លាចយ៉ាងខ្លាំងចំពោះរង្វិលជុំដែលឆ្លងកាត់បំណែក ហើយបដិសេធយ៉ាងដាច់អហង្ការចំពោះមុខងារក្នុងជួរដែលមានរង្វិលជុំបែបនេះ។

ប៉ុន្តែ​ខ្ញុំ​មិន​ខ្លាច​ទេ ហើយ​ខ្ញុំ​អាច​បោក​អ្នក​ចងក្រង​បាន​ដោយ​ការ​ប្រើ goto ជំនួស​ឱ្យ​ការ​រង្វិលជុំ​ដូច​ក្នុង​ថ្ងៃ​ល្អ​។

ហើយដូចដែលអ្នកបានឃើញ ឥឡូវនេះអ្នកចងក្រងនឹងបំពេញមុខងាររបស់យើងដោយរីករាយ! ជាលទ្ធផល យើងសន្សំបានប្រហែល 2 មីក្រូវិនាទី។ មិនអាក្រក់​ទេ!

ការស្ទះទីពីរគឺងាយស្រួលក្នុងការមើលថាតើអ្នកមើលយ៉ាងដិតដល់នូវលទ្ធផលនៃការដំឡើង។ អ្នកចងក្រងបានបន្ថែមការពិនិត្យមើលព្រំដែនផ្នែកខាងស្ដាំនៅខាងក្នុងរង្វិលជុំក្តៅបំផុតរបស់យើង។ ការពិតគឺថា Go គឺជាភាសាដែលមានសុវត្ថិភាព អ្នកចងក្រងខ្លាចថាអំណះអំណាងបីរបស់ខ្ញុំ (បីបំណែក) មានទំហំខុសៗគ្នា។ បន្ទាប់ពីបានទាំងអស់, បន្ទាប់មកនឹងមានលទ្ធភាពទ្រឹស្តីនៃការកើតឡើងនៃអ្វីដែលគេហៅថា buffer overflow ។

សូមធានាដល់អ្នកចងក្រងឡើងវិញដោយបង្ហាញវាថាចំណិតទាំងអស់មានទំហំដូចគ្នា។ យើងអាចធ្វើដូចនេះបានដោយបន្ថែមការត្រួតពិនិត្យសាមញ្ញមួយនៅដើមមុខងាររបស់យើង។

ដោយឃើញដូចនេះ អ្នកចងក្រងរីករាយនឹងរំលងការត្រួតពិនិត្យ ហើយយើងសន្សំបាន 500 ណាណូវិនាទីទៀត។

ចង្រ្កានធំ

ជាការប្រសើរណាស់ យើងបានគ្រប់គ្រងការអនុវត្តមួយចំនួនចេញពីការអនុវត្តដ៏សាមញ្ញរបស់យើង ប៉ុន្តែលទ្ធផលនេះពិតជាអាក្រក់ជាងលទ្ធភាពដែលអាចធ្វើទៅបានជាមួយផ្នែករឹងបច្ចុប្បន្ន។

អ្វី​ដែល​យើង​ធ្វើ​គឺ​ប្រតិបត្តិការ​ប៊ីត​មូលដ្ឋាន ហើយ​ប្រព័ន្ធ​ដំណើរការ​របស់​យើង​ដំណើរការ​វា​យ៉ាង​មាន​ប្រសិទ្ធភាព។ ប៉ុន្តែជាអកុសល យើង "ចិញ្ចឹម" ដំណើរការរបស់យើងជាមួយនឹងផ្នែកតូចៗនៃការងារ។ មុខងាររបស់យើងធ្វើប្រតិបត្តិការលើមូលដ្ឋានបៃបៃបៃ។ យើង​អាច​កែប្រែ​កូដ​របស់​យើង​យ៉ាង​ងាយ​ស្រួល​ដើម្បី​ធ្វើ​ការ​ជាមួយ​កំណាត់ 8-byte ដោយ​ប្រើ UInt64 slices ។

ដូចដែលអ្នកអាចមើលឃើញ ការផ្លាស់ប្តូរតូចមួយនេះបានបង្កើនល្បឿនកម្មវិធីរបស់យើងប្រាំបីដងដោយបង្កើនទំហំបាច់ចំនួនប្រាំបីដង។ ការទទួលបានអាចនិយាយបានថាជាលីនេអ៊ែរ។

ការអនុវត្តនៅក្នុងឧបករណ៍ដំឡើង

ប៉ុន្តែនេះមិនមែនជាទីបញ្ចប់ទេ។ ឧបករណ៍ដំណើរការរបស់យើងអាចធ្វើការជាមួយកំណាត់ 16, 32 និងសូម្បីតែ 64 បៃ។ ប្រតិបត្តិការ "ទូលំទូលាយ" បែបនេះត្រូវបានគេហៅថា single instruction multiple data (SIMD; one instruction, many data) ហើយដំណើរការនៃការបំប្លែងកូដដូច្នេះវាប្រើប្រតិបត្តិការបែបនេះត្រូវបានគេហៅថា vectorization ។

ជាអកុសល កម្មវិធីចងក្រង Go គឺនៅឆ្ងាយពីភាពល្អឥតខ្ចោះនៃវ៉ិចទ័រ។ បច្ចុប្បន្ននេះ មធ្យោបាយតែមួយគត់ដើម្បី vectorize កូដ Go គឺត្រូវយក និងដាក់ប្រតិបត្តិការទាំងនេះដោយដៃដោយប្រើ Go assembler ។

Go assembler គឺជាសត្វចម្លែក។ អ្នកប្រហែលជាដឹងហើយថា ភាសាជួបប្រជុំគ្នា គឺជាអ្វីមួយដែលត្រូវបានភ្ជាប់យ៉ាងខ្លាំងទៅនឹងស្ថាបត្យកម្មនៃកុំព្យូទ័រដែលអ្នកកំពុងសរសេរ ប៉ុន្តែនោះមិនមែនជាករណីនៅក្នុង Go នោះទេ។ កម្មវិធីដំឡើង Go គឺដូចជា IRL (ភាសាតំណាងកម្រិតមធ្យម) ឬភាសាកម្រិតមធ្យម៖ វាជាវេទិកាឯករាជ្យ។ Rob Pike បានផ្តល់ការសម្តែងដ៏អស្ចារ្យ របាយការណ៍ លើប្រធានបទនេះកាលពីប៉ុន្មានឆ្នាំមុននៅ GopherCon ក្នុងទីក្រុង Denver ។

លើសពីនេះ Go ប្រើទម្រង់ Plan 9 មិនធម្មតា ដែលខុសពីទម្រង់ AT&T និង Intel ដែលទទួលយកជាទូទៅ។

វាមានសុវត្ថិភាពក្នុងការនិយាយថាការសរសេរ Go assembler ដោយដៃមិនមែនជាការសប្បាយបំផុតនោះទេ។

ប៉ុន្តែជាសំណាងល្អ មានឧបករណ៍កម្រិតខ្ពស់ចំនួនពីរដែលជួយយើងក្នុងការសរសេរ Go assembler: PeachPy និង avo ។ ឧបករណ៍ប្រើប្រាស់ទាំងពីរបង្កើត Go assembler ពីកូដកម្រិតខ្ពស់ដែលសរសេរក្នុង Python និង Go រៀងគ្នា។

ឧបករណ៍ប្រើប្រាស់ទាំងនេះជួយសម្រួលអ្វីៗដូចជាការចុះឈ្មោះការបែងចែក ការសរសេររង្វិលជុំ និងជាទូទៅធ្វើឱ្យដំណើរការនៃការចូលទៅក្នុងពិភពនៃកម្មវិធីជួបប្រជុំគ្នានៅក្នុង Go ។

យើងនឹងប្រើ avo ដូច្នេះកម្មវិធីរបស់យើងនឹងក្លាយជាកម្មវិធី Go ធម្មតា។

នេះគឺជាអ្វីដែលឧទាហរណ៍សាមញ្ញបំផុតនៃកម្មវិធី avo មើលទៅដូច។ យើង​មាន​អនុគមន៍ main() ដែល​កំណត់​ក្នុង​ខ្លួន​វា​នូវ​មុខងារ Add() អត្ថន័យ​នៃ​ការ​បន្ថែម​លេខ​ពីរ។ មានមុខងារជំនួយនៅទីនេះ ដើម្បីទទួលបានប៉ារ៉ាម៉ែត្រតាមឈ្មោះ និងទទួលបានការចុះឈ្មោះដំណើរការមួយដោយឥតគិតថ្លៃ និងសមរម្យ។ ប្រតិបត្តិការរបស់ខួរក្បាលនីមួយៗមានមុខងារដែលត្រូវគ្នានៅលើ avo ដូចដែលបានឃើញនៅក្នុង ADDQ ។ ទីបំផុតយើងឃើញមុខងារជំនួយសម្រាប់រក្សាទុកតម្លៃលទ្ធផល។

តាមរយៈការហៅទៅបង្កើត យើងនឹងដំណើរការកម្មវិធីនៅលើ avo ហើយជាលទ្ធផល ឯកសារពីរនឹងត្រូវបានបង្កើត៖

• add.s ជាមួយនឹងលេខកូដលទ្ធផលនៅក្នុង Go assembler;
• stub.go ជាមួយ​នឹង​បឋមកថា​មុខងារ​ដើម្បី​ភ្ជាប់​ពិភព​ទាំងពីរ៖ ទៅ និង​ដំឡើង។

ឥឡូវនេះយើងបានឃើញនូវអ្វីដែល avo ធ្វើ និងរបៀប សូមមើលមុខងាររបស់យើង។ ខ្ញុំបានអនុវត្តទាំងកំណែ scalar និង vector (SIMD) នៃមុខងារ។

សូមក្រឡេកមើលកំណែមាត្រដ្ឋានជាមុនសិន។

ដូចក្នុងឧទាហរណ៍មុន យើងកំពុងស្នើសុំការចុះឈ្មោះគោលបំណងទូទៅដោយឥតគិតថ្លៃ និងត្រឹមត្រូវ យើងមិនចាំបាច់គណនាអុហ្វសិត និងទំហំសម្រាប់អាគុយម៉ង់នោះទេ។ អាវ៉ូធ្វើអ្វីៗទាំងអស់នេះសម្រាប់យើង។

យើងធ្លាប់ប្រើស្លាក និង Goto (ឬលោត) ដើម្បីកែលម្អដំណើរការ និងបញ្ឆោតកម្មវិធី Go compiler ប៉ុន្តែឥឡូវនេះយើងកំពុងធ្វើវាតាំងពីដំបូង។ ចំណុចនោះគឺថា វដ្តគឺជាគំនិតកម្រិតខ្ពស់។ នៅក្នុងការជួបប្រជុំគ្នា យើងមានតែស្លាកសញ្ញា និងលោតប៉ុណ្ណោះ។

លេខកូដដែលនៅសល់គួរតែធ្លាប់ស្គាល់ និងអាចយល់បាន។ យើងធ្វើត្រាប់តាមរង្វិលជុំជាមួយស្លាក និងលោត យកទិន្នន័យតូចមួយពីចំណិតពីររបស់យើង ផ្សំពួកវាជាមួយប្រតិបត្តិការបន្តិច (ហើយមិនមែនក្នុងករណីនេះ) ហើយបន្ទាប់មកដាក់លទ្ធផលទៅក្នុងចំណិតលទ្ធផល។ ទាំងអស់។

នេះជាអ្វីដែលលេខកូដដំឡើងចុងក្រោយមើលទៅ។ យើងមិនចាំបាច់គណនាអុហ្វសិត និងទំហំ (បន្លិចជាពណ៌បៃតង) ឬតាមដានការចុះឈ្មោះដែលបានប្រើ (បន្លិចជាពណ៌ក្រហម)។

ប្រសិនបើយើងប្រៀបធៀបដំណើរការនៃការអនុវត្តភាសាជួបប្រជុំគ្នាជាមួយនឹងដំណើរការនៃការអនុវត្តល្អបំផុតនៅក្នុង Go យើងនឹងឃើញថាវាដូចគ្នា។ ហើយនេះត្រូវបានរំពឹងទុក។ យ៉ាងណាមិញ យើងមិនបានធ្វើអ្វីពិសេសនោះទេ យើងគ្រាន់តែផលិតឡើងវិញនូវអ្វីដែលអ្នកចងក្រង Go នឹងធ្វើ។

ជាអកុសល យើងមិនអាចបង្ខំអ្នកចងក្រងឱ្យបញ្ចូលមុខងាររបស់យើងដែលសរសេរជាភាសាជួបប្រជុំគ្នាបានទេ។ Go compiler បច្ចុប្បន្នមិនមានមុខងារបែបនេះទេ ទោះបីជាមានការស្នើសុំឱ្យបន្ថែមវាមួយរយៈក៏ដោយ។

នេះ​ជា​មូលហេតុ​ដែល​វា​មិន​អាច​ទទួល​បាន​អត្ថប្រយោជន៍​ណាមួយ​ពី​មុខងារ​តូច​ៗ​ក្នុង​ភាសា​ដំឡើង​ទេ។ យើងត្រូវសរសេរមុខងារធំៗ ឬប្រើកញ្ចប់គណិតវិទ្យា/ប៊ីតថ្មី ឬរំលងភាសាដំឡើង។

ឥឡូវនេះ សូមក្រឡេកមើលកំណែវ៉ិចទ័រនៃមុខងាររបស់យើង។

សម្រាប់ឧទាហរណ៍នេះ ខ្ញុំបានសម្រេចចិត្តប្រើ AVX2 ដូច្នេះយើងនឹងប្រើប្រតិបត្តិការដែលដំណើរការលើកំណាត់ 32 បៃ។ រចនាសម្ព័ននៃកូដគឺស្រដៀងទៅនឹងកំណែមាត្រដ្ឋាន៖ ការផ្ទុកប៉ារ៉ាម៉ែត្រ ស្នើសុំការចុះឈ្មោះចែករំលែកដោយឥតគិតថ្លៃ។ល។

ការច្នៃប្រឌិតមួយគឺថាប្រតិបត្តិការវ៉ិចទ័រកាន់តែទូលំទូលាយប្រើការចុះឈ្មោះធំទូលាយពិសេស។ នៅក្នុងករណីនៃកំណាត់ 32-byte ទាំងនេះគឺជាការចុះឈ្មោះដែលបុព្វបទដោយ Y. នេះជាមូលហេតុដែលអ្នកឃើញមុខងារ YMM() នៅក្នុងកូដ។ ប្រសិនបើខ្ញុំកំពុងប្រើ AVX-512 ជាមួយនឹងកំណាត់ 64 ប៊ីត នោះបុព្វបទនឹងជា Z ។

ការច្នៃប្រឌិតទីពីរគឺថា ខ្ញុំបានសម្រេចចិត្តប្រើការបង្កើនប្រសិទ្ធភាពមួយហៅថា loop unrolling ដែលមានន័យថាធ្វើប្រតិបត្តិការរង្វិលជុំចំនួនប្រាំបីដោយដៃ មុនពេលលោតទៅការចាប់ផ្តើមនៃរង្វិលជុំ។ ការបង្កើនប្រសិទ្ធភាពនេះកាត់បន្ថយចំនួនសាខានៅក្នុងកូដ ហើយត្រូវបានកំណត់ដោយចំនួននៃការចុះឈ្មោះឥតគិតថ្លៃដែលមាន។

ចុះយ៉ាងណាចំពោះការសម្តែង? នាង​ស្អាត​ណាស់! យើងសម្រេចបានការបង្កើនល្បឿនប្រហែល XNUMX ដងធៀបនឹងដំណោះស្រាយ Go ល្អបំផុត។ គួរអោយចាប់អារម្មណ៍មែនទេ?

ប៉ុន្តែសូម្បីតែការអនុវត្តនេះក៏អាចត្រូវបានពន្លឿនដោយប្រើ AVX-512, prefetching ឬ JIT (just-in-time compiler) សម្រាប់កម្មវិធីកំណត់ពេលសំណួរ។ ប៉ុន្តែនេះពិតជាប្រធានបទសម្រាប់របាយការណ៍ដាច់ដោយឡែកមួយ។

បញ្ហាជាមួយសន្ទស្សន៍ផែនទីប៊ីត

ឥឡូវនេះ យើងបានមើលរួចហើយនូវការអនុវត្តដ៏សាមញ្ញនៃលិបិក្រមផែនទីក្នុង Go និងផលិតផលដែលមានផលិតភាពច្រើនជាងមុននៅក្នុងភាសាជួបប្រជុំគ្នា ទីបំផុតសូមនិយាយអំពីមូលហេតុដែលលិបិក្រមផែនទីត្រូវបានប្រើប្រាស់កម្រណាស់។

ឯកសារចាស់ៗនិយាយអំពីបញ្ហាបីជាមួយសន្ទស្សន៍ផែនទី ប៉ុន្តែឯកសារថ្មីជាងនេះ ហើយខ្ញុំប្រកែកថាវាលែងពាក់ព័ន្ធទៀតហើយ។ យើង​នឹង​មិន​ចុះ​ជ្រៅ​ក្នុង​បញ្ហា​នីមួយៗ​នោះ​ទេ ប៉ុន្តែ​នឹង​មើល​ទៅ​លើ​បញ្ហា​ទាំង​នោះ​ដោយ​ស្រពិចស្រពិល។

បញ្ហានៃ cardinality ខ្ពស់។

ដូច្នេះ យើង​ត្រូវ​បាន​គេ​ប្រាប់​ថា​សន្ទស្សន៍​ផែនទី​ប៊ីត​គឺ​សមរម្យ​សម្រាប់​តែ​វាល​ដែល​មាន​កម្រិត​ទាប​ប៉ុណ្ណោះ ពោល​គឺ​តម្លៃ​តិច​តួច (ឧទាហរណ៍ ភេទ ឬ​ពណ៌​ភ្នែក) ហើយ​មូលហេតុ​គឺ​តំណាង​ធម្មតា​នៃ​វាល​បែប​នេះ (មួយ ប៊ីតក្នុងមួយតម្លៃ) នៅក្នុងករណីនៃ cardinality ខ្ពស់ វានឹងយកកន្លែងទំនេរច្រើនពេក ហើយលើសពីនេះទៅទៀត សន្ទស្សន៍ bitmap ទាំងនេះនឹងត្រូវបានបំពេញយ៉ាងលំបាក (កម្រណាស់) ។


ពេលខ្លះយើងអាចប្រើតំណាងផ្សេងគ្នា ដូចជាស្តង់ដារដែលយើងប្រើដើម្បីតំណាងឱ្យលេខ។ ប៉ុន្តែវាគឺជាការមកដល់នៃក្បួនដោះស្រាយការបង្ហាប់ដែលផ្លាស់ប្តូរអ្វីគ្រប់យ៉ាង។ ក្នុងរយៈពេលប៉ុន្មានទសវត្សរ៍កន្លងមកនេះ អ្នកវិទ្យាសាស្ត្រ និងអ្នកស្រាវជ្រាវបានបង្កើតនូវក្បួនដោះស្រាយការបង្ហាប់មួយចំនួនធំសម្រាប់ផែនទីប៊ីត។ អត្ថប្រយោជន៍ចម្បងរបស់ពួកគេគឺថា មិនចាំបាច់បង្រួមផែនទីប៊ីត ដើម្បីអនុវត្តប្រតិបត្តិការប៊ីតទេ យើងអាចអនុវត្តប្រតិបត្តិការប៊ីតដោយផ្ទាល់នៅលើផែនទីប៊ីតដែលបានបង្ហាប់។

ថ្មីៗនេះ វិធីសាស្រ្តកូនកាត់បានចាប់ផ្តើមលេចចេញ ដូចជាផែនទីប៊ីតដែលកំពុងគ្រហឹម។ ពួកគេក្នុងពេលដំណាលគ្នាប្រើតំណាងបីផ្សេងគ្នាសម្រាប់ផែនទីប៊ីត - ផែនទីប៊ីតខ្លួនឯង អារេ និងអ្វីដែលហៅថាដំណើរការប៊ីត - និងតុល្យភាពរវាងពួកវាដើម្បីបង្កើនប្រសិទ្ធភាព និងកាត់បន្ថយការប្រើប្រាស់អង្គចងចាំ។

អ្នកអាចស្វែងរកផែនទីប៊ីតដែលកំពុងគ្រហឹមនៅក្នុងកម្មវិធីពេញនិយមបំផុត។ មានការអនុវត្តមួយចំនួនធំរួចហើយសម្រាប់ភាសាកម្មវិធីជាច្រើន រួមទាំងការអនុវត្តច្រើនជាងបីសម្រាប់ Go ។

វិធីសាស្រ្តមួយផ្សេងទៀតដែលអាចជួយយើងដោះស្រាយជាមួយនឹង cardinality ខ្ពស់ត្រូវបានគេហៅថា binning ។ ស្រមៃថាអ្នកមានវាលដែលតំណាងឱ្យកម្ពស់របស់មនុស្ស។ កម្ពស់គឺជាលេខអណ្តែតទឹក ប៉ុន្តែមនុស្សយើងមិនគិតពីវានោះទេ។ សម្រាប់យើងមិនមានភាពខុសប្លែកគ្នារវាងកម្ពស់ 185,2 សង់ទីម៉ែត្រ និង 185,3 សង់ទីម៉ែត្រទេ។

វាប្រែថាយើងអាចដាក់តម្លៃស្រដៀងគ្នាទៅជាក្រុមក្នុងរង្វង់ 1 សង់ទីម៉ែត្រ។

ហើយប្រសិនបើយើងដឹងដែរថាមានមនុស្សតិចណាស់ដែលខ្លីជាង 50 សង់ទីម៉ែត្រ និងខ្ពស់ជាង 250 សង់ទីម៉ែត្រនោះ យើងអាចប្រែក្លាយវាលដែលមានអក្សរកាត់គ្មានដែនកំណត់ទៅជាវាលមួយដែលមានតម្លៃប្រហែល 200 ។

ជាការពិតណាស់ ប្រសិនបើចាំបាច់ យើងអាចធ្វើការត្រងបន្ថែមនៅពេលក្រោយ។

បញ្ហាកម្រិតបញ្ជូនខ្ពស់។

បញ្ហាបន្ទាប់ជាមួយសន្ទស្សន៍ផែនទីប៊ីតគឺថាការធ្វើបច្ចុប្បន្នភាពពួកវាអាចមានតម្លៃថ្លៃណាស់។

មូលដ្ឋានទិន្នន័យត្រូវតែអាចធ្វើបច្ចុប្បន្នភាពទិន្នន័យ ខណៈដែលសំណួររាប់រយផ្សេងទៀតកំពុងស្វែងរកទិន្នន័យ។ យើងត្រូវការចាក់សោ ដើម្បីជៀសវាងបញ្ហាជាមួយនឹងការចូលប្រើទិន្នន័យក្នុងពេលដំណាលគ្នា ឬបញ្ហាចែករំលែកផ្សេងទៀត។ ហើយកន្លែងដែលមានសោធំមួយ មានបញ្ហាមួយ - សោរឈ្លោះគ្នា នៅពេលដែលសោរនេះក្លាយជាឧបសគ្គ។

បញ្ហា​នេះ​អាច​ត្រូវ​បាន​ដោះស្រាយ​ឬ​ជៀស​វាង​ដោយ​ការ​ប្រើ​ការ​បំបែក ឬ​ប្រើ​លិបិក្រម​កំណែ។

Sharding គឺជារឿងសាមញ្ញ និងល្បី។ អ្នកអាចបំបែកលិបិក្រមផែនទីប៊ីត ដូចដែលអ្នកចង់បានទិន្នន័យផ្សេងទៀត។ ជំនួសឱ្យសោធំមួយ អ្នកនឹងទទួលបានសោតូចៗជាច្រើន ហើយដូច្នេះកម្ចាត់ការឈ្លោះប្រកែកគ្នាដោយសោ។

វិធីទីពីរដើម្បីដោះស្រាយបញ្ហាគឺត្រូវប្រើលិបិក្រមកំណែ។ អ្នកអាចមានច្បាប់ចម្លងមួយនៃលិបិក្រមដែលអ្នកប្រើសម្រាប់ការស្វែងរក ឬអាន និងមួយច្បាប់ដែលអ្នកប្រើសម្រាប់ការសរសេរ ឬធ្វើបច្ចុប្បន្នភាព។ ហើយម្តងក្នុងកំឡុងពេលជាក់លាក់មួយ (ឧទាហរណ៍ រាល់ 100 ms ឬ 500 ms) អ្នកស្ទួនពួកវា ហើយប្តូរពួកវា។ ជាការពិតណាស់ វិធីសាស្រ្តនេះគឺអាចអនុវត្តបានតែក្នុងករណីដែលកម្មវិធីរបស់អ្នកអាចដោះស្រាយសន្ទស្សន៍ស្វែងរកយឺតបន្តិចប៉ុណ្ណោះ។

វិធីសាស្រ្តទាំងពីរនេះអាចត្រូវបានប្រើក្នុងពេលដំណាលគ្នា៖ អ្នកអាចមានសន្ទស្សន៍កំណែដែលបានបំបែក។

សំណួរស្មុគស្មាញជាង

បញ្ហាចុងក្រោយជាមួយសន្ទស្សន៍ផែនទីប៊ីតគឺថា យើងត្រូវបានគេប្រាប់ថាវាមិនសមល្អសម្រាប់ប្រភេទសំណួរដែលស្មុគស្មាញជាងនេះទេ ដូចជាសំណួរវិសាលភាពជាដើម។

ជាការពិតណាស់ ប្រសិនបើអ្នកគិតអំពីវា ប្រតិបត្តិការប៊ីតដូចជា AND, OR ជាដើម គឺមិនស័ក្តិសមបំផុតសម្រាប់សំណួរ "បង្ហាញខ្ញុំនូវសណ្ឋាគារជាមួយនឹងតម្លៃបន្ទប់ពី 200 ទៅ 300 ដុល្លារក្នុងមួយយប់។"

ដំណោះស្រាយឆោតល្ងង់ និងគ្មានប្រាជ្ញានឹងជាការទទួលយកលទ្ធផលសម្រាប់តម្លៃប្រាក់ដុល្លារនីមួយៗ ហើយបញ្ចូលវាជាមួយប្រតិបត្តិការ OR បន្តិច។

ដំណោះស្រាយល្អជាងបន្តិចគឺត្រូវប្រើការដាក់ជាក្រុម។ ឧទាហរណ៍ក្នុងក្រុម 50 ដុល្លារ។ នេះនឹងបង្កើនល្បឿនដំណើរការរបស់យើង 50 ដង។

ប៉ុន្តែបញ្ហាក៏ត្រូវបានដោះស្រាយយ៉ាងងាយស្រួលដោយប្រើទិដ្ឋភាពដែលបានបង្កើតជាពិសេសសម្រាប់ប្រភេទសំណើនេះ។ នៅក្នុងឯកសារវិទ្យាសាស្ត្រ វាត្រូវបានហៅថា ផែនទីប៊ីតដែលបានអ៊ិនកូដជួរ។

នៅក្នុងការតំណាងនេះ យើងមិនគ្រាន់តែកំណត់មួយប៊ីតសម្រាប់តម្លៃមួយចំនួន (ឧទាហរណ៍ 200) ប៉ុន្តែកំណត់តម្លៃនេះ និងអ្វីៗគ្រប់យ៉ាងខ្ពស់ជាងនេះ។ 200 និងខ្ពស់ជាងនេះ។ ដូចគ្នាសម្រាប់ 300: 300 និងខ្ពស់ជាងនេះ។ ល​ល។

ដោយប្រើតំណាងនេះ យើងអាចឆ្លើយសំណួរស្វែងរកប្រភេទនេះដោយឆ្លងកាត់សន្ទស្សន៍ត្រឹមតែពីរដងប៉ុណ្ណោះ។ ដំបូង យើងនឹងទទួលបានបញ្ជីសណ្ឋាគារដែលបន្ទប់មានតម្លៃតិចជាង ឬ 300 ដុល្លារ ហើយបន្ទាប់មកយើងនឹងដកចេញពីវា ដែលតម្លៃបន្ទប់តិចជាង ឬ 199 ដុល្លារ។ រួចរាល់។

អ្នក​នឹង​ភ្ញាក់​ផ្អើល ប៉ុន្តែ​សូម្បី​តែ​ភូមិសាស្ត្រ​ក៏​អាច​ប្រើ​ប្រាស់​លិបិក្រម​ផែនទី​ប៊ីត។ ល្បិចគឺប្រើតំណាងធរណីមាត្រដែលព័ទ្ធជុំវិញកូអរដោនេរបស់អ្នកជាមួយនឹងតួលេខធរណីមាត្រ។ ឧទាហរណ៍ S2 ពី Google ។ តួរលេខគួរតែអាចតំណាងក្នុងទម្រង់ជាបន្ទាត់ប្រសព្វបី ឬច្រើនដែលអាចដាក់លេខបាន។ វិធីនេះយើងអាចបង្វែរភូមិសាស្ត្ររបស់យើងទៅជាសំណួរជាច្រើន “តាមចន្លោះ” (តាមបន្ទាត់លេខទាំងនេះ)។

ដំណោះស្រាយរួចរាល់

ខ្ញុំសង្ឃឹមថាខ្ញុំចាប់អារម្មណ៍អ្នកបន្តិច ហើយឥឡូវនេះអ្នកមានឧបករណ៍មានប្រយោជន៍មួយផ្សេងទៀតនៅក្នុងឃ្លាំងអាវុធរបស់អ្នក។ បើ​អ្នក​ធ្លាប់​ត្រូវ​ធ្វើ​រឿង​បែប​នេះ អ្នក​នឹង​ដឹង​ថា​ត្រូវ​មើល​វិធី​ណា។

ទោះយ៉ាងណាក៏ដោយ មិនមែនគ្រប់គ្នាសុទ្ធតែមានពេលវេលា ភាពអត់ធ្មត់ ឬធនធានដើម្បីបង្កើតលិបិក្រមរូបភាពពីដំបូងឡើយ។ ជា​ពិសេស​ការ​ប្រើ​ស៊ីមឌី ជា​ឧទាហរណ៍

ជាសំណាងល្អ មានដំណោះស្រាយដែលត្រៀមរួចជាស្រេចជាច្រើនដើម្បីជួយអ្នក។

ផែនទី​ដែល​កំពុង​គ្រហឹម

ទីមួយ មានបណ្ណាល័យប៊ីតផែនទីដែលគ្រហឹមដូចគ្នា ដែលខ្ញុំបាននិយាយរួចហើយ។ វាមានកុងតឺន័រចាំបាច់ទាំងអស់ និងប្រតិបត្តិការប៊ីត ដែលអ្នកនឹងត្រូវធ្វើលិបិក្រមផែនទីប៊ីតពេញលេញ។

ជាអកុសល នៅពេលនេះ គ្មានការអនុវត្ត Go ណាមួយប្រើ SIMD ដែលមានន័យថាការអនុវត្ត Go មានប្រសិទ្ធភាពតិចជាងការអនុវត្ត C ជាឧទាហរណ៍។

ភីឡូសា

ផលិតផលមួយទៀតដែលអាចជួយអ្នកបានគឺ Pilosa DBMS ដែលតាមពិតមានតែសន្ទស្សន៍ផែនទីប៊ីតប៉ុណ្ណោះ។ នេះ​ជា​ដំណោះ​ស្រាយ​ថ្មី​មួយ ប៉ុន្តែ​វា​ឈ្នះ​ចិត្ត​ក្នុង​ល្បឿន​ដ៏​អស្ចារ្យ។

Pilosa ប្រើផែនទីប៊ីតដែលគ្រហឹមនៅខាងក្នុង ហើយផ្តល់ឱ្យអ្នកនូវសមត្ថភាពក្នុងការប្រើប្រាស់ពួកវា សម្រួល និងពន្យល់អ្វីៗទាំងអស់ដែលខ្ញុំបាននិយាយខាងលើ៖ ការដាក់ជាក្រុម ផែនទីប៊ីតដែលបានអ៊ិនកូដជួរ គំនិតនៃវាល។ល។

សូមក្រឡេកមើលឧទាហរណ៍នៃការប្រើប្រាស់ Pilosa ដើម្បីឆ្លើយសំណួរដែលអ្នកធ្លាប់ស្គាល់។

ឧទាហរណ៍គឺស្រដៀងនឹងអ្វីដែលអ្នកបានឃើញពីមុន។ យើងបង្កើតម៉ាស៊ីនភ្ញៀវទៅកាន់ម៉ាស៊ីនមេ Pilosa បង្កើតលិបិក្រម និងវាលចាំបាច់ បន្ទាប់មកបំពេញវាលរបស់យើងជាមួយនឹងទិន្នន័យចៃដន្យជាមួយនឹងប្រូបាប៊ីលីតេ ហើយទីបំផុតប្រតិបត្តិសំណួរដែលធ្លាប់ស្គាល់។

បន្ទាប់ពីនោះ យើងប្រើមិននៅលើវាល "ថ្លៃ" បន្ទាប់មកប្រសព្វលទ្ធផល (ឬ និងវា) ជាមួយវាល "រាបស្មើ" និងជាមួយវាល "កក់" ។ ហើយចុងក្រោយយើងទទួលបានលទ្ធផលចុងក្រោយ។

ខ្ញុំពិតជាសង្ឃឹមថានៅពេលអនាគតដ៏ខ្លីខាងមុខ សន្ទស្សន៍ប្រភេទថ្មីនេះក៏នឹងបង្ហាញនៅក្នុង DBMSs ដូចជា MySQL និង PostgreSQL - bitmap indexes ។

សេចក្តីសន្និដ្ឋាន

បើមិនទាន់បានគេងទេ អរគុណ។ ខ្ញុំត្រូវនិយាយខ្លីៗលើប្រធានបទជាច្រើន ដោយសារពេលវេលាមានកំណត់ ប៉ុន្តែខ្ញុំសង្ឃឹមថាការពិភាក្សានេះមានប្រយោជន៍ ហើយប្រហែលជាលើកទឹកចិត្តផងដែរ។

លិបិក្រម Bitmap គឺល្អដែលត្រូវដឹង បើទោះបីជាអ្នកមិនត្រូវការវាឥឡូវនេះក៏ដោយ។ អនុញ្ញាតឱ្យពួកវាជាឧបករណ៍មួយផ្សេងទៀតនៅក្នុងប្រអប់ឧបករណ៍របស់អ្នក។

យើងបានមើលល្បិចនៃការអនុវត្តផ្សេងៗសម្រាប់ Go និងអ្វីៗដែលអ្នកចងក្រង Go មិនទាន់ដោះស្រាយបានល្អនៅឡើយ។ ប៉ុន្តែវាពិតជាមានប្រយោជន៍សម្រាប់អ្នកសរសេរកម្មវិធី Go គ្រប់រូបដើម្បីដឹង។

នោះហើយជាអ្វីដែលខ្ញុំចង់ប្រាប់អ្នក។ សូមអរគុណ!

ប្រភព: www.habr.com