Permettez-moi de commencer par dire que ce n'est pas une question de devoirs. J'essaie de concevoir un cache dont la stratégie d'expulsion dépend des entrées survenues le plus dans le cache. En termes logiciels, supposons que nous avons un tableau avec différents éléments et nous voulons simplement trouver l'élément qui s'est produit le plus. Par exemple: {1,2,2,5,7,3,2,3} devrait revenir 2. Puisque je travaille avec du matériel, la solution naïf o (n ^ 2) nécessiterait une formidable surcharge de matériel. La solution plus intelligente d'utilisation d'une table de hachage fonctionne bien pour les logiciels car la taille de la table de hachage peut changer mais dans le matériel, je disposerai d'une table de hachage de taille fixe, probablement pas si grande, les collisions entraîneront donc de mauvaises décisions. Ma question est, dans le logiciel, pouvons-nous résoudre le problème ci-dessus dans la complexité du temps O (n) et (1) espace?
6 Réponses :
Il ne peut pas y avoir de comme Amit souligne , en résolvant cela, nous trouvons la solution au Problème de distinction de l'élément (déterminer si tous les éléments d'une liste sont distincts), qui a été prouvé de prendre Cependant, pratiquement parlant, la gamme serait principalement délimitée, si elle ne l'utilise pas sans autre raison que le type que l'on utilise généralement pour stocker chaque élément dans une taille fixe (par exemple un entier 32 bits). Si tel est le cas, cela permettrait un 2 options:
Garder un éventail du nombre d'occurrences de chaque élément (l'indice de réseau étant l'élément), émettant le plus fréquent.
Si vous avez une plage de valeurs délimitée, cette approche serait Les options associées sont TRI RADIX (a une variante sur place, similaire à QuicksTort) et Seau de godet .
partitionnement répété des données basées sur un pivot sélectionné (par échange d'échange) et recouvre sur les partitions.
Après avoir tri, nous pouvons simplement itérer via la matrice, en gardant une trace du nombre maximum d'éléments consécutifs.
Cela prendrait O (n) heure, O (1) Solution spatiale, au moins pas pour le cas générique.
θ (n journal n) lorsqu'il n'utilise pas d'éléments pour indexer la mémoire de l'ordinateur. Si nous devions utiliser des éléments pour indexer la mémoire de l'ordinateur, étant donné une plage de valeurs non liée, cela nécessite au moins θ (n) espace. Compte tenu de la réduction de ce problème à celui-là, les limites de ce problème appliquent des limites identiques sur ce problème.
O (n) heure, O (1) Solution spatiale, même éventuellement trop lent et utilisant trop de place en raison de la Les gros facteurs constants impliqués (comme la complexité de temps et d'espace dépendraient de la gamme de valeurs).
O (1) espace (et O (n) heure). Mais techniquement, l'approche de la table de hachage, de sorte que les facteurs constants ici sont probablement trop importants pour que cela soit acceptable.
O (n log n) heure et O (1) espace.
Je ne crois pas un temps O (n) Heure, O (1) Espace Vous pouvez laisser tomber le "Je ne crois pas", il n'y a pas. S'il y avait la résolution de problèmes de distinction pourrait être effectué dans O (n) de l'espace et de l'espace O (1), en exécutant l'algorithme pour obtenir un candidat, puis vérifiez son nombre de surveurs. Votre réponse récapitule à peu près les possibilités, donc +1.
@amit merci. Je (espérons-le avec précision) l'incorporated dans ma réponse.
Je ne connais pas une limite inférieure qui dit ED ne peut pas être résolue dans ce temps et espace attendu à l'aide d'un algorithme randomisé comme une table de hachage. Référence?
@Niklasb. Selon Wikipedia, la solution de table HASH relève des éléments pour indexer la mémoire de l'ordinateur et ne sont donc pas soumises à ces limites de temps et d'espace. Mais Wikipedia mentionne également que la même liaison inférieure a été prouvée à des algorithmes randomisés qui ne tombent pas sous cela, c'est-à-dire des algorithmes de modèle algébrique algébrique algébrique.
Je ne peux pas extraire du tout que de l'article de Wikipedia, mais si vous le dites
L'algorithme discuté dans l'algorithme de Wikipedia résout le problème d'un ensemble de nombres tirés des réels. Il ne suit pas qu'elle générale à toutes les classes de chiffres. Par exemple, il est trivialement simplement de le faire dans O (n) Heure et O (1) Espace pour les entiers tirés de l'intervalle [0,32). Je crois que l'ensemble des chiffres que l'astucieux traite de la moyenne, il est également possible pour leur collection (voir ma réponse ci-dessous).
@JackAdley J'ai fait la distinction entre les plages d'entier bornées et sans bornes dans ma réponse (affirmant que la durée de fonctionnement est accessible pour les gammes entière bornées). Wikipedia ne semble pas mentionner explicitement des valeurs réelles, mais il est certainement possible que l'article référencé le fait, bien que je doute que la distinction soit suffisante pour invalider la durée de fonctionnement.
@Dukeling: Oui, le peu de réels est dans l'article référencé non dans l'article Wikipedia. Je pense que c'est une condition clé, si vous avez un ensemble énumérable et suffisamment d'espace pour compter, vous pouvez toujours le résoudre dans O (n) temps.
Comme vous dites un élément maximum de votre cache peut être un très grand nombre, mais la suivante est l'une des solutions.
TC -> O (n) SC -> O (1)
Cela peut ne pas être réalisable pour les grands m comme dans votre cas. Mais voyez si vous pouvez optimiser ou altérer cet algo.
Assomption: tout l'élément est entier, pour d'autres types de données, nous pouvons également y parvenir si nous utilisons hashcode ()
Nous pouvons obtenir une complexité de temps Tout d'abord, trier la matrice, la complexité du temps est O (Nlog N) (nous devrions utiliser un algorithme de tri en place comme à l'aide de quatre variables entier, itération du début à la fin du tableau actuel code> qui indique la valeur que nous faisons référence à, comptent code>, ce qui indique le Nombre d'occurrences de actuel code>, résultat code> qui indique le résultat de la finale et résultatcount code>, qui indiquent le nombre d'occurrences de résultat code > p> DATA CODE> P> int result = 0;
int resultCount = -1;
int current = data[0];
int count = 1;
for(int i = 1; i < data.length; i++){
if(data[i] == current){
count++;
}else{
if(count > resultCount){
result = current;
resultCount = count;
}
current = data[i];
count = 1;
}
}
if(count > resultCount){
result = current;
resultCount = count;
}
return result;
Journal (1) + log (2) + ... + journal (n) = journal (1 * 2 * .... * n) = journal (n!) qui est dans Theta (nlogn). Je ne comprends pas d'où vient votre demande de quasi o (n).
De plus, l'insertion d'un élément à un emplacement arbitraire dans une matrice est O (n), car vous devez "pousser" tous les éléments à sa bonne étape. Si vous souhaitez utiliser une liste d'arbres / de saut pour obtenir O (logn), vous allez souffrir de constantes beaucoup plus élevées.
(J'ai bownvoché avant que la réponse ait été réparée et a révoqué mon bowvote quand c'était)
@PHAMRUNG: Désolé, je l'ai fait par erreur. Je n'ai pas vu le correctif. S'il vous plaît faire un mannequin modifier dans votre réponse afin que je puisse annuler mon bowvote.
@Eyalschneider c'est bon :)
@Eyalschneider Vous pouvez également faire le mannequin éditez-vous dans ces cas;)
Une solution sur le dessus de la tête:
Comme les chiffres peuvent être importants, je considère donc le hachage, au lieu de les stocker directement dans la matrice.
laisser il y a n chiffres pour (i = 0 à n-1)
De cette façon, vous obtiendrez enfin les éléments k, et le nombre requis en est l'un d'entre eux, vous devez donc traverser à nouveau l'entrée L'espace utilisé est 0 à n-1 .
Supposons que le nombre occurant les temps maximum, occour k fois.
Faisons des godets N / K N / K, initialement tous vides.
hachage (num) indique si num est présent dans n'importe quel godet.
hachad_2 (num) stocke le nombre de fois num est présent dans n'importe quel godet.
[i] , quelque chose comme hash_2 (entrée [i]) ++ < / li>
entrée [i] dans le 1er godet vide. hachage (entrée [i]) = true
entrant [i] dans n'importe quel godets.
Si le nombre de tout nombre devient zéro [voir hash_2 (numéro)], hachage (numéro) = false .
o (n) à enfin trouver le nombre réel.
o (k) et la complexité du temps est O (n) , compte tenu de la mise en œuvre de hachage O (1) . de
Donc, la performance dépend vraiment de k . Si k << n , cette méthode fonctionne mal.
Je ne pense pas que cela réponde à la question indiquée dans le titre, mais vous pouvez en réalité mettre en œuvre un cache avec la stratégie d'expulsion la moins fréquemment utilisée ayant un temps moyen constant pour mettre, obtenir et supprimer des opérations. Si vous maintenez votre structure de données correctement, il n'est pas nécessaire de numériser tous les éléments afin de trouver l'élément à expulser.
L'idée est d'avoir une table de hachage qui mesure les clés pour valoriser des enregistrements. Un enregistrement de valeur contient la valeur elle-même plus une référence à un "noeud de comptoir". Un noeud compteur fait partie d'une liste doublement liée et se compose de:
La liste est maintenue de telle sorte qu'elle soit toujours triée par le compteur d'accès (où la tête est min), et les valeurs de compteur sont uniques. Un nœud avec compteur d'accès C contient toutes les clés ayant ce compte d'accès. Notez que cela n'abrompte pas la complexité globale de l'espace de la structure de données.
une opération d'obtention (k) implique la promotion de K en la migrant vers un autre enregistrement de compteur (un nouveau ou le suivant de la liste).
Une opération d'expulsion déclenchée par une opération de mise consiste à vérifier la tête de la liste, en supprimant une clé arbitraire de son ensemble clé, puis de la retirer de la table de hachage.
Il est possible si nous faisons des hypothèses raisonnables (pour moi, de toute façon) sur votre ensemble de données.
Comme vous dites que vous pouvez le faire si vous pouviez hacher, car vous pouvez simplement compter-compter-by-hachain. Le problème est que vous pouvez obtenir des hachages non uniques. Vous mentionnez des chiffres 20bit, donc probablement 2 ^ 20 valeurs possibles et un désir d'une quantité petite et fixe de mémoire de travail pour les comptes réels de hachage. Ceci, on présume, conduira donc à des collisions de hash et donc une ventilation de l'algorithme de hachage. Mais vous pouvez résoudre ce problème en faisant plus d'un passage avec des algorithmes de hachage complémentaires.
Parce que ce sont des adresses de mémoire, ce n'est probablement que tous les bits ne seront probablement pas capables d'être définis. Par exemple, si vous n'allouez jamais des morceaux de mot (4 octets), vous pouvez ignorer les deux bits les moins importants. Je soupçonne, mais je ne sais pas, que vous ne faites que traiter avec des limites d'allocation plus importantes afin que cela puisse être encore meilleur que cela.
supposer que le mot aligné; Cela signifie que nous avons 18 bits à hachage.
Ensuite, vous avez probablement une taille de cache maximale qui est probablement assez petite. Je vais supposer que vous allociez un maximum de <= 256 articles car nous pourrons alors utiliser un octet unique pour le compte.
D'accord, afin de faire connaître nos hachages, nous rompons le nombre dans le cache en deux nombres de neuf bits, par ordre de signification le plus élevé au plus bas et jetez les deux derniers bits comme indiqué ci-dessus. Prenez le premier de ces morceaux et utilisez-le comme un hachage pour donner une première partie compte. Ensuite, nous prenons la deuxième de ces morceaux et l'utilisons comme une hachage, mais cette fois-ci, nous ne comptons que si la première partie hachage correspond à celle que nous avons identifiée comme ayant le hachage le plus élevé. Celui qui reste avec le hachage le plus élevé est maintenant identifié de manière unique comme ayant le nombre le plus élevé.
Ceci fonctionne dans O (n) temps et nécessite une table de hachage de 512 octets pour compter. Si c'est trop grand une table, vous pouvez diviser en trois morceaux et utiliser une table de 64 octets.
ajouté plus tard
J'ai pensé à cela et je me suis rendu compte qu'il a une condition d'échec: si la première passe compte deux groupes comme ayant le même nombre d'éléments, il ne peut pas distinguer efficacement les autres. Oh bien
Avez-vous une limite maximale à laquelle les éléments peuvent survenir?
@Aniket c'est assez gros parce que cela fait partie de l'adresse physique, environ 20 bits
Existe-t-il quelques limites sur le nombre maximum d'éléments pouvant être dans la matrice?
@Nikunjbanka Oui, la limite est la taille du cache. C'est grand mais fini
Êtes-vous autorisé à muter le tableau - le tri, par exemple? De plus, comme c'est un cache, une heuristique inexacte serait une option viable?
Quelles entrées expulsez-vous, ceux qui ont le plus de survenus, ou ceux qui sont les moins? C'est à dire. Que se passe-t-il lorsque vous remplissez tout le cache? Enjolez-vous les éléments qui survèrent moins de fois, puis insérez-vous le nouvel élément?
Qu'est-ce qui se passe dans la cache? Quelles exigences de performance avez-vous pour ajouter des choses au cache? Il serait possible d'éliminer rapidement si vous étiez disposé à ajouter des travaux supplémentaires à l'insertion ou à charger les objets mis en cache avec des données de suivi supplémentaires.
J'essaie de comprendre pourquoi vous auriez des éléments en double dans le cache du tout. J'approcherais le problème en maintenant un compteur pour chaque article, ce qui indique combien de fois cela a été consulté.
Si je vous comprends correctement, la matrice d'entrée indique (lu) les opérations d'accès au cache. Mais le tableau est-il connu en la fois ou avez-vous besoin d'un algorithme en ligne? Ce dernier est un cas habituel pour les caches. Pour les algorithmes en ligne, une autre fonctionnalité doit être prise en compte à côté de l'espace et de l'exécution: la qualité de la solution. Avez-vous besoin de "solution optimale garantie"? Ceci est généralement impossible pour les algorithmes en ligne. Est une liaison sur la divergence de la solution optimale requise / suffisante? Qui liait? Savez-vous que O (1) peut être assez grand, si vous spécifiez la taille du cache à être constante ?
Quelle est la taille des articles?