Нэг зүйл нөгөөгөөсөө хамаарах үед: DAG гэж юу вэ?

Бидний өдөр тутмын амьдралд зарим ажлыг хүссэн үедээ хийж болдоггүй. Жишээ нь, шалгалтаа өгөхийн өмнө хичээлээ үзэж, хичээлээ үзсэний дараа дасгал ажиллах хэрэгтэй болно. Өөрөөр хэлбэл нэг үйлдэл нөгөөгөөсөө хамаардаг тодорхой дараалалтай. Компьютерийн программ, системүүдэд ч ийм хамаарал маш их байдаг. Ийм хамаарлыг дүрслэхэд ашигладаг чухал бүтцийн нэг нь DAG буюу Directed Acyclic Graph юм.

DAG гэж юу вэ?

DAG гэдэг нь Directed Acyclic Graph гэсэн үгийн товчлол бөгөөд монголоор чиглэлтэй, мөчлөггүй граф гэж ойлгож болно. Энгийнээр хэлбэл, цэгүүдийг хооронд нь тодорхой чиглэлтэй сумнуудаар холбосон бүтэц юм. Жишээ нь A → B → C гэж үзвэл A-ийн дараа B, B-ийн дараа C гэсэн хамааралтай байна. Харин хамгийн чухал нь энэ зам буцаж эргээд өмнөх цэгтэйгээ холбогдож, тойрог үүсгэх ёсгүй. Тиймээс DAG-ийн гол санаа нь чиглэлтэй бөгөөд буцаж тойрдоггүй хамаарлуудыг дүрслэх юм.

Яагаад “мөчлөггүй” байх ёстой вэ?

DAG-ийн Acyclic буюу мөчлөггүй гэсэн хэсэг хамгийн чухал. Жишээ нь A → B → C гэсэн дараалал байвал аль ажил түрүүлж явах нь тодорхой. Харин C-ээс буцаад A руу холбогдвол A → B → C → A гэсэн мөчлөг үүснэ. Ингэвэл A-г ажиллуулахын тулд C хэрэгтэй, C-г ажиллуулахын тулд B, харин B-г ажиллуулахын тулд A хэрэгтэй болж, аль нь эхлэх нь тодорхойгүй болно. Тиймээс компьютерийн системд ажлуудын хамаарлыг зөв зохион байгуулахын тулд ийм мөчлөгийг үүсгэхгүй байх шаардлагатай.

DAG ба алгоритмын дараалал

DAG нь зөвхөн юмсыг зураглан харуулах зориулалттай биш, алгоритмд зөв дарааллыг олоход ашиглагддаг. Үүний нэг жишээ нь Topological Sort юм. Жишээ нь A → C, B → C, C → D гэсэн хамаарал байвал C-г A болон B-ээс өмнө ажиллуулж болохгүй. Topological Sort нь эдгээр хамаарлыг харгалзан үзэж, бүх үйлдлийг боломжит зөв дараалалд оруулдаг. Энэ санаа нь task scheduling, software dependency зэрэг олон асуудлын үндэс болдог.

Бодит амьдралд DAG хаана хэрэгтэй вэ?

DAG-ийн санаа бидний өдөр тутмын хэрэглэдэг технологийн цаана ч байдаг. Жишээ нь программ суулгах үед нэг програм ажиллахын тулд эхлээд өөр нэг library суулгасан байх шаардлагатай байж болно. Мөн их хэмжээний өгөгдөл боловсруулах үед өгөгдөл татах → боловсруулах → хадгалах гэсэн дараалал үүсдэг. Өгөгдлийн pipeline зохион байгуулахад ашигладаг Apache Airflow зэрэг системүүд ч task-уудын хоорондын ийм хамаарлыг DAG-аар дүрсэлдэг. Ингэснээр систем аль ажлыг эхэлж, аль ажлыг дараа нь ажиллуулахыг ойлгомжтой болгодог.

DAG яагаад чухал вэ?

Компьютерийн системд олон ажил зэрэг явагддаг ч тэдгээрийн зарим нь заавал тодорхой дарааллыг шаарддаг. DAG нь энэ хамаарлыг эмх цэгцтэй дүрсэлж, ямар ажил юунаас хамаарч байгааг харах боломж олгодог. Харин Topological Sort зэрэг алгоритм ашигласнаар уг хамааралд тохирсон дарааллыг автоматаар гаргаж болно. Тиймээс DAG нь энгийн нэг граф биш, харин хамааралтай ажлуудыг зөв зохион байгуулахад ашиглагддаг компьютерийн шинжлэх ухааны чухал ойлголт юм.

Дүгнэлт

DAG-ийг ойлгохын тулд гурван санааг санахад хангалттай: чиглэлтэй, хамааралтай, мөчлөггүй. Нэг зүйл нөгөөгөөсөө хамаарч байгаа бол тэдгээрийн дарааллыг DAG-аар дүрслэх боломжтой. Үүн дээр үндэслэн Topological Sort зэрэг алгоритм зөв дарааллыг олж, компьютерийн системүүд олон ажлыг зохион байгуулалттайгаар гүйцэтгэхэд тусалдаг. Тиймээс DAG нь зөвхөн Airflow-ийн нэг ойлголт биш, харин Graph болон Algorithm-ийн суурь мэдлэгт багтдаг өргөн хэрэглээтэй бүтэц юм.