Click here to Skip to main content
15,881,092 members
Home / Discussions / Algorithms
   

Algorithms

 
JokeRe: Storing more values in single BYTE. Pin
El Corazon6-Nov-07 3:29
El Corazon6-Nov-07 3:29 
GeneralRe: Storing more values in single BYTE. Pin
CPallini6-Nov-07 3:33
mveCPallini6-Nov-07 3:33 
JokeRe: Storing more values in single BYTE. Pin
El Corazon6-Nov-07 4:01
El Corazon6-Nov-07 4:01 
AnswerRe: Storing more values in single BYTE. Pin
Dan Neely6-Nov-07 2:14
Dan Neely6-Nov-07 2:14 
AnswerRe: Storing more values in single BYTE. Pin
Sameerkumar Namdeo6-Nov-07 19:33
Sameerkumar Namdeo6-Nov-07 19:33 
GeneralRe: Storing more values in single BYTE. Pin
Dan Neely7-Nov-07 2:19
Dan Neely7-Nov-07 2:19 
GeneralRe: Storing more values in single BYTE. Pin
Sameerkumar Namdeo7-Nov-07 17:04
Sameerkumar Namdeo7-Nov-07 17:04 
AnswerRe: Storing more values in single BYTE. Pin
sgorozco28-Nov-07 19:52
sgorozco28-Nov-07 19:52 
Hello, Smile | :)

Your programming problem is interesting. As someone already pointed out, what you actually need is 9 bit precision to store values ranging from 0 to 299.

A simple approach is packing these 9th bits into another byte, this would require an additional 1000 by 125 array (125 since we will pack these bits in a single byte, 1000 / 8 = 125)

Here is a simple class I wrote that does precisely that. Since your primary concern is reducing memory consumption, instead of using jagged arrays as you suggest ([][]), I'm proposing multidimensional arrays [,]. Multidimensional arrays consume less memory than jagged arrays.


using System;
using System.Diagnostics;

namespace stuff {

   
   public class MappedArray {
      private byte[,] _aByte = new byte[1000, 1000]; // we will store the 8 least significant bits here
      private byte[,] _msBit = new byte[1000, 125];  // we will store the 9th significant bits here, packed inside a byte  (1000 / 8 = 125)
      private int []  _U = new int[300];  // we will store the unique values ranging from 0 to 999999 here
      private int _uniqueCounter = 0;  // variable used to control the unique values that can be contained inside the array

      public MappedArray() {
			
      }

      protected int GetMappedIdx(int aValue) {
         for( int i = 0; i < _uniqueCounter; i++ )
            if( _U[i] == aValue )
               return i;

         if( _uniqueCounter >= 300 )
            throw new Exception("more than 300 unique elements");
         
         int idx = _uniqueCounter++;
         _U[idx] = aValue;
         return idx;
      }

      public void Set(int x, int y, int aValue) {
         Debug.Assert(x < 1000 && y < 1000);
         int mappedID = GetMappedIdx(aValue);

         // store the least 8 significant bits of the mappedID
         _aByte[x,y] = (byte)(mappedID & 0xff);

         // Now we will store the most significant bit (bit 9) in a packed array
         
         // first obtain the secondary idx of the byte that will store the bit
         int packedIdx = y / 8;
         byte msBits = _msBit[x, packedIdx];
         // now obtain the bit position of the msb inside this byte
         int bitpos = y % 8;
         if( mappedID >= 256 ) {
            // the most significant bit shoud be 1
            msBits|=  (byte)( 1 << bitpos);
         } else {
            // the most significant bit should be 0
            msBits&=  (byte)~( 1 << bitpos);
         }

         // store the updated packed bits
         _msBit[x, packedIdx] = msBits;

      }

      public int Get(int x, int y) {
         Debug.Assert(x < 1000 && y < 1000);
         
         // obtain the least 8 significant bits of the mappedID
         
         byte lsBits = _aByte[x,y];

         // Now we will retrieve the most significant bit (bit 9) from the packed array
         
         // first obtain the secondary idx of the byte that stores the bit
         int packedIdx = y / 8;
         byte msBits = _msBit[x, packedIdx];
         // now obtain the bit position of the msb inside this byte
         int bitpos = y % 8;

         // now extract the bit
         byte bitValue = (byte)(msBits & (1 << bitpos));

         // now reassemble the full 9-bit index value
         int idx = lsBits;
         if( bitValue != 0 )
            idx |= 0x100;
         return _U[idx];  // return the mapped value
      }
   }
}


This is the sample code I used to test the class was working correctly. I simply fill the array (Set method) with 300 unique values ranging from 0 to 999999 and test that the retrieved values (Get method) are the same.

private void button1_Click(object sender, System.EventArgs e) {
         MappedArray ma = new MappedArray();
         int[] rndArr = new int[300];
         Random rnd = new Random();

         for( int i = 0; i < 300; i++ )
            rndArr[i] = rnd.Next(999999);

         for( int i = 0; i < 1000; i++ ) 
            for( int j = 0; j < 1000; j++ ) {
               int val = rndArr[rnd.Next(300)];
               ma.Set(i, j, val);
               if( ma.Get(i,j) != val )
                  throw new Exception("oops, something's wrong with the mapping logic");
            }

      }


Hope this helps! Big Grin | :-D

Gerardo
QuestionRelative Speed of Trigonometry functions Pin
MikeMarq4-Nov-07 6:46
MikeMarq4-Nov-07 6:46 
AnswerRe: Relative Speed of Trigonometry functions Pin
Luc Pattyn4-Nov-07 6:59
sitebuilderLuc Pattyn4-Nov-07 6:59 
AnswerRe: Relative Speed of Trigonometry functions Pin
Paul Conrad4-Nov-07 7:31
professionalPaul Conrad4-Nov-07 7:31 
AnswerRe: Relative Speed of Trigonometry functions Pin
cmk4-Nov-07 10:22
cmk4-Nov-07 10:22 
GeneralRe: Relative Speed of Trigonometry functions Pin
Paul Conrad4-Nov-07 10:53
professionalPaul Conrad4-Nov-07 10:53 
GeneralRe: Relative Speed of Trigonometry functions Pin
Dan Neely5-Nov-07 2:20
Dan Neely5-Nov-07 2:20 
GeneralRe: Relative Speed of Trigonometry functions Pin
Paul Conrad5-Nov-07 12:05
professionalPaul Conrad5-Nov-07 12:05 
GeneralRe: Relative Speed of Trigonometry functions Pin
Dan Neely5-Nov-07 12:46
Dan Neely5-Nov-07 12:46 
GeneralRe: Relative Speed of Trigonometry functions Pin
Paul Conrad5-Nov-07 14:05
professionalPaul Conrad5-Nov-07 14:05 
GeneralRe: Relative Speed of Trigonometry functions Pin
Robodroid17-Jan-08 10:15
Robodroid17-Jan-08 10:15 
GeneralRe: Relative Speed of Trigonometry functions Pin
MikeMarq4-Nov-07 19:54
MikeMarq4-Nov-07 19:54 
GeneralRe: Relative Speed of Trigonometry functions Pin
cp98764-Nov-07 22:27
cp98764-Nov-07 22:27 
AnswerRe: Relative Speed of Trigonometry functions Pin
Luc Pattyn5-Nov-07 2:36
sitebuilderLuc Pattyn5-Nov-07 2:36 
AnswerRe: Relative Speed of Trigonometry functions Pin
Alan Balkany29-Nov-07 5:02
Alan Balkany29-Nov-07 5:02 
AnswerRe: Relative Speed of Trigonometry functions Pin
serge_bal19-Dec-07 5:38
serge_bal19-Dec-07 5:38 
QuestionAlogorithim to compare two pictures Pin
w2094-Nov-07 3:33
w2094-Nov-07 3:33 
AnswerRe: Alogorithim to compare two pictures Pin
Luc Pattyn4-Nov-07 4:10
sitebuilderLuc Pattyn4-Nov-07 4:10 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.