utils.java

一个数据挖掘软件ALPHAMINERR的整个过程的JAVA版源代码

	helpIndex = new int[numEqual];
	for (int j = 0; j < numEqual; j++) {
	  helpIndex[j] = i + j;
	}
	quickSort(index, helpIndex, 0, numEqual - 1);
	for (int j = 0; j < numEqual; j++) {
	  newIndex[i + j] = index[helpIndex[j]];
	}
	i += numEqual;
      } else {
	newIndex[i] = index[i];
	i++;
      }
    }
    return newIndex;
  }

  /**
   * Sorts a given array of doubles in ascending order and returns an
   * array of integers with the positions of the elements of the
   * original array in the sorted array. NOTE THESE CHANGES: the sort
   * is no longer stable and it doesn't use safe floating-point
   * comparisons anymore. Occurrences of Double.NaN are treated as 
   * Double.MAX_VALUE
   *
   * @param array this array is not changed by the method!
   * @return an array of integers with the positions in the sorted
   * array.  
   */
  public static int[] sort(double [] array) {

    int [] index = new int[array.length];
    array = (double [])array.clone();
    for (int i = 0; i < index.length; i++) {
      index[i] = i;
      if (Double.isNaN(array[i])) {
        array[i] = Double.MAX_VALUE;
      }
    }
    quickSort(array, index, 0, array.length - 1);
    return index;
  }

  /**
   * Sorts a given array of doubles in ascending order and returns an 
   * array of integers with the positions of the elements of the original 
   * array in the sorted array. The sort is stable (Equal elements remain
   * in their original order.) Occurrences of Double.NaN are treated as 
   * Double.MAX_VALUE
   *
   * @param array this array is not changed by the method!
   * @return an array of integers with the positions in the sorted
   * array.
   */
  public static int[] stableSort(double [] array){

    int [] index = new int[array.length];
    int [] newIndex = new int[array.length];
    int [] helpIndex;
    int numEqual;
    
    array = (double [])array.clone();
    for (int i = 0; i < index.length; i++) {
      index[i] = i;
      if (Double.isNaN(array[i])) {
        array[i] = Double.MAX_VALUE;
      }
    }
    quickSort(array,index,0,array.length-1);

    // Make sort stable

    int i = 0;
    while (i < index.length) {
      numEqual = 1;
      for (int j = i+1; ((j < index.length) && Utils.eq(array[index[i]],
							array[index[j]])); j++)
	numEqual++;
      if (numEqual > 1) {
	helpIndex = new int[numEqual];
	for (int j = 0; j < numEqual; j++)
	  helpIndex[j] = i+j;
	quickSort(index, helpIndex, 0, numEqual-1);
	for (int j = 0; j < numEqual; j++) 
	  newIndex[i+j] = index[helpIndex[j]];
	i += numEqual;
      } else {
	newIndex[i] = index[i];
	i++;
      }
    }

    return newIndex;
  }

  /**
   * Computes the variance for an array of doubles.
   *
   * @param vector the array
   * @return the variance
   */
  public static double variance(double[] vector) {
  
    double sum = 0, sumSquared = 0;

    if (vector.length <= 1) {
      return 0;
    }
    for (int i = 0; i < vector.length; i++) {
      sum += vector[i];
      sumSquared += (vector[i] * vector[i]);
    }
    double result = (sumSquared - (sum * sum / (double) vector.length)) / 
      (double) (vector.length - 1);

    // We don't like negative variance
    if (result < 0) {
      return 0;
    } else {
      return result;
    }
  }

  /**
   * Computes the sum of the elements of an array of doubles.
   *
   * @param doubles the array of double
   * @return the sum of the elements
   */
  public static double sum(double[] doubles) {

    double sum = 0;

    for (int i = 0; i < doubles.length; i++) {
      sum += doubles[i];
    }
    return sum;
  }

  /**
   * Computes the sum of the elements of an array of integers.
   *
   * @param ints the array of integers
   * @return the sum of the elements
   */
  public static int sum(int[] ints) {

    int sum = 0;

    for (int i = 0; i < ints.length; i++) {
      sum += ints[i];
    }
    return sum;
  }

  /**
   * Returns c*log2(c) for a given integer value c.
   *
   * @param c an integer value
   * @return c*log2(c) (but is careful to return 0 if c is 0)
   */
  public static double xlogx(int c) {
    
    if (c == 0) {
      return 0.0;
    }
    return c * Utils.log2((double) c);
  }

  /**
   * Implements quicksort for an array of indices.
   *
   * @param array the array of integers to be sorted
   * @param index the index which should contain the positions in the
   * sorted array
   * @param lo0 the first index of the subset to be sorted
   * @param hi0 the last index of the subset to be sorted
   */
  private static void quickSort(int [] array, int [] index,
				int lo0, int hi0) {

    int lo = lo0;
    int hi = hi0;
    int mid;
    int help;
    
    if (hi0 > lo0) {
      
      // Arbitrarily establishing partition element as the midpoint of
      // the array.
      mid = array[index[(lo0 + hi0) / 2]];

      // loop through the array until indices cross
      while (lo <= hi) {
	
	// find the first element that is greater than or equal to  
	// the partition element starting from the left Index.
	while ((array[index[lo]] < mid) && (lo < hi0)) {
	  ++lo;
	}
	
	// find an element that is smaller than or equal to 
	// the partition element starting from the right Index.
	while ((array[index[hi]] > mid) && (hi > lo0)) {
	  --hi;
	}
	
	// if the indexes have not crossed, swap
	if (lo <= hi) {
	  help = index[lo];
	  index[lo] = index[hi];
	  index[hi] = help;
	  ++lo;
	  --hi;
	}
      }
      
      // If the right index has not reached the left side of array
      // must now sort the left partition.
      if (lo0 < hi) {
	quickSort(array, index, lo0, hi);
      }
      
      // If the left index has not reached the right side of array
      // must now sort the right partition.
      if (lo < hi0) {
	quickSort(array, index, lo, hi0);
      }
    }
  }

  /**
   * Implements unsafe quicksort for an array of indices.
   *
   * @param array the array of doubles to be sorted
   * @param index the index which should contain the positions in the
   * sorted array
   * @param lo0 the first index of the subset to be sorted
   * @param hi0 the last index of the subset to be sorted
   */
  private static void quickSort(double [] array, int [] index, int lo0, int hi0) {

    int lo = lo0;
    int hi = hi0;
    double mid;
    int help;
    
    if (hi0 > lo0) {
      
      // Arbitrarily establishing partition element as the midpoint of
      // the array.
      mid = array[index[(lo0 + hi0) / 2]];

      // loop through the array until indices cross
      while (lo <= hi) {
	
	// find the first element that is greater than or equal to  
	// the partition element starting from the left Index.
	while ((array[index[lo]] < mid) && (lo < hi0)) {
	  ++lo;
	}
	
	// find an element that is smaller than or equal to 
	// the partition element starting from the right Index.
	while ((array[index[hi]] > mid) && (hi > lo0)) {
	  --hi;
	}
	
	// if the indexes have not crossed, swap
	if (lo <= hi) {
	  help = index[lo];
	  index[lo] = index[hi];
	  index[hi] = help;
	  ++lo;
	  --hi;
	}
      }
      
      // If the right index has not reached the left side of array
      // must now sort the left partition.
      if (lo0 < hi) {
	quickSort(array, index, lo0, hi);
      }
      
      // If the left index has not reached the right side of array
      // must now sort the right partition.
      if (lo < hi0) {
	quickSort(array, index, lo, hi0);
      }
    }
  }

  /**
   * Main method for testing this class.
   *
   * @param ops some dummy options
   */
  public static void main(String[] ops) {

    double[] doubles = {4.5, 6.7, Double.NaN, 3.4, 4.8, 1.2, 3.4};
    int[] ints = {12, 6, 2, 18, 16, 6, 7, 5};

    try {

      // Option handling
      System.out.println("First option split up:");
      if (ops.length > 0) {
	String[] firstOptionSplitUp = Utils.splitOptions(ops[0]);
	for (int i = 0; i < firstOptionSplitUp.length; i ++) {
	  System.out.println(firstOptionSplitUp[i]);
	}
      }					       
      System.out.println("Partitioned options: ");
      String[] partitionedOptions = Utils.partitionOptions(ops);
      for (int i  = 0; i < partitionedOptions.length; i++) {
	System.out.println(partitionedOptions[i]);
      }
      System.out.println("Get flag -f: " + Utils.getFlag('f', ops));
      System.out.println("Get option -o: " + Utils.getOption('o', ops));
      System.out.println("Checking for remaining options... ");
      Utils.checkForRemainingOptions(ops);
      
      // Statistics
      System.out.println("Original array (doubles): ");
      for (int i = 0; i < doubles.length; i++) {
	System.out.print(doubles[i] + " ");
      }
      System.out.println();
      System.out.println("Original array (ints): ");
      for (int i = 0; i < ints.length; i++) {
	System.out.print(ints[i] + " ");
      }
      System.out.println();
      System.out.println("Correlation: " + Utils.correlation(doubles, doubles, 
							     doubles.length));
      System.out.println("Mean: " + Utils.mean(doubles));
      System.out.println("Variance: " + Utils.variance(doubles));
      System.out.println("Sum (doubles): " + Utils.sum(doubles));
      System.out.println("Sum (ints): " + Utils.sum(ints));
      System.out.println("Max index (doubles): " + Utils.maxIndex(doubles));
      System.out.println("Max index (ints): " + Utils.maxIndex(ints));
      System.out.println("Min index (doubles): " + Utils.minIndex(doubles));
      System.out.println("Min index (ints): " + Utils.minIndex(ints));
      
      // Sorting and normalizing
      System.out.println("Sorted array (doubles): ");
      int[] sorted = Utils.sort(doubles);
      for (int i = 0; i < doubles.length; i++) {
	System.out.print(doubles[sorted[i]] + " ");
      }
      System.out.println();
      System.out.println("Normalized array (doubles): ");
      Utils.normalize(doubles);
      for (int i = 0; i < doubles.length; i++) {
	System.out.print(doubles[i] + " ");
      }
      System.out.println();
      System.out.println("Normalized again (doubles): ");
      Utils.normalize(doubles, Utils.sum(doubles));
      for (int i = 0; i < doubles.length; i++) {
	System.out.print(doubles[i] + " ");
      }
      System.out.println();
      
      // Pretty-printing
      System.out.println("-4.58: " + Utils.doubleToString(-4.57826535, 2));
      System.out.println("-6.78: " + Utils.doubleToString(-6.78214234, 6,2));
      
      // Comparisons
      System.out.println("5.70001 == 5.7 ? " + Utils.eq(5.70001, 5.7));
      System.out.println("5.70001 > 5.7 ? " + Utils.gr(5.70001, 5.7));
      System.out.println("5.70001 >= 5.7 ? " + Utils.grOrEq(5.70001, 5.7));
      System.out.println("5.7 < 5.70001 ? " + Utils.sm(5.7, 5.70001));
      System.out.println("5.7 <= 5.70001 ? " + Utils.smOrEq(5.7, 5.70001));
      
      // Math
      System.out.println("Info (ints): " + Utils.info(ints));
      System.out.println("log2(4.6): " + Utils.log2(4.6));
      System.out.println("5 * log(5): " + Utils.xlogx(5));
      System.out.println("5.5 rounded: " + Utils.round(5.5));
      System.out.println("5.55555 rounded to 2 decimal places: " + 
			 Utils.roundDouble(5.55555, 2));
    } catch (Exception e) {
      e.printStackTrace();
    }
  }
}