CODEWITHSUNDEEP
.netlistsortingsearchindexing
Matan L
Matan L

Reputation: 1027

Best Implementation of "Sql Table index" on a .net list

In SQL you can apply an index on a table, by that the table is sorted behind the scenes by these columns, which makes inserting and updating more slow, yet selecting by that column is much faster,

Is there a way to implement, or what is the best way to implement such format on a .net List (of course the column is the object's property)

What i came in mind so far :

  1. I know that if i would sort the list by some property i could implement my own "binary search by" that property using the binary-search of .net list.

  2. I could also create a dictionary of the column i wish to index, and the values would be the items that match it, or some reference to them.

Yet these solutions only create a "1 column" indexing implementation, i know i can use a dictionary of dictionaries and than have a "2 columns" one, yet i assume that there must be something else over there to make a more generic solution for this issue.

Is there ?

Upvotes: 0

Views: 49

Answers (1)

Ondrej Svejdar
Ondrej Svejdar

Reputation: 22054

If your method that compares two objects of same type takes into account both properites or you implement hashcode based on two properties, you should be fine (the same stands for three or more properties). No need to create dictionary of dictionaries.

E.g.:

public class PersonKey {
  private class MyComparer : Comparer<PersonKey> {
    public override int Compare(PersonKey x, PersonKey y) {
      int result = x.Name.CompareTo(y.Name);
      if (result == 0) {
        return x.Age.CompareTo(y.Age);
      }
      return result;        
    }
  }
  public static readonly Comparer<PersonKey> Comparer = new MyComparer();

  public string Name { get; set; }
  public int Age { get; set; }

  public override int GetHashCode() {
    return Name.GetHashCode() ^ Age;
  }

  public override bool Equals(object obj) {
    var person = (PersonKey)obj;
    return Age == person.Age && string.Compare(Name, person.Name, StringComparison.Ordinal) == 0;
  }
}

public class Person : PersonKey {
  public string LastName { get; set; }
}

Now how to use them:

var unsortedPersons = new List<Person> {
  new Person { Age = 26, Name = "Dan", LastName ="Brown" },
  new Person { Age = 18, Name = "Amanda", LastName = "Lear" },
  new Person { Age = 19, Name = "Amanda", LastName = "Brown" },
  new Person { Age = 15, Name = "Cicero", LastName = "Pubius" }
};

var hashset = unsortedPersons.ToDictionary<Person, PersonKey>(p => p);
// O(1) you can't have two items with same key there though
var dan = hashset[new PersonKey { Age = 26, Name = "Dan" }];

// array is now usable for binary search
var sortedPersons = unsortedPersons.OrderBy(p => p, PersonKey.Comparer).ToArray();
// O(log(N))
int index = Array.BinarySearch<Person>(sortedPersons, new Person { Name = "Amanda", Age = 18 }, PersonKey.Comparer);
var amanda = sortedPersons[index];

Upvotes: 1

Related Questions