sparsevector.java

常用机器学习算法,java编写源代码,内含常用分类算法,包括说明文档

	 *   set this[i] *= factor * v[i].
	 *  If v has indices that are not present in this,
	 *   these are just ignored.
	 */
	public void timesEqualsSparse (SparseVector v, double factor)
	{
    // Special case for dense sparse vector
    if (indices == null) { denseTimesEqualsSparse (v, factor); return; }

		int loc1 = 0;
		int loc2 = 0;
		
		while ((loc1 < numLocations()) && (loc2 < v.numLocations())) {
			int idx1 = indexAtLocation (loc1);
			int idx2 = v.indexAtLocation (loc2);
			if (idx1 == idx2) {
				values [loc1] *= v.valueAtLocation (loc2) * factor;
				++loc1; ++loc2;
			} else if (idx1 < idx2) {
				++loc1;
			} else {
        // idx2 not present in this. Ignore.
				++loc2;
			}
		}
	}

    

        /**
	 * Scale all elements by the same factor.
	 */
        public void timesEquals( double factor )
        {
	    for (int i = 0; i < values.length; i++)
		values[i] *= factor;
	}


  private void densePlusEqualsSparse (SparseVector v, double factor)
  {
    int maxloc = v.numLocations();
    for (int loc = 0; loc < maxloc; loc++) {
      int idx = v.indexAtLocation (loc);
      if (idx >= values.length) break;
      values [idx] += v.valueAtLocation (loc) * factor;
    }
  }


  private void denseTimesEqualsSparse (SparseVector v, double factor)
  {
    int maxloc = v.numLocations();
    for (int loc = 0; loc < maxloc; loc++) {
      int idx = v.indexAtLocation (loc);
      if (idx >= values.length) break;
      values [idx] *= v.valueAtLocation (loc) * factor;
    }
  }

    /**
	 * Increments this[index] by value.
	 * @throws IllegalArgumentException If index is not present.
	 */
	public void incrementValue (int index, double value)
		throws IllegalArgumentException
	{
		int loc = location (index);
		if (loc >= 0)
			values[loc] += value;
		else
			throw new IllegalArgumentException ("Trying to set value that isn't present in SparseVector");
	}

	/** Sets every present index in the vector to v. */
	public void setAll (double v)
	{
		for (int i = 0; i < values.length; i++)
			values[i] = v;
	}

	/**
	 * Sets the value at the given index.
	 *  @throws IllegalArgumentException If index is not present.
	 */
	public void setValue (int index, double value)
		throws IllegalArgumentException
	{
		if (indices == null)
			values[index] = value;
		else {
			int loc = location(index);
			if (loc < 0)
				throw new IllegalArgumentException ("Can't insert values into a sparse Vector.");
			else
				values[loc] = value;
		}
	}

	/** Sets the value at the given location. */
	public void setValueAtLocation (int location, double value)
	{
		values[location] = value;
	}

        /** Copy values from an array into this vector. The array should have the
	 * same size as the vector */
    // yanked from DenseVector
        public final void arrayCopyFrom( double[] a ) 
        {
	    arrayCopyFrom(a,0);
	}

        /** Copy values from an array starting at a particular location into this
	 * vector. The array must have at least as many values beyond the 
	 * starting location as there are in the vector.
	 *
	 * @return Next uncopied location in the array.
	 */
        public final int arrayCopyFrom( double [] a , int startingArrayLocation )
        {
	    System.arraycopy( a, startingArrayLocation, 
			      values, 0, values.length );
	    
	    return startingArrayLocation + values.length;
	}
	

    /** 
     * Applies the method argument to each value in a non-binary vector. 
     * The method should both accept a Double as an argument and return a Double.
     *
     * @throws IllegalArgumentException If the method argument has an 
     *                                  inappropriate signature.
     * @throws UnsupportedOperationException If vector is binary 
     * @throws IllegalAccessException If the method is inaccessible
     * @throws Throwable If the method throws an exception it is relayed
     */
    public final void map (Method f) throws IllegalAccessException, Throwable
    {
	if (values == null)
	    throw new UnsupportedOperationException
		("Binary values may not be altered via map");

	if (f.getParameterTypes().length!=1 ||
	    f.getParameterTypes()[0] != Double.class ||
	    f.getReturnType() != Double.class )
	    throw new IllegalArgumentException
		("Method signature must be \"Double f (Double x)\"");

	try {
	    for (int i=0 ; i<values.length ; i++)
		values[i] = ((Double)f.invoke 
			     (null, 
			      new Object[]
				 {new Double(values[i])})).doubleValue ();
	} catch (InvocationTargetException e) {
	    throw e.getTargetException();
	}
    }


        /** Copy the contents of this vector into an array starting at a 
	 * particular location. 
	 *
	 * @return Next available location in the array 
	 */
        public final int arrayCopyInto (double[] array, int startingArrayLocation)
	{
		System.arraycopy (values, 0, array, startingArrayLocation, 
				  values.length);
		return startingArrayLocation + values.length;
	}



	/***********************************************************************
	 *  VECTOR OPERATIONS
	 ***********************************************************************/
	
	public double dotProduct (ConstantMatrix m) {
		if (m instanceof SparseVector) return dotProduct ((SparseVector)m);
		else if (m instanceof DenseVector) return dotProduct ((DenseVector)m);
		else throw new IllegalArgumentException ("Unrecognized Matrix type "+m.getClass());
	}

	public double dotProduct (DenseVector v) {
		double ret = 0;
		if (values == null)
			for (int i = 0; i < indices.length; i++)
				ret += v.value(indices[i]);
		else
			for (int i = 0; i < indices.length; i++)
				ret += values[i] * v.value(indices[i]);
		return ret;
	}


	// added by dmetzler
	public double dotProduct (SparseVector v)
	{
		double ret = 0.0;
		SparseVector vShort = null;
		SparseVector vLong = null;
		// this ensures minimal computational effort
		if(numLocations() > v.numLocations ()) {
			vShort = v;
			vLong = this;
		} else {
			vShort = this;
			vLong = v;
		}

		for(int i = 0; i < vShort.numLocations(); i++) {
			ret += vShort.valueAtLocation (i) *
						 vLong.value (vShort.indexAtLocation(i));
		}
	
		return ret;
	}
	

	public SparseVector vectorAdd(SparseVector v, double scale) {
		if(indices != null) { // sparse SparseVector
			int [] ind = v.getIndices();
			double [] val = v.getValues();
			int [] newIndices = new int[ind.length+indices.length];
			double [] newVals = new double[ind.length+indices.length];
			for(int i = 0; i < indices.length; i++) {
		    newIndices[i] = indices[i];
		    newVals[i] = values[i];
			}
			for(int i = 0; i < ind.length; i++) {
		    newIndices[i+indices.length] = ind[i];
		    newVals[i+indices.length] = scale*val[i];
			}
			return new SparseVector(newIndices, newVals, true, true, false);
		}
		int [] newIndices = new int[values.length];
		double [] newVals = new double[values.length]; // dense SparseVector
		int curPos = 0;
		for(int i = 0; i < values.length; i++) {
			double val = values[i]+scale*v.value(i);
			if(val != 0.0) {
		    newIndices[curPos] = i;
		    newVals[curPos++] = val;
			}
		}
		return new SparseVector(newIndices, newVals, true, true, false);
	}

	public double oneNorm () {
		double ret = 0;
		if (values == null)
			return indices.length;
		for (int i = 0; i < values.length; i++)
			ret += values[i];
		return ret;
	}

	public double absNorm () {
		double ret = 0;
		if (values == null)
			return indices.length;
		for (int i = 0; i < values.length; i++)
			ret += Math.abs(values[i]);
		return ret;
	}
	
	public double twoNorm () {
		double ret = 0;
		if (values == null)
			return Math.sqrt (indices.length);
		for (int i = 0; i < values.length; i++)
			ret += values[i] * values[i];
		return Math.sqrt (ret);
	}
	
	public double infinityNorm () {
		if (values == null)
			return 1.0;
		double max = Double.NEGATIVE_INFINITY;
		for (int i = 0; i < values.length; i++)
			if (Math.abs(values[i]) > max)
				max = Math.abs(values[i]);
		return max;
	}		

	public void print() 
	{
		if (values == null) {
			// binary sparsevector
			for (int i = 0; i < indices.length; i++)
				System.out.println ("SparseVector["+indices[i]+"] = 1.0");
		} else {
			for (int i = 0; i < values.length; i++) {
				int idx = (indices == null) ? i : indices [i];
				System.out.println ("SparseVector["+idx+"] = "+values[i]);
			}
		}
	}
		
	public boolean isNaN() {
		if (values == null)
			return false;
		for (int i = 0; i < values.length; i++)
			if (Double.isNaN(values[i]))
				return true;
		return false;
	}

	
	protected void sortIndices ()
	{
		int numDuplicates = 0;
		if (indices == null)
			// It's dense, and thus by definition sorted.
			return;
		if (values == null)
			java.util.Arrays.sort (indices);
		else {
			// Just BubbleSort; this is efficient when already mostly sorted.
			// Note that we BubbleSort from the the end forward; this is most efficient
			//  when we have added a few additional items to the end of a previously sorted list.
			//  We could be much smarter if we remembered the highest index that was already sorted
			for (int i = indices.length-1; i >= 0; i--) {
				boolean swapped = false;
				for (int j = 0; j < i; j++)
					if (indices[j] == indices[j+1] && i == indices.length-1) {
						numDuplicates++;
					} else if (indices[j] > indices[j+1]) {
						// Swap both indices and values
						int f;
						f = indices[j];
						indices[j] = indices[j+1];
						indices[j+1] = f;
						if (values != null) {
							double v;
							v = values[j];
							values[j] = values[j+1];
							values[j+1] = v;
						}
						swapped = true;
					}
				if (!swapped)
					break;
			}
		}

		//if (values == null)
		numDuplicates = 0;
		for (int i = 1; i < indices.length; i++)
			if (indices[i-1] == indices[i])
				numDuplicates++;

		if (numDuplicates > 0)
			removeDuplicates (numDuplicates);
	}

	// Argument zero is special value meaning that this function should count them.
	protected void removeDuplicates (int numDuplicates)
	{
		if (numDuplicates == 0)
			for (int i = 1; i < indices.length; i++)
				if (indices[i-1] == indices[i])
					numDuplicates++;
		if (numDuplicates == 0)
			return;
		int[] newIndices = new int[indices.length - numDuplicates];
		double[] newValues = values == null ? null : new double[indices.length - numDuplicates];
		newIndices[0] = indices[0];
		if (values != null) newValues[0] = values[0];
		for (int i = 1, j = 1; i < indices.length; i++) {
			if (indices[i] == indices[i-1]) {
				if (newValues != null)
					newValues[j-1] += values[i];
			} else {
				newIndices[j] = indices[i];
				if (values != null)
					newValues[j] = values[i];
				j++;
			}
		}
		this.indices = newIndices;
		this.values = newValues;
	}


	/// Serialization

	private static final long serialVersionUID = 2;  
	private static final int CURRENT_SERIAL_VERSION = 1;
	
	
	private void writeObject (ObjectOutputStream out) throws IOException
	{
		out.writeInt (CURRENT_SERIAL_VERSION);
		out.writeInt (indices == null ? -1 : indices.length);
		out.writeInt (values == null ? -1 : values.length);
		if (indices != null)
			for (int i = 0; i < indices.length; i++)
				out.writeInt (indices[i]);
		if (values != null)
			for (int i = 0; i < values.length; i++)
				out.writeDouble (values[i]);
	}

	private void readObject (ObjectInputStream in)
		throws IOException, ClassNotFoundException
	{
		int version = in.readInt ();
		int indicesSize = in.readInt();
		int valuesSize = in.readInt();

		if (indicesSize >= 0) {
			indices = new int[indicesSize];
			for (int i = 0; i < indicesSize; i++)
				indices[i] = in.readInt();
		}
		if (valuesSize >= 0) {
			values = new double[valuesSize];
			for (int i = 0; i < valuesSize; i++)
				values[i] = in.readDouble();
		}
	}
}