15,881,092 members
Home / Discussions / Algorithms

# Algorithms

 Re: Storing more values in single BYTE. El Corazon6-Nov-07 3:29 El Corazon 6-Nov-07 3:29
 Re: Storing more values in single BYTE. CPallini6-Nov-07 3:33 CPallini 6-Nov-07 3:33
 Re: Storing more values in single BYTE. El Corazon6-Nov-07 4:01 El Corazon 6-Nov-07 4:01
 Re: Storing more values in single BYTE. Dan Neely6-Nov-07 2:14 Dan Neely 6-Nov-07 2:14
 Re: Storing more values in single BYTE. Sameerkumar Namdeo6-Nov-07 19:33 Sameerkumar Namdeo 6-Nov-07 19:33
 Re: Storing more values in single BYTE. Dan Neely7-Nov-07 2:19 Dan Neely 7-Nov-07 2:19
 Re: Storing more values in single BYTE. Sameerkumar Namdeo7-Nov-07 17:04 Sameerkumar Namdeo 7-Nov-07 17:04
 Re: Storing more values in single BYTE. sgorozco28-Nov-07 19:52 sgorozco 28-Nov-07 19:52
 Hello, 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! Gerardo
 Relative Speed of Trigonometry functions MikeMarq4-Nov-07 6:46 MikeMarq 4-Nov-07 6:46
 Re: Relative Speed of Trigonometry functions Luc Pattyn4-Nov-07 6:59 Luc Pattyn 4-Nov-07 6:59
 Re: Relative Speed of Trigonometry functions Paul Conrad4-Nov-07 7:31 Paul Conrad 4-Nov-07 7:31
 Re: Relative Speed of Trigonometry functions cmk4-Nov-07 10:22 cmk 4-Nov-07 10:22
 Re: Relative Speed of Trigonometry functions Paul Conrad4-Nov-07 10:53 Paul Conrad 4-Nov-07 10:53
 Re: Relative Speed of Trigonometry functions Dan Neely5-Nov-07 2:20 Dan Neely 5-Nov-07 2:20
 Re: Relative Speed of Trigonometry functions Paul Conrad5-Nov-07 12:05 Paul Conrad 5-Nov-07 12:05
 Re: Relative Speed of Trigonometry functions Dan Neely5-Nov-07 12:46 Dan Neely 5-Nov-07 12:46
 Re: Relative Speed of Trigonometry functions Paul Conrad5-Nov-07 14:05 Paul Conrad 5-Nov-07 14:05
 Re: Relative Speed of Trigonometry functions Robodroid17-Jan-08 10:15 Robodroid 17-Jan-08 10:15
 Re: Relative Speed of Trigonometry functions MikeMarq4-Nov-07 19:54 MikeMarq 4-Nov-07 19:54
 Re: Relative Speed of Trigonometry functions cp98764-Nov-07 22:27 cp9876 4-Nov-07 22:27
 Re: Relative Speed of Trigonometry functions Luc Pattyn5-Nov-07 2:36 Luc Pattyn 5-Nov-07 2:36
 Re: Relative Speed of Trigonometry functions Alan Balkany29-Nov-07 5:02 Alan Balkany 29-Nov-07 5:02
 Re: Relative Speed of Trigonometry functions serge_bal19-Dec-07 5:38 serge_bal 19-Dec-07 5:38
 Alogorithim to compare two pictures w2094-Nov-07 3:33 w209 4-Nov-07 3:33
 Re: Alogorithim to compare two pictures Luc Pattyn4-Nov-07 4:10 Luc Pattyn 4-Nov-07 4:10
 Last Visit: 31-Dec-99 18:00     Last Update: 18-Apr-24 12:49 Refresh ᐊ Prev1...222223224225226227228229230231 Next ᐅ