Data structure for a huge dataset

Question

I need to make an efficient data structure for a class which stores a Collection of size varying from 50,000 to 100,000 of values.

class TypeData
{
    public string Name { get; set; }
    public Collection<double> Data{ get; set; }
}

Now, user wants to perform some operations on this data, the operation then replaces the actual values in collection with '0'. For example

Before operation:
3.4
5.6
66.71
101.44
3.567
345.09

After operation:
3.4
0.0
0.0
101.44
0.0
345.09

Now, user wants to revert that operation. Then I have to remove all the 0.0 and have to placed the original values on those indexes in collection.

Question 1: How to keep track of changed indexes? Do i need to keep an another list containing all the changed indexes? Question 2: How to improve the data structure of this class so that it can accommodate thousand of instances i.e

List<TypeData> dataList = new List<TypeData>(); // the size this list can grow to 5000

Answer 1

Question 1: How to keep track of changed indexes? Do i need to keep an another list containing all the changed indexes?

I wouldn't store a Collection<double> but a Collection<CustomType> which stores the value, the curent state and the history (if any).

For example:

public class TypeData
{
    public string Name { get; set; }
    public List<Data> Data { get; set; }
}

public class Data
{
    public enum State
    {
        Unassigned,
        Original,
        Modified
    }

    private double _Value = 0.0d;
    public double Value
    {
        get { return _Value; }
        set
        {
            if (CurrentState == State.Unassigned)
                CurrentState = State.Original;
            else
                CurrentState = State.Modified;
            _Value = value;
            _ValueHistory.Add(value);
            if (_ValueHistory.Count > MaxHistoryCount)
                ClearValueHistory();
        }
    }

    private List<double> _ValueHistory = new List<double> { 0.0d };
    private List<double> ValueHistory
    {
        get { return _ValueHistory; }
        set { _ValueHistory = value; }
    }

    private int _MaxHistoryCount = int.MaxValue;
    public int MaxHistoryCount
    {
        get { return _MaxHistoryCount; }
        set { _MaxHistoryCount = value; }
    }

    public void ClearValueHistory()
    {
        if (_ValueHistory.Count > 1)
            _ValueHistory.RemoveRange(0, _ValueHistory.Count - 1); // keep last
    }

    private State _CurrentState = State.Unassigned;
    public State CurrentState
    {
        get { return _CurrentState; }
        private set { _CurrentState = value; }
    }

    public void RevertOperation(int numRevertCount = 1)
    {
        int newRevisionIndex = _ValueHistory.Count - 1 - numRevertCount;
        if (newRevisionIndex < 0) newRevisionIndex = 0;
        double val = _ValueHistory[newRevisionIndex];
        _ValueHistory.RemoveRange(newRevisionIndex + 1, _ValueHistory.Count - 1 - newRevisionIndex);
        this._Value = val;
    }

    public override string ToString()
    {
        return Value.ToString();
    }
}

Here's is sample data and an examplary reverse-operation:

var listOfData = new List<TypeData>{ 
    new TypeData {
        Name = "TestData",
        Data = new List<Data> 
        {
            new Data { Value = 1.5 }, new Data { Value = 2.4 }, new Data { Value = 1.2 },  new Data(),
            new Data { Value = 0.7 }, new Data { Value = -4.7 }, new Data { Value = 0.0 }, new Data { Value = 4711}
        }
    }
};

foreach (var td in listOfData)
{
    foreach (var data in td.Data.Take(10))
    {
        data.Value = 4711.4711;
    }
}
foreach (var td in listOfData)
{
    foreach (var data in td.Data.Take(10))
    {
        data.RevertOperation();
    }
}

Question 2: How to improve the data structure of this class so that it can accommodate thousand of instances i.e

Why do you need to improve it? I would keep it as it is. I doubt that it needs too much memory. Otherwise you should decide whether you buy more memory or you should use a database instead.

Answer 2

If you have to undo operation only once, then solution with holding active/actual values of Tim Schmelter is the right one.

If you need multiple undo's, then you have to implement a history. Same way you could also provide redo possibility.

With some assumptions undo can be actually very easy task. If number of items in the list between undo is not changed, then you can save in the history (which is basically another list) index and value for all your changes. Undo operation will go through the history, take index and just restore the value.

If number of items will be changed, then easiest would be to save a complete state of data, by making a copy. This, however, is memory consuming operation, though still can be implemented if you consider to use database or file to save such states.

Other solution would be to implement operations, which you can save in the history. You still have to save state, but it would be only of that size, which operation is required (to example, in case of deleting item you don't need to store whole list, only index and value of deleted item). Undo in this case will looks like a reading from history last operation and performing it backward (or you can have inverted history from start, ready for undo, to example, in case of deleting item, you instead save insert operation). In case of list manipulation the basic list of possible operation could be: clear, insert at, delete at, change value at.