Mark–compact algorithm
ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ಮಾರ್ಕ್-ಕಾಂಪ್ಯಾಕ್ಟ್ ಅಲ್ಗಾರಿದಮ್ ಎನ್ನುವುದು ತಲುಪಲಾಗದ ಮೆಮೊರಿಯನ್ನು ಮರುಪಡೆಯಲು ಬಳಸುವ ಒಂದು ರೀತಿಯ ಕಸ ಸಂಗ್ರಹಣಾ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಮಾರ್ಕ್-ಕಾಂಪ್ಯಾಕ್ಟ್ ಅಲ್ಗಾರಿದಮ್ಗಳನ್ನು ಮಾರ್ಕ್-ಸ್ವೀಪ್ ಅಲ್ಗಾರಿದಮ್ ಮತ್ತು ಚೆನಿಯ ಕಾಪಿ ಅಲ್ಗಾರಿದಮ್ನ ಸಂಯೋಜನೆ ಎಂದು ಪರಿಗಣಿಸಬಹುದು. ಮೊದಲು, ತಲುಪಬಹುದಾದ ವಸ್ತುಗಳನ್ನು ಗುರುತಿಸಲಾಗುತ್ತದೆ, ನಂತರ ಸಂಕುಚಿತಗೊಳಿಸುವ ಹಂತವು ತಲುಪಬಹುದಾದ (ಗುರುತಿಸಲಾದ) ವಸ್ತುಗಳನ್ನು ರಾಶಿ ಪ್ರದೇಶದ ಪ್ರಾರಂಭದ ಕಡೆಗೆ ಸ್ಥಳಾಂತರಿಸುತ್ತದೆ. ಸಂಕೀರ್ಣ ತ್ಯಾಜ್ಯ ಸಂಗ್ರಹವನ್ನು ಆಧುನಿಕ ಜೆವಿಎಂಗಳು, ಮೈಕ್ರೋಸಾಫ್ಟ್ನ ಕಾಮನ್ ಲ್ಯಾಂಗ್ವೇಜ್ ರನ್ಟೈಮ್ ಮತ್ತು ಗ್ಲ್ಯಾಸ್ಗೋ ಹ್ಯಾಸ್ಕೆಲ್ ಕಂಪೈಲರ್ ಬಳಸುತ್ತವೆ. ಅಲ್ಗಾರಿದಮ್ಗಳು ಮಾರ್ಕ್-ಸ್ವೀಪ್ ಅಲ್ಗಾರಿದಮ್ನಂತೆಯೇ ಜೀವಂತ ವಸ್ತುಗಳನ್ನು ರಾಶಿಯಲ್ಲಿ ಗುರುತಿಸಿದ ನಂತರ, ರಾಶಿಯು ಆಗಾಗ್ಗೆ ವಿಭಜನೆಯಾಗುತ್ತದೆ. ಮಾರ್ಕ್-ಕಾಂಪ್ಯಾಕ್ಟ್ ಕ್ರಮಾವಳಿಗಳ ಗುರಿಯು ಜೀವಂತ ವಸ್ತುಗಳನ್ನು ಒಟ್ಟಿಗೆ ಮೆಮೊರಿಯಲ್ಲಿ ಬದಲಾಯಿಸುವುದು, ಆದ್ದರಿಂದ ವಿಘಟನೆಯನ್ನು ತೆಗೆದುಹಾಕಲಾಗುತ್ತದೆ. ಚಲಿಸಲಾದ ವಸ್ತುಗಳಿಗೆ ಎಲ್ಲಾ ಪಾಯಿಂಟರ್ಗಳನ್ನು ಸರಿಯಾಗಿ ನವೀಕರಿಸುವುದು ಸವಾಲಾಗಿದೆ, ಅವುಗಳಲ್ಲಿ ಹೆಚ್ಚಿನವು ಸಂಕೋಚನದ ನಂತರ ಹೊಸ ಮೆಮೊರಿ ವಿಳಾಸಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಪಾಯಿಂಟರ್ ನವೀಕರಣಗಳನ್ನು ನಿರ್ವಹಿಸುವ ಸಮಸ್ಯೆಯನ್ನು ವಿವಿಧ ರೀತಿಯಲ್ಲಿ ನಿರ್ವಹಿಸಲಾಗುತ್ತದೆ. ಟೇಬಲ್-ಆಧಾರಿತ ಸಂಕೋಚನವನ್ನು ಟೇಬಲ್-ಆಧಾರಿತ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಮೊದಲ ಬಾರಿಗೆ 1967 ರಲ್ಲಿ ಹ್ಯಾಡನ್ ಮತ್ತು ವೇಟ್ ವಿವರಿಸಿದ್ದಾರೆ. ಇದು ರಾಶಿಯಲ್ಲಿ ಜೀವಂತ ವಸ್ತುಗಳ ಸಾಪೇಕ್ಷ ನಿಯೋಜನೆಯನ್ನು ಸಂರಕ್ಷಿಸುತ್ತದೆ ಮತ್ತು ಕೇವಲ ಸ್ಥಿರವಾದ ಓವರ್ಹೆಡ್ನ ಅಗತ್ಯವಿರುತ್ತದೆ. ಸಂಕೋಚನವು ರಾಶಿಯ ಕೆಳಗಿನಿಂದ (ಕಡಿಮೆ ವಿಳಾಸಗಳು) ಮೇಲ್ಭಾಗಕ್ಕೆ (ಹೆಚ್ಚಿನ ವಿಳಾಸಗಳು) ಮುಂದುವರಿಯುತ್ತದೆ. ಲೈವ್ (ಅಂದರೆ, ಗುರುತಿಸಲಾದ) ವಸ್ತುಗಳು ಎದುರಾದಾಗ, ಅವುಗಳನ್ನು ಲಭ್ಯವಿರುವ ಮೊದಲ ಕಡಿಮೆ ವಿಳಾಸಕ್ಕೆ ಸ್ಥಳಾಂತರಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಸ್ಥಳಾಂತರ ಮಾಹಿತಿಯ ಬ್ರೇಕ್ ಟೇಬಲ್ಗೆ ದಾಖಲೆಯನ್ನು ಸೇರಿಸಲಾಗುತ್ತದೆ. ಪ್ರತಿ ಜೀವಂತ ವಸ್ತುವಿಗೆ, ಬ್ರೇಕ್ ಟೇಬಲ್ನಲ್ಲಿನ ದಾಖಲೆಯು ಸಂಕೋಚನದ ಮೊದಲು ವಸ್ತುವಿನ ಮೂಲ ವಿಳಾಸವನ್ನು ಮತ್ತು ಸಂಕೋಚನದ ನಂತರ ಮೂಲ ವಿಳಾಸ ಮತ್ತು ಹೊಸ ವಿಳಾಸದ ನಡುವಿನ ವ್ಯತ್ಯಾಸವನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಬ್ರೇಕ್ ಟೇಬಲ್ ಅನ್ನು ಸಂಕುಚಿತಗೊಳಿಸಲಾಗುತ್ತಿರುವ ರಾಶಿಯಲ್ಲಿ ಸಂಗ್ರಹಿಸಲಾಗುತ್ತದೆ, ಆದರೆ ಬಳಕೆಯಾಗದ ಎಂದು ಗುರುತಿಸಲಾದ ಪ್ರದೇಶದಲ್ಲಿ. ಸಂಕೋಚನವು ಯಾವಾಗಲೂ ಯಶಸ್ವಿಯಾಗುತ್ತದೆ ಎಂದು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು, ರಾಶಿಯಲ್ಲಿನ ಕನಿಷ್ಠ ವಸ್ತುವಿನ ಗಾತ್ರವು ಬ್ರೇಕ್ ಟೇಬಲ್ ರೆಕಾರ್ಡ್ಗಿಂತ ದೊಡ್ಡದಾಗಿರಬೇಕು ಅಥವಾ ಅದೇ ಗಾತ್ರದಲ್ಲಿರಬೇಕು. ಸಂಕೋಚನವು ಮುಂದುವರೆದಂತೆ, ಸ್ಥಳಾಂತರಿಸಲಾದ ವಸ್ತುಗಳನ್ನು ರಾಶಿಯ ಕೆಳಭಾಗದಲ್ಲಿ ನಕಲಿಸಲಾಗುತ್ತದೆ. ಅಂತಿಮವಾಗಿ ಒಂದು ವಸ್ತುವನ್ನು ಬ್ರೇಕ್ ಟೇಬಲ್ ಆಕ್ರಮಿಸಿಕೊಂಡಿರುವ ಜಾಗಕ್ಕೆ ನಕಲಿಸಬೇಕಾಗುತ್ತದೆ, ಅದನ್ನು ಈಗ ಬೇರೆಡೆಗೆ ಸ್ಥಳಾಂತರಿಸಬೇಕು. ಬ್ರೇಕ್ ಟೇಬಲ್ನ ಈ ಚಲನೆಗಳು (ಲೇಖಕರು ಟೇಬಲ್ ಅನ್ನು ರೋಲಿಂಗ್ ಎಂದು ಕರೆಯುತ್ತಾರೆ) ಸ್ಥಳಾಂತರದ ದಾಖಲೆಗಳು ಅಸ್ತವ್ಯಸ್ತಗೊಳ್ಳಲು ಕಾರಣವಾಗುತ್ತವೆ, ಸಂಕೋಚನವು ಪೂರ್ಣಗೊಂಡ ನಂತರ ಬ್ರೇಕ್ ಟೇಬಲ್ ಅನ್ನು ವಿಂಗಡಿಸಬೇಕಾಗುತ್ತದೆ. ಬ್ರೇಕ್ ಟೇಬಲ್ ಅನ್ನು ವಿಂಗಡಿಸುವ ವೆಚ್ಚವು ಒ (ಎನ್ ಲಾಗ್ ಎನ್) ಆಗಿದೆ, ಅಲ್ಲಿ ಎನ್ ಎಂಬುದು ಅಲ್ಗಾರಿದಮ್ನ ಗುರುತು ಹಂತದಲ್ಲಿ ಕಂಡುಬರುವ ಜೀವಂತ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯಾಗಿದೆ. ಅಂತಿಮವಾಗಿ, ಸ್ಥಳಾಂತರಿಸಿದ ವಸ್ತುಗಳ ಒಳಗೆ ಪಾಯಿಂಟರ್ ಕ್ಷೇತ್ರಗಳನ್ನು ಸರಿಹೊಂದಿಸಲು ಬ್ರೇಕ್ ಟೇಬಲ್ ಸ್ಥಳಾಂತರ ದಾಖಲೆಗಳನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಲೈವ್ ಆಬ್ಜೆಕ್ಟ್ಗಳನ್ನು ಪಾಯಿಂಟರ್ಗಳಿಗಾಗಿ ಪರೀಕ್ಷಿಸಲಾಗುತ್ತದೆ, ಬ್ರೇಕ್ ಟೇಬಲ್ ಅನ್ನು ಒಟ್ಟು ಓ (ಎನ್ ಲಾಗ್ ಎನ್) ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯಕ್ಕೆ ವಿಂಗಡಿಸಿದರೆ ಒ (ಲಾಗ್ ಎನ್) ಸಮಯದಲ್ಲಿ ಗಾತ್ರದ ಎನ್ ವಿಂಗಡಿಸಲಾದ ಬ್ರೇಕ್ ಟೇಬಲ್ನಲ್ಲಿ ನೋಡಬಹುದು. ನಂತರ ಪಾಯಿಂಟರ್ಗಳನ್ನು ಸ್ಥಳಾಂತರ ಕೋಷ್ಟಕದಲ್ಲಿ ನಿರ್ದಿಷ್ಟಪಡಿಸಿದ ಮೊತ್ತದಿಂದ ಸರಿಹೊಂದಿಸಲಾಗುತ್ತದೆ. ಓ (ಎನ್ ಲಾಗ್ ಎನ್) ಸಂಕೀರ್ಣತೆಯನ್ನು ತಪ್ಪಿಸಲು, ಅಲ್ಗಾರಿದಮ್ ರಾಶಿಯ ಮೇಲೆ ಮೂರು ವಿಭಿನ್ನ ಪಾಸ್ಗಳನ್ನು ಬಳಸುತ್ತದೆ. ಇದಲ್ಲದೆ, ರಾಶಿ ವಸ್ತುಗಳು ಪ್ರತ್ಯೇಕ ಫಾರ್ವರ್ಡಿಂಗ್ ಪಾಯಿಂಟರ್ ಸ್ಲಾಟ್ ಅನ್ನು ಹೊಂದಿರಬೇಕು, ಅದನ್ನು ಕಸ ಸಂಗ್ರಹಣೆಯ ಹೊರಗೆ ಬಳಸಲಾಗುವುದಿಲ್ಲ. ಸ್ಟ್ಯಾಂಡರ್ಡ್ ಮಾರ್ಕಿಂಗ್ ನಂತರ, ಅಲ್ಗಾರಿದಮ್ ಈ ಕೆಳಗಿನ ಮೂರು ಪಾಸ್ಗಳಲ್ಲಿ ಮುಂದುವರಿಯುತ್ತದೆಃ ಲೈವ್ ಆಬ್ಜೆಕ್ಟ್ಗಳಿಗಾಗಿ ಫಾರ್ವರ್ಡ್ ಮಾಡುವ ಸ್ಥಳವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ. ಉಚಿತ ಮತ್ತು ಲೈವ್ ಪಾಯಿಂಟರ್ ಅನ್ನು ಟ್ರ್ಯಾಕ್ ಮಾಡಿ ಮತ್ತು ರಾಶಿಗಳ ಆರಂಭದವರೆಗೆ ಎರಡನ್ನೂ ಪ್ರಾರಂಭಿಸಿ. ಲೈವ್ ಪಾಯಿಂಟರ್ ಲೈವ್ ಆಬ್ಜೆಕ್ಟ್ ಅನ್ನು ಸೂಚಿಸಿದರೆ, ಆ ಆಬ್ಜೆಕ್ಟ್ನ ಫಾರ್ವರ್ಡ್ ಮಾಡುವ ಪಾಯಿಂಟರ್ ಅನ್ನು ಪ್ರಸ್ತುತ ಫ್ರೀ ಪಾಯಿಂಟರ್ಗೆ ನವೀಕರಿಸಿ ಮತ್ತು ಆಬ್ಜೆಕ್ಟ್ನ ಗಾತ್ರಕ್ಕೆ ಅನುಗುಣವಾಗಿ ಫ್ರೀ ಪಾಯಿಂಟರ್ ಅನ್ನು ಹೆಚ್ಚಿಸಿ. ಲೈವ್ ಪಾಯಿಂಟರ್ ರಾಶಿಯ ಅಂತ್ಯವನ್ನು ತಲುಪಿದಾಗ ಲೈವ್ ಪಾಯಿಂಟರ್ ಅನ್ನು ಮುಂದಿನ ಆಬ್ಜೆಕ್ಟ್ ಎಂಡ್ಗೆ ಸರಿಸಿ. ಪ್ರತಿ ಲೈವ್ ಆಬ್ಜೆಕ್ಟ್ಗೆ, ಅವರು ಸೂಚಿಸುವ ಆಬ್ಜೆಕ್ಟ್ಗಳ ಫಾರ್ವರ್ಡಿಂಗ್ ಪಾಯಿಂಟರ್ಗಳ ಪ್ರಕಾರ ಅದರ ಪಾಯಿಂಟರ್ಗಳನ್ನು ನವೀಕರಿಸಿ. ವಸ್ತುಗಳನ್ನು ಸರಿಸಿ ಪ್ರತಿ ಜೀವಂತ ವಸ್ತುವಿಗಾಗಿ, ಅದರ ದತ್ತಾಂಶವನ್ನು ಅದರ ರವಾನೆ ಸ್ಥಳಕ್ಕೆ ಸರಿಸಿ. ಈ ಅಲ್ಗಾರಿದಮ್ ರಾಶಿಯ ಗಾತ್ರದ ಮೇಲೆ O (n) ಆಗಿದೆ; ಇದು ಟೇಬಲ್-ಆಧಾರಿತ ವಿಧಾನಕ್ಕಿಂತ ಉತ್ತಮ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿದೆ, ಆದರೆ ಟೇಬಲ್-ಆಧಾರಿತ ವಿಧಾನದ n ಎಂಬುದು ಬಳಸಿದ ಜಾಗದ ಗಾತ್ರವಾಗಿದೆ, LISP2 ಅಲ್ಗಾರಿದಮ್ನಲ್ಲಿರುವಂತೆ ಸಂಪೂರ್ಣ ರಾಶಿ ಸ್ಥಳವಲ್ಲ. ಆದಾಗ್ಯೂ, LISP2 ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸುವುದು ಸರಳವಾಗಿದೆ. ಡೆಡ್-ಕೋಡ್ ಎಲಿಮಿನೇಷನ್ ಟ್ರೇಸಿಂಗ್ ಗಾರ್ಬೇಜ್ ಕಲೆಕ್ಷನ್ ಉಲ್ಲೇಖಗಳು ಆಟೋಮ್ಯಾಟಿಕ್ ಮೆಮೊರಿ ಮ್ಯಾನೇಜ್ಮೆಂಟ್ ಮೆಮೊರಿ ಮ್ಯಾನೇಜ್ಮೆಂಟ್ ಅಲ್ಗಾರಿದಮ್ಗಳನ್ನು ಸಹ ನೋಡಿ.