1

I am writing a method that does some manipulation on a List. During each iteration, the algorithm will either delete, add or move an existing item (so the list is changing, one item at a time). Move operation will be performed using an extension method that is implemented with the following logic:

T item = base[oldIndex];
base.RemoveItem(oldIndex);
base.InsertItem(newIndex, item);

Also, during each iteration, one item in the list will be queried for its current index. List.IndexOf(item) is an expensive operation (O(n)), and I wonder if there is a way to improve the performance of this operation. I thought about keeping a dictionary of the indices, but then on every insertion and removal of an item I will need to update the indices of O(n) items the come after it, so that does not help.

Note: I am ware that List.InsertItem and List.RemoveItem take O(n) anyway, but I am specifically asking about how to improve the performance of the IndexOf operation in such a scenario.

Thanks

Kobi Hari
  • 1,259
  • 1
  • 10
  • 25
  • Will the same item be present in the list twice? – Rich O'Kelly Sep 30 '14 at 11:59
  • Keeping track of the id's is impossible, unless you update them every time you modify the list. This must be implemented by iterating over said list and updating every item, which 'indexOf' probably already does. Why not just remove from the list by value instead of index? That is basicly doing the same as finding the index and then removing said index, just in 1 step. Also: http://stackoverflow.com/a/5481789/321135 has this answered already :-) – DoXicK Sep 30 '14 at 12:00
  • 1
    The answer would be to use the right data structure, Lists are good for general purpose. Dictionaries are good for look ups poor for insertions/deletes. Linked Lists are good for insertions/deletes but poor for look ups. A Sorted list will have better look up times depending on your key (because it can use a binary search instead of a linear one) but insertion time will be affected. – James Sep 30 '14 at 12:13
  • @rich.okelly Nope, each item is unique – Kobi Hari Sep 30 '14 at 12:17
  • @DoXicK I do not follow. I never said I remove an item by index. I said that I modify the list on every iteration (having nothing to do with indices) and then I want to query the index of a specific item. The page you linked to answers a completely different question :-) – Kobi Hari Sep 30 '14 at 12:20
  • @JamesBarrass The data structure we use is list because indices is the main issue and the most basic structure that defines random access using an index is IList, which List implements. The list is not sorted, so there is no need for a sorted list, and a linked list is terrible here because most of what we do is access by index. The method I am implementing is only a specific manipulation of the data structure which provides a lot of other uses. I am just trying to implement this specific manipulation in the best performance I can achieve. – Kobi Hari Sep 30 '14 at 12:23
  • @KobiHari what is the specific manipulation you are trying to achieve? From what i understoond it it was: get the index of an item, remove the item, reinsert the item somewhere else, correct? – DoXicK Oct 01 '14 at 12:18

0 Answers0