תורת ההסתברות בפועל או האם אתה יודע על רנדום

מבוא

יש הרבה מדעים בעולם שחוקרים את תורת ההסתברות. ומדעים מורכבים מחלקים שונים. לדוגמה, במתמטיקה יש קטע נפרד המוקדש לחקר אירועים אקראיים, כמויות וכו'. אבל המדע לא נלקח בקלות ראש. במקרה זה, תורת ההסתברות החלה להתגבש כאשר אנשים ניסו להבין אילו דפוסים יש בהטלת קוביות כאשר משחקים במשחקי מזל. אם אתה מסתכל היטב, יש הרבה דברים אקראיים לכאורה סביבנו. אבל כל דבר אקראי הוא לא לגמרי אקראי. אבל עוד על כך בהמשך. לשפת התכנות Java יש גם תמיכה במספרים אקראיים, החל מהגרסה הראשונה של ה-JDK. ניתן להשתמש במספרים אקראיים ב-Java באמצעות המחלקה java.util.Random . לבדיקה, נשתמש ב- tutorialspoint java מהדר מקוון . הנה דוגמה פרימיטיבית לשימוש באקראי כדי לחקות זריקת "קוביות", או קוביות ברוסית:

import java.util.Random;

public class HelloWorld{
    public static void main(String []args){
        Random rnd = new Random();
        int number = rnd.nextInt(6) + 1;
        System.out.println("Random number: " + number);
    }
}

נראה שזה יכול להיות סוף התיאור של אקראי , אבל זה לא כל כך פשוט. בואו נפתח את התיאור של המחלקה java.util.Random ב-Java API. וכאן אנו רואים דברים מעניינים. המחלקה האקראית משתמשת במספרים פסאודו אקראיים. איך זה? מסתבר שמספרים אקראיים הם לא כל כך אקראיים?

פסאודו-אקראי java.util.Random

התיעוד של המחלקה java.util.Random אומר שאם נוצרים מופעים של Random עם אותו פרמטר seed ומבצעים אותם רצפים של פעולות על המופעים, הם מחזירים רצפים זהים של מספרים. ואם נסתכל מקרוב, נוכל לראות שלרנדום יש למעשה בנאי שלוקח ערך ארוך כסיד:

Random rnd1 = new Random(1L);
Random rnd2 = new Random(1L);
boolean test = rnd1.nextInt(6) == rnd2.nextInt(6);
System.out.println("Test: " + test);

דוגמה זו תחזור נכון כי הזרע של שני המקרים זהה. מה לעשות? בנאי ברירת המחדל פותר חלקית את הבעיה. להלן דוגמה לתוכן של הבנאי האקראי :

public Random() {
	this(seedUniquifier() ^ System.nanoTime());
}

בנאי ברירת המחדל משתמש בפעולת OR בלעדית בשיטת סיביות . ומשתמש באורך המייצג את השעה הנוכחית ובאיזה סיד בשביל זה :

private static long seedUniquifier() {
	for (;;) {
		long current = seedUniquifier.get();
		long next = current * 181783497276652981L;
		if (seedUniquifier.compareAndSet(current, next))
			return next;
	}
}

דבר מעניין נוסף כאן הוא שכל קריאה לשיטת seedUniquifier getter משנה את הערך של seedUniquifier . כלומר, המחלקה נועדה לבחור מספרים אקראיים בצורה יעילה ככל האפשר. עם זאת, כפי שאומר התיעוד, הם " אינם מאובטחים מבחינה קריפטוגרפית ". כלומר, למטרות מסוימות של שימוש למטרות הצפנה (יצירת סיסמא וכדומה) זה לא מתאים, כיון הרצף עם הגישה הנכונה צפוי. יש דוגמאות בנושא זה באינטרנט, למשל כאן: " חיזוי של Math.random() הבא ב-Java ". או למשל קוד המקור כאן: " Vulnerability Weak Crypto ". ל-java.util.Random (מחולל מספרים אקראיים) יש "קיצור דרך" מסוים , כלומר גרסה מקוצרת של הקריאה שמתבצעת דרך Math.random:

public static void main(String []args){
	int random_number = 1 + (int) (Math.random() * 6);
	System.out.println("Value: " + random_number);
}

אבל אם תסתכלו היטב, אותו רנדום יושב בפנים:

public static double random() {
	return RandomNumberGeneratorHolder.randomNumberGenerator.nextDouble();
}
private static final class RandomNumberGeneratorHolder {
	static final Random randomNumberGenerator = new Random();
}

ה-JavaDoc מייעץ להשתמש במחלקה SecureRandom עבור " מחולל מספרים פסאודו-אקראי מאובטח מבחינה קריפטוגרפית ".

Secure Random Java

המחלקה SecureRandom היא תת-מחלקה של java.util.Random וממוקמת בחבילת java.security . השוואה בין שתי המחלקות הללו ניתן לקרוא במאמר " ההבדל בין java.util.Random ל-java.security.SecureRandom ". למה ה-SecureRandom הזה כל כך טוב? העובדה היא שעבורו המקור למספרים אקראיים הוא דבר שנשמע קסום כמו "בריכת האנטרופיית הליבה". זה גם פלוס וגם מינוס. אתה יכול לקרוא על החסרונות של זה במאמר: " הסכנות של java.security.SecureRandom ". בקיצור, ללינוקס יש מחולל מספרים אקראיים (RNG). RNG מייצר מספרים אקראיים על סמך נתונים ממאגר האנטרופיה, שמתמלא על סמך אירועים אקראיים במערכת, כגון תזמוני מקלדת ודיסקים, תנועות עכבר, פסיקות ותעבורת רשת. מידע נוסף על מאגר האנטרופיה מתואר בחומר " מספרים אקראיים בלינוקס (RNG) או כיצד "למלא" /dev/random ו-/dev/urandom ". במערכות Windows, נעשה שימוש ב-SHA1PRNG, מיושם ב-sun.security.provider.SecureRandom. עם הפיתוח של Java, גם SecureRandom השתנה, שכדאי לקרוא עליו בסקירה " Java SecureRandom עדכונים החל מאפריל 2016 " לתמונה מלאה.

ריבוי חוטים או להיות כמו קיסר

אם אתה מסתכל על הקוד של המחלקה האקראית , נראה ששום דבר לא מעיד על בעיות. שיטות אינן מסומנות מסונכרנות . אבל יש אבל אחד: בעת יצירת Random עם בנאי ברירת המחדל בכמה שרשורים, נשתף ביניהם את אותו מופע seed , שבאמצעותו יווצר Random . וגם כאשר מתקבל מספר אקראי חדש, גם AtomicLong הפנימי של המופע משתנה . מצד אחד, אין בזה שום פסול מבחינה הגיונית, כי... נעשה שימוש ב- AtomicLong . מצד שני, אתה צריך לשלם על הכל, כולל פרודוקטיביות. וגם בשביל זה. לכן, אפילו התיעוד הרשמי של java.util.Random אומר: " מופעים של java.util.Random הם בטוחים ל-threads. עם זאת, השימוש בו-זמני של אותו מופע java.util.Random על פני שרשורים עלול להיתקל במחלוקת וכתוצאה מכך ביצועים גרועים. שקול במקום זאת שימוש ב-ThreadLocalRandom בעיצובים עם ריבוי הליכי ". כלומר, ביישומים מרובי הליכי כאשר משתמשים באופן פעיל ב-Random ממספר שרשורים, עדיף להשתמש במחלקה ThreadLocalRandom . השימוש בו שונה במקצת מאקראי רגיל :

public static void main(String []args){
	int rand = ThreadLocalRandom.current().nextInt(1,7);
	System.out.println("Value: " + rand);
}

כפי שאתה יכול לראות, איננו מציינים זרע עבורו . דוגמה זו מתוארת במדריך הרשמי של Oracle: Concurrent Random Numbers . אתה יכול לקרוא עוד על מחלקה זו בסקירה: " מדריך ל-ThreadLocalRandom ב-Java ".

StreamAPI ו-Random

עם שחרורו של Java 8, יש לנו הרבה תכונות חדשות. כולל Stream API. והשינויים השפיעו גם על יצירת הערכים האקראיים . לדוגמה, למחלקה Random יש שיטות חדשות המאפשרות לך לקבל Stream עם ערכים אקראיים כמו int, doubleאו long. לדוגמה:

import java.util.Random;

public class HelloWorld{
    public static void main(String []args){
        new Random().ints(10, 1, 7).forEach(n -> System.out.println(n));
    }
}

יש גם מחלקה חדשה SplittableRandom :

import java.util.SplittableRandom;

public class HelloWorld{
    public static void main(String []args){
        new SplittableRandom().ints(10, 1, 7).forEach(n -> System.out.println(n));
    }
}

אתה יכול לקרוא עוד על ההבדל בין SplittableRandom למחלקות אחרות כאן: " דרכים שונות ליצור מספרים אקראיים ב-Java ".

סיכום

אני חושב שכדאי להסיק מסקנה. עליך לקרוא בעיון את ה-JavaDoc עבור השיעורים שבהם נעשה שימוש. מאחורי משהו פשוט במבט ראשון כמו אקראי יש ניואנסים שיכולים לשחק בדיחה אכזרית. #ויאצ'סלב