Introselect
ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ಇಂಟ್ರೊಸೆಲೆಕ್ಟ್ ("ಅಂತರ್ದೃಷ್ಟಿಯ ಆಯ್ಕೆ" ಗಾಗಿ ಚಿಕ್ಕದಾಗಿದೆ) ಎಂಬುದು ಆಯ್ಕೆ ಕ್ರಮಾವಳಿಯಾಗಿದ್ದು, ಇದು ತ್ವರಿತ ಆಯ್ಕೆ ಮತ್ತು ಮೀಡಿಯನ್ಗಳ ಹೈಬ್ರಿಡ್ ಆಗಿದ್ದು, ಇದು ವೇಗದ ಸರಾಸರಿ ಕಾರ್ಯಕ್ಷಮತೆ ಮತ್ತು ಅತ್ಯುತ್ತಮ ಕೆಟ್ಟ-ಕೇಸ್ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ಹೊಂದಿದೆ. ಇಂಟ್ರೋಸೆಲೆಕ್ಟ್ ಇಂಟ್ರೋಸಾರ್ಟ್ ಸಾರ್ಟಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ಗೆ ಸಂಬಂಧಿಸಿದೆಃ ಇವು ಮೂಲಭೂತ ತ್ವರಿತ ಆಯ್ಕೆ ಮತ್ತು ತ್ವರಿತ ವಿಂಗಡಣೆ ಅಲ್ಗಾರಿದಮ್ಗಳ ಸದೃಶ ಪರಿಷ್ಕರಣೆಗಳಾಗಿವೆ, ಅವುಗಳಲ್ಲಿ ಎರಡೂ ತ್ವರಿತ ಅಲ್ಗಾರಿದಮ್ನೊಂದಿಗೆ ಪ್ರಾರಂಭವಾಗುತ್ತವೆ, ಇದು ಉತ್ತಮ ಸರಾಸರಿ ಕಾರ್ಯಕ್ಷಮತೆ ಮತ್ತು ಕಡಿಮೆ ಓವರ್ಹೆಡ್ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಆದರೆ ತ್ವರಿತ ಅಲ್ಗಾರಿದಮ್ ಸಾಕಷ್ಟು ವೇಗವಾಗಿ ಪ್ರಗತಿ ಹೊಂದದಿದ್ದರೆ ಅತ್ಯುತ್ತಮವಾದ ಕೆಟ್ಟ-ಕೇಸ್ ಅಲ್ಗಾರಿದಮ್ಗೆ (ಹೆಚ್ಚಿನ ಓವರ್ಹೆಡ್ನೊಂದಿಗೆ) ಹಿಂತಿರುಗುತ್ತದೆ. ಸಿ + + ಸ್ಟ್ಯಾಂಡರ್ಡ್ ಲೈಬ್ರರಿಗೆ ಸಾಮಾನ್ಯ ಕ್ರಮಾವಳಿಗಳನ್ನು ಒದಗಿಸುವ ಉದ್ದೇಶದಿಂದ ಡೇವಿಡ್ ಮುಸರ್ ಅವರು ಎರಡೂ ಕ್ರಮಾವಳಿಗಳನ್ನು ಪರಿಚಯಿಸಿದರು, ಇದು ವೇಗದ ಸರಾಸರಿ ಕಾರ್ಯಕ್ಷಮತೆ ಮತ್ತು ಅತ್ಯುತ್ತಮ ಕೆಟ್ಟ-ಕೇಸ್ ಕಾರ್ಯಕ್ಷಮತೆ ಎರಡನ್ನೂ ಹೊಂದಿದೆ, ಹೀಗಾಗಿ ಕಾರ್ಯಕ್ಷಮತೆಯ ಅವಶ್ಯಕತೆಗಳನ್ನು ಬಿಗಿಗೊಳಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಹೆಚ್ಚಿನ ಸಿ + + ಸ್ಟ್ಯಾಂಡರ್ಡ್ ಲೈಬ್ರರಿ ಅನುಷ್ಠಾನಗಳಲ್ಲಿ, ವಿಭಿನ್ನ "ಇಂಟ್ರೊಸೆಲೆಕ್ಟ್" ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸಲಾಗುತ್ತದೆ, ಇದು ತ್ವರಿತ ಆಯ್ಕೆ ಮತ್ತು ಹೀಪ್ಸೆಲೆಕ್ಟ್ ಅನ್ನು ಸಂಯೋಜಿಸುತ್ತದೆ ಮತ್ತು ಒ (ಎನ್ ಲಾಗ್ ಎನ್) ನ ಕೆಟ್ಟ-ಕೇಸ್ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯವನ್ನು ಹೊಂದಿದೆ. 2022ರಂತೆ, ಸಿ + + ಕರಡು ಮಾನದಂಡವು ಅತ್ಯಂತ ಕೆಟ್ಟ ಕಾರ್ಯಕ್ಷಮತೆಯ ಅವಶ್ಯಕತೆಗಳನ್ನು ಹೊಂದಿಲ್ಲ, ಆದ್ದರಿಂದ ಅಂತಹ ಆಯ್ಕೆಯನ್ನು ಅನುಮತಿಸುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ಸ್ ಇಂಟ್ರೊಸಾರ್ಟ್ ಕ್ವಿಕ್ಸಾರ್ಟ್ಗೆ ಹೋಲಿಸಬಹುದಾದ ಪ್ರಾಯೋಗಿಕ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ಸಾಧಿಸುತ್ತದೆ ಮತ್ತು ಕ್ವಿಕ್ಸಾರ್ಟ್ ಮತ್ತು ಹೀಪ್ಸೋರ್ಟ್ನ ಹೈಬ್ರಿಡ್ ಅನ್ನು ರಚಿಸುವ ಮೂಲಕ ಒ (ಎನ್ ಲಾಗ್ ಎನ್) ಕೆಟ್ಟ-ಕೇಸ್ ನಡವಳಿಕೆಯನ್ನು ಸಂರಕ್ಷಿಸುತ್ತದೆ. ಇಂಟ್ರೋಸಾರ್ಟ್ ಕ್ವಿಕ್ಸಾರ್ಟ್ನೊಂದಿಗೆ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ, ಆದ್ದರಿಂದ ಕ್ವಿಕ್ಸಾರ್ಟ್ ಕೆಲಸ ಮಾಡಿದರೆ ಅದು ಕ್ವಿಕ್ಸಾರ್ಟ್ನಂತೆಯೇ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ಸಾಧಿಸುತ್ತದೆ ಮತ್ತು ಕ್ವಿಕ್ಸಾರ್ಟ್ ಸಾಕಷ್ಟು ವೇಗವಾಗಿ ಪ್ರಗತಿ ಹೊಂದದಿದ್ದರೆ ಅದು ಹೀಪ್ಸಾರ್ಟ್ಗೆ ಹಿಂತಿರುಗುತ್ತದೆ (ಇದು ಅತ್ಯುತ್ತಮವಾದ ಕೆಟ್ಟ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ಹೊಂದಿದೆ). ಅಂತೆಯೇ, ಇಂಟ್ರೊಸೆಲೆಕ್ಟ್ ತ್ವರಿತ ಆಯ್ಕೆಯಂತೆಯೇ ಕಾರ್ಯಕ್ಷಮತೆಯೊಂದಿಗೆ ಕೆಟ್ಟ-ಕೇಸ್ ರೇಖೀಯ ಆಯ್ಕೆಯನ್ನು ಸಾಧಿಸಲು ಮೀಡಿಯನ್ಗಳೊಂದಿಗೆ ತ್ವರಿತ ಆಯ್ಕೆಯನ್ನು ಸಂಯೋಜಿಸುತ್ತದೆ. ಇಂಟ್ರೊಸೆಲೆಕ್ಟ್ ತ್ವರಿತವಾಗಿ ಆಯ್ಕೆ ಮಾಡುವುದರೊಂದಿಗೆ ಆಶಾದಾಯಕವಾಗಿ ಪ್ರಾರಂಭವಾಗುವ ಮೂಲಕ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ ಮತ್ತು ಸಾಕಷ್ಟು ಪ್ರಗತಿಯನ್ನು ಸಾಧಿಸದೆ ಹಲವಾರು ಬಾರಿ ಪುನರಾವರ್ತನೆಯಾದರೆ ಕೆಟ್ಟ-ಕೇಸ್ ರೇಖೀಯ-ಸಮಯ ಆಯ್ಕೆ ಅಲ್ಗಾರಿದಮ್ಗೆ (ಮೀಡಿಯನ್ಸ್ ಅಲ್ಗಾರಿದಮ್ನ ಬ್ಲಮ್-ಫ್ಲಾಯ್ಡ್-ಪ್ರಾಟ್-ರಿವೆಸ್ಟ್-ಟಾರ್ಜನ್ ಮೀಡಿಯನ್) ಮಾತ್ರ ಬದಲಾಯಿಸುತ್ತದೆ. ಸ್ವಿಚಿಂಗ್ ತಂತ್ರವು ಅಲ್ಗಾರಿದಮ್ನ ಮುಖ್ಯ ತಾಂತ್ರಿಕ ವಿಷಯವಾಗಿದೆ. ಪುನರಾವರ್ತನೆಯನ್ನು ಸ್ಥಿರವಾದ ಆಳಕ್ಕೆ ಸೀಮಿತಗೊಳಿಸುವುದು ಸಾಕಾಗುವುದಿಲ್ಲ, ಏಕೆಂದರೆ ಇದು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಎಲ್ಲಾ ಸಾಕಷ್ಟು ದೊಡ್ಡ ಪಟ್ಟಿಗಳನ್ನು ಬದಲಾಯಿಸುವಂತೆ ಮಾಡುತ್ತದೆ. ಮುಸರ್ ಒಂದೆರಡು ಸರಳ ವಿಧಾನಗಳನ್ನು ಚರ್ಚಿಸುತ್ತಾರೆಃ ಇಲ್ಲಿಯವರೆಗೆ ಸಂಸ್ಕರಿಸಿದ ಉಪವಿಭಾಗಗಳ ಗಾತ್ರಗಳ ಪಟ್ಟಿಯ ಮೇಲೆ ನಿಗಾ ಇಡಿ. ಪಟ್ಟಿಯ ಗಾತ್ರವನ್ನು ಅರ್ಧದಷ್ಟು ಕಡಿಮೆ ಮಾಡದೆ ಯಾವುದೇ ಹಂತದಲ್ಲಿ ಕೆ ಪುನರಾವರ್ತಿತ ಕರೆಗಳನ್ನು ಮಾಡಿದರೆ, ಕೆಲವು ಸಣ್ಣ ಧನಾತ್ಮಕ ಕೆಗಾಗಿ, ಕೆಟ್ಟ-ಕೇಸ್ ರೇಖೀಯ ಅಲ್ಗಾರಿದಮ್ಗೆ ಬದಲಾಯಿಸಿ. ಇಲ್ಲಿಯವರೆಗೆ ರಚಿಸಲಾದ ಎಲ್ಲಾ ವಿಭಾಗಗಳ ಗಾತ್ರವನ್ನು ಒಟ್ಟುಗೂಡಿಸಿ. ಇದು ಪಟ್ಟಿಯ ಗಾತ್ರವನ್ನು ಕೆಲವು ಸಣ್ಣ ಧನಾತ್ಮಕ ಸ್ಥಿರಾಂಕ k ಅನ್ನು ಮೀರಿದರೆ, ಕೆಟ್ಟ-ಕೇಸ್ ರೇಖೀಯ ಅಲ್ಗಾರಿದಮ್ಗೆ ಬದಲಾಯಿಸಿ. ಈ ಮೊತ್ತವನ್ನು ಒಂದೇ ಸ್ಕೇಲಾರ್ ವೇರಿಯೇಬಲ್ನಲ್ಲಿ ಟ್ರ್ಯಾಕ್ ಮಾಡುವುದು ಸುಲಭ. ಎರಡೂ ವಿಧಾನಗಳು ಪುನರಾವರ್ತನೆಯ ಆಳವನ್ನು k′ log n′ = O (log n) ಗೆ ಮತ್ತು ಒಟ್ಟು ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯವನ್ನು O (n) ಗೆ ಸೀಮಿತಗೊಳಿಸುತ್ತವೆ. ಇಂಟ್ರೊಸೆಲೆಕ್ಟ್ ಬಗ್ಗೆ ಹೆಚ್ಚಿನ ಸಂಶೋಧನೆಗಳು ಬರಲಿವೆ ಎಂದು ಲೇಖನವು ಸೂಚಿಸಿತು, ಆದರೆ ಲೇಖಕರು ಅಂತಹ ಯಾವುದೇ ಹೆಚ್ಚಿನ ಸಂಶೋಧನೆಯನ್ನು ಪ್ರಕಟಿಸದೆ 2007 ರಲ್ಲಿ ನಿವೃತ್ತರಾದರು. ಫ್ಲಾಯ್ಡ್-ರಿವೆಸ್ಟ್ ಅಲ್ಗಾರಿದಮ್ ಉಲ್ಲೇಖಗಳ ಆಯ್ಕೆ ಅಲ್ಗಾರಿದಮ್ಗಳನ್ನು ಸಹ ನೋಡಿ