ಕಳೆದ ಬೇಸಿಗೆಯಲ್ಲಿ ನಾನು ಭಾಗವಹಿಸಿದ್ದೆ - Google ನಿಂದ ವಿದ್ಯಾರ್ಥಿಗಳಿಗೆ ಒಂದು ಪ್ರೋಗ್ರಾಂ. ಪ್ರತಿ ವರ್ಷ, ಸಂಘಟಕರು ಹಲವಾರು ಓಪನ್ ಸೋರ್ಸ್ ಪ್ರಾಜೆಕ್ಟ್‌ಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತಾರೆ, ಅಂತಹ ಪ್ರಸಿದ್ಧ ಸಂಸ್ಥೆಗಳಿಂದ и . ಈ ಯೋಜನೆಗಳಲ್ಲಿ ಕೆಲಸ ಮಾಡಲು ಪ್ರಪಂಚದಾದ್ಯಂತದ ವಿದ್ಯಾರ್ಥಿಗಳನ್ನು Google ಆಹ್ವಾನಿಸುತ್ತದೆ.
ಗೂಗಲ್ ಸಮ್ಮರ್ ಆಫ್ ಕೋಡ್ 2019 ರಲ್ಲಿ ಪಾಲ್ಗೊಳ್ಳುವವನಾಗಿ, ನಾನು ಲೈಬ್ರರಿಯಲ್ಲಿ ಪ್ರಾಜೆಕ್ಟ್ ಮಾಡಿದ್ದೇನೆ ಸಂಘಟನೆಯೊಂದಿಗೆ , ಇದು ಹ್ಯಾಸ್ಕೆಲ್ ಭಾಷೆಯನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸುತ್ತಿದೆ - ಇದು ಅತ್ಯಂತ ಪ್ರಸಿದ್ಧ ಕ್ರಿಯಾತ್ಮಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಭಾಷೆಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ. ಆಲ್ಗಾ ಪ್ರತಿನಿಧಿಸುವ ಗ್ರಂಥಾಲಯವಾಗಿದೆ ಹ್ಯಾಸ್ಕೆಲ್ನಲ್ಲಿ ಗ್ರಾಫ್‌ಗಳಿಗೆ ಪ್ರಾತಿನಿಧ್ಯ. ಇದನ್ನು ಬಳಸಲಾಗುತ್ತದೆ, ಉದಾಹರಣೆಗೆ, ಇನ್ — ಸಂಕೇತದ ಆಧಾರದ ಮೇಲೆ ಲಾಕ್ಷಣಿಕ ಮರಗಳು, ಕರೆ ಮತ್ತು ಅವಲಂಬನೆ ಗ್ರಾಫ್‌ಗಳನ್ನು ನಿರ್ಮಿಸುವ ಗಿಥಬ್ ಲೈಬ್ರರಿ ಮತ್ತು ಅವುಗಳನ್ನು ಹೋಲಿಸಬಹುದು. ಬೈಪಾರ್ಟೈಟ್ ಗ್ರಾಫ್‌ಗಳು ಮತ್ತು ಆ ಪ್ರಾತಿನಿಧ್ಯಕ್ಕಾಗಿ ಅಲ್ಗಾರಿದಮ್‌ಗಳಿಗೆ ಟೈಪ್-ಸುರಕ್ಷಿತ ಪ್ರಾತಿನಿಧ್ಯವನ್ನು ಸೇರಿಸುವುದು ನನ್ನ ಯೋಜನೆಯಾಗಿತ್ತು.
ಈ ಪೋಸ್ಟ್‌ನಲ್ಲಿ ನಾನು ಹ್ಯಾಸ್ಕೆಲ್ನಲ್ಲಿ ದ್ವಿಪಕ್ಷೀಯತೆಗಾಗಿ ಗ್ರಾಫ್ ಅನ್ನು ಪರಿಶೀಲಿಸಲು ಅಲ್ಗಾರಿದಮ್ನ ನನ್ನ ಅನುಷ್ಠಾನದ ಕುರಿತು ಮಾತನಾಡುತ್ತೇನೆ. ಅಲ್ಗಾರಿದಮ್ ಅತ್ಯಂತ ಮೂಲಭೂತವಾದುದಾದರೂ ಸಹ, ಅದನ್ನು ಕ್ರಿಯಾತ್ಮಕ ಶೈಲಿಯಲ್ಲಿ ಸುಂದರವಾಗಿ ಕಾರ್ಯಗತಗೊಳಿಸಲು ನನಗೆ ಹಲವಾರು ಪುನರಾವರ್ತನೆಗಳನ್ನು ತೆಗೆದುಕೊಂಡಿತು ಮತ್ತು ಸಾಕಷ್ಟು ಕೆಲಸ ಬೇಕಾಗುತ್ತದೆ. ಪರಿಣಾಮವಾಗಿ, ನಾನು ಮೊನಾಡ್ ಟ್ರಾನ್ಸ್ಫಾರ್ಮರ್ಗಳೊಂದಿಗೆ ಅನುಷ್ಠಾನದಲ್ಲಿ ನೆಲೆಸಿದೆ.
ನನ್ನ ಬಗ್ಗೆ
ನನ್ನ ಹೆಸರು ವಾಸಿಲಿ ಅಲ್ಫೆರೋವ್, ನಾನು ಸೇಂಟ್ ಪೀಟರ್ಸ್ಬರ್ಗ್ HSE ನಲ್ಲಿ ನಾಲ್ಕನೇ ವರ್ಷದ ವಿದ್ಯಾರ್ಥಿಯಾಗಿದ್ದೇನೆ. ಮೊನ್ನೆ ಬ್ಲಾಗ್ ನಲ್ಲಿ ಬರೆದಿದ್ದೆ и . ಇದೀಗ ನಾನು ಇಂಟರ್ನ್‌ಶಿಪ್‌ನಲ್ಲಿದ್ದೇನೆ ನಾರ್ವೆಯಲ್ಲಿ, ನಾನು ಸಮಸ್ಯೆಯ ವಿಧಾನಗಳ ಮೇಲೆ ಕೆಲಸ ಮಾಡುತ್ತಿದ್ದೇನೆ . ನನ್ನ ಆಸಕ್ತಿಗಳು ಪ್ಯಾರಾಮೀಟರ್ ಅಲ್ಗಾರಿದಮ್‌ಗಳು ಮತ್ತು ಕ್ರಿಯಾತ್ಮಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಅನ್ನು ಒಳಗೊಂಡಿವೆ.
ಅಲ್ಗಾರಿದಮ್ ಅನುಷ್ಠಾನದ ಬಗ್ಗೆ
ಮುನ್ನುಡಿ
ಕಾರ್ಯಕ್ರಮದಲ್ಲಿ ಭಾಗವಹಿಸುವ ವಿದ್ಯಾರ್ಥಿಗಳು ಬ್ಲಾಗ್ ಮಾಡಲು ಬಲವಾಗಿ ಪ್ರೋತ್ಸಾಹಿಸಲಾಗುತ್ತದೆ. ಅವರು ನನಗೆ ಬ್ಲಾಗ್‌ಗೆ ವೇದಿಕೆಯನ್ನು ಒದಗಿಸಿದರು . ಈ ಲೇಖನವು ಅನುವಾದವಾಗಿದೆ , ನಾನು ಅಲ್ಲಿ ಜುಲೈನಲ್ಲಿ ಇಂಗ್ಲಿಷ್‌ನಲ್ಲಿ ಸಣ್ಣ ಮುನ್ನುಡಿಯೊಂದಿಗೆ ಬರೆದಿದ್ದೇನೆ.
ಪ್ರಶ್ನೆಯಲ್ಲಿರುವ ಕೋಡ್‌ನೊಂದಿಗೆ ಪುಲ್ ವಿನಂತಿಯನ್ನು ಕಾಣಬಹುದು .
ನನ್ನ ಕೆಲಸದ ಫಲಿತಾಂಶಗಳ ಬಗ್ಗೆ ನೀವು ಓದಬಹುದು (ಇಂಗ್ಲಿಷ್‌ನಲ್ಲಿ) .
ಈ ಪೋಸ್ಟ್ ಕ್ರಿಯಾತ್ಮಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್‌ನಲ್ಲಿನ ಮೂಲ ಪರಿಕಲ್ಪನೆಗಳೊಂದಿಗೆ ಓದುಗರನ್ನು ಪರಿಚಿತಗೊಳಿಸಲು ಉದ್ದೇಶಿಸಲಾಗಿದೆ, ಆದರೂ ಸಮಯ ಬಂದಾಗ ಬಳಸಿದ ಎಲ್ಲಾ ಪದಗಳನ್ನು ನಾನು ನೆನಪಿಸಿಕೊಳ್ಳಲು ಪ್ರಯತ್ನಿಸುತ್ತೇನೆ.
ದ್ವಿಪಕ್ಷೀಯತೆಗಾಗಿ ಗ್ರಾಫ್‌ಗಳನ್ನು ಪರಿಶೀಲಿಸಲಾಗುತ್ತಿದೆ
ದ್ವಿಪಕ್ಷೀಯತೆಗಾಗಿ ಗ್ರಾಫ್ ಅನ್ನು ಪರಿಶೀಲಿಸುವ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಅಲ್ಗಾರಿದಮ್‌ಗಳ ಕೋರ್ಸ್‌ನಲ್ಲಿ ಸರಳವಾದ ಗ್ರಾಫ್ ಅಲ್ಗಾರಿದಮ್‌ಗಳಲ್ಲಿ ಒಂದಾಗಿ ನೀಡಲಾಗುತ್ತದೆ. ಅವರ ಕಲ್ಪನೆಯು ಸರಳವಾಗಿದೆ: ಮೊದಲು ನಾವು ಹೇಗಾದರೂ ಎಡ ಅಥವಾ ಬಲ ಭಾಗದಲ್ಲಿ ಶೃಂಗಗಳನ್ನು ಹಾಕುತ್ತೇವೆ ಮತ್ತು ಸಂಘರ್ಷದ ಅಂಚು ಕಂಡುಬಂದಾಗ, ಗ್ರಾಫ್ ದ್ವಿಪಕ್ಷೀಯವಲ್ಲ ಎಂದು ನಾವು ಪ್ರತಿಪಾದಿಸುತ್ತೇವೆ.
ಸ್ವಲ್ಪ ಹೆಚ್ಚು ವಿವರ: ಮೊದಲು ನಾವು ಎಡ ಹಂಚಿನಲ್ಲಿ ಕೆಲವು ಶೃಂಗವನ್ನು ಹಾಕುತ್ತೇವೆ. ನಿಸ್ಸಂಶಯವಾಗಿ, ಈ ಶೃಂಗದ ಎಲ್ಲಾ ನೆರೆಹೊರೆಯವರು ಬಲ ಹಾಲೆಯಲ್ಲಿ ಮಲಗಿರಬೇಕು. ಇದಲ್ಲದೆ, ಈ ಶೃಂಗದ ನೆರೆಹೊರೆಯವರ ಎಲ್ಲಾ ನೆರೆಹೊರೆಯವರು ಎಡ ಹಾಲೆಯಲ್ಲಿ ಮಲಗಬೇಕು, ಇತ್ಯಾದಿ. ನಾವು ಪ್ರಾರಂಭಿಸಿದ ಶೃಂಗದ ಸಂಪರ್ಕಿತ ಘಟಕದಲ್ಲಿ ಇನ್ನೂ ಶೃಂಗಗಳು ಇರುವವರೆಗೂ ನಾವು ಶೇರ್‌ಗಳನ್ನು ಶೃಂಗಗಳಿಗೆ ನಿಯೋಜಿಸುವುದನ್ನು ಮುಂದುವರಿಸುತ್ತೇವೆ ಮತ್ತು ನಾವು ನೆರೆಹೊರೆಯವರನ್ನು ನಿಯೋಜಿಸಿಲ್ಲ. ನಂತರ ನಾವು ಎಲ್ಲಾ ಸಂಪರ್ಕಿತ ಘಟಕಗಳಿಗೆ ಈ ಕ್ರಿಯೆಯನ್ನು ಪುನರಾವರ್ತಿಸುತ್ತೇವೆ.
ಒಂದೇ ವಿಭಾಗದಲ್ಲಿ ಬೀಳುವ ಶೃಂಗಗಳ ನಡುವೆ ಅಂಚು ಇದ್ದರೆ, ಗ್ರಾಫ್‌ನಲ್ಲಿ ಬೆಸ ಚಕ್ರವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಕಷ್ಟವೇನಲ್ಲ, ಇದು ಬೈಪಾರ್ಟೈಟ್ ಗ್ರಾಫ್‌ನಲ್ಲಿ ವ್ಯಾಪಕವಾಗಿ ತಿಳಿದಿರುವ (ಮತ್ತು ಸಾಕಷ್ಟು ನಿಸ್ಸಂಶಯವಾಗಿ) ಅಸಾಧ್ಯವಾಗಿದೆ. ಇಲ್ಲದಿದ್ದರೆ, ನಾವು ಸರಿಯಾದ ವಿಭಾಗವನ್ನು ಹೊಂದಿದ್ದೇವೆ, ಅಂದರೆ ಗ್ರಾಫ್ ಬೈಪಾರ್ಟೈಟ್ ಆಗಿದೆ.
ವಿಶಿಷ್ಟವಾಗಿ, ಈ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಕಾರ್ಯಗತಗೊಳಿಸಲಾಗುತ್ತದೆ ಅಥವಾ . ಕಡ್ಡಾಯ ಭಾಷೆಗಳಲ್ಲಿ, ಆಳ-ಮೊದಲ ಹುಡುಕಾಟವನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಬಳಸಲಾಗುತ್ತದೆ ಏಕೆಂದರೆ ಇದು ಸ್ವಲ್ಪ ಸರಳವಾಗಿದೆ ಮತ್ತು ಹೆಚ್ಚುವರಿ ಡೇಟಾ ರಚನೆಗಳ ಅಗತ್ಯವಿರುವುದಿಲ್ಲ. ಇದು ಹೆಚ್ಚು ಸಾಂಪ್ರದಾಯಿಕವಾದ್ದರಿಂದ ನಾನು ಆಳ-ಮೊದಲ ಹುಡುಕಾಟವನ್ನು ಸಹ ಆರಿಸಿದೆ.
ಹೀಗಾಗಿ, ನಾವು ಈ ಕೆಳಗಿನ ಯೋಜನೆಗೆ ಬಂದಿದ್ದೇವೆ. ನಾವು ಆಳ-ಮೊದಲ ಹುಡುಕಾಟವನ್ನು ಬಳಸಿಕೊಂಡು ಗ್ರಾಫ್‌ನ ಶೃಂಗಗಳನ್ನು ದಾಟುತ್ತೇವೆ ಮತ್ತು ಅವುಗಳಿಗೆ ಷೇರುಗಳನ್ನು ನಿಯೋಜಿಸುತ್ತೇವೆ, ನಾವು ಅಂಚಿನಲ್ಲಿ ಚಲಿಸುವಾಗ ಹಂಚಿಕೆಯ ಸಂಖ್ಯೆಯನ್ನು ಬದಲಾಯಿಸುತ್ತೇವೆ. ನಾವು ಈಗಾಗಲೇ ಹಂಚಿಕೆಯನ್ನು ಹೊಂದಿರುವ ಶೃಂಗಕ್ಕೆ ಪಾಲನ್ನು ನಿಯೋಜಿಸಲು ಪ್ರಯತ್ನಿಸಿದರೆ, ಗ್ರಾಫ್ ಬೈಪಾರ್ಟೈಟ್ ಅಲ್ಲ ಎಂದು ನಾವು ಸುರಕ್ಷಿತವಾಗಿ ಹೇಳಬಹುದು. ಎಲ್ಲಾ ಶೃಂಗಗಳಿಗೆ ಪಾಲನ್ನು ನಿಗದಿಪಡಿಸಿದ ಕ್ಷಣ ಮತ್ತು ನಾವು ಎಲ್ಲಾ ಅಂಚುಗಳನ್ನು ನೋಡಿದಾಗ, ನಾವು ಉತ್ತಮ ವಿಭಜನೆಯನ್ನು ಹೊಂದಿದ್ದೇವೆ.
ಲೆಕ್ಕಾಚಾರಗಳ ಶುದ್ಧತೆ
ಹ್ಯಾಸ್ಕೆಲ್ನಲ್ಲಿ ನಾವು ಎಲ್ಲಾ ಲೆಕ್ಕಾಚಾರಗಳು ಎಂದು ಭಾವಿಸುತ್ತೇವೆ ಶುದ್ಧ. ಆದಾಗ್ಯೂ, ಇದು ನಿಜವಾಗಿಯೂ ನಿಜವಾಗಿದ್ದರೆ, ಪರದೆಯ ಮೇಲೆ ಏನನ್ನೂ ಮುದ್ರಿಸಲು ನಮಗೆ ಯಾವುದೇ ಮಾರ್ಗವಿಲ್ಲ. ಎಲ್ಲಾ, ಸ್ವಚ್ಛಗೊಳಿಸಲು ಲೆಕ್ಕಾಚಾರಗಳು ಎಷ್ಟು ಸೋಮಾರಿಯಾಗಿವೆ ಎಂದರೆ ಒಂದೂ ಇಲ್ಲ ಸ್ವಚ್ .ಗೊಳಿಸಿ ಏನನ್ನಾದರೂ ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಕಾರಣಗಳು. ಪ್ರೋಗ್ರಾಂನಲ್ಲಿ ಸಂಭವಿಸುವ ಎಲ್ಲಾ ಲೆಕ್ಕಾಚಾರಗಳು ಹೇಗಾದರೂ ಬಲವಂತವಾಗಿರುತ್ತವೆ "ಅಶುದ್ಧ" ಮೊನಾಡ್ IO.
ಮೊನಾಡ್ಗಳು ಲೆಕ್ಕಾಚಾರಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಒಂದು ಮಾರ್ಗವಾಗಿದೆ ಪರಿಣಾಮಗಳು ಹ್ಯಾಸ್ಕೆಲ್ ನಲ್ಲಿ. ಅವರು ಹೇಗೆ ಕೆಲಸ ಮಾಡುತ್ತಾರೆ ಎಂಬುದನ್ನು ವಿವರಿಸುವುದು ಈ ಪೋಸ್ಟ್‌ನ ವ್ಯಾಪ್ತಿಯನ್ನು ಮೀರಿದೆ. ಉತ್ತಮ ಮತ್ತು ಸ್ಪಷ್ಟವಾದ ವಿವರಣೆಯನ್ನು ಇಂಗ್ಲಿಷ್‌ನಲ್ಲಿ ಓದಬಹುದು .
IO ನಂತಹ ಕೆಲವು ಮೊನಾಡ್‌ಗಳನ್ನು ಕಂಪೈಲರ್ ಮ್ಯಾಜಿಕ್ ಮೂಲಕ ಕಾರ್ಯಗತಗೊಳಿಸಿದರೆ, ಉಳಿದವುಗಳನ್ನು ಸಾಫ್ಟ್‌ವೇರ್‌ನಲ್ಲಿ ಅಳವಡಿಸಲಾಗಿದೆ ಮತ್ತು ಅವುಗಳಲ್ಲಿನ ಎಲ್ಲಾ ಲೆಕ್ಕಾಚಾರಗಳು ಶುದ್ಧವಾಗಿವೆ ಎಂದು ಇಲ್ಲಿ ನಾನು ಗಮನಿಸಲು ಬಯಸುತ್ತೇನೆ.
ಬಹಳಷ್ಟು ಪರಿಣಾಮಗಳಿವೆ ಮತ್ತು ಪ್ರತಿಯೊಂದೂ ತನ್ನದೇ ಆದ ಮೊನಾಡ್ ಅನ್ನು ಹೊಂದಿದೆ. ಇದು ಅತ್ಯಂತ ಬಲವಾದ ಮತ್ತು ಸುಂದರವಾದ ಸಿದ್ಧಾಂತವಾಗಿದೆ: ಎಲ್ಲಾ ಮೊನಾಡ್ಗಳು ಒಂದೇ ಇಂಟರ್ಫೇಸ್ ಅನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸುತ್ತವೆ. ನಾವು ಈ ಕೆಳಗಿನ ಮೂರು ಮೊನಾಡ್‌ಗಳ ಬಗ್ಗೆ ಮಾತನಾಡುತ್ತೇವೆ:
- ಒಂದೋ ea ಎಂಬುದು ಟೈಪ್ ಎ ಮೌಲ್ಯವನ್ನು ಹಿಂದಿರುಗಿಸುವ ಅಥವಾ ಟೈಪ್ ಇ ನ ವಿನಾಯಿತಿಯನ್ನು ಎಸೆಯುವ ಲೆಕ್ಕಾಚಾರವಾಗಿದೆ. ಈ ಮೊನಾಡ್‌ನ ನಡವಳಿಕೆಯು ಕಡ್ಡಾಯ ಭಾಷೆಗಳಲ್ಲಿ ವಿನಾಯಿತಿ ನಿರ್ವಹಣೆಗೆ ಹೋಲುತ್ತದೆ: ದೋಷಗಳನ್ನು ಹಿಡಿಯಬಹುದು ಅಥವಾ ರವಾನಿಸಬಹುದು. ಮುಖ್ಯ ವ್ಯತ್ಯಾಸವೆಂದರೆ ಮೊನಾಡ್ ಅನ್ನು ಹ್ಯಾಸ್ಕೆಲ್‌ನ ಪ್ರಮಾಣಿತ ಗ್ರಂಥಾಲಯದಲ್ಲಿ ಸಂಪೂರ್ಣವಾಗಿ ತಾರ್ಕಿಕವಾಗಿ ಅಳವಡಿಸಲಾಗಿದೆ, ಆದರೆ ಕಡ್ಡಾಯ ಭಾಷೆಗಳು ಸಾಮಾನ್ಯವಾಗಿ ಆಪರೇಟಿಂಗ್ ಸಿಸ್ಟಮ್ ಕಾರ್ಯವಿಧಾನಗಳನ್ನು ಬಳಸುತ್ತವೆ.
- ಸ್ಟೇಟ್ sa ಎಂಬುದು ಒಂದು ಲೆಕ್ಕಾಚಾರವಾಗಿದ್ದು ಅದು ಟೈಪ್ a ನ ಮೌಲ್ಯವನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ ಮತ್ತು s ಪ್ರಕಾರದ ರೂಪಾಂತರಗೊಳ್ಳುವ ಸ್ಥಿತಿಗೆ ಪ್ರವೇಶವನ್ನು ಹೊಂದಿರುತ್ತದೆ.
- ಬಹುಶಃ ಎ. ನಥಿಂಗ್ ಅನ್ನು ಹಿಂದಿರುಗಿಸುವ ಮೂಲಕ ಯಾವುದೇ ಸಮಯದಲ್ಲಿ ಅಡ್ಡಿಪಡಿಸಬಹುದಾದ ಲೆಕ್ಕಾಚಾರವನ್ನು ಬಹುಶಃ ಮೊನಾಡ್ ವ್ಯಕ್ತಪಡಿಸುತ್ತದೆ. ಆದಾಗ್ಯೂ, ನಾವು ಬಹುಶಃ ಮಾದರಿಗೆ ಮೊನಾಡ್‌ಪ್ಲಸ್ ವರ್ಗದ ಅನುಷ್ಠಾನದ ಬಗ್ಗೆ ಮಾತನಾಡುತ್ತೇವೆ, ಇದು ವಿರುದ್ಧ ಪರಿಣಾಮವನ್ನು ವ್ಯಕ್ತಪಡಿಸುತ್ತದೆ: ಇದು ಒಂದು ನಿರ್ದಿಷ್ಟ ಮೌಲ್ಯವನ್ನು ಹಿಂದಿರುಗಿಸುವ ಮೂಲಕ ಯಾವುದೇ ಸಮಯದಲ್ಲಿ ಅಡ್ಡಿಪಡಿಸಬಹುದಾದ ಲೆಕ್ಕಾಚಾರವಾಗಿದೆ.
ಅಲ್ಗಾರಿದಮ್ನ ಅಳವಡಿಕೆ
ನಾವು ಎರಡು ಡೇಟಾ ಪ್ರಕಾರಗಳನ್ನು ಹೊಂದಿದ್ದೇವೆ, ಗ್ರಾಫ್ ಎ ಮತ್ತು ಬಿಗ್ರಾಫ್ ಎಬಿ, ಅದರಲ್ಲಿ ಮೊದಲನೆಯದು ಎ ಪ್ರಕಾರದ ಮೌಲ್ಯಗಳೊಂದಿಗೆ ಲೇಬಲ್ ಮಾಡಲಾದ ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್‌ಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ ಮತ್ತು ಎರಡನೆಯದು ಟೈಪ್ ಎ ಮತ್ತು ಬಲದ ಮೌಲ್ಯಗಳೊಂದಿಗೆ ಲೇಬಲ್ ಮಾಡಲಾದ ಎಡ-ಬದಿಯ ಶೃಂಗಗಳೊಂದಿಗೆ ಬೈಪಾರ್ಟೈಟ್ ಗ್ರಾಫ್‌ಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ. -ಬದಿಯ ಶೃಂಗಗಳನ್ನು ಟೈಪ್ ಬಿ ಮೌಲ್ಯಗಳೊಂದಿಗೆ ಲೇಬಲ್ ಮಾಡಲಾಗಿದೆ.
ಇವು ಅಲ್ಗಾ ಲೈಬ್ರರಿಯಿಂದ ಬಂದ ಪ್ರಕಾರಗಳಲ್ಲ. ನಿರ್ದೇಶನವಿಲ್ಲದ ದ್ವಿಪಕ್ಷೀಯ ಗ್ರಾಫ್‌ಗಳಿಗೆ ಆಲ್ಗಾ ಪ್ರಾತಿನಿಧ್ಯವನ್ನು ಹೊಂದಿಲ್ಲ. ಸ್ಪಷ್ಟತೆಗಾಗಿ ನಾನು ಈ ರೀತಿಯ ಪ್ರಕಾರಗಳನ್ನು ಮಾಡಿದ್ದೇನೆ.
ಕೆಳಗಿನ ಸಹಿಗಳೊಂದಿಗೆ ನಮಗೆ ಸಹಾಯಕ ಕಾರ್ಯಗಳು ಸಹ ಅಗತ್ಯವಿದೆ:
-- Список соседей данной вершины.
neighbours :: Ord a => a -> Graph a -> [a]
-- Построить двудольный граф по графу и функции, для каждой вершины
-- выдающей её долю и пометку в новой доле, игнорируя конфликтные рёбра.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Список вершин в графе
vertexList :: Ord a => Graph a -> [a]
Сигнатура функции, которую мы будем писать, выглядит так:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)ಆಳ-ಮೊದಲ ಹುಡುಕಾಟದ ಸಮಯದಲ್ಲಿ ನಾವು ಸಂಘರ್ಷದ ಅಂಚನ್ನು ಕಂಡುಕೊಂಡರೆ, ಬೆಸ ಚಕ್ರವು ರಿಕರ್ಶನ್ ಸ್ಟಾಕ್‌ನ ಮೇಲ್ಭಾಗದಲ್ಲಿದೆ ಎಂದು ನೋಡುವುದು ಸುಲಭ. ಹೀಗಾಗಿ, ಅದನ್ನು ಪುನಃಸ್ಥಾಪಿಸಲು, ನಾವು ರಿಕರ್ಶನ್ ಸ್ಟಾಕ್‌ನಿಂದ ಕೊನೆಯ ಶೃಂಗದ ಮೊದಲ ಸಂಭವಿಸುವಿಕೆಯವರೆಗೆ ಎಲ್ಲವನ್ನೂ ಕತ್ತರಿಸಬೇಕಾಗುತ್ತದೆ.
ಪ್ರತಿ ಶೃಂಗಕ್ಕೆ ಷೇರು ಸಂಖ್ಯೆಗಳ ಸಹಾಯಕ ಶ್ರೇಣಿಯನ್ನು ನಿರ್ವಹಿಸುವ ಮೂಲಕ ನಾವು ಆಳ-ಮೊದಲ ಹುಡುಕಾಟವನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸುತ್ತೇವೆ. ನಾವು ಆಯ್ಕೆ ಮಾಡಿದ ಮೊನಾಡ್‌ನ ಫಂಕ್ಟರ್ ವರ್ಗದ ಅನುಷ್ಠಾನದ ಮೂಲಕ ಪುನರಾವರ್ತನೆಯ ಸ್ಟಾಕ್ ಅನ್ನು ಸ್ವಯಂಚಾಲಿತವಾಗಿ ನಿರ್ವಹಿಸಲಾಗುತ್ತದೆ: ನಾವು ಪುನರಾವರ್ತಿತ ಕಾರ್ಯದಿಂದ ಹಿಂತಿರುಗಿದ ಫಲಿತಾಂಶಕ್ಕೆ ಮಾರ್ಗದಿಂದ ಎಲ್ಲಾ ಶೃಂಗಗಳನ್ನು ಮಾತ್ರ ಇರಿಸಬೇಕಾಗುತ್ತದೆ.
ಒಂದೋ ಮೊನಾಡ್ ಅನ್ನು ಬಳಸುವುದು ನನ್ನ ಮೊದಲ ಆಲೋಚನೆಯಾಗಿದೆ, ಅದು ನಮಗೆ ಅಗತ್ಯವಿರುವ ಪರಿಣಾಮಗಳನ್ನು ನಿಖರವಾಗಿ ಕಾರ್ಯಗತಗೊಳಿಸುತ್ತದೆ. ನಾನು ಬರೆದ ಮೊದಲ ಅನುಷ್ಠಾನವು ಈ ಆಯ್ಕೆಗೆ ಬಹಳ ಹತ್ತಿರದಲ್ಲಿದೆ. ವಾಸ್ತವವಾಗಿ, ನಾನು ಒಂದು ಹಂತದಲ್ಲಿ ಐದು ವಿಭಿನ್ನ ಅನುಷ್ಠಾನಗಳನ್ನು ಹೊಂದಿದ್ದೇನೆ ಮತ್ತು ಅಂತಿಮವಾಗಿ ಇನ್ನೊಂದರಲ್ಲಿ ನೆಲೆಸಿದ್ದೇನೆ.
ಮೊದಲಿಗೆ, ನಾವು ಷೇರು ಗುರುತಿಸುವಿಕೆಗಳ ಸಹಾಯಕ ಶ್ರೇಣಿಯನ್ನು ನಿರ್ವಹಿಸಬೇಕಾಗಿದೆ - ಇದು ರಾಜ್ಯಕ್ಕೆ ಸಂಬಂಧಿಸಿದ ವಿಷಯವಾಗಿದೆ. ಎರಡನೆಯದಾಗಿ, ಸಂಘರ್ಷ ಪತ್ತೆಯಾದಾಗ ನಾವು ನಿಲ್ಲಿಸಲು ಸಾಧ್ಯವಾಗುತ್ತದೆ. ಇದು ಮೊನಾಡ್ ಆಗಿರಬಹುದು ಅಥವಾ ಬಹುಶಃ ಮೊನಾಡ್‌ಪ್ಲಸ್ ಆಗಿರಬಹುದು. ಮುಖ್ಯ ವ್ಯತ್ಯಾಸವೆಂದರೆ ಲೆಕ್ಕಾಚಾರವನ್ನು ನಿಲ್ಲಿಸದಿದ್ದರೆ ಮೌಲ್ಯವನ್ನು ಹಿಂತಿರುಗಿಸಬಹುದು ಮತ್ತು ಬಹುಶಃ ಈ ಸಂದರ್ಭದಲ್ಲಿ ಈ ಬಗ್ಗೆ ಮಾಹಿತಿಯನ್ನು ಮಾತ್ರ ಹಿಂತಿರುಗಿಸಬಹುದು. ಯಶಸ್ಸಿಗೆ ನಮಗೆ ಪ್ರತ್ಯೇಕ ಮೌಲ್ಯ ಅಗತ್ಯವಿಲ್ಲದ ಕಾರಣ (ಅದನ್ನು ಈಗಾಗಲೇ ರಾಜ್ಯದಲ್ಲಿ ಸಂಗ್ರಹಿಸಲಾಗಿದೆ), ನಾವು ಬಹುಶಃ ಆಯ್ಕೆ ಮಾಡುತ್ತೇವೆ. ಮತ್ತು ನಾವು ಎರಡು ಮೊನಾಡ್‌ಗಳ ಪರಿಣಾಮಗಳನ್ನು ಸಂಯೋಜಿಸಬೇಕಾದ ಕ್ಷಣದಲ್ಲಿ, ಅವು ಹೊರಬರುತ್ತವೆ , ಇದು ನಿಖರವಾಗಿ ಈ ಪರಿಣಾಮಗಳನ್ನು ಸಂಯೋಜಿಸುತ್ತದೆ.
ನಾನು ಅಂತಹ ಸಂಕೀರ್ಣ ಪ್ರಕಾರವನ್ನು ಏಕೆ ಆರಿಸಿದೆ? ಎರಡು ಕಾರಣಗಳು. ಮೊದಲನೆಯದಾಗಿ, ಅನುಷ್ಠಾನವು ಕಡ್ಡಾಯಕ್ಕೆ ಹೋಲುತ್ತದೆ. ಎರಡನೆಯದಾಗಿ, ಬೆಸ ಲೂಪ್ ಅನ್ನು ಮರುಸ್ಥಾಪಿಸಲು ಪುನರಾವರ್ತನೆಯಿಂದ ಹಿಂತಿರುಗುವಾಗ ಸಂಘರ್ಷದ ಸಂದರ್ಭದಲ್ಲಿ ನಾವು ಹಿಂತಿರುಗಿಸುವ ಮೌಲ್ಯವನ್ನು ಕುಶಲತೆಯಿಂದ ನಿರ್ವಹಿಸಬೇಕಾಗಿದೆ, ಇದು ಬಹುಶಃ ಮೊನಾಡ್‌ನಲ್ಲಿ ಮಾಡಲು ಹೆಚ್ಚು ಸುಲಭವಾಗಿದೆ.
ಹೀಗಾಗಿ ನಾವು ಈ ಅನುಷ್ಠಾನವನ್ನು ಪಡೆಯುತ್ತೇವೆ.
{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE ScopedTypeVariables #-}
data Part = LeftPart | RightPart
otherPart :: Part -> Part
otherPart LeftPart = RightPart
otherPart RightPart = LeftPart
type PartMap a = Map.Map a Part
type OddCycle a = [a]
toEither :: Ord a => PartMap a -> a -> Either a a
toEither m v = case fromJust (v `Map.lookup` m) of
LeftPart -> Left v
RightPart -> Right v
type PartMonad a = MaybeT (State (PartMap a)) [a]
detectParts :: forall a. Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)
detectParts g = case runState (runMaybeT dfs) Map.empty of
(Just c, _) -> Left $ oddCycle c
(Nothing, m) -> Right $ toBipartiteWith (toEither m) g
where
inVertex :: Part -> a -> PartMonad a
inVertex p v = ((:) v) <$> do modify $ Map.insert v p
let q = otherPart p
msum [ onEdge q u | u <- neigbours v g ]
{-# INLINE onEdge #-}
onEdge :: Part -> a -> PartMonad a
onEdge p v = do m <- get
case v `Map.lookup` m of
Nothing -> inVertex p v
Just q -> do guard (q /= p)
return [v]
processVertex :: a -> PartMonad a
processVertex v = do m <- get
guard (v `Map.notMember` m)
inVertex LeftPart v
dfs :: PartMonad a
dfs = msum [ processVertex v | v <- vertexList g ]
oddCycle :: [a] -> [a]
oddCycle c = tail (dropWhile ((/=) last c) c)
ಅಲ್ಲಿ ಬ್ಲಾಕ್ ಅಲ್ಗಾರಿದಮ್ನ ತಿರುಳು. ಅದರೊಳಗೆ ಏನಾಗುತ್ತಿದೆ ಎಂಬುದನ್ನು ವಿವರಿಸಲು ನಾನು ಪ್ರಯತ್ನಿಸುತ್ತೇನೆ.
- inVertex ನಾವು ಮೊದಲ ಬಾರಿಗೆ ಶೃಂಗಕ್ಕೆ ಭೇಟಿ ನೀಡುವ ಆಳ-ಮೊದಲ ಹುಡುಕಾಟದ ಭಾಗವಾಗಿದೆ. ಇಲ್ಲಿ ನಾವು ಶೃಂಗಕ್ಕೆ ಷೇರು ಸಂಖ್ಯೆಯನ್ನು ನಿಯೋಜಿಸುತ್ತೇವೆ ಮತ್ತು ಎಲ್ಲಾ ನೆರೆಹೊರೆಯವರ ಮೇಲೆ ಆನ್ ಎಡ್ಜ್ ಅನ್ನು ರನ್ ಮಾಡುತ್ತೇವೆ. ಇಲ್ಲಿಯೇ ನಾವು ಕರೆ ಸ್ಟಾಕ್ ಅನ್ನು ಮರುಸ್ಥಾಪಿಸುತ್ತೇವೆ: msum ಮೌಲ್ಯವನ್ನು ಹಿಂತಿರುಗಿಸಿದರೆ, ನಾವು ವರ್ಟೆಕ್ಸ್ v ಅನ್ನು ಅಲ್ಲಿಗೆ ತಳ್ಳುತ್ತೇವೆ.
- onEdge ನಾವು ಅಂಚಿಗೆ ಭೇಟಿ ನೀಡುವ ಭಾಗವಾಗಿದೆ. ಪ್ರತಿ ಅಂಚಿಗೆ ಇದನ್ನು ಎರಡು ಬಾರಿ ಕರೆಯಲಾಗುತ್ತದೆ. ಇಲ್ಲಿ ನಾವು ಇನ್ನೊಂದು ಬದಿಯಲ್ಲಿರುವ ಶೃಂಗವನ್ನು ಭೇಟಿ ಮಾಡಲಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತೇವೆ ಮತ್ತು ಇಲ್ಲದಿದ್ದರೆ ಅದನ್ನು ಭೇಟಿ ಮಾಡುತ್ತೇವೆ. ಭೇಟಿ ನೀಡಿದರೆ, ಅಂಚು ಸಂಘರ್ಷವಾಗಿದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಅದು ಇದ್ದರೆ, ನಾವು ಮೌಲ್ಯವನ್ನು ಹಿಂತಿರುಗಿಸುತ್ತೇವೆ - ರಿಕರ್ಶನ್ ಸ್ಟಾಕ್‌ನ ಅತ್ಯಂತ ಮೇಲ್ಭಾಗ, ಅಲ್ಲಿ ಎಲ್ಲಾ ಇತರ ಶೃಂಗಗಳನ್ನು ಹಿಂತಿರುಗಿದ ನಂತರ ಇರಿಸಲಾಗುತ್ತದೆ.
- processVertex ಪ್ರತಿ ಶೃಂಗವನ್ನು ಭೇಟಿ ಮಾಡಲಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತದೆ ಮತ್ತು ಇಲ್ಲದಿದ್ದರೆ ಅದರ ಮೇಲೆ inVertex ಅನ್ನು ರನ್ ಮಾಡುತ್ತದೆ.
- dfs ಎಲ್ಲಾ ಶೃಂಗಗಳಲ್ಲಿ processVertex ಅನ್ನು ನಡೆಸುತ್ತದೆ.
ಅಷ್ಟೇ.
INLINE ಪದದ ಇತಿಹಾಸ
INLINE ಪದವು ಅಲ್ಗಾರಿದಮ್ನ ಮೊದಲ ಅನುಷ್ಠಾನದಲ್ಲಿ ಇರಲಿಲ್ಲ; ಅದು ನಂತರ ಕಾಣಿಸಿಕೊಂಡಿತು. ನಾನು ಉತ್ತಮ ಅನುಷ್ಠಾನವನ್ನು ಹುಡುಕಲು ಪ್ರಯತ್ನಿಸಿದಾಗ, ಕೆಲವು ಗ್ರಾಫ್‌ಗಳಲ್ಲಿ INLINE ಅಲ್ಲದ ಆವೃತ್ತಿಯು ಗಮನಾರ್ಹವಾಗಿ ನಿಧಾನವಾಗಿದೆ ಎಂದು ನಾನು ಕಂಡುಕೊಂಡೆ. ಶಬ್ದಾರ್ಥದಲ್ಲಿ ಕಾರ್ಯಗಳು ಒಂದೇ ರೀತಿ ಕಾರ್ಯನಿರ್ವಹಿಸಬೇಕು ಎಂದು ಪರಿಗಣಿಸಿ, ಇದು ನನಗೆ ಬಹಳ ಆಶ್ಚರ್ಯವನ್ನುಂಟುಮಾಡಿತು. ಇನ್ನೂ ವಿಚಿತ್ರವೆಂದರೆ, GHC ಯ ವಿಭಿನ್ನ ಆವೃತ್ತಿಯೊಂದಿಗೆ ಮತ್ತೊಂದು ಯಂತ್ರದಲ್ಲಿ ಯಾವುದೇ ಗಮನಾರ್ಹ ವ್ಯತ್ಯಾಸವಿಲ್ಲ.
GHC ಕೋರ್ ಔಟ್‌ಪುಟ್ ಅನ್ನು ಓದಲು ಒಂದು ವಾರ ಕಳೆದ ನಂತರ, ಸ್ಪಷ್ಟವಾದ INLINE ನ ಒಂದು ಸಾಲಿನ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ನನಗೆ ಸಾಧ್ಯವಾಯಿತು. GHC 8.4.4 ಮತ್ತು GHC 8.6.5 ರ ನಡುವೆ ಕೆಲವು ಹಂತದಲ್ಲಿ ಆಪ್ಟಿಮೈಜರ್ ಇದನ್ನು ತನ್ನದೇ ಆದ ಮೇಲೆ ಮಾಡುವುದನ್ನು ನಿಲ್ಲಿಸಿತು.
ಹ್ಯಾಸ್ಕೆಲ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್‌ನಲ್ಲಿ ಅಂತಹ ಕೊಳಕು ಎದುರಾಗುತ್ತದೆ ಎಂದು ನಾನು ನಿರೀಕ್ಷಿಸಿರಲಿಲ್ಲ. ಆದಾಗ್ಯೂ, ಇಂದಿಗೂ ಸಹ, ಆಪ್ಟಿಮೈಜರ್‌ಗಳು ಕೆಲವೊಮ್ಮೆ ತಪ್ಪುಗಳನ್ನು ಮಾಡುತ್ತಾರೆ ಮತ್ತು ಅವರಿಗೆ ಸುಳಿವುಗಳನ್ನು ನೀಡುವುದು ನಮ್ಮ ಕೆಲಸವಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, ಕಾರ್ಯವನ್ನು ಇನ್‌ಲೈನ್ ಮಾಡಬೇಕೆಂದು ಇಲ್ಲಿ ನಮಗೆ ತಿಳಿದಿದೆ ಏಕೆಂದರೆ ಅದು ಕಡ್ಡಾಯ ಆವೃತ್ತಿಯಲ್ಲಿ ಒಳಪಟ್ಟಿರುತ್ತದೆ ಮತ್ತು ಕಂಪೈಲರ್‌ಗೆ ಸುಳಿವು ನೀಡಲು ಇದು ಒಂದು ಕಾರಣವಾಗಿದೆ.
ಮುಂದೆ ಏನಾಯಿತು?
ನಂತರ ನಾನು ಇತರ ಮೊನಾಡ್‌ಗಳೊಂದಿಗೆ ಹಾಪ್‌ಕ್ರಾಫ್ಟ್-ಕಾರ್ಪ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಿದೆ ಮತ್ತು ಅದು ಕಾರ್ಯಕ್ರಮದ ಅಂತ್ಯವಾಗಿತ್ತು.
Google ಸಮ್ಮರ್ ಆಫ್ ಕೋಡ್‌ಗೆ ಧನ್ಯವಾದಗಳು, ನಾನು ಕ್ರಿಯಾತ್ಮಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್‌ನಲ್ಲಿ ಪ್ರಾಯೋಗಿಕ ಅನುಭವವನ್ನು ಪಡೆದುಕೊಂಡಿದ್ದೇನೆ, ಇದು ಮುಂದಿನ ಬೇಸಿಗೆಯಲ್ಲಿ ಜೇನ್ ಸ್ಟ್ರೀಟ್‌ನಲ್ಲಿ ಇಂಟರ್ನ್‌ಶಿಪ್ ಪಡೆಯಲು ನನಗೆ ಸಹಾಯ ಮಾಡಿತು (ಈ ಸ್ಥಳವು ಹಬರ್‌ನ ಜ್ಞಾನವುಳ್ಳ ಪ್ರೇಕ್ಷಕರಲ್ಲಿ ಎಷ್ಟು ಪ್ರಸಿದ್ಧವಾಗಿದೆ ಎಂದು ನನಗೆ ಖಚಿತವಿಲ್ಲ, ಆದರೆ ಇದು ಒಂದಾಗಿದೆ ನೀವು ಬೇಸಿಗೆಯಲ್ಲಿ ಕ್ರಿಯಾತ್ಮಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್‌ನಲ್ಲಿ ತೊಡಗಿಸಿಕೊಳ್ಳಬಹುದಾದ ಕೆಲವರಲ್ಲಿ), ಆದರೆ ಈ ಮಾದರಿಯನ್ನು ಪ್ರಾಯೋಗಿಕವಾಗಿ ಅನ್ವಯಿಸುವ ಅದ್ಭುತ ಜಗತ್ತನ್ನು ನನಗೆ ಪರಿಚಯಿಸಿದೆ, ಸಾಂಪ್ರದಾಯಿಕ ಭಾಷೆಗಳಲ್ಲಿನ ನನ್ನ ಅನುಭವಕ್ಕಿಂತ ಗಮನಾರ್ಹವಾಗಿ ಭಿನ್ನವಾಗಿದೆ.
ಮೂಲ: www.habr.com