CODEWITHSUNDEEP
c#.nettime-complexityspace-complexity
James Wierzba
James Wierzba

Reputation: 17548

Most memory efficient way to remember visited cells in 2d matrix?

Given a 2d array int[n,n], and given we are implementing some algorithm that requires remembering an arbitrary number of cells (potentially all n of them, however on average much lower, see below):

What is the most efficient way we can store the fact we have visited a cell, in the most efficient way possible (least amount of memory) while maintaining constant time lookup?

Let me add another detail:

Worst case is O(n) for quantity of cells we need to remember, however average case is much lower. Lets say on average we only need to remember less than O(logn) cells.

I'm interested in optimizing this for the average case.

Upvotes: 0

Views: 237

Answers (1)

adjan
adjan

Reputation: 13674

You could use the MSB of int to use it as a flag for whether the cell was visited or not. If you don't need integers below -230 = -1,073,741,824 or above 230-1 = 1,073,741,823 this would be the way to go:

public struct TaggableInteger 
{
    private uint _value;

    public bool IsTagged
    {
        get
        {
            return ((this._value >> 31) & 0x1) == 0x1;
        }

        set
        {
            this._value |= value ? (uint)0x1 << 31 : 0;
            this._value &= value ? this._value : (uint)0x7FFFFFFF;
        }
    }

    public int Value 
    { 
        get
        {
            return (int)(this._value << 1) >> 1;
        }

        set 
        {
            this._value = ((uint)value << 1) >> 1;
        }
    }

    public TaggableInteger(int valueInt) 
    {
        uint value = (uint) valueInt;
        this._value = (value << 1) >> 1;
    }
}

Test Program:

public static void Main()
{
    var i = new TaggableInteger(1047483640);
    Console.WriteLine("{0} {1}", i.IsTagged, i.Value);
    i.IsTagged = true;
    Console.WriteLine("{0} {1}", i.IsTagged, i.Value);
    i.IsTagged = false;
    Console.WriteLine("{0} {1}", i.IsTagged, i.Value);
}

Prints

False 1047483640
True 1047483640
False 1047483640

Upvotes: 1

Related Questions