[KYA]

We've had language specific challenges for a while now, here's a Computer Science one.

Come up with a data structure that gets more memory efficient as more stuff is put into it.

i.e. if you put in 5 items and it's 80 bytes per item [on average], 10 items in the structure would have a lower average [say 60, it doesn't necessarily have to half the average].

Now, this is theoretical, but implementing it in a language *cough* C/C++ * cough* is highly encouraged.


Hint 1:

Spoiler

Look into how you can relate the information/data in the structure so that it can "cluster", resulting in elements sharing already allocated memory up until a certain point.

Hint 2:

Spoiler

Think of the nature of trees.

Hint 3:

Spoiler

It doesn't actually have to be a full blown structure. You can implement this with just pointers.

[NeoTifa]

B-Trees?

[macosxnerd101]

Here are my thoughts on this problem:

Spoiler

The design of Java is that Objects that are equal by the equals() method return the same values for hashCode(). So a HashMap<Integer, Object> to manage the Object pool, and a List<Object> for the structure would be sufficient.

import java.util.*;

class MemEfficient{

      private HashMap<Integer, Object> pool;
      private List<Object> contents;

      public MemEfficient(){
           pool = new HashMap<String, Object>();
           contents = new ArrayList<Object>();
      }      
      
      //returns true if the Object was in the pool
      public boolean insert(Object o){
           Object temp = pool.get(o.hashCode());
           if(temp == null)
                  map.put(o.hashCode(), o);

           contents.add(o);
           return (temp == null);
      }

      public boolean elementExists(Object o){ 
            return pool.contains(o.hashCode(); 
      }

      //used to allow user to get equal() objects
      //and prevent storing two objects that are equal()
      public Object getExisting(Object o){ 
           return pool.get(o.hashCode());
      }

      public Object getExisting(int hashcode){
           return pool.get(hashcode);
      }

}

That implementation hinders on lots of repeated elements though. One advantage is, if the user is using Objects storing other elements, they can lookup existing elements in the pool and use those, saving more memory.

My thoughts for solving general memory efficiency would be to look at a Huffman Tree model, in terms of the given digit directing the tree traversal path. Basically, break an Object down into bits, characters, etc., and store clusters of digits. Ie., 101011111 can be broken down into clusters of three: 101, 011 and 111. The root Node would be empty, and each Node will store a^x (a is the cluster size, x is the number of permutations of the cluster size) children Nodes, representing the permutations of the digits. The more elements there are, the more they will fall under those clusters. And the more clusters, the shallower the Tree will be. Thus, memory will be saved in terms of the number of Nodes, and the number of Collections within each Node.

[KYA]

Exactly.

Spoiler

Huffman codes are an excellent example.

Another would be the storage of something that can be represented in a single unsigned integer. You can break it into four bytes giving you a constant time lookup with a 4D array or log n with a tree.

i.e.

Store 0 0 0 0 and it costs X bytes
Adding 0 1 0 0 requires less since the first 0 was already allocated

void toBytes(uint8_t bytes[], uint32_t num){
     for(int i = 24, j = 0; i >= 0; i-= 8, j++) bytes[j] = (num >> i) & 0xFF;
     return;
}

int main(){
    uint8_t bytes[4];
    uint32_t orderNum = 1000;
    
    toBytes(bytes, orderNum);
    for(int i = 0; i < 4; i++) cout << (int)bytes[i] << endl;
    return 0;
}

[ishkabible]

i couldn't think of anything very creative, i just made a queue that handles redundant objects differently. it might be useful for storing large highly redundant objects however. maybe extremely large Big Nums with highly redundant values.

Spoiler

template<typename T>
class RedundancyQueue {
private:
	std::map<T, T*> record;
	std::deque<T*> stack;
public:
    ~RedundancyQueue() {
    	std::map<int, int* >::iterator iter;
		for(iter=record.begin();iter!=record.end();++iter) {
			delete &*iter;
		}
    }
	void push(int x) {
		if(!record.count(x)) {
			record[x] = new int(x);
		}
		stack.push_front(record[x]);
	}
	void pop() {
		stack.pop_back();
	}
	T& top() {
		return stack.back();
	}
};

edit: oops i forgot to add spoiler tags...

This post has been edited by ishkabible: 08 May 2011 - 11:38 AM

[diego_pmc]

I have a question, not an answer.

Spoiler

So the way you'd make large collections more memory efficient is by -- for example -- storing all the values in a tree; every common byte would only be stored once and branching only occurs when a difference occurs. (Like in KYA's example.) But is it possible to access arbitrary elements in such a tree without having to iterate through the tree and search for the desired leaf?

This post has been edited by diego_pmc: 08 May 2011 - 12:17 PM

[macosxnerd101]

Hope this helps some.

Spoiler

You can use a hashtable or map to store the individual Nodes and relate them. Thus if you have the key, it is O(k) or O(log(n)) lookup time depending on the specific structure.

[AdamSpeight2008]

KYA you don't mention anything about;-
if you have to preserve to ordering?
if the same value is allow multiple times?