ಕೆಲವು ದಿನಗಳ ಹಿಂದೆ ನಡೆದಿತ್ತು . JUG.ru ಗುಂಪಿನ ವ್ಯಕ್ತಿಗಳು ಕನಸಿನ ಸ್ಪೀಕರ್‌ಗಳನ್ನು ಆಹ್ವಾನಿಸಿದರು (ಲೆಸ್ಲಿ ಲ್ಯಾಂಪೋರ್ಟ್! ಕ್ಲಿಫ್ ಕ್ಲಿಕ್! ಮಾರ್ಟಿನ್ ಕ್ಲೆಪ್‌ಮನ್!) ಮತ್ತು ವಿತರಣೆ ವ್ಯವಸ್ಥೆಗಳು ಮತ್ತು ಕಂಪ್ಯೂಟಿಂಗ್‌ಗೆ ಎರಡು ದಿನಗಳನ್ನು ಮೀಸಲಿಟ್ಟರು. ಸಮ್ಮೇಳನದ ಮೂವರು ಪಾಲುದಾರರಲ್ಲಿ ಕೊಂಟೂರು ಒಬ್ಬರು. ನಾವು ಬೂತ್‌ನಲ್ಲಿ ಮಾತನಾಡಿದೆವು, ನಮ್ಮ ವಿತರಿಸಿದ ಸಂಗ್ರಹಣೆಯ ಕುರಿತು ಮಾತನಾಡಿದೆವು, ಬಿಂಗೊ ಆಡಿದೆವು ಮತ್ತು ಒಗಟುಗಳನ್ನು ಪರಿಹರಿಸಿದೆವು.
ಇದು ಅವರ ಪಠ್ಯದ ಲೇಖಕರಿಂದ ಕೊಂಟೂರ್ ಸ್ಟ್ಯಾಂಡ್‌ನಲ್ಲಿನ ಕಾರ್ಯಗಳ ವಿಶ್ಲೇಷಣೆಯೊಂದಿಗೆ ಪೋಸ್ಟ್ ಆಗಿದೆ. ಹೈಡ್ರಾದಲ್ಲಿ ಯಾರು ಇದ್ದರು - ಇದು ಆಹ್ಲಾದಕರ ಅನುಭವವನ್ನು ನೆನಪಿಟ್ಟುಕೊಳ್ಳಲು ನಿಮ್ಮ ಕಾರಣವಾಗಿದೆ, ಯಾರು ಇರಲಿಲ್ಲ - ನಿಮ್ಮ ಮೆದುಳನ್ನು ವಿಸ್ತರಿಸುವ ಅವಕಾಶ ದೊಡ್ಡ ಒ- ಸಂಕೇತ.
ತಮ್ಮ ನಿರ್ಧಾರವನ್ನು ಬರೆಯಲು ಫ್ಲಿಪ್‌ಚಾರ್ಟ್ ಅನ್ನು ಸ್ಲೈಡ್‌ಗಳಾಗಿ ಕಿತ್ತುಹಾಕಿದ ಭಾಗವಹಿಸುವವರು ಸಹ ಇದ್ದರು. ನಾನು ತಮಾಷೆ ಮಾಡುತ್ತಿಲ್ಲ - ಅವರು ಈ ಕಾಗದದ ರಾಶಿಯನ್ನು ಪರಿಶೀಲನೆಗಾಗಿ ಹಸ್ತಾಂತರಿಸಿದರು:
ಒಟ್ಟು ಮೂರು ಕಾರ್ಯಗಳು ಇದ್ದವು:
- ಲೋಡ್ ಬ್ಯಾಲೆನ್ಸಿಂಗ್ಗಾಗಿ ತೂಕದ ಮೂಲಕ ಪ್ರತಿಕೃತಿಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡುವ ಬಗ್ಗೆ
- ಇನ್-ಮೆಮೊರಿ ಡೇಟಾಬೇಸ್ ವಿರುದ್ಧ ಪ್ರಶ್ನೆ ಫಲಿತಾಂಶಗಳನ್ನು ವಿಂಗಡಿಸುವ ಬಗ್ಗೆ
- ರಿಂಗ್ ಟೋಪೋಲಜಿಯೊಂದಿಗೆ ವಿತರಿಸಿದ ವ್ಯವಸ್ಥೆಯಲ್ಲಿ ರಾಜ್ಯದ ವರ್ಗಾವಣೆಯ ಮೇಲೆ
ಕಾರ್ಯ 1. ಕ್ಲಸ್ಟರ್ ಕ್ಲೈಂಟ್
ವಿತರಿಸಿದ ವ್ಯವಸ್ಥೆಯ N ತೂಕದ ಪ್ರತಿಕೃತಿಗಳಿಂದ K ಯ ಸಮರ್ಥ ಆಯ್ಕೆಗಾಗಿ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತಾಪಿಸುವುದು ಅಗತ್ಯವಾಗಿತ್ತು:
N ನೋಡ್‌ಗಳ ಬೃಹತ್ ಪ್ರಮಾಣದಲ್ಲಿ ವಿತರಿಸಲಾದ ಕ್ಲಸ್ಟರ್‌ಗಾಗಿ ಕ್ಲೈಂಟ್ ಲೈಬ್ರರಿಯನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸಲು ನಿಮ್ಮ ತಂಡವು ಕಾರ್ಯ ನಿರ್ವಹಿಸುತ್ತದೆ. ಲೈಬ್ರರಿಯು ನೋಡ್‌ಗಳಿಗೆ ಸಂಬಂಧಿಸಿದ ವಿವಿಧ ಮೆಟಾಡೇಟಾವನ್ನು ಟ್ರ್ಯಾಕ್ ಮಾಡುತ್ತದೆ (ಉದಾ, ಅವುಗಳ ಲೇಟೆನ್ಸಿಗಳು, 4xx/5xx ಪ್ರತಿಕ್ರಿಯೆ ದರಗಳು, ಇತ್ಯಾದಿ.) ಮತ್ತು ಫ್ಲೋಟಿಂಗ್ ಪಾಯಿಂಟ್ ತೂಕವನ್ನು W1..WN ಅನ್ನು ನಿಯೋಜಿಸುತ್ತದೆ. ಏಕಕಾಲೀನ ಕಾರ್ಯನಿರ್ವಹಣೆಯ ಕಾರ್ಯತಂತ್ರವನ್ನು ಬೆಂಬಲಿಸಲು, ಗ್ರಂಥಾಲಯವು ಯಾದೃಚ್ಛಿಕವಾಗಿ N ನೋಡ್‌ಗಳ K ಅನ್ನು ಆಯ್ಕೆ ಮಾಡಲು ಸಾಧ್ಯವಾಗುತ್ತದೆ-ಆಯ್ಕೆಯಾಗುವ ಅವಕಾಶವು ನೋಡ್‌ನ ತೂಕಕ್ಕೆ ಅನುಗುಣವಾಗಿರಬೇಕು.
ನೋಡ್‌ಗಳನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಆಯ್ಕೆ ಮಾಡಲು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತಾಪಿಸಿ. ದೊಡ್ಡ O ಸಂಕೇತವನ್ನು ಬಳಸಿಕೊಂಡು ಅದರ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆಯನ್ನು ಅಂದಾಜು ಮಾಡಿ.
ಎಲ್ಲವೂ ಇಂಗ್ಲಿಷ್‌ನಲ್ಲಿ ಏಕೆ?
ಏಕೆಂದರೆ ಈ ರೂಪದಲ್ಲಿ ಸಮ್ಮೇಳನದಲ್ಲಿ ಭಾಗವಹಿಸುವವರು ಅವರೊಂದಿಗೆ ಹೋರಾಡಿದರು ಮತ್ತು ಇಂಗ್ಲಿಷ್ ಹೈಡ್ರಾ ಅಧಿಕೃತ ಭಾಷೆಯಾಗಿತ್ತು. ಕಾರ್ಯಗಳು ಈ ರೀತಿ ಕಾಣುತ್ತವೆ:
ಪೇಪರ್ ಮತ್ತು ಪೆನ್ಸಿಲ್ ತೆಗೆದುಕೊಳ್ಳಿ, ಯೋಚಿಸಿ, ಈಗಿನಿಂದಲೇ ಸ್ಪಾಯ್ಲರ್‌ಗಳನ್ನು ತೆರೆಯಲು ಹೊರದಬ್ಬಬೇಡಿ 🙂
ಪರಿಹಾರದ ವಿಶ್ಲೇಷಣೆ (ವಿಡಿಯೋ)
5:53 ರಿಂದ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ, ಕೇವಲ 4 ನಿಮಿಷಗಳು:
ಮತ್ತು ಫ್ಲಿಪ್‌ಚಾರ್ಟ್ ಹೊಂದಿರುವ ವ್ಯಕ್ತಿಗಳು ತಮ್ಮ ಪರಿಹಾರವನ್ನು ಹೇಗೆ ರೂಪಿಸಿದರು ಎಂಬುದು ಇಲ್ಲಿದೆ:
ಪರಿಹಾರದ ವಿಶ್ಲೇಷಣೆ (ಪಠ್ಯ)
ಕೆಳಗಿನ ಪರಿಹಾರವು ಮೇಲ್ಮೈಯಲ್ಲಿದೆ: ಎಲ್ಲಾ ಪ್ರತಿಕೃತಿಗಳ ತೂಕವನ್ನು ಒಟ್ಟುಗೂಡಿಸಿ, 0 ರಿಂದ ಎಲ್ಲಾ ತೂಕಗಳ ಮೊತ್ತಕ್ಕೆ ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಯನ್ನು ರಚಿಸಿ, ನಂತರ 0 ರಿಂದ (i-1) ನೇವರೆಗಿನ ಪ್ರತಿಕೃತಿ ತೂಕದ ಮೊತ್ತವನ್ನು i-ಪ್ರತಿಕೃತಿಯನ್ನು ಆಯ್ಕೆಮಾಡಿ ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಗಿಂತ ಕಡಿಮೆ, ಮತ್ತು 0 ರಿಂದ i-th ವರೆಗಿನ ಪ್ರತಿರೂಪದ ತೂಕದ ಮೊತ್ತ - ಅದಕ್ಕಿಂತ ಹೆಚ್ಚು. ಆದ್ದರಿಂದ ಒಂದು ಪ್ರತಿಕೃತಿಯನ್ನು ಆಯ್ಕೆ ಮಾಡಲು ಸಾಧ್ಯವಾಗುತ್ತದೆ, ಮತ್ತು ಮುಂದಿನದನ್ನು ಆಯ್ಕೆ ಮಾಡಲು, ಆಯ್ಕೆಮಾಡಿದ ಪ್ರತಿಕೃತಿಯನ್ನು ಪರಿಗಣಿಸದೆ ನೀವು ಸಂಪೂರ್ಣ ಕಾರ್ಯವಿಧಾನವನ್ನು ಪುನರಾವರ್ತಿಸಬೇಕಾಗುತ್ತದೆ. ಅಂತಹ ಅಲ್ಗಾರಿದಮ್ನೊಂದಿಗೆ, ಒಂದು ಪ್ರತಿಕೃತಿಯನ್ನು ಆಯ್ಕೆಮಾಡುವ ಸಂಕೀರ್ಣತೆಯು O(N), K ಪ್ರತಿಕೃತಿಗಳನ್ನು ಆಯ್ಕೆಮಾಡುವ ಸಂಕೀರ್ಣತೆಯು O(N K) ~ O(N2) ಆಗಿದೆ.
ಕ್ವಾಡ್ರಾಟಿಕ್ ಸಂಕೀರ್ಣತೆ ಕೆಟ್ಟದಾಗಿದೆ, ಆದರೆ ಅದನ್ನು ಸುಧಾರಿಸಬಹುದು. ಇದನ್ನು ಮಾಡಲು, ನಾವು ನಿರ್ಮಿಸುತ್ತೇವೆ ತೂಕದ ಮೊತ್ತಗಳಿಗೆ. lg N ನ ಆಳದ ಮರವನ್ನು ಪಡೆಯಲಾಗುತ್ತದೆ, ಅದರ ಎಲೆಗಳಲ್ಲಿ ಪ್ರತಿಕೃತಿ ತೂಕ ಇರುತ್ತದೆ, ಮತ್ತು ಉಳಿದ ನೋಡ್‌ಗಳಲ್ಲಿ - ಭಾಗಶಃ ಮೊತ್ತಗಳು, ಮರದ ಮೂಲದಲ್ಲಿರುವ ಎಲ್ಲಾ ತೂಕಗಳ ಮೊತ್ತದವರೆಗೆ. ಮುಂದೆ, ನಾವು 0 ರಿಂದ ಎಲ್ಲಾ ತೂಕಗಳ ಮೊತ್ತಕ್ಕೆ ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಯನ್ನು ರಚಿಸುತ್ತೇವೆ, i-th ಪ್ರತಿಕೃತಿಯನ್ನು ಕಂಡುಹಿಡಿಯುತ್ತೇವೆ, ಅದನ್ನು ಮರದಿಂದ ತೆಗೆದುಹಾಕಿ ಮತ್ತು ಉಳಿದ ಪ್ರತಿಕೃತಿಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವ ವಿಧಾನವನ್ನು ಪುನರಾವರ್ತಿಸುತ್ತೇವೆ. ಈ ಅಲ್ಗಾರಿದಮ್ನೊಂದಿಗೆ, ಮರವನ್ನು ನಿರ್ಮಿಸುವ ಸಂಕೀರ್ಣತೆಯು O(N), i-th ಪ್ರತಿಕೃತಿಯನ್ನು ಕಂಡುಹಿಡಿಯುವ ಮತ್ತು ಅದನ್ನು ಮರದಿಂದ ತೆಗೆದುಹಾಕುವ ಸಂಕೀರ್ಣತೆ O(lg N), K ಪ್ರತಿಕೃತಿಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡುವ ಸಂಕೀರ್ಣತೆ O(N + K lg N) ~ O(N lg N) .
ಲೀನಿಯರ್-ಲಾಗ್ ಸಂಕೀರ್ಣತೆಯು ಕ್ವಾಡ್ರಾಟಿಕ್ ಸಂಕೀರ್ಣತೆಗಿಂತ ಉತ್ತಮವಾಗಿದೆ, ವಿಶೇಷವಾಗಿ ದೊಡ್ಡ ಕೆ.
ಇದು ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ ಯೋಜನೆಯಿಂದ ಕ್ಲಸ್ಟರ್ ಕ್ಲೈಂಟ್ ಗ್ರಂಥಾಲಯಗಳು "". (ಅಲ್ಲಿ, ಮರವನ್ನು O(N lg N) ನಲ್ಲಿ ನಿರ್ಮಿಸಲಾಗಿದೆ, ಆದರೆ ಇದು ಅಲ್ಗಾರಿದಮ್‌ನ ಅಂತಿಮ ಸಂಕೀರ್ಣತೆಯ ಮೇಲೆ ಪರಿಣಾಮ ಬೀರುವುದಿಲ್ಲ.)
ಕಾರ್ಯ 2. ಜೀಬ್ರಾ
ಅನಿಯಂತ್ರಿತ ಸೂಚ್ಯಂಕವಲ್ಲದ ಕ್ಷೇತ್ರದಿಂದ ಮೆಮೊರಿಯಲ್ಲಿ ದಾಖಲೆಗಳನ್ನು ಸಮರ್ಥವಾಗಿ ವಿಂಗಡಿಸಲು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತಾಪಿಸುವುದು ಅಗತ್ಯವಾಗಿತ್ತು:
ನಿಮ್ಮ ತಂಡವು ಛಿದ್ರಗೊಂಡ ಇನ್-ಮೆಮೊರಿ ಡಾಕ್ಯುಮೆಂಟ್ ಡೇಟಾಬೇಸ್ ಅನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸುವ ಕಾರ್ಯವನ್ನು ಹೊಂದಿದೆ. M (ಸಾಮಾನ್ಯವಾಗಿ N <100 << M) ಗಾತ್ರದ ಸಂಗ್ರಹದಿಂದ ಅನಿಯಂತ್ರಿತ (ಸೂಚಿಕೆ ಮಾಡದ) ಸಂಖ್ಯಾ ಕ್ಷೇತ್ರದಿಂದ ವಿಂಗಡಿಸಲಾದ ಉನ್ನತ N ದಾಖಲೆಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದು ಸಾಮಾನ್ಯ ಕೆಲಸದ ಹೊರೆಯಾಗಿದೆ. ಉನ್ನತ S ಡಾಕ್ಯುಮೆಂಟ್‌ಗಳನ್ನು (S ~ N) ಬಿಟ್ಟುಬಿಟ್ಟ ನಂತರ ಉನ್ನತ N ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದು ಸ್ವಲ್ಪ ಕಡಿಮೆ ಸಾಮಾನ್ಯ ಕೆಲಸದ ಹೊರೆಯಾಗಿದೆ.
ಅಂತಹ ಪ್ರಶ್ನೆಗಳನ್ನು ಸಮರ್ಥವಾಗಿ ಕಾರ್ಯಗತಗೊಳಿಸಲು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತಾಪಿಸಿ. ಸರಾಸರಿ ಪ್ರಕರಣ ಮತ್ತು ಕೆಟ್ಟ ಸನ್ನಿವೇಶಗಳಲ್ಲಿ ದೊಡ್ಡ O ಸಂಕೇತವನ್ನು ಬಳಸಿಕೊಂಡು ಅದರ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆಯನ್ನು ಅಂದಾಜು ಮಾಡಿ.
ಪರಿಹಾರದ ವಿಶ್ಲೇಷಣೆ (ವಿಡಿಯೋ)
34:50 ರಿಂದ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ, ಕೇವಲ 6 ನಿಮಿಷಗಳು:
ಪರಿಹಾರದ ವಿಶ್ಲೇಷಣೆ (ಪಠ್ಯ)
ಮೇಲ್ಮೈ ಪರಿಹಾರ: ಎಲ್ಲಾ ದಾಖಲೆಗಳನ್ನು ವಿಂಗಡಿಸಿ (ಉದಾಹರಣೆಗೆ ), ನಂತರ N+S ದಾಖಲೆಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳಿ. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ವಿಂಗಡಣೆಯ ಸಂಕೀರ್ಣತೆಯು ಸರಾಸರಿ O (M lg M), ಕೆಟ್ಟ O (M2) ನಲ್ಲಿದೆ.
ಎಲ್ಲಾ M ದಾಖಲೆಗಳನ್ನು ವಿಂಗಡಿಸುವುದು ಮತ್ತು ಅವುಗಳಲ್ಲಿ ಒಂದು ಸಣ್ಣ ಭಾಗವನ್ನು ಮಾತ್ರ ತೆಗೆದುಕೊಳ್ಳುವುದು ಅಸಮರ್ಥವಾಗಿದೆ ಎಂಬುದು ಸ್ಪಷ್ಟವಾಗಿದೆ. ಎಲ್ಲಾ ದಾಖಲೆಗಳನ್ನು ವಿಂಗಡಿಸದಿರುವ ಸಲುವಾಗಿ, ಅಲ್ಗಾರಿದಮ್ ಸೂಕ್ತವಾಗಿದೆ , ಇದು ಬಯಸಿದ ದಾಖಲೆಗಳ N + S ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ (ಅವುಗಳನ್ನು ಯಾವುದೇ ಅಲ್ಗಾರಿದಮ್ ಮೂಲಕ ವಿಂಗಡಿಸಬಹುದು). ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಸಂಕೀರ್ಣತೆಯು ಸರಾಸರಿ O(M) ಗೆ ಕಡಿಮೆಯಾಗುತ್ತದೆ, ಆದರೆ ಕೆಟ್ಟ ಪ್ರಕರಣವು ಒಂದೇ ಆಗಿರುತ್ತದೆ.
ಆದಾಗ್ಯೂ, ನೀವು ಅದನ್ನು ಇನ್ನಷ್ಟು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಮಾಡಬಹುದು - ಅಲ್ಗಾರಿದಮ್ ಬಳಸಿ . ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಮೊದಲ N+S ಡಾಕ್ಯುಮೆಂಟ್‌ಗಳನ್ನು ಕನಿಷ್ಠ ಅಥವಾ ಗರಿಷ್ಠ-ರಾಶಿಗೆ ಸೇರಿಸಲಾಗುತ್ತದೆ (ವಿಂಗಡಣೆ ದಿಕ್ಕನ್ನು ಅವಲಂಬಿಸಿ), ಮತ್ತು ನಂತರ ಪ್ರತಿ ಮುಂದಿನ ಡಾಕ್ಯುಮೆಂಟ್ ಅನ್ನು ಮರದ ಮೂಲಕ್ಕೆ ಹೋಲಿಸಲಾಗುತ್ತದೆ, ಇದು ಪ್ರಸ್ತುತ ಕನಿಷ್ಠ ಅಥವಾ ಗರಿಷ್ಠ ದಾಖಲೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಮತ್ತು ಅಗತ್ಯವಿದ್ದರೆ ಮರಕ್ಕೆ ಸೇರಿಸಲಾಗುತ್ತದೆ. . ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ಸಂಕೀರ್ಣತೆ, ನೀವು ನಿರಂತರವಾಗಿ ಮರವನ್ನು ಮರುನಿರ್ಮಾಣ ಮಾಡಬೇಕಾದಾಗ, O (M lg M), ಕ್ವಿಕ್‌ಸೆಲೆಕ್ಟ್‌ನಂತೆ ಸರಾಸರಿ ಸಂಕೀರ್ಣತೆ O (M).
ಆದಾಗ್ಯೂ, ಹೀಪ್ ಸ್ಟ್ರೀಮಿಂಗ್ ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿಯಾಗಿದೆ ಏಕೆಂದರೆ ಪ್ರಾಯೋಗಿಕವಾಗಿ ಹೆಚ್ಚಿನ ದಾಖಲೆಗಳನ್ನು ಅದರ ಮೂಲ ಅಂಶದೊಂದಿಗೆ ಒಂದೇ ಹೋಲಿಕೆಯ ನಂತರ ರಾಶಿಯನ್ನು ಮರುನಿರ್ಮಾಣ ಮಾಡದೆಯೇ ತಿರಸ್ಕರಿಸಬಹುದು. ಅಂತಹ ವಿಂಗಡಣೆಯನ್ನು ಕೊಂಟೂರಿನಲ್ಲಿ ಅಭಿವೃದ್ಧಿಪಡಿಸಿದ ಮತ್ತು ಬಳಸಲಾದ ಜೀಬ್ರಾ ಇನ್-ಮೆಮೊರಿ ಡಾಕ್ಯುಮೆಂಟ್ ಡೇಟಾಬೇಸ್‌ನಲ್ಲಿ ಅಳವಡಿಸಲಾಗಿದೆ.
ಕಾರ್ಯ 3. ರಾಜ್ಯ ವಿನಿಮಯಗಳು
ರಾಜ್ಯಗಳನ್ನು ಬದಲಾಯಿಸಲು ಅತ್ಯಂತ ಪರಿಣಾಮಕಾರಿ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತಾಪಿಸುವುದು ಅಗತ್ಯವಾಗಿತ್ತು:
N ನೋಡ್‌ಗಳ ವಿತರಿಸಿದ ಕ್ಲಸ್ಟರ್‌ಗಾಗಿ ಫ್ಯಾನ್ಸಿ ಸ್ಟೇಟ್ ಎಕ್ಸ್‌ಚೇಂಜ್ ಮೆಕ್ಯಾನಿಸಂ ಅನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸಲು ನಿಮ್ಮ ತಂಡವು ಕಾರ್ಯ ನಿರ್ವಹಿಸುತ್ತದೆ. i-th ನೋಡ್‌ನ ಸ್ಥಿತಿಯನ್ನು (i+1)-th ನೋಡ್‌ಗೆ ವರ್ಗಾಯಿಸಬೇಕು, N-th ನೋಡ್‌ನ ಸ್ಥಿತಿಯನ್ನು ಮೊದಲ ನೋಡ್‌ಗೆ ವರ್ಗಾಯಿಸಬೇಕು. ಎರಡು ನೋಡ್‌ಗಳು ತಮ್ಮ ಸ್ಥಿತಿಯನ್ನು ಪರಮಾಣುವಾಗಿ ವಿನಿಮಯ ಮಾಡಿಕೊಂಡಾಗ ಕೇವಲ ಬೆಂಬಲಿತ ಕಾರ್ಯಾಚರಣೆಯೆಂದರೆ ಸ್ಟೇಟ್ ಸ್ವಾಪ್. ಒಂದು ರಾಜ್ಯದ ಸ್ವಾಪ್ M ಮಿಲಿಸೆಕೆಂಡುಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಎಂದು ತಿಳಿದಿದೆ. ಪ್ರತಿಯೊಂದು ನೋಡ್ ಯಾವುದೇ ಕ್ಷಣದಲ್ಲಿ ಒಂದೇ ರಾಜ್ಯದ ಸ್ವಾಪ್‌ನಲ್ಲಿ ಭಾಗವಹಿಸಲು ಸಾಧ್ಯವಾಗುತ್ತದೆ.
ಕ್ಲಸ್ಟರ್‌ನಲ್ಲಿ ಎಲ್ಲಾ ನೋಡ್‌ಗಳ ಸ್ಥಿತಿಗಳನ್ನು ವರ್ಗಾಯಿಸಲು ಎಷ್ಟು ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ?
ಪರಿಹಾರದ ವಿಶ್ಲೇಷಣೆ (ಪಠ್ಯ)
ಮೇಲ್ಮೈ ಪರಿಹಾರ: ಮೊದಲ ಮತ್ತು ಎರಡನೆಯ ಅಂಶದ ಸ್ಥಿತಿಗಳನ್ನು ವಿನಿಮಯ ಮಾಡಿಕೊಳ್ಳಿ, ನಂತರ ಮೊದಲ ಮತ್ತು ಮೂರನೇ, ನಂತರ ಮೊದಲ ಮತ್ತು ನಾಲ್ಕನೇ, ಇತ್ಯಾದಿ. ಪ್ರತಿ ವಿನಿಮಯದ ನಂತರ, ಒಂದು ಅಂಶದ ಸ್ಥಿತಿಯು ಅಪೇಕ್ಷಿತ ಸ್ಥಾನದಲ್ಲಿರುತ್ತದೆ. ನೀವು O(N) ಕ್ರಮಪಲ್ಲಟನೆಗಳನ್ನು ಮಾಡಬೇಕು ಮತ್ತು O(N M) ಸಮಯವನ್ನು ಕಳೆಯಬೇಕು.
ರೇಖೀಯ ಸಮಯವು ಉದ್ದವಾಗಿದೆ, ಆದ್ದರಿಂದ ನೀವು ಅಂಶಗಳ ಸ್ಥಿತಿಯನ್ನು ಜೋಡಿಯಾಗಿ ವಿನಿಮಯ ಮಾಡಿಕೊಳ್ಳಬಹುದು: ಮೊದಲನೆಯದು ಎರಡನೆಯದು, ಮೂರನೆಯದು ನಾಲ್ಕನೆಯದು, ಇತ್ಯಾದಿ. ಪ್ರತಿ ರಾಜ್ಯ ವಿನಿಮಯದ ನಂತರ, ಪ್ರತಿ ಎರಡನೇ ಅಂಶವು ಸರಿಯಾದ ಸ್ಥಾನದಲ್ಲಿರುತ್ತದೆ. ನೀವು O(lg N) ಕ್ರಮಪಲ್ಲಟನೆಗಳನ್ನು ಮಾಡಬೇಕು ಮತ್ತು O(M lg N) ಸಮಯವನ್ನು ಕಳೆಯಬೇಕು.
ಆದಾಗ್ಯೂ, ಶಿಫ್ಟ್ ಅನ್ನು ಇನ್ನಷ್ಟು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಮಾಡಲು ಸಾಧ್ಯವಿದೆ - ರೇಖಾತ್ಮಕವಾಗಿ ಅಲ್ಲ, ಆದರೆ ನಿರಂತರ ಸಮಯದಲ್ಲಿ. ಇದನ್ನು ಮಾಡಲು, ಮೊದಲ ಹಂತದಲ್ಲಿ, ನೀವು ಮೊದಲ ಅಂಶದ ಸ್ಥಿತಿಯನ್ನು ಕೊನೆಯದರೊಂದಿಗೆ ವಿನಿಮಯ ಮಾಡಿಕೊಳ್ಳಬೇಕು, ಎರಡನೆಯದು ಉಪಾಂತ್ಯದೊಂದಿಗೆ, ಮತ್ತು ಹೀಗೆ. ಕೊನೆಯ ಅಂಶದ ಸ್ಥಿತಿಯು ಸರಿಯಾದ ಸ್ಥಾನದಲ್ಲಿರುತ್ತದೆ. ಮತ್ತು ಈಗ ನಾವು ಎರಡನೇ ಅಂಶದ ಸ್ಥಿತಿಯನ್ನು ಕೊನೆಯದರೊಂದಿಗೆ ವಿನಿಮಯ ಮಾಡಿಕೊಳ್ಳಬೇಕಾಗಿದೆ, ಮೂರನೆಯದು ಅಂತಿಮ ಅಂಶದೊಂದಿಗೆ, ಇತ್ಯಾದಿ. ಈ ಸುತ್ತಿನ ವಿನಿಮಯದ ನಂತರ, ಎಲ್ಲಾ ಅಂಶಗಳ ಸ್ಥಿತಿಗಳು ಸರಿಯಾದ ಸ್ಥಾನದಲ್ಲಿರುತ್ತವೆ. ಒಟ್ಟು O(2M) ~ O(1) ಕ್ರಮಪಲ್ಲಟನೆಗಳು ಇರುತ್ತವೆ.
ಅಂತಹ ಪರಿಹಾರವು ಗಣಿತಶಾಸ್ತ್ರಜ್ಞನನ್ನು ಆಶ್ಚರ್ಯಗೊಳಿಸುವುದಿಲ್ಲ, ಅವರು ತಿರುಗುವಿಕೆಯು ಎರಡು ಅಕ್ಷೀಯ ಸಮ್ಮಿತಿಗಳ ಸಂಯೋಜನೆಯಾಗಿದೆ ಎಂದು ಇನ್ನೂ ನೆನಪಿಸಿಕೊಳ್ಳುತ್ತಾರೆ. ಮೂಲಕ, ಇದು ಒಂದು ಶಿಫ್ಟ್ಗೆ ಕ್ಷುಲ್ಲಕವಾಗಿ ಸಾಮಾನ್ಯೀಕರಿಸಲ್ಪಟ್ಟಿದೆ, ಆದರೆ K <N ಸ್ಥಾನಗಳಿಂದ. (ಎಷ್ಟು ನಿಖರವಾಗಿ ಕಾಮೆಂಟ್‌ಗಳಲ್ಲಿ ಬರೆಯಿರಿ.)
ನೀವು ಒಗಟುಗಳನ್ನು ಇಷ್ಟಪಟ್ಟಿದ್ದೀರಾ? ನಿಮಗೆ ಇತರ ಪರಿಹಾರಗಳು ತಿಳಿದಿದೆಯೇ? ಕಾಮೆಂಟ್‌ಗಳಲ್ಲಿ ಹಂಚಿಕೊಳ್ಳಿ.
ಮತ್ತು ಕೊನೆಯಲ್ಲಿ ಕೆಲವು ಉಪಯುಕ್ತ ಲಿಂಕ್‌ಗಳು ಇಲ್ಲಿವೆ:
- ಬಗ್ಗೆ ಇನ್ನಷ್ಟು ತಿಳಿಯಿರಿ ಬಾಹ್ಯರೇಖೆಯಲ್ಲಿ
- ಆಂತರಿಕ ದಾಖಲೆಗಳನ್ನು ನೋಡಿ ವಿತರಿಸಿದ ವ್ಯವಸ್ಥೆಗಳ ಬಗ್ಗೆ
- ವೀಡಿಯೊ ಉಪನ್ಯಾಸಗಳ ಸರಣಿಯನ್ನು ವೀಕ್ಷಿಸಿ»
- ನಮ್ಮ ಚಂದಾದಾರರಾಗಿ
ಮೂಲ: www.habr.com