Skip to content

Instantly share code, notes, and snippets.

Avatar

Alrecenk Alrecenk

View GitHub Profile
@Alrecenk
Alrecenk / insland.java
Created Sep 30, 2017
Island Counting: Flood Fill vs Hash Deduping
View insland.java
package scratch;
import java.util.*;
public class islands {
public static void main(String args[]){
boolean map[][] = generateIslands(180, 50, new Random(287), 25, 15, .3);
System.out.println(drawMap(map));
@Alrecenk
Alrecenk / Cache.java
Created Oct 21, 2015
LRU Cache using java generics.
View Cache.java
/* This is an efficient implementation of a fixed size cache using Java generics.
* It uses a least recently used eviction policy implemented via a combination hashtable/linked list data structure.
* Written by Alrecenk October 2015 because I felt like playing with generics.
*/
import java.util.HashMap;
import java.util.Random;
public class Cache<KeyType, RecordType>{
@Alrecenk
Alrecenk / fastexp.java
Last active Oct 15, 2019
Very fast accurate approximation to Math.exp in java using floating point bit hacks.
View fastexp.java
/* fast floating point exp function
* must initialize table with buildexptable before using
Based on
A Fast, Compact Approximation of the Exponential Function
Nicol N. Schraudolph 1999
Adapted to single precision to improve speed and added adjustment table to improve accuracy.
Alrecenk 2014
@Alrecenk
Alrecenk / PerfectThumbnail.java
Last active Aug 29, 2015
Scales down an image by an area weighted averaging of all overlapping pixels. Equivalent to infinite supersampling.
View PerfectThumbnail.java
//scales an image, maintaining aspect ratio, to fit within the desired width and height
//averages color over squares weighted by overlap area to get "perfect" results when scaling down
//does not interpolate and is not designed for scaling up, only down (hence thumbnail)
public static BufferedImage makethumbnail(BufferedImage img, double desiredwidth, double desiredheight){
//System.out.println("Original Image size: " + img.getWidth(null)+ " x "+img.getHeight(null));
if(img ==null || img.getWidth(null) <1 || img.getHeight(null) <1){
return null; // something wrong with image
}else{
byte image[][][] = convertimage(img) ; // convert to byte array, first index is x, then y, then {r,g,b}
@Alrecenk
Alrecenk / LogisticRegressionHessian.java
Created May 21, 2014
Hessian (second derivative) of error calculation for a logistic regression model.
View LogisticRegressionHessian.java
//returns the hessian (gradient of gradient) of error with respect to weights
//for a logistic regression with weights w on the given input and output
//output should be in the form 0 for negative, 1 for positive
public double[][] hessian(double w[]){
heval++;//keep track of how many times this has been called
double h[][] = new double[w.length][] ;
//second derivative matrices are always symmetric so we only need triangular portion
for(int j=0;j<h.length;j++){
h[j] = new double [j+1] ;
}
@Alrecenk
Alrecenk / LogisticRegressionGradientDescent.java
Created May 20, 2014
Functions required for gradient descent to fit a Logistic Regression model.
View LogisticRegressionGradientDescent.java
//starting from w0 searches for a weight vector using gradient descent
//and Wolfe condition line-search until the gradient magnitude is below tolerance
//or a maximum number of iterations is reached.
public double[] gradientDescent(double w0[], double tolerance, int maxiter){
double w[] = w0 ;
double gradient[] = gradient(w0) ;
int iteration = 0 ;
while(Math.sqrt(dot(gradient,gradient)) > tolerance && iteration < maxiter){
iteration++ ;
//calculate step-size in direction of negative gradient
@Alrecenk
Alrecenk / WolfeConditionInexactLineSearch.java
Last active Aug 29, 2015
Performs an inexact line-search for optimization . Finds a step-size satisfying the Wolfe conditions by binary search.
View WolfeConditionInexactLineSearch.java
//Performs a binary search to satisfy the Wolfe conditions
//returns alpha where next x =should be x0 + alpha*d
//guarantees convergence as long as search direction is bounded away from being orthogonal with gradient
//x0 is starting point, d is search direction, alpha is starting step size, maxit is max iterations
//c1 and c2 are the constants of the Wolfe conditions (0.1 and 0.9 can work)
public static double stepSize(OptimizationProblem problem, double[] x0, double[] d, double alpha, int maxit, double c1, double c2){
//get error and gradient at starting point
double fx0 = problem.error(x0);
double gx0 = dot(problem.gradient(x0), d);
@Alrecenk
Alrecenk / LogisticRegressionInitialGuess.java
Created May 17, 2014
A simple initial guess for a logistic regression. P and N are the average inputs of the positives and negatives respectively.
View LogisticRegressionInitialGuess.java
for(int k=0;k<pos.length;k++){
pp += pos[k]*pos[k] ;
pn += pos[k]*neg[k] ;// calculate relevant dot products
nn += neg[k]*neg[k] ;
}
//assuming w = alpha * (pos- neg) with b in the last w slot
//solve for alpha and b so that pos returns 0.75 and neg returns 0.25
double alphab[] = lineIntersection(pp-pn,1,sinv(0.75),pn-nn,1,sinv(0.25)) ;
w = new double[input[0].length] ;
for(int k=0;k<w.length-1;k++){
@Alrecenk
Alrecenk / LogisticRegressionSimple.java
Last active Aug 29, 2015
A logistic regression algorithm for binary classification implemented using Newton's method and a Wolfe condition based inexact line-search.
View LogisticRegressionSimple.java
/* A logistic regression algorithm for binary classification implemented using Newton's method and
* a Wolfe condition based inexact line-search.
*created by Alrecenk for inductivebias.com May 2014
*/
public class LogisticRegressionSimple {
double w[] ; //the weights for the logistic regression
int degree ; // degree of polynomial used for preprocessing
//preprocessed list of input/output used for calculating error and its gradients
@Alrecenk
Alrecenk / RotationForestsplit.java
Created Nov 5, 2013
The core learning algorithm for the rotation forest that calculates the best split based on approximate information gain.
View RotationForestsplit.java
//splits this node if it should and returns whether it did
//data is assumed to be a set of presorted lists where data[k][j] is the jth element of data when sorted by axis[k]
public boolean split(int minpoints){
//if already split or one class or not enough points remaining then don't split
if (branchnode || totalpositive == 0 || totalnegative == 0 || totalpositive + totalnegative < minpoints){
return false;
}else{
int bestaxis = -1, splitafter=-1;
double bestscore = Double.MAX_VALUE;//any valid split will beat no split
int bestLp=0, bestLn=0;