API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jun 14th, 2013
683
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 20.95 KB | None | 0 0
raw download clone embed print report
  1. import java.io.IOException;
  2. import java.io.PrintWriter;
  3. import java.util.Arrays;
  4. import java.util.Random;
  5.  
  6.  
  7. /**
  8.  * Generator which creates a test where Java 7 dual-pivot quicksort algorithm runs in O(n^2) time.
  9.  *
  10.  * Number of operations is not the best possible:
  11.  * maximal recursion depth is about n^2 / 5 while best possible result is n^2 / 4.
  12.  *
  13.  * It's because Java 7 checks if array is nearly sorted.
  14.  * If it is, a strange algorithm with something called 'runs' is used.
  15.  * In our case it is not, but in process of this checking Java 7 swaps some elements.
  16.  * I didn't figure out how to maintain these swaps yet. Feel free to improve it!
  17.  *
  18.  * @author Alexey Dergunov
  19.  * @since  1.7
  20.  */
  21. public class Java7QuicksortKiller implements Runnable {
  22.  
  23.     private final Random rnd = new Random(239);
  24.    
  25.     private final int INSERTION_SORT_THRESHOLD = 47;
  26. //    private final int MAX_RUN_LENGTH = 33;
  27. //    private final int QUICKSORT_THRESHOLD = 286;
  28. //    private final int MAX_RUN_COUNT = 67;
  29.    
  30.     private int MIN_VALUE;
  31.     private int MAX_VALUE;
  32.     private final int NO_VALUE = -1;
  33.    
  34.     private void hackedSort(int[] a, int[] p, int left, int right, boolean leftmost) {
  35.         int length = right - left + 1;
  36.        
  37.         // Use insertion sort on tiny arrays
  38.         if (length < INSERTION_SORT_THRESHOLD) {
  39.             for (int i = right; i >= left; i--) {
  40.                 if (a[i] == NO_VALUE) a[i] = MIN_VALUE++;
  41.             }
  42.             randomShuffle(a, left, right); // why not?
  43.  
  44.             if (leftmost) {
  45.                 /*
  46.                  * Traditional (without sentinel) insertion sort,
  47.                  * optimized for server VM, is used in case of
  48.                  * the leftmost part.
  49.                  */
  50.                 for (int i = left, j = i; i < right; j = ++i) {
  51.                     int ai = a[i + 1];
  52.                     int pi = p[i + 1];
  53.                     while (ai < a[j]) {
  54.                         a[j + 1] = a[j];
  55.                         p[j + 1] = p[j];
  56.                         if (j-- == left) {
  57.                             break;
  58.                         }
  59.                     }
  60.                     a[j + 1] = ai;
  61.                     p[j + 1] = pi;
  62.                 }
  63.             } else {
  64.                 /*
  65.                  * Skip the longest ascending sequence.
  66.                  */
  67.                 do {
  68.                     if (left >= right) {
  69.                         return;
  70.                     }
  71.                 } while (a[++left] >= a[left - 1]);
  72.  
  73.                 /*
  74.                  * Every element from adjoining part plays the role
  75.                  * of sentinel, therefore this allows us to avoid the
  76.                  * left range check on each iteration. Moreover, we use
  77.                  * the more optimized algorithm, so called pair insertion
  78.                  * sort, which is faster (in the context of Quicksort)
  79.                  * than traditional implementation of insertion sort.
  80.                  */
  81.                 for (int k = left; ++left <= right; k = ++left) {
  82.                     int a1 = a[k], a2 = a[left];
  83.                     int p1 = p[k], p2 = p[left];
  84.  
  85.                     if (a1 < a2) {
  86.                         a2 = a1; a1 = a[left];
  87.                         p2 = p1; p1 = p[left];
  88.                     }
  89.                     while (a1 < a[--k]) {
  90.                         a[k + 2] = a[k];
  91.                         p[k + 2] = p[k];
  92.                     }
  93.                     ++k;
  94.                     a[k + 1] = a1;
  95.                     p[k + 1] = p1;
  96.  
  97.                     while (a2 < a[--k]) {
  98.                         a[k + 1] = a[k];
  99.                         p[k + 1] = p[k];
  100.                     }
  101.                     a[k + 1] = a2;
  102.                     p[k + 1] = p2;
  103.                 }
  104.                 int last = a[right];
  105.                 int plast = p[right];
  106.  
  107.                 while (last < a[--right]) {
  108.                     a[right + 1] = a[right];
  109.                     p[right + 1] = p[right];
  110.                 }
  111.                 a[right + 1] = last;
  112.                 p[right + 1] = plast;
  113.             }
  114.             return;
  115.         }
  116.  
  117.         // Inexpensive approximation of length / 7
  118.         int seventh = (length >> 3) + (length >> 6) + 1;
  119.  
  120.         /*
  121.          * Sort five evenly spaced elements around (and including) the
  122.          * center element in the range. These elements will be used for
  123.          * pivot selection as described below. The choice for spacing
  124.          * these elements was empirically determined to work well on
  125.          * a wide variety of inputs.
  126.          */
  127.         int e3 = (left + right) >>> 1; // The midpoint
  128.         int e2 = e3 - seventh;
  129.         int e1 = e2 - seventh;
  130.         int e4 = e3 + seventh;
  131.         int e5 = e4 + seventh;
  132.        
  133.         if (a[e5] == NO_VALUE) a[e5] = MIN_VALUE++;
  134.         if (a[e4] == NO_VALUE) a[e4] = MIN_VALUE++;
  135.        
  136.         if (a[e1] == NO_VALUE) a[e1] = MAX_VALUE--;
  137.         if (a[e2] == NO_VALUE) a[e2] = MAX_VALUE--;
  138.  
  139.         // Sort these elements using insertion sort
  140.         if (less(a[e2], a[e1])) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t;
  141.                                   int s = p[e2]; p[e2] = p[e1]; p[e1] = s; }
  142.  
  143.         if (less(a[e3], a[e2])) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
  144.                                   int s = p[e3]; p[e3] = p[e2]; p[e2] = s;
  145.             if (less(t, a[e1])) { a[e2] = a[e1]; a[e1] = t;
  146.                                   p[e2] = p[e1]; p[e1] = s; }
  147.         }
  148.         if (less(a[e4], a[e3])) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
  149.                                   int s = p[e4]; p[e4] = p[e3]; p[e3] = s;
  150.             if (less(t, a[e2])) { a[e3] = a[e2]; a[e2] = t;
  151.                                   p[e3] = p[e2]; p[e2] = s;
  152.                 if (less(t, a[e1])) { a[e2] = a[e1]; a[e1] = t;
  153.                                       p[e2] = p[e1]; p[e1] = s; }
  154.             }
  155.         }
  156.         if (less(a[e5], a[e4])) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
  157.                                   int s = p[e5]; p[e5] = p[e4]; p[e4] = s;
  158.             if (less(t, a[e3])) { a[e4] = a[e3]; a[e3] = t;
  159.                                   p[e4] = p[e3]; p[e3] = s;
  160.                 if (less(t, a[e2])) { a[e3] = a[e2]; a[e2] = t;
  161.                                       p[e3] = p[e2]; p[e2] = s;
  162.                     if (less(t, a[e1])) { a[e2] = a[e1]; a[e1] = t;
  163.                                           p[e2] = p[e1]; p[e1] = s; }
  164.                 }
  165.             }
  166.         }
  167.  
  168.         // Pointers
  169.         int less  = left;  // The index of the first element of center part
  170.         int great = right; // The index before the first element of right part
  171.  
  172.         if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
  173.             /*
  174.              * Use the second and fourth of the five sorted elements as pivots.
  175.              * These values are inexpensive approximations of the first and
  176.              * second terciles of the array. Note that pivot1 <= pivot2.
  177.              */
  178.             int pivot1 = a[e2];
  179.             int pivot2 = a[e4];
  180.             int ppivot1 = p[e2];
  181.             int ppivot2 = p[e4];
  182.  
  183.             /*
  184.              * The first and the last elements to be sorted are moved to the
  185.              * locations formerly occupied by the pivots. When partitioning
  186.              * is complete, the pivots are swapped back into their final
  187.              * positions, and excluded from subsequent sorting.
  188.              */
  189.             a[e2] = a[left];
  190.             a[e4] = a[right];
  191.             p[e2] = p[left];
  192.             p[e4] = p[right];
  193.  
  194.             /*
  195.              * Skip elements, which are less or greater than pivot values.
  196.              */
  197.             //while (a[++less] < pivot1);
  198.             //while (a[--great] > pivot2);
  199.             while (less(a[++less], pivot1));
  200.             while (greater(a[--great], pivot2));
  201.  
  202.             /*
  203.              * Partitioning:
  204.              *
  205.              *   left part           center part                   right part
  206.              * +--------------------------------------------------------------+
  207.              * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
  208.              * +--------------------------------------------------------------+
  209.              *               ^                          ^       ^
  210.              *               |                          |       |
  211.              *              less                        k     great
  212.              *
  213.              * Invariants:
  214.              *
  215.              *              all in (left, less)   < pivot1
  216.              *    pivot1 <= all in [less, k)     <= pivot2
  217.              *              all in (great, right) > pivot2
  218.              *
  219.              * Pointer k is the first index of ?-part.
  220.              */
  221.             outer:
  222.             for (int k = less - 1; ++k <= great; ) {
  223.                 int ak = a[k];
  224.                 int pk = p[k];
  225.                 //if (ak < pivot1) { // Move a[k] to left part
  226.                 if (less(ak, pivot1)) { // Move a[k] to left part
  227.                     a[k] = a[less];
  228.                     p[k] = p[less];
  229.                     /*
  230.                      * Here and below we use "a[i] = b; i++;" instead
  231.                      * of "a[i++] = b;" due to performance issue.
  232.                      */
  233.                     a[less] = ak;
  234.                     p[less] = pk;
  235.                     ++less;
  236.                 //} else if (ak > pivot2) { // Move a[k] to right part
  237.                 } else if (greater(ak, pivot2)) { // Move a[k] to right part
  238.                     //while (a[great] > pivot2) {
  239.                     while (greater(a[great], pivot2)) {
  240.                         if (great-- == k) {
  241.                             break outer;
  242.                         }
  243.                     }
  244.                     //if (a[great] < pivot1) { // a[great] <= pivot2
  245.                     if (less(a[great], pivot1)) { // a[great] <= pivot2
  246.                         a[k] = a[less];
  247.                         p[k] = p[less];
  248.                         a[less] = a[great];
  249.                         p[less] = p[great];
  250.                         ++less;
  251.                     } else { // pivot1 <= a[great] <= pivot2
  252.                         a[k] = a[great];
  253.                         p[k] = p[great];
  254.                     }
  255.                     /*
  256.                      * Here and below we use "a[i] = b; i--;" instead
  257.                      * of "a[i--] = b;" due to performance issue.
  258.                      */
  259.                     a[great] = ak;
  260.                     p[great] = pk;
  261.                     --great;
  262.                 }
  263.             }
  264.  
  265.             // Swap pivots into their final positions
  266.             a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
  267.             a[right] = a[great + 1]; a[great + 1] = pivot2;
  268.             p[left]  = p[less  - 1]; p[less  - 1] = ppivot1;
  269.             p[right] = p[great + 1]; p[great + 1] = ppivot2;
  270.            
  271.  
  272.             // Sort left and right parts recursively, excluding known pivots
  273.             hackedSort(a, p, left, less - 2, leftmost);
  274.             hackedSort(a, p, great + 2, right, false);
  275.  
  276.             /*
  277.              * If center part is too large (comprises > 4/7 of the array),
  278.              * swap internal pivot values to ends.
  279.              */
  280.             if (less < e1 && e5 < great) {
  281.                 /*
  282.                  * Skip elements, which are equal to pivot values.
  283.                  */
  284.                 while (a[less] == pivot1) {
  285.                     throw new RuntimeException("We should not enter here!");
  286. //                    ++less;
  287.                 }
  288.  
  289.                 while (a[great] == pivot2) {
  290.                     throw new RuntimeException("We should not enter here!");
  291. //                    --great;
  292.                 }
  293.  
  294.                 /*
  295.                  * Partitioning:
  296.                  *
  297.                  *   left part         center part                  right part
  298.                  * +----------------------------------------------------------+
  299.                  * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
  300.                  * +----------------------------------------------------------+
  301.                  *              ^                        ^       ^
  302.                  *              |                        |       |
  303.                  *             less                      k     great
  304.                  *
  305.                  * Invariants:
  306.                  *
  307.                  *              all in (*,  less) == pivot1
  308.                  *     pivot1 < all in [less,  k)  < pivot2
  309.                  *              all in (great, *) == pivot2
  310.                  *
  311.                  * Pointer k is the first index of ?-part.
  312.                  */
  313.                 outer:
  314.                 for (int k = less - 1; ++k <= great; ) {
  315.                     int ak = a[k];
  316.                     int pk = p[k];
  317.                     if (ak == pivot1) { // Move a[k] to left part
  318.                         a[k] = a[less];
  319.                         p[k] = p[less];
  320.                         a[less] = ak;
  321.                         p[less] = pk;
  322.                         ++less;
  323.                     } else if (ak == pivot2) { // Move a[k] to right part
  324.                         while (a[great] == pivot2) {
  325.                             if (great-- == k) {
  326.                                 break outer;
  327.                             }
  328.                         }
  329.                         if (a[great] == pivot1) { // a[great] < pivot2
  330.                             a[k] = a[less];
  331.                             p[k] = p[less];
  332.                             /*
  333.                              * Even though a[great] equals to pivot1, the
  334.                              * assignment a[less] = pivot1 may be incorrect,
  335.                              * if a[great] and pivot1 are floating-point zeros
  336.                              * of different signs. Therefore in float and
  337.                              * double sorting methods we have to use more
  338.                              * accurate assignment a[less] = a[great].
  339.                              */
  340.                             a[less] = pivot1;
  341.                             p[less] = ppivot1;
  342.                             ++less;
  343.                         } else { // pivot1 < a[great] < pivot2
  344.                             a[k] = a[great];
  345.                             p[k] = p[great];
  346.                         }
  347.                         a[great] = ak;
  348.                         p[great] = pk;
  349.                         --great;
  350.                     }
  351.                 }
  352.             }
  353.  
  354.             // Sort center part recursively
  355.             hackedSort(a, p, less, great, false);
  356.  
  357.         } else { // Partitioning with one pivot
  358.             throw new RuntimeException("We should not enter here!");            
  359. //            /*
  360. //             * Use the third of the five sorted elements as pivot.
  361. //             * This value is inexpensive approximation of the median.
  362. //             */
  363. //            int pivot = a[e3];
  364. //            int ppivot = p[e3];
  365. //
  366. //            /*
  367. //             * Partitioning degenerates to the traditional 3-way
  368. //             * (or "Dutch National Flag") schema:
  369. //             *
  370. //             *   left part    center part              right part
  371. //             * +-------------------------------------------------+
  372. //             * |  < pivot  |   == pivot   |     ?    |  > pivot  |
  373. //             * +-------------------------------------------------+
  374. //             *              ^              ^        ^
  375. //             *              |              |        |
  376. //             *             less            k      great
  377. //             *
  378. //             * Invariants:
  379. //             *
  380. //             *   all in (left, less)   < pivot
  381. //             *   all in [less, k)     == pivot
  382. //             *   all in (great, right) > pivot
  383. //             *
  384. //             * Pointer k is the first index of ?-part.
  385. //             */
  386. //            for (int k = less; k <= great; ++k) {
  387. //                if (a[k] == pivot) {
  388. //                    continue;
  389. //                }
  390. //                int ak = a[k];
  391. //                int pk = p[k];
  392. //                if (less(ak, pivot)) { // Move a[k] to left part
  393. //                    a[k] = a[less];
  394. //                    p[k] = p[less];
  395. //                    a[less] = ak;
  396. //                    p[less] = pk;
  397. //                    ++less;
  398. //                } else { // a[k] > pivot - Move a[k] to right part
  399. //                    while (greater(a[great], pivot)) {
  400. //                        --great;
  401. //                    }
  402. //                    if (less(a[great], pivot)) { // a[great] <= pivot
  403. //                        a[k] = a[less];
  404. //                        p[k] = p[less];
  405. //                        a[less] = a[great];
  406. //                        p[less] = p[great];
  407. //                        ++less;
  408. //                    } else { // a[great] == pivot
  409. //                        /*
  410. //                         * Even though a[great] equals to pivot, the
  411. //                         * assignment a[k] = pivot may be incorrect,
  412. //                         * if a[great] and pivot are floating-point
  413. //                         * zeros of different signs. Therefore in float
  414. //                         * and double sorting methods we have to use
  415. //                         * more accurate assignment a[k] = a[great].
  416. //                         */
  417. //                        a[k] = pivot;
  418. //                        p[k] = ppivot;
  419. //                    }
  420. //                    a[great] = ak;
  421. //                    p[great] = pk;
  422. //                    --great;
  423. //                }
  424. //            }
  425. //
  426. //            /*
  427. //             * Sort left and right parts recursively.
  428. //             * All elements from center part are equal
  429. //             * and, therefore, already sorted.
  430. //             */
  431. //            hackedSort(a, p, left, less - 1, leftmost, depth + 1);
  432. //            hackedSort(a, p, great + 1, right, false, depth + 1);
  433.         }
  434.     }
  435.    
  436.     private void randomShuffle(int[] a, int left, int right) {
  437.         for (int i = left; i <= right; i++) {
  438.             int j = left + rnd.nextInt(i - left + 1);
  439.             swap(a, i, j);
  440.         }
  441.     }
  442.    
  443.     private void swap(int[] a, int i, int j) {
  444.         int t = a[i];
  445.         a[i] = a[j];
  446.         a[j] = t;
  447.     }
  448.  
  449.     private boolean less(int a, int b) {
  450.         if (a != NO_VALUE && b != NO_VALUE) {
  451.             return a < b;
  452.         }
  453.         if (a == NO_VALUE) {
  454.             return b > MAX_VALUE;
  455.         }
  456.         if (b == NO_VALUE) {
  457.             return a < MIN_VALUE;
  458.         }
  459.         throw new RuntimeException("We should not enter here!");
  460.     }
  461.    
  462.     private boolean greater(int a, int b) {
  463.         if (a != NO_VALUE && b != NO_VALUE) {
  464.             return a > b;
  465.         }
  466.         if (a == NO_VALUE) {
  467.             return b < MIN_VALUE;
  468.         }
  469.         if (b == NO_VALUE) {
  470.             return a > MAX_VALUE;
  471.         }
  472.         throw new RuntimeException("We should not enter here!");
  473.     }
  474.    
  475.     public void run() {
  476.         int n = 60000;
  477.        
  478.         int[] a = new int[n];
  479.         int[] p = new int[n];
  480.        
  481.         for (int i = 0; i < n; i++) {
  482.             a[i] = NO_VALUE;
  483.             p[i] = i;
  484.         }
  485.         MIN_VALUE = 1;
  486.         MAX_VALUE = n;
  487.        
  488.         long t1, t2;
  489.        
  490.         t1 = System.currentTimeMillis();
  491.         hackedSort(a, p, 0, n-1, true);
  492.         t2 = System.currentTimeMillis();
  493.         System.out.println("Generation time = " + (t2 - t1) + " ms.");
  494.        
  495.         checkValues(a, 1, n);
  496.         checkValues(p, 0, n-1);
  497.        
  498.         applyPermutation(a, p);
  499.        
  500.         /*
  501.         try {
  502.             printArray(a, new PrintWriter("output.txt"));
  503.         } catch (IOException e) {
  504.             throw new RuntimeException(e);
  505.         }
  506.         */
  507.        
  508.         t1 = System.currentTimeMillis();
  509.         Arrays.sort(a.clone());
  510.         t2 = System.currentTimeMillis();
  511.         System.out.println("Sorting time = " + (t2 - t1) + " ms.");
  512.     }
  513.    
  514.     private void applyPermutation(int[] a, int[] pos) {
  515.         int n = a.length;
  516.         int[] tmp = new int[n];
  517.         for (int i = 0; i < n; i++) {
  518.             tmp[pos[i]] = a[i];
  519.         }
  520.         for (int i = 0; i < n; i++) {
  521.             a[i] = tmp[i];
  522.             pos[i] = i;
  523.         }
  524.     }
  525.  
  526.     private void checkValues(int[] a, int min, int max) {
  527.         boolean[] b = new boolean[max - min + 1];
  528.         for (int x : a) {
  529.             if (b[x - min]) {
  530.                 throw new RuntimeException();
  531.             }
  532.             b[x - min] = true;
  533.         }
  534.     }
  535.  
  536.     private void printArray(int[] a, PrintWriter pw) {
  537.         int n = a.length;
  538.         pw.println(n);
  539.         for (int i = 0; i < n; i++) {
  540.             pw.print(a[i]);
  541.             if (i == n-1) pw.println(); else pw.print(' ');
  542.         }
  543.         pw.close();
  544.     }
  545.    
  546.     public static void main(String[] args) {
  547.         new Thread(null, new Java7QuicksortKiller(), "", 128*1024*1024).start();
  548.     }
  549.  
  550. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!