Je convertis du code C ++ en c # et cela appelle std :: map :: moindre_bound (k) pour trouver une entrée sur la carte dont la clé est égale ou supérieure à k. Cependant, je ne vois aucun moyen de faire la même chose avec le type de type .NET. Je soupçonne que je pourrais implémenter une solution de contournement à l'aide de la triède, mais malheureusement triéList est trop lent (O (N) pour l'insertion et la suppression de touches). Que puis-je faire?
Remarque: j'ai trouvé une solution de contournement en utilisant qui profite de mon scénario particulier ... Plus précisément, mes clés sont une population dense d'entiers commençant à un peu plus de 0, alors j'ai utilisé une liste
8 Réponses :
trouver le plus proche de k: ou beaucoup plus rapide:
... maintenant, il est en place de O (n) à O (n log n).
J'ai besoin de le faire dans O (log n). Théoriquement, le triodictionnaire est capable de le faire, mais je ne vois pas d'une API pour cela.
Le problème est qu'un dictionnaire / hachage est conçu pour arriver à un emplacement de mémoire unique basé sur une valeur d'entrée. Vous aurez donc besoin d'une structure de données conçue pour accueillir une plage liée à chaque valeur que vous stockez et. à la fois mettre à jour chaque intervalle correctement
Je pense Skip Lists (ou arbres bassables équilibrés) peut vous aider. Bien qu'ils ne puissent pas effectuer des recherches dans O (n), ils peuvent faire logarithmiquement et encore plus rapides que les arbres.
Je sais que ce n'est pas une réponse appropriée car je ne peux pas dire que le BCL .Net contient déjà une telle classe, vous devez malheureusement vous mettre en œuvre un vous-même ou trouver une assemblée tierce qui le supporte pour vous. Il semble y avoir un bel exemple sur Le codeProject ici , cependant. < / p>
Soyeddicary semble être mis en œuvre avec un arbre noir noir; Dommage que toutes ses capacités ne sont pas rendues publiques.
Il n'y a pas de mise en œuvre de la collecte d'arborescences de recherche binaire dans le cadre de base, vous devez donc construire une ou trouver une implémentation. Comme vous l'avez noté, la sélection est la plus proche en termes de recherche, mais est plus lente (en raison de sa mise en œuvre de la matrice sous-jacente) pour l'insertion / la suppression.
Soyeddicary est un arbre de recherche binaire. Son API publique laisse simplement la fonctionnalité de recherche.
Je pense qu'il y a une erreur dans la question sur LiedList complexité.
tritedlist a o (log (n)) complexité amortise pour Insertion nouvel article. Si vous connaissez à l'avance la capacité possible dans O (log (n)) dans le pire des cas.
Microsoft bêtement n'indique pas la complexité Big-O de la documentation ( msdn.microsoft.com/en-us/library/... ) Mais il semble impliquer que le tri des clés stocke les clés et les valeurs dans les tableaux. Les tableaux triés ont une complexité O (n) insérez si les clés étant insérées sont aléatoires.
Il fait, dans MSDN.MicRosoft.com/fr- US / Bibliothèque / ... Il dit: "Cette méthode est une opération O (n) pour les données non formées, où n est compté. C'est une opération O (log n) si le nouvel élément est ajouté à la fin de La liste. Si l'insertion provoque un redimensionnement, l'opération est O (n). "
Les données non traitées sont normales. Si vos données sont déjà triées, vous n'avez pas besoin de tri définie dans la première place (liste BinarySearch méthode.) Donc, votre affirmation selon laquelle "tri (journal (n)) complexité amortis "est tout simplement faux.
Vous pouvez essayer le code que j'ai écrit ci-dessous. Il utilise une recherche binaire, supposant ainsi que 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;
}
}
}
Merci d'avoir contribué à cet algorithme de recherche binaire, mais cela n'aurait pas résolu mon problème, puisqu'il nécessite une matrice triée. Dans mon scénario (désolé de ne pas être clair dans la question), les inserts de clé sont entrelacés avec des requêtes clés. Maintenir l'ordre de tri d'un tableau sur chaque insert (afin que les recherches binaires sont possibles) nécessitent une heure (n). Ainsi, un tableau trié par la clé n'aurait pas de bonnes performances. Maintenant, si le tableau pouvait être intégré à l'avance, puis être suivi d'une série de requêtes, le tri ne devrait être fait qu'une fois, ce qui serait efficace. Mais ce n'était pas une option pour moi.
J'ai développé plusieurs classes de collecte prenant en charge "Rechercher la clé Next plus haute" et "Trouver la prochaine clé inférieure".
Tout d'abord, j'ai fait un ensemble de Compact Patricia Trie collections. Ce sont des ensembles / dictionnaires conçus pour minimiser l'utilisation de la mémoire; Ils sont particulièrement efficaces pour les grandes collections d'URL et certains autres types de données. Ils ne résolvent que partiellement le problème, car seuls certains types de clés sont pris en charge, à savoir Après la publication de cette réponse, j'ai fabriqué des structures de données plus triées qui résolvent ce problème en général: octet [] , chaîne et tous les types d'entiers primitifs (int8..uint64). En outre, le tri des chaînes est sensible à la casse. Paquet Nuget: LOYC.UTILITÉS
Blist BDICTIONRY bmultimap sparsealiste
Je suis d'accord. Il existe d'autres meilleures solutions, par exemple Le TreeDicticaire faiblessecessor / tryweaksuccessor méthodes déjà.
J'ai créé plusieurs structures de données fournissant cette fonctionnalité pour tout type de données: J'ai aussi fait une collection "cessée", Toutes ces collections sont dans le LOYC.Collections Package Nuget. < / p> Blist BDICTIONY bmultimap wwwowerboundbound () et Findupperbound () méthodes fonctionnant comme c ++ 's inférieur_bound et upper_bound . En interne, ces collections sont similaires à B + arbres , ils ont donc une bonne performance et une mémoire faible usage; BDICTARY <,> utilise généralement environ 44% de mémoire de moins qu'un type standard <,> (qui utilise en moyenne une mémoire légèrement moins que le dictionnaire < ,> ), en supposant des clés de 64 bits et des valeurs 64 bits.
sparsealist bdictionary
Vous pouvez le faire pour triède
Même Question , mais sans restriction sur
tritedlist < / code>.