Est-il possible de créer des tableaux en fonction de leur index comme dans
int x = 4; int y = 5; int someNr = 123; int foo[x][y] = someNr;
dynamiquement / en cours d'exécution, sans créer foo [0 ... 3] [0 ... 4]?
Sinon, existe-t-il une structure de données qui me permet de faire quelque chose de similaire en C?
3 Réponses :
Non.
Tel qu'il est écrit, votre code n'a aucun sens. Vous avez besoin que foo soit déclaré quelque part, puis vous pouvez l'indexer avec foo[x][y] = someNr; . Mais vous ne pouvez pas simplement faire exister foo ce qui ressemble à ce que vous essayez de faire.
Soit créer foo avec des tailles correctes (vous seul pouvez dire ce qu'elles sont) int foo[16][16]; par exemple ou utilisez une structure de données différente. En C ++, vous pouvez faire une map<pair<int, int>, int>
Je sais que cela n'a aucun sens, il s'agissait d'illustrer ce que je voulais faire. J'ai jeté un coup d'œil au mappage pour C, et il semble que je doive hacher pour trouver la bonne carte dans un tableau de mappage, oui?
Il existe différentes approches. Le hachage est probablement le plus courant. «Tableau clairsemé» est un bon terme de recherche pour plus de recherche. Comme @tadman l'a dit dans les commentaires: 1024x1024 n'est pas si cher (peut-être ne le mettez pas sur la pile), donc si vous devez faire un autre type de données ou simplement allouer un grand tableau est vraiment votre appel.
Je sais que ce n'est normalement pas un gros problème de prendre 4 Mo de mémoire, mais je travaille sur un système d'exploitation, où sur un 32 bits, cela ne prend que 4 Mo par programme en cours d'exécution. Mais sur un 64 bits, j'aurais besoin de quelque chose comme 2 * 2 ^ 25 int array
Eh bien, on dirait que quelque chose comme un tableau clairsemé est la voie à suivre.
Même si x et y étaient remplacés par des constantes, vous ne pouviez pas initialiser le tableau en utilisant la notation indiquée. Vous auriez besoin d'utiliser:
int x = 4;
int y = 5;
int someNr = 123;
int foo[x][y];
for (int i = 0; i < x; i++)
{
for (int j = 0; j < y; j++)
foo[i][j] = someNr + i * (x + 1) + j;
}
ou similaire (accolades supplémentaires, peut-être; plus de valeurs peut-être). Vous pouvez cependant déclarer / définir des tableaux de longueur variable (VLA), mais vous ne pouvez pas du tout les initialiser. Alors, vous pourriez écrire:
int fixed[3][4] = { someNr };
De toute évidence, vous ne pouvez pas utiliser x et y comme index sans écrire (ou lire) en dehors des limites du tableau. Il vous incombe de vous assurer qu'il y a suffisamment d'espace sur la pile pour les valeurs choisies comme limites sur les tableaux (ce ne sera pas un problème à 3x4; cela pourrait être à 300x400 cependant, et sera à 3000x4000). Vous pouvez également utiliser l'allocation dynamique de VLA pour gérer des matrices plus volumineuses.
Le support VLA est obligatoire dans C99, facultatif dans C11 et C18, et inexistant dans C90 strict.
Si vous voulez une «prise en charge des tableaux épars», il n'y a pas de fonction intégrée en C qui vous aidera. Vous devez concevoir (ou trouver) du code qui gérera cela pour vous. Cela peut certainement être fait; Les programmeurs Fortran devaient le faire assez souvent dans le mauvais vieux temps, lorsque les mégaoctets de mémoire étaient un luxe et MIPS signifiait des millions d'instructions par seconde et les gens étaient heureux lorsque leur ordinateur pouvait faire un MIPS à deux chiffres (et la norme Fortran 90 était encore des années dans le futur).
Vous devrez concevoir une structure et un ensemble de fonctions pour gérer le tableau fragmenté. Vous devrez probablement décider si vous avez des valeurs dans chaque ligne ou si vous n'enregistrez les données que dans certaines lignes. Vous aurez besoin d'une fonction pour attribuer une valeur à une cellule et d'une autre pour récupérer la valeur d'une cellule. Vous devrez réfléchir à la valeur quand il n'y a pas d'entrée explicite. (La réflexion n'est probablement pas difficile. La valeur par défaut est généralement zéro, mais un infini ou un NaN (pas un nombre) peut être approprié, selon le contexte.) Vous auriez également besoin d'une fonction pour allouer la structure de base (serait vous spécifiez les tailles maximales?) et un autre pour le libérer.
Le moyen le plus efficace de créer un index dynamique d'un tableau est de créer un tableau vide du même type de données que le tableau à indexer.
Imaginons que nous utilisions des nombres entiers par souci de simplicité. Vous pouvez ensuite étendre le concept à tout autre type de données.
La profondeur d'index idéale dépendra de la longueur des données à indexer et se situera quelque part près de la longueur des données.
Supposons que vous ayez 1 million d'entiers 64 bits dans le tableau à indexer.
Tout d'abord, vous devez commander les données et éliminer les doublons. C'est quelque chose de facile à réaliser en utilisant qsort () (la fonction intégrée de tri rapide C) et en supprimant la fonction dupliquée telle que
index[11] = 2023;
Adaptez le code ci-dessus à vos besoins, vous devez libérer () le tableau non ordonné lorsque la fonction a fini de le commander dans le tableau ordonné. La fonction ci-dessus est très rapide, elle retournera zéro entrée lorsque le tableau à commander contient un élément, mais c'est probablement quelque chose avec lequel vous pouvez vivre.
Une fois les données ordonnées et uniques, créez un index d'une longueur proche de celle des données. Il n'a pas besoin d'être d'une longueur exacte, bien que le fait de s'engager à des puissances de 10 facilitera tout, en cas d'entiers.
index[10] = 733;
Cela créera un tableau d'index vide. Remplissez ensuite l'index. Parcourez votre tableau pour indexer une seule fois et chaque fois que vous détectez un changement dans le nombre de chiffres significatifs (identique à la profondeur d'index) vers la gauche, ajoutez la position où ce nouveau nombre a été détecté.
Si vous choisissez une profondeur d'index de 2, vous aurez 10² = 100 valeurs possibles dans votre index, allant généralement de 0 à 99.
Lorsque vous détectez qu'un certain nombre commence par 10 (103456), vous ajoutez une entrée à l'index, disons que 103456 a été détecté à la position 733, votre entrée d'index serait:
uint64_t* idx = calloc(pow(10, indexdepth), sizeof(uint64_t));
La prochaine entrée commençant par 11 doit être ajoutée dans le prochain emplacement d'index, disons que le premier numéro commençant par 11 se trouve à la position 2023
uint64_t remove_dupes(char *unord_arr, char *ord_arr, uint64_t arr_size)
{
uint64_t i, j=0;
for (i=1;i<arr_size;i++)
{
if ( strcmp(unord_arr[i], unord_arr[i-1]) != 0 ){
strcpy(ord_arr[j],unord_arr[i-1]);
j++;
}
if ( i == arr_size-1 ){
strcpy(ord_arr[j],unord_arr[i]);
j++;
}
}
return j;
}
Etc.
Lorsque vous avez besoin ultérieurement de trouver un certain nombre dans votre tableau d'origine stockant 1 million d'entrées, vous n'avez pas à parcourir le tableau entier, il vous suffit de vérifier où dans votre index le premier nombre commençant par les deux premiers chiffres significatifs est stocké. L'index d'entrée [10] vous indique où le premier nombre commençant par 10 est stocké. Vous pouvez ensuite parcourir jusqu'à ce que vous trouviez votre correspondance.
Dans mon exemple, j'ai utilisé un petit index, donc le nombre moyen d'itérations que vous devrez effectuer sera 1000000/100 = 10000
Si vous agrandissez votre index à un endroit proche de la longueur des données, le nombre d'itérations tendra à 1, ce qui rendra toute recherche extrêmement rapide.
Ce que j'aime faire, c'est créer un algorithme simple qui me dit quelle est la profondeur idéale de l'index après avoir connu le type et la longueur des données à indexer.
Veuillez noter que dans l'exemple que j'ai posé, les nombres de 64 bits sont indexés par leurs premiers chiffres significatifs de profondeur d'index, ainsi 10 et 100001 seront stockés dans le même segment d'index. Ce n'est pas un problème en soi, néanmoins chaque maître a son petit livre de secrets. Traiter les nombres comme une chaîne hexadécimale de longueur fixe peut aider à conserver un ordre numérique strict.
Vous n'avez pas besoin de changer la base, vous pouvez considérer que 10 est 0000010 pour le garder dans le segment d'index 00 et garder les nombres de base 10 ordonnés, l'utilisation de bases numériques différentes est néanmoins triviale en C, ce qui est d'une grande aide pour cela tâche.
Au fur et à mesure que vous augmentez la profondeur de votre index, le nombre d'entrées par segment d'index sera réduit
Veuillez noter que la programmation, en particulier au niveau inférieur comme C, consiste à comprendre en grande partie le commerce entre les cycles de processeur et l'utilisation de la mémoire.
La création de l'index proposé est un moyen de réduire le nombre de cycles CPU requis pour localiser une valeur au prix d'utiliser plus de mémoire lorsque l'index devient plus grand. C'est néanmoins la voie à suivre de nos jours, car des quantités massives de mémoire sont bon marché.
À mesure que la vitesse des disques SSD se rapproche de celle de la RAM, l'utilisation de fichiers pour stocker des index doit être prise en compte. Néanmoins, les systèmes d'exploitation modernes ont tendance à se charger autant qu'ils le peuvent dans la RAM, donc l'utilisation de fichiers aboutirait à quelque chose de similaire d'un point de vue opérationnel.
On dirait que vous voudrez peut-être une carte stackoverflow.com/questions/21958247/...
Vous devez d'abord déclarer le tableau, puis affecter le second, sauf si vous êtes prêt à attribuer les valeurs correctement . Toutes les valeurs que vous n'initialisez pas sont, par définition, non initialisées et contiennent des données indésirables, vous souhaiterez donc probablement toutes les initialiser, pas de manière sélective.
@tadman Si je le déclare d'abord, alors ce ne sera pas dynamiquement
Si vous voulez qu'il soit entièrement dynamique, vous utilisez
malloc. Vous devez connaître la taille maximale au préalable ou ce n'est pas possible. Comme le dit bhspencer, une carte peut être ce que vous voulez si vous n'avez aucune idée de l'endroit où ces valeurs dexetyvont atterrir.@bhspencer c'est très similaire à ce que je recherche, mais devez-vous hacher pour obtenir la valeur? Je veux vraiment le faire dans le temps O (1) et avec le hachage je risque d'avoir le même index de devoir les lier entre eux et de le faire en 2 opérations
@tadman Je sais qu'ils vont atterrir entre 0 et 1023, mais moi aussi maintenant que même pas 1/4 ne sera régulièrement occupé, donc cela semble être une perte d'espace pour déclarer une mémoire qui ne sera pas utilisée. J'ai jeté un coup d'œil rapide à la cartographie, et cela semble être dans le bon sens, mais j'ai un problème avec cela (voir le commentaire précédent)
Si seulement 25% sont occupés, vous devez vous concentrer sur le coût réel ici. Est-ce que 1024 * 1024 * 4 casserait vraiment la banque? Cela ne représente que 4 Mo de mémoire. À moins que vous n'ayez des milliers de ces choses ou que vous soyez vraiment à court de mémoire, ce ne sera pas un gros problème. Vous pouvez économiser de la mémoire en utilisant à la place
short intou uncharsi cela était critique. Pensez aux contraintes à la fois en termes de valeurs que vous devez capturer et de conditions de mémoire dans lesquelles vous devez opérer.Ce que j'essaie de mettre en œuvre, c'est une table de pages à plusieurs niveaux. Et s'il occupe 4 Mo de mémoire, il bat le point d'une table de pages à plusieurs niveaux. Ils sont censés être alloués au besoin. Mais merci beaucoup pour les suggestions
@TomasBerger si vous utilisez des entiers comme clés et que vous savez qu'il n'y aura pas de collisions, non, vous n'avez pas besoin de hacher vos clés, utilisez simplement les entiers directement dans votre carte.