it.unimi.dsi.mg4j.util
Class Fast

java.lang.Object
  extended byit.unimi.dsi.mg4j.util.Fast

public final class Fast
extends Object

All-purpose optimised static-method container class.

This class contains static optimised utility methods that are used by all MG4J classes.

Since:
0.1
Author:
Sebastiano Vigna

Field Summary
static int[] BYTELSB
          Precomputed least significant bits for bytes (-1 for 0 ).
static int[] BYTEMSB
          Precomputed most significant bits for bytes (-1 for 0 ).
static double GOLOMB_ADD
           
protected static double GOLOMB_GAUSSIAN
           
static double GOLOMB_MULT
           
static double[] GOLOMB_STEP
           
static int GOLOMB_STEP_LENGTH
           
static double GOLOMB_THRESHOLD
           
 
Method Summary
static String format(double d)
          Formats a number.
static String format(long l)
          Formats a number.
static int gaussianGolombModulus(double sigma)
          Computes the Golomb modulus for (positive and negative) integers normally distributed with given standard deviation using the formula ⌈ 2 sqrt( 2 / π ) ln(2) σ ⌉.
static int golombModulus(double p)
          Computes the Golomb modulus for a given frequency using the formula GOLOMB_ADD + GOLOMB_MULT / p if p is smaller than GOLOMB_THRESHOLD, scanning GOLOMB_STEP otherwise.
static int int2nat(int x)
          Maps integers bijectively into natural numbers.
static int leastSignificantBit(int x)
          Computes the least significant bit of an integer.
static int leastSignificantBit(long x)
          Computes the least significant bit of a long integer.
static int[] loadInts(String filename)
          Loads a list of integers from a data-input file stream.
static int[] loadInts(String filename, ProgressMeter pm)
          Loads a list of integers from a data-input file stream.
static Object loadObject(String filename)
          Loads an object from a given file.
static int mostSignificantBit(int x)
          Computes the most significant bit of an integer.
static int mostSignificantBit(long x)
          Computes the most significant bit of a long integer.
static int nat2int(int x)
          Maps natural numbers bijectively into integers.
static int parseIntSize(CharSequence s)
          Parses a size specified using units (e.g., K, Ki, M, Mi,…), ensuring that the results fits an integer.
static long parseSize(CharSequence s)
          Parses a size specified using units (e.g., K, Ki, M, Mi,…).
static void storeObject(Object o, String filename)
          Stores an object in a given file.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

GOLOMB_STEP

public static final double[] GOLOMB_STEP

GOLOMB_STEP_LENGTH

public static final int GOLOMB_STEP_LENGTH

GOLOMB_THRESHOLD

public static final double GOLOMB_THRESHOLD
See Also:
Constant Field Values

GOLOMB_ADD

public static final double GOLOMB_ADD

GOLOMB_MULT

public static final double GOLOMB_MULT

GOLOMB_GAUSSIAN

protected static final double GOLOMB_GAUSSIAN

BYTELSB

public static final int[] BYTELSB
Precomputed least significant bits for bytes (-1 for 0 ).


BYTEMSB

public static final int[] BYTEMSB
Precomputed most significant bits for bytes (-1 for 0 ).

Method Detail

mostSignificantBit

public static int mostSignificantBit(int x)
Computes the most significant bit of an integer.

Parameters:
x - an integer.
Returns:
the most significant bit of the argument (-1 for 0).

mostSignificantBit

public static int mostSignificantBit(long x)
Computes the most significant bit of a long integer.

Parameters:
x - a long integer.
Returns:
the most significant bit of the argument (-1 for 0 ).

leastSignificantBit

public static int leastSignificantBit(int x)
Computes the least significant bit of an integer.

Parameters:
x - an integer.
Returns:
the least significant bit of the argument (-1 for 0).

leastSignificantBit

public static int leastSignificantBit(long x)
Computes the least significant bit of a long integer.

Parameters:
x - a long integer.
Returns:
the least significant bit of the argument (-1 for 0).

golombModulus

public static int golombModulus(double p)
Computes the Golomb modulus for a given frequency using the formula GOLOMB_ADD + GOLOMB_MULT / p if p is smaller than GOLOMB_THRESHOLD, scanning GOLOMB_STEP otherwise. This gives results that are extremely close to ⌈ log( 2 - p ) / log( 1 - p ) ⌉, but order of magnitudes more quickly.

Parameters:
p - the frequency divided by the overall number of documents.
Returns:
the Golomb modulus for the given ratio.

gaussianGolombModulus

public static int gaussianGolombModulus(double sigma)
Computes the Golomb modulus for (positive and negative) integers normally distributed with given standard deviation using the formula ⌈ 2 sqrt( 2 / π ) ln(2) σ ⌉.

The resulting Golomb modulus is near to optimal for coding such integers after they have been passed through int2nat(int). Note, however, that Golomb coding is not optimal for a normal distribution.

Parameters:
sigma - the standard deviation.
Returns:
the Golomb modulus for the given standard deviation.

int2nat

public static int int2nat(int x)
Maps integers bijectively into natural numbers.

This method will map a negative integer x to -2x-1 and a nonnegative integer x to 2x. It can be used to save arbitrary integers using the standard coding methods (which all work on natural numbers).

The inverse of the above map is computed by nat2int(int)

Parameters:
x - an integer.
Returns:
the argument mapped into natural numbers.
See Also:
nat2int(int)

nat2int

public static int nat2int(int x)
Maps natural numbers bijectively into integers.

This method computes the inverse of int2nat(int)

Parameters:
x - a natural number.
Returns:
the argument mapped into an integer.
See Also:
int2nat(int)

format

public static String format(double d)
Formats a number.

This method formats a double separating thousands and printing just two fractional digits.

Parameters:
d - a number.
Returns:
a string containing a pretty print of the number.

format

public static String format(long l)
Formats a number.

This method formats a double separating thousands and printing just two fractional digits.

Parameters:
l - a number.
Returns:
a string containing a pretty print of the number.

parseSize

public static long parseSize(CharSequence s)
Parses a size specified using units (e.g., K, Ki, M, Mi,…). The argument must be in the form number [unit] (with no space inbetween). Unit may be one of K (103), Ki (210), M (106), Mi (220), G (109), Gi (230), T (1012), Ti (240).

Parameters:
s - a size specified as above.
Returns:
the corresponding number.
Throws:
IllegalArgumentException - if number is negative or unit is not among the abovementioned ones.

parseIntSize

public static int parseIntSize(CharSequence s)
Parses a size specified using units (e.g., K, Ki, M, Mi,…), ensuring that the results fits an integer.

Parameters:
s - a size specified as above.
Returns:
the corresponding number.
Throws:
IllegalArgumentException - parseSize(CharSequence) would, or if the resulting size exceeds Integer.MAX_VALUE.
See Also:
parseSize(CharSequence)

storeObject

public static void storeObject(Object o,
                               String filename)
                        throws FileNotFoundException,
                               IOException
Stores an object in a given file.

Parameters:
o - an object.
filename - a filename.
Throws:
FileNotFoundException
IOException

loadObject

public static Object loadObject(String filename)
                         throws IOException,
                                ClassNotFoundException
Loads an object from a given file.

Parameters:
filename - a filename.
Throws:
IOException
ClassNotFoundException

loadInts

public static int[] loadInts(String filename)
                      throws IOException
Loads a list of integers from a data-input file stream.

This method considers the given filename as a list of integers saved in DataOutput format.

Parameters:
filename - a filename.
Returns:
an array of integers, loaded from the given file opened as a DataInput.
Throws:
IOException

loadInts

public static int[] loadInts(String filename,
                             ProgressMeter pm)
                      throws IOException
Loads a list of integers from a data-input file stream.

This method considers the given filename as a list of integers saved in DataOutput format.

Parameters:
filename - a filename.
pm - a progress meter, or null.
Returns:
an array of integers, loaded from the given file opened as a DataInput.
Throws:
IOException