Storing more values in single BYTE.

Sameerkumar Namdeo

One BYTE variable can store 256 distinct values. One short variable can store 65535 distinct values. Can one BYTE or short datatype variable store a value between 0 and 999999 ? Any intermediate variables , arrays can be utilised which will help in packing single BYTE or short variable with values from 0 to 999999. Thanks & Regards.

CPallini

ccpptrain wrote:

Can one BYTE or short datatype variable store a value between 0 and 999999 ?

Oh yes (just matter of mapping), but NOT ANY VALUE between 0 and 999999. :-D

If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.

Dan Neely

A byte can store 256 of the million values, a short can store 65536 of the million directly, but if you need to be able to store the entire range you're going to need to use a minimum of 20 bits, and unless your storage requirements are very tight relative to your hardware performanace bit packing isn't going to be worth the CPU overhead vs storing in a native 32 bit value. If you're archiving data or transmitting it in packets instead of streaming it in realtime you can use data compression, and potentially be able to use <16bits per value.

-- If you view money as inherently evil, I view it as my duty to assist in making you more virtuous.

El Corazon

CPallini wrote:

but NOT ANY VALUE between 0 and 999999.

I believe the proper term would be ALL values between 0 and 999999. Using a replacement map, I can map byte==0 to any number of bits, but I can store at most 256 values in my map.

_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)

CPallini

El Corazon wrote:

I believe the proper term would be ALL values between 0 and 999999

I believe the proper term is EVERY value between 0 and 999999. :-D

If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.

El Corazon

damn... got me... okay... I stand... err... sit corrected. ;P This reminds me of an old joke about mapping my college prof told.... what is the size limit of values you can store in one bit? no limit on size, but you can only store two of them. :-D

_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)

Sameerkumar Namdeo

Thanks all for correcting my question and giving suggestion. I am having 2D array of size say 1000*1000 In this 2D array each element has any value between 0 to 999999 So decided to take int Aint[1000][1000] as array. There are only 300 unique elements in this array and all other elements are repeated, i.e this array has repeated values with only 300 unique values. Also this array takes 1000*1000*4 = 4000000 bytes. So I am trying to construct an array int u[300] which will contain the unique values from Aint[1000][1000]. And instead of making int Aint[1000][1000] I decided to make BYTE Abyte[1000][1000] as my 2D array. Now this Abyte 2D array's elements should contain any values from 0 to 299. Previously: int value = Aint[750][750] = 999999; Now I will fetch value in this manner: Abyte[750][750] = 290; u[290] = 999999; int value = u[ Abyte[750][750] ] = 999999; But problem is Abyte's element can have values between 0 and 255. I need to store 290 in single BYTE. This approach has reduced memory requirement from 4000000 Bytes ( sizeof(Aint) ) to 1001200 bytes ( sizeof (Abyte) + sizeof(u) ) With this approach page faults can be reduced. Thanks & Regards.

Dan Neely

You cannot store more than 256 unique values in individual cells of a Byte array. You could reduce your memory footprint in two ways. The first would be to compress the array in memory. The cost of that would be the loss of easy random access. Instead of O(C) performance to access an arbitrary value you'd have O(N) performance, like a linked list. IIRC with most modern compression algos modifying a value will require recompressing the array from the insert point forward, making an insert even more expensive. The second would be to use bit packing, to simulate a 9bit int. This would remain O(C) performance, but the constant value would be much higher. You'd probably need to implement both these approaches and try multiple compression algos for the first (compressed size vs speed to partially decompress to get an arbitrary value) and do performance testing to see if these are actually faster than using an extra 1 meg of memory (using a 16bit int). Unless you're working on an embedded system with very tight memory constraints however I'm doubtful that either will actually be faster if you're doing any nontrivial examination/processing of the data.

-- If you view money as inherently evil, I view it as my duty to assist in making you more virtuous.

Sameerkumar Namdeo

Thanks for the pointers...

sgorozco

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 updat