Go Down

### Topic: memory efficient distance table class (Read 737 times)previous topic - next topic

#### robtillaart ##### Jun 19, 2015, 04:08 pmLast Edit: Jun 19, 2015, 06:29 pm by robtillaart
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.
Code: (distanceTable.ino) [Select]
`////    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)
Code: [Select]
`clear: 372set: 3840get: 3340count: 58ram: 7025`

The library -version 0.1.01 - is attached.

As always remarks and comments are welcome.
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Go Up