Searching for data in a table

Question

How can I optimize this code to increase the performance of searching data?

public class TableRowInfo : IEquatable<GridRowInfo>
{
    #region Ctor

    public TableRowInfo(int rowIndex, object rowData, NodeEntry nodeEntry, bool isNewRow = false)
    {
        this.RowData = rowData;
        this.NodeEntry = nodeEntry;
        this.RowIndex = rowIndex;
        this.IsNewRow = isNewRow;
    }


    public TableRowInfo(int rowIndex, bool isNewRow)
    {
        this.RowData = null;
        this.NodeEntry = null;
        this.RowIndex = rowIndex;
        this.IsNewRow = isNewRow;
    }

    #endregion

    #region Properties


    public object RowData { get; private set; }


    public bool IsDataRow
    {
        get { return RowData != null; }
    }


    public bool IsNewRow
    {
        get;
        set;
    }


    public int RowIndex { get; internal set; }


    internal NodeEntry NodeEntry { get; private set; }

    #endregion

    public override int GetHashCode()
    {
        int rowDataHashCode = this.RowData == null ? 0 : this.RowData.GetHashCode();
        return rowDataHashCode ^ this.RowIndex;
    }

    #region IEquatable<TableRowInfo> Members

    public bool Equals(GridRowInfo other)
    {
        if (Object.ReferenceEquals(other, null)) return false;

        if (Object.ReferenceEquals(this, other)) return true;

        if (!this.IsDataRow == other.IsDataRow)
            return false;
        else if (this.IsDataRow)
            return this.RowData == other.RowData;
        else
            return this.RowIndex == other.RowIndex;
    }

    #endregion
}

public class TableSelectedRowsCollection : List<TableRowInfo>
{
    #region Ctor

    public TableSelectedRowsCollection()
    {
    }

    #endregion

    #region IList Members

    public bool Contains(TableRowInfo rowInfo)
    {
        if (rowInfo.IsNewRow)
            return Find(rowInfo.RowIndex) != null;
        else
            return Find(rowInfo.NodeEntry) != null;
    }

    public bool Contains(int rowIndex)
    {
        return Find(rowIndex) != null;
    }

    public bool Contains(object rowData)
    {
        return Find(rowData) != null;
    }

    public bool Contains(NodeEntry nodeEntry)
    {
        return Find(nodeEntry) != null;
    }

    #endregion

    #region Helper Methods

    internal TableRowInfo Find(NodeEntry nodeEntry)
    {
        if (nodeEntry != null && this.Count > 0)
        {
            return this.FirstOrDefault(rowInfo => rowInfo.NodeEntry == nodeEntry);
        }
        return null;
    }

    internal TableRowInfo Find(int rowIndex)
    {
        if (rowIndex > 0 && this.Count > 0)
        {
            return this.FirstOrDefault(rowInfo => rowInfo.RowIndex == rowIndex);
        }
        return null;
    }

    internal TableRowInfo Find(object rowData)
    {
        if (rowData != null && this.Count > 0)
        {
            return this.FirstOrDefault(rowInfo => rowInfo.RowData == rowData);
        }
        return null;
    }

    internal TableRowInfo Find(TableRowInfo rowInfo)
    {
        if (rowInfo != null && this.Count > 0)
        {
            return this.FirstOrDefault(item => item.NodeEntry == rowInfo.NodeEntry);
        }
        return null;
    }

    internal List<int> GetRowIndexes()
    {
        var rowIndexes = new List<int>();
        if (this.Count > 0)
        {
            this.ForEach(rowInfo => rowIndexes.Add(rowInfo.RowIndex));
        }
        return rowIndexes;
    }

    #endregion
}

Answer 1

For faster searching and since you're searching by different properties, one way would be a different dictionary for each property you want to search for. The indexing property is the key and the value can be the tablerowinfo object or if indexes may be duplicated a list of tablerowinfoinfo objects.

Dictionary<NodeEntry, TableRowInfo> nodeEntryIndex;
Dictionary<int, TableRowInfo> rowNumberIndex;
Dictionary<object, TableRowInfo> rowDataIndex;

Assuming you've implemented Add and Remove methods, simply add/remove the appropriate entries to the dictionaries, in those methods.

The Find method would look something like this:

internal TableRowInfo Find(NodeEntry nodeEntry)
{
    if (nodeEntryIndex.ContainsKey(nodeEntry))
    {
        return nodeEntryIndex[nodeEntry];
    }
    return null;
}

One suggestion. When you inherit from a List like this, you expose all the members you've inherited from the list, outside the class. If you're going to provide your own version for all of them that's fine. However if you're only going to implement a subset of them then you might want to consider not inheriting but having a List as a private property to store the collection. This gives you much more flexibility in choosing what gets exposed outside the class.

Another suggestion. Instead of using object as the rowData type, the DataRow Class would probably be better suited for that. This increase the robustness of your class.

Answer 2

I agree with tinstaafl's suggestions but since this is a code review I wanted to make a few additional comments about the code.

First, let's take a look at one of the Find methods.

internal TableRowInfo Find(NodeEntry nodeEntry)
{
    if (nodeEntry != null && this.Count > 0)
    {
        return this.FirstOrDefault(rowInfo => rowInfo.NodeEntry == nodeEntry);
    }
    return null;
}

The bounds checking really doesn't add any value. If the list is empty, FirstOrDefault will already return null with the same performance so checking if the Count > 0 is only making the code a little more complex for no benefit.

Second, it's worth considering if a null input value is really a valid value. You'll probably find in a lot of cases that passing null into the method is actually a bug. My preference is to throw an exception in this case and leave it up to the caller to check the input. Using invariants like this can make your code easier to implement and makes it clearer to the caller what the contract is with your class.

So the method would become:

internal TableRowInfo Find(NodeEntry nodeEntry)
{
    if(nodeEntry == null) throw new ArgumentNullException("nodeEntry");

    return this.FirstOrDefault(rowInfo => rowInfo.NodeEntry == nodeEntry);
}

Last, just a small thing about dictionary look-ups (as described in tinstaafl's answer). It's slightly more efficient to use TryGetValue instead of ContainsKey so that the code doesn't have to look-up the key twice.

internal TableRowInfo Find(NodeEntry nodeEntry)
{
    TableRowInfo tableRowInfo;
    if (nodeEntryIndex.TryGetValue(nodeEntry, out tableRowInfo))
    {
        return tableRowInfo;
    }
    return null;
}