Qu'est-ce que le dictionnaire .NET prend en charge une opération de « trouver la clé la plus proche »?
https://stackoverflow.com/questions/1690929
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je convertir une partie du code C ++ C # et il appelle std :: map :: lower_bound (k) pour trouver une entrée dans la carte dont la clé est égale ou supérieure à k. Cependant, je ne vois aucune façon de faire la même chose avec SortedDictionary de .NET. Je pense que je pourrais mettre en œuvre une solution de contournement à l'aide SortedList, mais malheureusement SortedList est trop lent (O (n) pour l'insertion et suppression de clés). Que puis-je faire?
Note: J'ai trouvé une solution à l'aide qui profite de mon scénario particulier ... Plus précisément, mes clés sont une population dense de nombres entiers à partir de un peu plus de 0, donc j'utilisé une liste
La solution 4
J'ai créé trois structures de données liées à des arbres B + qui offrent cette fonctionnalité pour tout type de données: BList<T>, BDictionary<K,V> et BMultiMap<K,V> . Chacune de ces structures de données fournissent des méthodes de FindLowerBound() et FindUpperBound() qui fonctionnent comme lower_bound et upper_bound de C ++.
Autres conseils
Il a fallu deux mois de travail, mais enfin je peux offrir au moins une solution partielle à ce problème ... Je l'appelle le Compact Patricia Trie, un dictionnaire Sorted qui offre une opération de « trouver la clé suivante plus grande ».
http://www.codeproject.com/KB/recipes/cptrie.aspx
Il est seulement une solution partielle puisque seuls certains types de clés sont pris en charge, à savoir byte[], string, et tous les types entiers primitifs (Int8..UInt64). En outre, le tri des cordes est sensible à la casse.
Le problème est qu'une table dictionnaire / hachage est conçu pour arriver à un emplacement de mémoire unique basé sur une valeur d'entrée, de sorte que vous aurez besoin d'une structure de données qui est conçue pour accueillir une gamme liée à chaque valeur que vous stockez et en même temps mettre à jour correctement chaque intervalle
Je pense que sauter les listes peuvent vous aider (ou arbres binaires équilibrés). Bien qu'ils ne peuvent pas effectuer des recherches dans O (n), ils peuvent faire encore et logarithmiquement plus vite que les arbres.
Je sais que ce n'est pas une bonne réponse car je ne peux pas dire que la BCL .NET contient déjà une telle classe, vous aurez malheureusement à mettre en œuvre un vous-même, ou de trouver un ensemble 3ème partie qui soutient pour vous. Il semble y avoir un bel exemple sur Le CodeProject , cependant.
Vous pouvez essayer le code ci-dessous je l'ai écrit. à l'aide d'une recherche binaire, en supposant donc la liste / tableau est pré-triée.
public static class ListExtensions
{
public static int GetAtMostIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer)
{
return GetAtMostIndex(list, value, comparer, 0, list.Count);
}
public static int GetAtLeastIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer)
{
return GetAtLeastIndex(list, value, comparer, 0, list.Count);
}
public static int GetAtMostIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer, int index, int count)
{
if (count == 0)
{
return -1;
}
int startIndex = index;
int endIndex = index + count - 1;
int middleIndex = 0;
int compareResult = -1;
while (startIndex < endIndex)
{
middleIndex = (startIndex + endIndex) >> 1; // / 2
compareResult = comparer.Invoke(list[middleIndex], value);
if (compareResult > 0)
{
endIndex = middleIndex - 1;
}
else if (compareResult < 0)
{
startIndex = middleIndex + 1;
}
else
{
return middleIndex;
}
}
if (startIndex == endIndex)
{
compareResult = comparer.Invoke(list[startIndex], value);
if (compareResult <= 0)
{
return startIndex;
}
else
{
int returnIndex = startIndex - 1;
if (returnIndex < index)
{
return -1;
}
else
{
return returnIndex;
}
}
}
else
{
//todo: test
return startIndex - 1;
}
}
public static int GetAtLeastIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer, int index, int count)
{
if (count == 0)
{
return -1;
}
int startIndex = index;
int endIndex = index + count - 1;
int middleIndex = 0;
int compareResult = -1;
while (startIndex < endIndex)
{
middleIndex = (startIndex + endIndex) >> 1; // / 2
compareResult = comparer.Invoke(list[middleIndex], value);
if (compareResult > 0)
{
endIndex = middleIndex - 1;
}
else if (compareResult < 0)
{
startIndex = middleIndex + 1;
}
else
{
return middleIndex;
}
}
if (startIndex == endIndex)
{
compareResult = comparer.Invoke(list[startIndex], value);
if (compareResult >= 0)
{
return startIndex;
}
else
{
int returnIndex = startIndex + 1;
if (returnIndex >= index + count)
{
return -1;
}
else
{
return returnIndex;
}
}
}
else
{
return endIndex + 1;
}
}
}
trouver le plus proche de K:
dict.Keys.Where(i => i >= K).OrderBy(i => i).First();
ou bien plus rapide:
public int? GetNearestKey(dict, K)
{
int? lowerK = null;
foreach (int key in dict.Keys)
{
if (key == K)
{
lowerK = K;
break;
}
else if (key >= K && (!lowerK.HasValue || key < lowerK))
{
lowerK = key;
}
}
return lowerK;
}
Il n'y a pas une mise en œuvre de la collecte des arbres de recherche binaire dans le cadre de base, de sorte que vous devrez soit construire un ou de trouver une mise en œuvre. Comme vous l'avez dit, SortedList est le plus proche en termes de recherche, mais est plus lente (en raison de sa mise en œuvre du tableau sous-jacent) pour l'insertion / suppression.
Je pense qu'il ya une erreur dans la question sur SortedList complexité.
SortedList a O (log (n)) amorti complexité pour insérer nouvel élément. Si vous savez à l'avance la capacité dont il peut être fait en O (log (n)) dans le pire des cas.
Vous pouvez le faire pour SortedSet<T> avec suivant les méthodes d'extension:
public static class SortedSetExtensions
{
public static bool FindLowerOrEqualThan<T>(this SortedSet<T> set, T value, out T first)
{
if(set.Count == 0)
{
first = default(T);
return false;
}
var minimum = set.Min;
if(set.Comparer.Compare(minimum, value) > 0)
{
first = default(T);
return false;
}
first = set.GetViewBetween(minimum, value).Max;
return true;
}
public static bool FindGreaterOrEqualThan<T>(this SortedSet<T> set, T value, out T first)
{
if (set.Count == 0)
{
first = default(T);
return false;
}
var maximum = set.Max;
if (set.Comparer.Compare(maximum, value) < 0)
{
first = default(T);
return false;
}
first = set.GetViewBetween(value, maximum).Min;
return true;
}
}
