خلطة فيشر ييتس 基本思想(خلط كنوث):
لخلط مصفوفة a من العناصر n (المؤشرات 0..n-1):
لأني من n - 1 إلى 1 افعل
j ← عدد صحيح عشوائي مع 0 ≥ j ≥ i
تبادل [ي] و[i]
تعليمات JDK:
/**
* ينقل كل عنصر من عناصر القائمة إلى موضع جديد عشوائي في القائمة
* استخدام مولد الأرقام العشوائية المحدد.
*
* @قائمة المعلمة
* قائمة خلط ورق اللعب
* @param عشوائي
* مولد الأرقام العشوائية
*
* @throws UnsupportedOperationException
* عند استبدال عنصر في القائمة غير مدعوم
*/
@SuppressWarnings("تم إلغاء التحديد")
خلط الفراغ الثابت العام (قائمة<؟>، عشوائي عشوائي) {
إذا (!(قائمة مثيلات الوصول العشوائي)) {
Object[] array = list.toArray();
لـ (int i = array.length - 1; i > 0; i--) {
مؤشر كثافة العمليات = عشوائي.nextInt(i + 1);
إذا (الفهرس <0) {
الفهرس = -index;
}
درجة حرارة الكائن = المصفوفة[i];
array[i] = array[index];
صفيف [الفهرس] = درجة الحرارة؛
}
كثافة العمليات ط = 0؛
ListIterator<Object> it = قائمة (ListIterator<Object>).
.listIterator();
بينما (it.hasNext()) {
it.next();
it.set(array[i++]);
}
} آخر {
List<Object> RawList = (List<Object>) list;
لـ (int i = RawList.size() - 1; i > 0; i--) {
مؤشر كثافة العمليات = عشوائي.nextInt(i + 1);
إذا (الفهرس <0) {
الفهرس = -index;
}
RawList.set(index, RawList.set(i, RawList.get(index)));
}
}
}
public static void main(final String args[]) {
تغيير الكائن درجة الحرارة؛
List<Integer> numList = new ArrayList<Integer>();
List<Integer> firstList = new ArrayList<Integer>();
List<Integer> SecondList = new ArrayList<Integer>();
List<Integer> ThirdList = new ArrayList<Integer>();
List<Integer> fourList = new ArrayList<Integer>();
لـ (int i = 1; i <= 100000; i++) {
numList.add(i);
firstList.add(i);
SecondList.add(i);
ThirdList.add(i);
fourList.add(i);
}
// خلط ورق اللعب أولاً، استخدم ChangeTemp
getStartTime();
int randInt = 0;
for (int i = 0, length = firstList.size(); i < length; i++) {
randInt = getRandom(i, firstList.size());
ChangeTemp = firstList.get(i);
firstList.set(i, firstList.get(randInt));
firstList.set(randInt, javaShuffle.temp);
}
getEndTime("وقت التشغيل العشوائي الأول");
// التبديل الثاني، قائمة التبادل
getStartTime();
for (int i = 0, length = SecondList.size(); i < length; i++) {
randInt = getRandom(i, SecondList.size());
SecondList.set(i, SecondList.set(randInt, SecondList.get(i)));
}
getEndTime("وقت التشغيل العشوائي الثاني");
// التبديل الثالث، قم بإنشاء تغيير عشوائي int
getStartTime();
Object[] tempArray = ThirdList.toArray();
راند عشوائي = جديد عشوائي ()؛
كثافة العمليات ي = 0;
for (int i = tempArray.length - 1; i > 0; i--) {
j = rand.nextInt(i + 1);
ThirdList.set(i,thirdList.set(j,thirdList.get(i)));
}
getEndTime("وقت التشغيل العشوائي الثالث");
// خلط ورق اللعب الرابع، محاكاة خلط جافا
getStartTime();
عشوائي عشوائي = عشوائي جديد ()؛
إذا (!(مثيل القائمة الرابعة للوصول العشوائي)) {
Object[] array = fourList.toArray();
لـ (int i = array.length - 1; i > 0; i--) {
مؤشر كثافة العمليات = عشوائي.nextInt(i + 1);
إذا (الفهرس <0) {
الفهرس = -index;
}
درجة حرارة الكائن = المصفوفة[i];
array[i] = array[index];
صفيف [الفهرس] = درجة الحرارة؛
}
كثافة العمليات ط = 0؛
ListIterator<Integer> it = (ListIterator<Integer>) fourList.listIterator();
بينما (it.hasNext()) {
it.next();
it.set((عدد صحيح) صفيف[i++]);
}
} آخر {
List<Integer> RawList = (List<Integer>) fourList;
لـ (int i = RawList.size() - 1; i > 0; i--) {
مؤشر كثافة العمليات = عشوائي.nextInt(i + 1);
إذا (الفهرس <0) {
الفهرس = -index;
}
RawList.set(index, RawList.set(i, RawList.get(index)));
}
}
getEndTime("وقت التشغيل العشوائي الرابع");
// جافا خلط ورق اللعب
getStartTime();
Collections.shuffle(numList);
getEndTime("وقت تشغيل جافا العشوائي");
}
مبادلة الفراغ الثابت العام (int a، int b) {
javaShuffle.temp = a;
أ = ب؛
ب = javaShuffle.temp;
}
public static int getRandom(final int low, Final int High) {
return (int) (Math.random() * (high - low) + low);
}
الفراغ الثابت العام getStartTime() {
javaShuffle.start = System.nanoTime();
}
public static void getEndTime(final String s) {
javaShuffle.end = System.nanoTime();
System.out.println(s + ": " + (javaShuffle.end - javaShuffle.start) + "ns");
}
}
يجب أن يكون سعر المنتج 100000 دولار أمريكي:
وقت التشغيل العشوائي الأول: 85029499ns
وقت التشغيل العشوائي الثاني: 80909474ns
وقت التشغيل العشوائي الثالث: 71543926ns
وقت التشغيل العشوائي الرابع: 76520595ns
وقت تشغيل جافا العشوائي: 61027643ns
وقت التشغيل العشوائي الأول: 82326239ns
وقت التشغيل العشوائي الثاني: 78575611ns
وقت التشغيل العشوائي الثالث: 95009632ns
وقت التشغيل العشوائي الرابع: 105946897ns
وقت تشغيل جافا العشوائي: 90849302ns
وقت التشغيل العشوائي الأول: 84539840ns
وقت التشغيل العشوائي الثاني: 85965575ns
وقت التشغيل العشوائي الثالث: 101814998ns
وقت التشغيل العشوائي الرابع: 113309672ns
وقت تشغيل جافا العشوائي: 35089693ns
وقت التشغيل العشوائي الأول: 87679863ns
وقت التشغيل العشوائي الثاني: 79991814ns
وقت التشغيل العشوائي الثالث: 73720515ns
وقت التشغيل العشوائي الرابع: 78353061ns
وقت تشغيل جافا العشوائي: 64146465ns
وقت التشغيل العشوائي الأول: 84314386ns
وقت التشغيل العشوائي الثاني: 80074803ns
وقت التشغيل العشوائي الثالث: 74001283ns
وقت التشغيل العشوائي الرابع: 79931321ns
وقت تشغيل جافا العشوائي: 86427540ns
وقت التشغيل العشوائي الأول: 84315523ns
وقت التشغيل العشوائي الثاني: 81468386ns
وقت التشغيل العشوائي الثالث: 75052284ns
وقت التشغيل العشوائي الرابع: 79461407ns
وقت تشغيل جافا العشوائي: 66607729ns
الرقم القياسي 10000000 رينجيت ماليزي:
وقت التشغيل العشوائي الأول: 2115703288ns
وقت التشغيل العشوائي الثاني: 3114045871ns
وقت التشغيل العشوائي الثالث: 4664426798ns
وقت التشغيل العشوائي الرابع: 2962686695ns
وقت تشغيل جافا العشوائي: 3246883026ns وقت التشغيل العشوائي الأول: 2165398466ns
وقت التشغيل العشوائي الثاني: 3129558913ns
وقت التشغيل العشوائي الثالث: 4147859664ns
وقت التشغيل العشوائي الرابع: 2911849942ns
وقت تشغيل جافا العشوائي: 4311703487ns وقت التشغيل العشوائي الأول: 2227462247ns
وقت التشغيل العشوائي الثاني: 3279548770ns
وقت التشغيل العشوائي الثالث: 4704344954ns
وقت التشغيل العشوائي الرابع: 2942635980ns
وقت تشغيل جافا العشوائي: 3933172427ns وقت التشغيل العشوائي الأول: 2200158789ns
وقت التشغيل العشوائي الثاني: 3172666791ns
وقت التشغيل العشوائي الثالث: 4715631517ns
وقت التشغيل العشوائي الرابع: 2950817535ns
وقت تشغيل جافا العشوائي: 3387417676ns وقت التشغيل العشوائي الأول: 2201124449ns
وقت التشغيل العشوائي الثاني: 3203823874ns
وقت التشغيل العشوائي الثالث: 4179926278ns
وقت التشغيل العشوائي الرابع: 2913690411ns
وقت تشغيل جافا العشوائي: 3571313813ns وقت التشغيل العشوائي الأول: 2163053190ns
وقت التشغيل العشوائي الثاني: 3073889926ns
وقت التشغيل العشوائي الثالث: 4493831518ns
وقت التشغيل العشوائي الرابع: 2852713887ns
وقت تشغيل جافا العشوائي: 3773602415ns
في هذه الحالة، يمكنك استخدام خلط ورق اللعب في جافا.
يمكن أن يحدث هذا في أي وقت من الأوقات، حيث قد يكون هناك حاجة إلى جافا أو أي شيء آخر.