existe-t-il une structure de données connue qui fournit un accès aléatoire O (1) sans utiliser de bloc de mémoire contigu de taille O (n) ou plus? Ceci a été inspiré par Cette réponse et est à la demande de la curiosité Sake plutôt que pour tout cas d'utilisation pratique spécifique, bien qu'il puisse être utile hypothétiquement dans des cas d'un tas gravement fragmenté.
4 Réponses :
Vous pouvez utiliser un Trie où la longueur de la clé est borné. En tant que recherche dans une trie avec une clé de longueur Pensez donc à la trie d'une trie où les clés sont des chaînes sur l'alphabet Voici une implémentation en C #: P> m code> est o (m) code>, si nous lions la longueur des touches, nous avons lié m code> et maintenant, la recherche est o (1) code>. {0, 1} code> (c'est-à-dire que nous sommes penser aux clés comme étant la représentation binaire des entiers). Si nous avons lié la longueur des clés pour dire 32 lettres, nous avons une structure que nous pouvons penser comme étant indexée par des entiers 32 bits et est accessible au hasard dans O (1) code> temps. class Program {
static void Main(string[] args) {
int length = 10;
TrieArray<int> array = new TrieArray<int>(length);
for (int i = 0; i < length; i++) {
array[i] = i * i;
}
for (int i = 0; i < length; i++) {
Console.WriteLine(array[i]);
}
}
}
C'est faux - Recherche dans Toute structure est constant une fois que vous avez limité la taille de la clé. Une trie binaire au plus 32 niveaux profonde est O (1) dans le même sens qu'un arbre binaire au plus 32 niveaux profond. L'arbre sera beaucoup plus rapide que la trie, cependant, car il faut beaucoup plus de temps pour le remplir le point où vous visitez 32 nœuds avant de retourner. La trie implémente simplement le comportement des arbres pire cas après la première insertion.
Absolument pas. À l'heure actuelle, les autres idées sont des hashtables, qui ont une recherche O (1), mais peuvent être considérées comme une mémoire contiguë et une gamme de pointeurs vers des tableaux, ce qui satisfait absolument la question.
@Potatoswatter: Quel est ton point? Les tableaux théoriques ne sont pas O (1) sauf si vous avez lié la taille de l'index maximum (car l'addition n'est pas O (1) sauf si vous avez lié les opérandes). Je me suis moqué d'un tableau indexable de la même manière que les matrices sont indexables.
@Jason: Je ne peux pas analyser que du tout, je vais répéter: un arbre binaire équilibré avec des clés 32 bits a au maximum 32 nœuds. L'opération la plus lente possible de recherche visit 32 nœuds, identique à votre trie. Cependant, l'arborescence équilibré ne devient que lentement lorsqu'elle détient plus de 2 ^ 31 nœuds, tandis que votre trie est aussi lente lorsqu'il contient 1 noeud. Votre trie est toujours plus lente qu'un arbre binaire. Essai sont rapides pour certaines choses, mais ce n'est pas un tel cas.
@jason: Si je comprends votre commentaire, c'est une défense de votre recherche O (longueur de la clé), comme l'ajout n'est pas O (1). Mais l'addition est O (log n), pas O (n), vous n'aurez donc jamais d'avance sur une matrice de bignum théorique.
@Potatoswatter: Non, mon point est que les matrices sont O (1) accès aléatoire exactement parce que les indices sont délimités. Si vous acceptez les indices délimités, vous devez accepter les clés liées.
@jason: Pourquoi dire quoi que ce soit sur Tries, alors? Vous pouvez également stocker des paires (clé, valeur) dans une liste liée et elle sera toujours O (1). De même, le problème d'arrêt d'un système avec une mémoire finie est O (1).
Tout ce que ce volet est vraiment inutile. Le fait est que c'est une bonne réponse pratique à la question. Bien que les recherches trie soient théoriquement O (log n), le facteur constant indiquant un logarithme de base-1024 les rend performant comme O (1) dans la pratique, contrairement à la plupart des structures de données O (log n). Ils peuvent être mis en œuvre avec une ligne droite (1) code comme t & opérateur [] (taille_t x) {table de retour [index0 (x)] [index1 (x)] [index3 (x) )]; } , et ils peuvent finir par surperformer certaines des autres réponses proposées O (1) pour les ensembles de données volumineux. Contraster des arbres binaires.
@Jason: Les essais binaires avec des clés de taille fixe sont totalement peu pratiques. Vous confondez la taille de la clé avec la taille de la structure. Un arbre binaire avec taille de clé n a au plus 2 ^ n éléments à l'intérieur et nécessite au plus N étapes indirections (mais dans la pratique beaucoup moins que cela stocke moins de données que 2 ^ n ), contrairement à votre trie qui nécessite exactement n < / code> indirections. Ce n'est pas un eribing. Votre structure est juste un arbre binaire pessimal.
@Jason Orendorff: Oups, cette dernière réponse était pour vous. Quoi qu'il en soit, les essais fonctionnent bien lorsque la taille de la clé est variable et que l'opération de comparaison est O (n) et une commande lexicographique permet une comparaison pliante dans la descente. Ici, il est impraticable car la comparaison est O (1) - une instruction d'une machine.
@Potatoswatter: whoa - vous avez raison, je n'ai pas lu la réponse assez près. Je pensais que Jason proposait une vraie trie avec quelque chose comme 8-12 bits à chaque niveau de l'arbre, pas un peu. Vous avez raison, les essais binaires seraient un choix très idiot ici.
Oui, voici un exemple en C ++:
template<class T>
struct Deque {
struct Block {
enum {
B = 4*1024 / sizeof(T), // use any strategy you want
// this gives you ~4KiB blocks
length = B
};
T data[length];
};
std::vector<Block*> blocks;
T& operator[](int n) {
return blocks[n / Block::length]->data[n % Block::length]; // O(1)
}
// many things left out for clarity and brevity
};
La longueur du bloc :: Data O (n)? C'est une fraction de n, mais c'est une fraction constante et donc o (n).
Ceci est une structure contiguë: tous les éléments sont là dans une ligne sans lacunes. Nice adressant la sémantique, mais pas vraiment réactive à la question.
@dsimcha: Non, la longueur est une constante de temps de compilation.
@DMCKEE: Les éléments ne sont pas stockés dans "Un bloc de mémoire contigu [unique] contigu", comment ne répond pas à la question?
@Dsimcha: Non, Bloc :: La longueur est constante (j'ai utilisé B ici, mais cela pourrait être 42, 3, etc.) et ne change jamais, peu importe le nombre d'éléments stockés.
@Roger: OK, tu as raison, j'ai mal interprété ça, mais ne bloque pas O (n)? Ne serait pas bloqué.Size () == n / b?
@dsimcha: Oui, peut-être que j'ai mal interprété "sans utiliser de bloc de mémoire contigu de taille O (n) ou plus grand" qui semble gênant. Pourriez-vous clarifier ce que vous voulez? Si ma réponse ne correspond pas à votre définition, alors rien ne sera, à moins que vous artificiellement limite la taille du conteneur. (Je peux vous limiter à INT_MAX Articles, stockez cette drique dans un arbre, et appelez cette recherche O (1), par exemple.)
@ "Roger Pate": Vous devriez avoir juste répondu std :: deque pour éviter la confusion.
@ "Roger Pate": Je suis également en désaccord avec votre déclaration "et, en fait, il y a un peu d'un problème implémentant STD :: deque d'avoir tous" push_front, push_back et op [] être O (1) - sauf si vous discutez votre implémentation spécifique. Si vous avez utilisé des listes liées pour stocker les blocs plutôt qu'un vecteur, toutes les opérations peuvent être effectuées dans O (1).
Très cool, et merci de me faire m'informer de la complexité de std :: deque :: iterator :: opérateur + ! Je suggérerais de faire chaque bloc deux fois la taille du dernier, cependant. Pour trouver quel bloc a l'objet, index blocs avec le nombre de bits dans l'index et le bloc avec les bits suivant le premier. Les deux premiers objets sont dans le premier bloc comme cas particulier.
@ceretllis: J'ai essayé d'éviter la confusion par donnant un exemple spécifique. Une desquelles avec un LL de blocs a une recherche O (n) (avec un facteur de 1 / B, il est donc encore très petit), pas O (1).
@Potatoswatter: Cela fonctionne si vous ne grandissez que à une extrémité ou à l'autre, mais si vous traitez la drique comme une FIFO (E.g. Utilisez uniquement Push_back et POP_Front), il tombera en panne. (Vous pourriez avoir un meilleur exemple de structure pour cette question spécifique.)
@Roger: Ne dites jamais jamais. Vous pouvez effacer des blocs comme bloquer.end ()
* Je veux dire, ne rétrécit jamais outre les blocs de "plomb" plus petits qui ont finalement libéré autant d'espace que la taille du bloc final.
Poatoswatter: Il semble que o (1) un accès aléatoire serait alors un gâchis à mettre en œuvre.
Comment diriez-vous d'une carte / dictionnaire? Dernier j'ai vérifié, c'est o (1) performance.
Une carte de hachage prend une mémoire contiguë. Une carte d'arborescence ou une liste de sauts prend O (journal n) heure de recherche (bien que si vous êtes toujours séquentiel, une arborescence de spelie peut retourner cela dans O (1) amorti).
Eh bien, Sorta. Si les types peuvent être consultés par référence, il peut être mis en œuvre pour ne pas prendre cela - le réseau de base ne doit pas nécessairement être O (n) et que les allocations de tout débordement ne doivent certainement pas être toutes contiguës et la Les types stockés réels peuvent être stockés dans des endroits arbitraires s'ils sont stockés sous forme de réfs / pointeurs. Il y a un certain niveau de dépendance linguistique là-bas, cependant.
Kyoryu a raison que vous puissiez stocker une carte de hachage de différentes manières qui ne nécessitent pas une seule allocation contiguë de taille de conteneur, mais que la recherche est uniquement O (1) si vous connaissez certaines choses sur la fonction Hash et le jeu de données.
@Roger: C'est vrai - la performance peut potentiellement dégrader à O (n), mais dans les cas généraux, je l'ai généralement vu accepté comme O (1) (compte tenu des informations suffisantes sur le jeu de données, vous pouvez concevoir un système pour obtenir efficacement o (1) perf)
Si seulement vous avez eu une structure de données fournie à O (1) recherche et utilisée de la mémoire non contiguë, vous pouvez utiliser que pour la table de hachage.
Eh bien, puisque j'ai passé du temps à y penser, et il pourrait être affirmé que tous les hashtables sont un bloc de taille contigu> N ou ont une liste de seau proportionnelle à N, et Roger's Tableau de niveau supérieur de Block code> S est O (n) avec un coefficient inférieur à 1, et j'ai proposé une solution à celle des commentaires à sa question, voici: int magnitude( size_t x ) { // many platforms have an insn for this
for ( int m = 0; x >>= 1; ++ m ) ; // return 0 for input 0 or 1
return m;
}
template< class T >
struct half_power_deque {
vector< vector< T > > blocks; // max log(N) blocks of increasing size
int half_first_block_mag; // blocks one, two have same size >= 2
T &operator[]( size_t index ) {
int index_magnitude = magnitude( index );
size_t block_index = max( 0, index_magnitude - half_first_block_mag );
vector< T > &block = blocks[ block_index ];
size_t elem_index = index;
if ( block_index != 0 ) elem_index &= ( 1<< index_magnitude ) - 1;
return block[ elem_index ];
}
};
template< class T >
struct power_deque {
half_power_deque forward, backward;
ptrdiff_t begin_offset; // == - backward.size() or indexes into forward
T &operator[]( size_t index ) {
ptrdiff_t real_offset = index + begin_offset;
if ( real_offset < 0 ) return backward[ - real_offset - 1 ];
return forward[ real_offset ];
}
};
Woops, le plus grand bloc attribué par ce schéma est d'au moins 1/4 de la capacité totale et qui se qualifie comme O (n). Néanmoins, c'est une idée astucieuse et devrait fonctionner mieux qu'une deque. (Ma mise en œuvre a eu la plus laid que je voulais que ce soit et que je l'ai abandonnée ... devrait y revenir ...)
Pour aborder spécifiquement une certaine confusion de la question
std :: vecteur question: la plupart du temps, les gens en parlent dans le contexte de traiteret de vecteur [0] en tant que tableau C . Les implémentations de vecteurs pathologiques pourraient casser la compatibilité de la graphique C tout en respectant facilement les besoins d'accès aléatoire C ++ 98's O (1) en stockant simplement des éléments dans l'ordre inverse.Que défaut a été corrigé en C ++ 03. Il ne vaut vraiment pas la peine de débattre-haves pour un défaut connu qui n'a jamais été mal compris dans les bibliothèques du monde réel. Voir les commentaires de Stroustrup à velocityreviews.com/forums/...
Droite, je m'expliquant simplement pourquoi les exigences de C ++ 98 ne sont que implicites de la mémoire contiguë plutôt que de nécessiter la mémoire contiguë (ce qui est ce qui a incité cette question). Je suis totalement d'accord c'est un non-question.
@jamesdlin: ah, je n'ai pas vu cette confusion de la question.