Alias method
ಗಣನೆಯಲ್ಲಿ, ಅಲಿಯಾಸ್ ವಿಧಾನವು 1974 ರಲ್ಲಿ ಎ. ಜೆ. ವಾಕರ್ ಪ್ರಕಟಿಸಿದ ಪ್ರತ್ಯೇಕ ಸಂಭವನೀಯತೆಯ ವಿತರಣೆಯಿಂದ ಮಾದರಿಗಾಗಿ ಸಮರ್ಥ ಕ್ರಮಾವಳಿಗಳ ಒಂದು ಕುಟುಂಬವಾಗಿದೆ. ಅಂದರೆ, ಇದು ಕೆಲವು ಅನಿಯಂತ್ರಿತ ಸಂಭವನೀಯತೆಯ ವಿತರಣೆಯ ಪ್ರಕಾರ ಪೂರ್ಣಾಂಕ ಮೌಲ್ಯಗಳನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ. ಕ್ರಮಾವಳಿಗಳು ಸಾಮಾನ್ಯವಾಗಿ ಸಮಯವನ್ನು ಬಳಸುತ್ತವೆ ಅಥವಾ ಪೂರ್ವ ಸಂಸ್ಕರಿಸುತ್ತವೆ, ಅದರ ನಂತರ ಯಾದೃಚ್ಛಿಕ ಮೌಲ್ಯಗಳನ್ನು ಸಮಯದ ವಿತರಣೆಯಿಂದ ತೆಗೆದುಕೊಳ್ಳಬಹುದು. ಕಾರ್ಯಾಚರಣೆಯು ಆಂತರಿಕವಾಗಿ, ಅಲ್ಗಾರಿದಮ್ ಎರಡು ಕೋಷ್ಟಕಗಳನ್ನು ಸಮಾಲೋಚಿಸುತ್ತದೆ, ಒಂದು ಸಂಭವನೀಯತೆ ಕೋಷ್ಟಕ ಮತ್ತು ಒಂದು ಅಲಿಯಾಸ್ ಕೋಷ್ಟಕ (ಫಾರ್). ಯಾದೃಚ್ಛಿಕ ಫಲಿತಾಂಶವನ್ನು ಸೃಷ್ಟಿಸಲು, ಎರಡು ಕೋಷ್ಟಕಗಳಲ್ಲಿ ಸೂಚ್ಯಂಕವನ್ನು ನಿರ್ಧರಿಸಲು ನ್ಯಾಯೋಚಿತ ಡೈಸ್ ಅನ್ನು ಸುತ್ತಲಾಗುತ್ತದೆ. ಆ ಸೂಚ್ಯಂಕದಲ್ಲಿ ಸಂಗ್ರಹಿಸಲಾದ ಸಂಭವನೀಯತೆಯ ಆಧಾರದ ಮೇಲೆ, ಪಕ್ಷಪಾತದ ನಾಣ್ಯವನ್ನು ನಂತರ ತಿರುಗಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ತಿರುಗಿಸುವಿಕೆಯ ಫಲಿತಾಂಶವನ್ನು ಮತ್ತು ಫಲಿತಾಂಶದ ನಡುವೆ ಆಯ್ಕೆ ಮಾಡಲು ಬಳಸಲಾಗುತ್ತದೆ. ಹೆಚ್ಚು ನಿಖರವಾಗಿ, ಅಲ್ಗಾರಿದಮ್ ಈ ಕೆಳಗಿನಂತೆ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆಃ ಏಕರೂಪದ ಯಾದೃಚ್ಛಿಕ ರೂಪಾಂತರವನ್ನು ರಚಿಸಿ. ಮತ್ತು ಆಗಲಿ. (ಇದು ಏಕರೂಪವಾಗಿ ವಿತರಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಏಕರೂಪವಾಗಿ ವಿತರಿಸಲಾಗುತ್ತದೆ.) ಇದ್ದರೆ, ಹಿಂತಿರುಗಿ. ಇದು ಪಕ್ಷಪಾತದ ನಾಣ್ಯ ತಿರುವು. ಇಲ್ಲದಿದ್ದರೆ, ಹಿಂತಿರುಗಿ. ಮಾರ್ಸಗ್ಲಿಯಾ ಮತ್ತು ಇತರರು ಪ್ರಸ್ತಾಪಿಸಿದ ಸಂಭವನೀಯತೆಯ ಕೋಷ್ಟಕದ ಪರ್ಯಾಯ ಸೂತ್ರೀಕರಣ. "ಸ್ಕ್ವೇರ್ ಹಿಸ್ಟೋಗ್ರಾಮ್" ವಿಧಾನವಾಗಿ, ಕಂಪ್ಯೂಟಿಂಗ್ ಬದಲಿಗೆ ಮೂರನೇ ಹಂತದಲ್ಲಿ (ಎಲ್ಲಿ) ಸ್ಥಿತಿಯನ್ನು ಬಳಸುತ್ತದೆ. ಟೇಬಲ್ ಉತ್ಪಾದನೆ ವಿತರಣೆಯನ್ನು ಎರಡು ಶಕ್ತಿಯಂತಹ ಅನುಕೂಲಕರ ಮೌಲ್ಯಕ್ಕೆ ಹೆಚ್ಚಿಸಲು ಹೆಚ್ಚುವರಿ ಸಂಭವನೀಯತೆಗಳೊಂದಿಗೆ ಪ್ಯಾಡ್ ಮಾಡಬಹುದು. ಟೇಬಲ್ ಅನ್ನು ರಚಿಸಲು, ಮೊದಲು ಪ್ರಾರಂಭಿಸಿ. ಇದನ್ನು ಮಾಡುವಾಗ, ಟೇಬಲ್ ನಮೂದುಗಳನ್ನು ಮೂರು ವರ್ಗಗಳಾಗಿ ವಿಂಗಡಿಸಿಃ "ಓವರ್ ಫುಲ್" ಗುಂಪು, ಅಲ್ಲಿ, "ಅಂಡರ್ಫುಲ್" ಗುಂಪು, ಅಲ್ಲಿ ಮತ್ತು ಪ್ರಾರಂಭಿಸಲಾಗಿಲ್ಲ, ಮತ್ತು "ನಿಖರವಾಗಿ ಪೂರ್ಣ" ಗುಂಪು, ಅಲ್ಲಿ ಅಥವಾ ಪ್ರಾರಂಭಿಸಲಾಗಿದೆ. ಒಂದು ವೇಳೆ, ಅನುಗುಣವಾದ ಮೌಲ್ಯವನ್ನು ಎಂದಿಗೂ ಪರಿಶೀಲಿಸಲಾಗುವುದಿಲ್ಲ ಮತ್ತು ಅದು ಮುಖ್ಯವಲ್ಲ, ಆದರೆ ಅದರ ಮೌಲ್ಯವು ಸಂವೇದನಾಶೀಲವಾಗಿರುತ್ತದೆ. ಎಲ್ಲ ಟೇಬಲ್ ನಮೂದುಗಳು ನಿಖರವಾಗಿ ತುಂಬಿಲ್ಲದಿರುವವರೆಗೆ, ಈ ಕೆಳಗಿನ ಹಂತಗಳನ್ನು ಪುನರಾವರ್ತಿಸಿಃ ಅನಿಯಂತ್ರಿತವಾಗಿ ಅತಿಯಾದ ನಮೂದು ಮತ್ತು ಕಡಿಮೆ ಭರ್ತಿ ನಮೂದನ್ನು ಆಯ್ಕೆ ಮಾಡಿ. (ಇವುಗಳಲ್ಲಿ ಒಂದು ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ, ಇನ್ನೊಂದು ಕೂಡ ಅಸ್ತಿತ್ವದಲ್ಲಿರಬೇಕು.) ಸೆಟ್ಟಿಂಗ್ ಮಾಡುವ ಮೂಲಕ ಫಲಿತಾಂಶದ ಪ್ರವೇಶದಲ್ಲಿ ಬಳಕೆಯಾಗದ ಜಾಗವನ್ನು ನಿಯೋಜಿಸಿ. ಬದಲಿಸುವ ಮೂಲಕ ಪ್ರವೇಶದಿಂದ ನಿಗದಿಪಡಿಸಿದ ಜಾಗವನ್ನು ತೆಗೆದುಹಾಕಿ. ಪ್ರವೇಶವು ಈಗ ನಿಖರವಾಗಿ ತುಂಬಿದೆ. ಹೊಸ ಮೌಲ್ಯದ ಆಧಾರದ ಮೇಲೆ ಸೂಕ್ತ ವರ್ಗಕ್ಕೆ ನಮೂದನ್ನು ನಿಯೋಜಿಸಿ. ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯು ಕನಿಷ್ಠ ಒಂದು ನಮೂದನ್ನು "ನಿಖರವಾಗಿ ಪೂರ್ಣ" ವರ್ಗಕ್ಕೆ ಚಲಿಸುತ್ತದೆ (ಮತ್ತು ಕೊನೆಯದು ಎರಡು ಚಲಿಸುತ್ತದೆ), ಆದ್ದರಿಂದ ಹೆಚ್ಚಿನ ಪುನರಾವರ್ತನೆಗಳ ನಂತರ ಕಾರ್ಯವಿಧಾನವು ಕೊನೆಗೊಳ್ಳುತ್ತದೆ ಎಂದು ಖಾತರಿಪಡಿಸಲಾಗುತ್ತದೆ. ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯನ್ನು ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿ ಮಾಡಬಹುದು, ಆದ್ದರಿಂದ ಟೇಬಲ್ ಅನ್ನು ಸಮಯಕ್ಕೆ ಹೊಂದಿಸಬಹುದು. ಫ್ಲೋಟಿಂಗ್-ಪಾಯಿಂಟ್ ರೌಂಡಿಂಗ್ ದೋಷಗಳು ಹಂತ 1 ರಲ್ಲಿ ಉಲ್ಲೇಖಿಸಲಾದ ಖಾತರಿಯನ್ನು ಉಲ್ಲಂಘಿಸಲು ಕಾರಣವಾಗಬಹುದು ಎಂದು ವೋಸ್ ಗಮನಸೆಳೆದಿದ್ದಾರೆ. ಒಂದು ವರ್ಗವು ಇನ್ನೊಂದರ ಮೊದಲು ಖಾಲಿಯಾದರೆ, ಉಳಿದ ನಮೂದುಗಳು ಅತ್ಯಲ್ಪ ದೋಷದೊಂದಿಗೆ 1ಕ್ಕೆ ಹೊಂದಿಸಿರಬಹುದು. ಫ್ಲೋಟಿಂಗ್ ಪಾಯಿಂಟ್ಗೆ ಪರಿಹಾರ ಲೆಕ್ಕಪತ್ರವನ್ನು ಕೆಲವೊಮ್ಮೆ ವಾಕರ್-ವೋಸ್ ವಿಧಾನ ಅಥವಾ ವೋಸ್ ಅಲಿಯಾಸ್ ವಿಧಾನ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಅಲಿಯಾಸ್ ರಚನೆಯು ಅನನ್ಯವಾಗಿಲ್ಲ. ಹುಡುಕುವ ಪ್ರಕ್ರಿಯೆಯು ಸ್ವಲ್ಪ ವೇಗವಾಗಿರುವುದರಿಂದ (ಏಕೆಂದರೆ ಸಮಾಲೋಚಿಸುವ ಅಗತ್ಯವಿಲ್ಲ), ಟೇಬಲ್ ಉತ್ಪಾದನೆಯ ಸಮಯದಲ್ಲಿ ಒಂದು ಗುರಿಯು ಒಟ್ಟು ಮೊತ್ತವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸುವುದು. ಇದನ್ನು ಅತ್ಯುತ್ತಮವಾಗಿ ಮಾಡುವುದರಿಂದ ಎನ್ಪಿ ಕಷ್ಟವಾಗುತ್ತದೆ, ಆದರೆ ದುರಾಸೆಯ ಅಲ್ಗಾರಿದಮ್ ಸಮಂಜಸವಾಗಿ ಹತ್ತಿರ ಬರುತ್ತದೆಃ ಶ್ರೀಮಂತರಿಂದ ದೋಚಿ ಬಡವರಿಗೆ ನೀಡಿ. ಅಂದರೆ, ಪ್ರತಿ ಹಂತದಲ್ಲೂ ದೊಡ್ಡ ಮತ್ತು ಚಿಕ್ಕದನ್ನು ಆಯ್ಕೆ ಮಾಡಿ. ಇದಕ್ಕೆ ವಿಂಗಡಿಸುವ ಅಗತ್ಯವಿರುವುದರಿಂದ, ಇದಕ್ಕೆ ಸಮಯ ಬೇಕಾಗುತ್ತದೆ. ದಕ್ಷತೆ ಏಕರೂಪದ ವಿಚಲನವನ್ನು ಉತ್ಪಾದಿಸುವುದು ಸ್ವತಃ ವೇಗವಾಗಿದ್ದರೆ ಅಲಿಯಾಸ್ ವಿಧಾನವು ತುಂಬಾ ಪರಿಣಾಮಕಾರಿಯಾಗಿದ್ದರೂ, ಯಾದೃಚ್ಛಿಕ ಬಿಟ್ ಬಳಕೆಯ ವಿಷಯದಲ್ಲಿ ಇದು ಸೂಕ್ತವಲ್ಲದ ಸಂದರ್ಭಗಳಿವೆ. ಏಕೆಂದರೆ ಇದು ಪ್ರತಿ ಬಾರಿಯೂ ಕೆಲವು ಯಾದೃಚ್ಛಿಕ ಬಿಟ್ಗಳ ಅಗತ್ಯವಿದ್ದರೂ ಸಹ ಪೂರ್ಣ-ನಿಖರ ಯಾದೃಚ್ಛಿಕ ವ್ಯತ್ಯಾಸವನ್ನು ಬಳಸುತ್ತದೆ. ಸಂಭವನೀಯತೆಗಳು ವಿಶೇಷವಾಗಿ ಸಮತೋಲಿತವಾಗಿದ್ದಾಗ, ಅನೇಕವಾಗಿದ್ದಾಗ ಮತ್ತು ಅಗತ್ಯವಿಲ್ಲದಿದ್ದಾಗ ಒಂದು ಪ್ರಕರಣವು ಉದ್ಭವಿಸುತ್ತದೆ. ಉತ್ಪಾದಿಸುವುದು ಸಮಯದ ವ್ಯರ್ಥವಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, 32-ಬಿಟ್ ಯಾದೃಚ್ಛಿಕ ವೇರಿಯೇಟ್ ಅನ್ನು 32 ಆಯ್ಕೆಗಳನ್ನು ಮಾಡಲು ಬಳಸಬಹುದು, ಆದರೆ ಅಲಿಯಾಸ್ ವಿಧಾನವು ಒಂದನ್ನು ಮಾತ್ರ ಉತ್ಪಾದಿಸುತ್ತದೆ. ಸಂಭವನೀಯತೆಗಳು ಬಲವಾಗಿ ಅಸಮತೋಲಿತವಾಗಿದ್ದಾಗ ಮತ್ತೊಂದು ಪ್ರಕರಣವು ಉದ್ಭವಿಸುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಮತ್ತು, ನಂತರ ಹೆಚ್ಚಿನ ಸಮಯ, ಪ್ರಕರಣ 1 ಅನ್ವಯಿಸುತ್ತದೆ ಎಂದು ನಿರ್ಧರಿಸಲು ಕೆಲವು ಯಾದೃಚ್ಛಿಕ ಬಿಟ್ಗಳು ಮಾತ್ರ ಬೇಕಾಗುತ್ತವೆ. ಅಂತಹ ಸಂದರ್ಭಗಳಲ್ಲಿ, ಮಾರ್ಸಾಗ್ಲಿಯಾ ಮತ್ತು ಇತರರು ವಿವರಿಸಿದ ಟೇಬಲ್ ವಿಧಾನ. ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿಯಾಗಿದೆ. ನಾವು ಒಂದೇ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ ಅನೇಕ ಆಯ್ಕೆಗಳನ್ನು ಮಾಡಿದರೆ ನಮಗೆ ಸರಾಸರಿ ಒಂದಕ್ಕಿಂತ ಕಡಿಮೆ ಪಕ್ಷಪಾತವಿಲ್ಲದ ಯಾದೃಚ್ಛಿಕ ಬಿಟ್ ಅಗತ್ಯವಿರುತ್ತದೆ. ಅಂಕಗಣಿತದ ಕೋಡಿಂಗ್ ತಂತ್ರಗಳನ್ನು ಬಳಸಿಕೊಂಡು ನಾವು ಬೈನರಿ ಎಂಟ್ರೊಪಿ ಕಾರ್ಯದಿಂದ ನೀಡಲಾದ ಮಿತಿಯನ್ನು ತಲುಪಬಹುದು. ಸಾಹಿತ್ಯ ಡೋನಾಲ್ಡ್ ಕ್ನುತ್, ದಿ ಆರ್ಟ್ ಆಫ್ ಕಂಪ್ಯೂಟರ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್, ಸಂಪುಟ 2: ಸೆಮಿನ್ಯೂಮರಿಕಲ್ ಅಲ್ಗಾರಿದಮ್ಸ್, ವಿಭಾಗ 3.4.1. ಅನುಷ್ಠಾನಗಳು http://www.keithschwarz.com/darts-dice-coins ಕೀತ್ ಶ್ವಾರ್ಜ್ಃ ವಿವರವಾದ ವಿವರಣೆ, ವೋಸ್ನ ಅಲ್ಗಾರಿದಮ್ನ ಸಂಖ್ಯಾತ್ಮಕವಾಗಿ ಸ್ಥಿರವಾದ ಆವೃತ್ತಿ, ಮತ್ತು ಜಾವಾ ಅನುಷ್ಠಾನಕ್ಕೆ ಲಿಂಕ್ https://jugit.fz-juelich.de/mlz/ransampl ಜೊವಾಕಿಮ್ ವುಟ್ಕೆಃ ಸಣ್ಣ ಸಿ ಲೈಬ್ರರಿಯಾಗಿ ಅನುಷ್ಠಾನ. https://gist.github.com/0b5786e9bfc73e75eb8180b5400cd1f8 ಲಿಯಾಮ್ ಹುವಾಂಗ್ ಅವರ C + + https://github.com/joseftw/jos.weightedresult/blob/develop/src/JOS.WeightedResult/AliasMethodVose.cs C #ವೋಸ್ನ ಅಲ್ಗಾರಿದಮ್ನ ಅನುಷ್ಠಾನ. ಫ್ಲೋಟಿಂಗ್ ಪಾಯಿಂಟ್ ಅಸ್ಥಿರತೆಯಿಲ್ಲದೆ ವೋಸ್ನ ಅಲ್ಗಾರಿದಮ್ನ https://github.com/cdanek/KaimiraWeightedList C #ಅನುಷ್ಠಾನ. ಉಲ್ಲೇಖಗಳು ಸ್ಯೂಡೋರಾಂಡಂ ಸಂಖ್ಯೆ ಉತ್ಪಾದಕಗಳು