В очередной раз припёрло.
Надо переизобрести как можно более шустрый велосипед с вот таким вот интерфейсом:
interface IStorageIndex<T> // для всех T есть EqualityComparer, для большей части - ещё и Comparer<T>
{
// index изменяться не будет, value - не уникальное. Распределение заранее неизвестно.void AddIndex(T value, int index);
void RemoveIndex(T value, int index);
int[] IndexesOf(T value); // обязательно O(1).
}
Подозреваю, что много не выжать — индекс на ~5 млн элементов уже сейчас строится за секунду-две. На практике коллекции будут в пару-тройку тысяч элементов, но зато их будет несколько десятков и изменяться они будут достаточно часто.
Все реализации "в лоб" идут нос к носу — надо копать в сторону алгоритмической сложности. Как пример:
internal class StorageIndex<T>: IStorageIndex<T>
{
private Dictionary<T, SortedSet<int>> valueIndexes;
private SortedSet<int> nullValueIndexes;
public StorageIndex(IEqualityComparer<T> valueComparer)
{
this.valueIndexes = new Dictionary<T, SortedSet<int>>(valueComparer);
this.nullValueIndexes = new SortedSet<int>();
}
private bool TryGetIndexes(T value, out SortedSet<int> indexes)
{
bool result;
if (value == null)
{
indexes = nullValueIndexes;
result = true;
}
else
{
result = valueIndexes.TryGetValue(value, out indexes);
}
return result;
}
public void AddIndex(T value, int index)
{
//EnumerableCode.ValidIndex(index, "index");
SortedSet<int> indexes;
if (TryGetIndexes(value, out indexes))
{
if (!indexes.Add(index))
{
//Code.Bug(@"Indexing already indexed value.");
}
}
else
{
indexes = new SortedSet<int>() { index };
valueIndexes.Add(value, indexes);
}
}
public void RemoveIndex(T value, int index)
{
//EnumerableCode.ValidIndex(index, "index");
SortedSet<int> indexes;
bool removed = false;
if (TryGetIndexes(value, out indexes))
{
removed = indexes.Remove(index);
}
if (!removed)
{
//Code.Bug(@"Removing index on non-indexed value.");
}
if (value != null && indexes.Count == 0)
{
valueIndexes.Remove(value);
}
}
public int[] IndexesOf(T value)
{
SortedSet<int> indexes;
return TryGetIndexes(value, out indexes) ?
indexes.ToArray() :
new int[0];
}
}
Здравствуйте, Aen Sidhe, Вы писали:
AS>http://i4o.codeplex.com/ ?
Оно через рефлексию работает, причём крайне своеобразно. Для начала, будет падать на null-ах и пропускать дубликаты.
Переизобретённый HashSet тоже улыбнул:
public void Add(T newItem)
{
foreach (PropertyInfo info in typeof(T).GetProperties())
{
if (this._indexes.ContainsKey(info.Name))
{
Dictionary<int, List<T>> dictionary = this._indexes[info.Name];
int hashCode = info.GetValue(newItem, null).GetHashCode();
if (dictionary.ContainsKey(hashCode))
{
dictionary[hashCode].Add(newItem); // ??:)
}
else
{
List<T> list = new List<T>(1);
list.Add(newItem);
dictionary.Add(hashCode, list);
}
}
}
base.Add(newItem);
}
А сама идея — везде одна и та же: Dictionary<int, ICollection<T>>.
Надо будет всё-таки поиграться с RBTree.
Здравствуйте, Sinix, Вы писали:
S>Надо будет всё-таки поиграться с RBTree.
В тему не вчитывался, поэтому может не в тему скажу, просто напомню, что в SortedDictionary используется как раз RBTree...
Здравствуйте, Lloyd, Вы писали:
S>>Надо будет всё-таки поиграться с RBTree.
L>У него, по идее, харектиристики будут хуже, чем у словаря.
Ну да, я наивно надеюсь, что O(log(N)) каким-то чудом можно сделать быстрее, чем O(1)
А уверенность шла от того, что я пощупал DataTable как готовый пример индексов — он, зараза, работал быстрее. Оказалось, что по-дефолту DataTable создаёт ровно один индекс по всем столбцам сразу
Ок, остановимся на текущей реализации и не будем дёргаться попусту.
Здравствуйте, MozgC, Вы писали:
MC>В тему не вчитывался, поэтому может не в тему скажу, просто напомню, что в SortedDictionary используется как раз RBTree...
Проверял, примерно с тем-же результатом. Почему вопреки теории надеялся на RBTree — постом выше.
Не, ну должна же где-то быть SuperFastSuperSecretCollectionThatDoesWhatYouWant<T1,T2,T3,T4,T5,T6,T7...>
