pt.tumba.ngram.svm
Class Cache

java.lang.Object
  pt.tumba.ngram.svm.Cache

public class Cache
extends java.lang.Object

SVM Kernel Cache, implementing a least recently used (LRU) policy. Since the Kernel is fully dense and may not be stored in computer memory, elements of the Kernel matrix are calculated as needed. The cache simply stores the more recently used elements, reducing the computational cost of later iterations.

Since final iterations usually need few columns of the kernel matrix, most evaluations can be avoided at the end.

Author:

Bruno Martins

Nested Class Summary

private class

Cache.CacheNode Inner class representing a Cache node.

Field Summary

private int	l The number of total data items.
private Cache.CacheNode	lru_head The first node in the LRU cache.
private Cache.CacheNode[]	nodes The Nodes in the cache.
private int	size The cache size limit in bytes.

Constructor Summary

Cache(int l, int size)
Constructor for Cache

Method Summary

private void	deleteLRU(Cache.CacheNode h) Delete a node from the cache.
(package private) int	getData(int index, float[][] data, int len) Returns free space in the cache.
private void	insertLRU(Cache.CacheNode h) Insert a node in the cache (at the last position).
void	swapIndex(int i, int j) Swap two nodes in the cache.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

l

private final int l

The number of total data items.

size

private int size

The cache size limit in bytes.

nodes

private final Cache.CacheNode[] nodes

The Nodes in the cache.

lru_head

private Cache.CacheNode lru_head

The first node in the LRU cache.

Constructor Detail

Cache

public Cache(int l,
             int size)

Constructor for Cache

Parameters:

l - The number of total data items.

size - The cache size limit in bytes.

Method Detail

deleteLRU

private void deleteLRU(Cache.CacheNode h)

Delete a node from the cache.

Parameters:

h - The node to delete.

insertLRU

private void insertLRU(Cache.CacheNode h)

Insert a node in the cache (at the last position).

Parameters:

h - The node to insert.

getData

int getData(int index,
            float[][] data,
            int len)

Returns free space in the cache. [0,len)

Parameters:

index - The least recently used index at the cache.

data - The data to store in the Cache.

len - maximum length of the data to store in the Cache.

Returns:

some position p where [p,len) need to be filled (p >= len if nothing needs to be filled)

swapIndex

public void swapIndex(int i,
                      int j)

Swap two nodes in the cache.

Parameters:

i - Position in the List for the first node.

j - Position in the List for the second node.