# memory efficient distance table class

During a discussion about the Traveling Salesman algorithm I was wondering how to efficiently store a distance table for N points. Typical this is a NxN 2D array which uses indices for access e.g.
distance = distance[x,y];

A distance table has two properties that would allow more efficient storage:

A distance table is (mostly) symmetric - d[x,y] == d[y,x]
A distance table has a diagonal of zero’s - d[x,x] == 0

These two properties state that an NxN distance table can be stored in (NxN - N ) / 2 elements.
(The -N is the diagonal removed and the /2 is the mirror)

This thought lead to the class DistanceTable. In essence it maps a triangular matrix without diagonal upon a linear array. An example sketch shows its memory use and performance.

``````//
//    FILE: distanceTable.ino
//  AUTHOR: Rob Tillaart
// VERSION: 0.1.00
// PURPOSE: demo of memory efficient distance table class
//    DATE: 2015-06-18
//     URL:
//
// Released to the public domain
//

#include "DistanceTable.h"

uint32_t freeRam()
{
extern int __heap_start, *__brkval;
int v;
return (uint32_t) &v - (__brkval == 0 ? (uint32_t) &__heap_start : (uint32_t) __brkval);
};

DistanceTable dt(20);

uint32_t start;
uint32_t stop;

void setup()
{
Serial.begin(115200);
DISTANCETABLE_LIB_VERSION
Serial.print("DistanceTable: ");
Serial.println(DISTANCETABLE_LIB_VERSION);
Serial.println("DistanceTable test 20x20: ");

Serial.print("clear:\t");
start = micros();
dt.clear();
stop = micros();
Serial.println(stop - start);

Serial.print("set:\t");
start = micros();
for (int i = 0; i < 20; i++)
{
for (int j = 0; j < 20; j++)
{
dt.set(i, j, i * j);
}
}
stop = micros();
Serial.println(stop - start);

Serial.print("get:\t");
int count = 0;
start = micros();
for (int i = 0; i < 20; i++)
{
for (int j = 0; j < 20; j++)
{
if ( dt.get(i, j) < 0.5 ) count++;
}
}
stop = micros();
Serial.println(stop - start);
Serial.print("count:\t");
Serial.println(count);

Serial.print("ram:\t");
Serial.println(freeRam());

Serial.println();
Serial.println("dump:\t");
for (int i = 0; i < 20; i++)
{
for (int j = 0; j < 20; j++)
{
Serial.print( dt.get(i, j), 1);
Serial.print("\t");
}
Serial.println();
}

Serial.println();
Serial.println("dump:\t");
dt.dump();

Serial.println();
Serial.println("done...");
}

void loop(){}
``````

Partial output of the test sketch (run on MEGA)

``````clear:	372
set:	3840
get:	3340
count:	58
ram:	7025
``````

The library -version 0.1.01 - is attached.

As always remarks and comments are welcome.

DistanceTable.zip (1.18 KB)