J'ai une liste de recettes obtenues à partir d'une base de données qui ressemble à ceci: Recherche d'une recette aléatoire de En ce moment, ma seule idée est de créer une liste de alors, L'inconvénient de cette approche est la taille de ce réseau multidimensionnel serait y a-t-il un Une structure de données ou un algorithme de données plus efficace que je pourrais utiliser pour me permettre de trouver une recette aléatoire contenant une assiette autorisée? Merci! récipient , entre autres choses, a une propriété qui fait référence à un ou plusieurs Tags (tels que dîner , petit-déjeuner , côté , végétarien , vacances , et environ 60 autres). _Recipelist in O (1) serait bien sûr facile, cependant, ce que je dois faire trouve une recette aléatoire qui a, disons, 5 dans les balises in o (1). _recipelistbytag [5] contiendrait une liste de toutes les recettes ayant une 5 dans les balises < / Code> Array. Je pourrais alors choisir une étiquette autorisée aléatoire et une recette aléatoire dans cette étiquette dans O (1). Recettes * Tags (par exemple, la somme des étiquettes) à travers toutes les recettes), qui commence à prendre beaucoup de mémoire car je stocke un nombre potentiellement énorme de recettes dans ce tableau. Bien sûr, depuis recipénode est un type de référence, je ne répète que les pointeurs de 4 octets aux recettes, cela pourrait donc être le meilleur moyen d'aller.
5 Réponses :
Je ferais une exportation de la liste source à une autre avec des références à tous les éléments qui vous conviennent. Il fait un choix aléatoire et prenez un élément de la liste source, en fonction de la référence. S'il est possible que vous optiez à nouveau, utilisez la même liste dérivée, mettez de telles listes dans une liste plus grande. (De Cource, l'algorithme choisi dépend des statistiques réelles de votre liste.)
Si vous n'utilisez qu'un seul paramètre, vous pouvez commander votre liste par ce paramètre et rappelez-vous dans une autre liste B de références informatiques à l'endroit où les éléments avec la même valeur de paramètre démarrent. Plus tard, vous pourriez simplement prendre au hasard dans l'intervalle (B [4]; B [5] -1). Cela rendrait la vitesse d'un choix aléatoire égal à O (const).
Si je comprends cela correctement, il semble similaire à ce que le @Alexd disait. Stocker les compensations où chaque groupe commence et se termine. Je pense que c'est la même chose qu'un tableau déchiqueté.
Oui, c'est équivalent. Mais la pensée principale - il est impossible de proposer l'algorithme optimal ne sachant pas les supposées statistiques de son utilisation.
Si vous utilisez des étiquettes entières avec quelques valeurs possibles, vous n'avez même pas besoin de commander par balises. Mieux vaut prendre max et min et faire une liste de recettes pour chaque position entre ces deux. Ce serait une matrice déchiquetée d'épargne.
Dans ce cas, je voudrais, personnellement, allez pour SQLite solution (comme je, personnellement , sais que c'est mieux que les autres). Je vois que vous vous inquiétez d'un espace et non de la performance en termes de vitesse, mais en termes de temps de récupération constante, vous vous inquiétez également de la flexibilité de l'accès des données. IMO, dans ce cas, Concevez votre petite dB d'une manière que vous aimez et exécutez des requêtes et des jointures d'une manière que vous souhaitiez.
Ce est vieux mais toujours valide Exemple de comment pouvez-vous l'utiliser.
Il y a aussi une solution ORM naturellement (par exemple le pilote Linq), mais pour moi personnellement, il semble un peu de frais généraux.
J'espère que cela aide. sqlite est un moyen d'aller.
Si la quantité de mémoire occupée par vos structures de données vous est très chère, n'oubliez pas de appeler la liste.TrimExcess () après avoir peuplé chaque liste. Liste recettes * tags parce que chaque liste Dans le tableau contiendra autant de recettes que correspondant à une balise, et pas plus. Sa taille deviendrait recettes * tags si chaque recette contenait chaque étiquette.
Mes excuses de ne pas formuler ce droit - ce que je voulais dire, c'est que si une recette contenait la balise 5 et la balise 10, une référence à celle-ci serait répétée Index 5 et 10. La longueur serait le nombre de relations entre une recette et une étiquette.
J'ai décidé d'aller à cet itinéraire et j'ai un tableau pour chaque étiquette. Même avec un million d'accompagnements, qu'est-ce qui se trouve encore 4 Megs sur le tas droit?
Je le crois. Mais 4 Megs ne sont rien de plus aujourd'hui.
Si vous souhaitez conserver les données en mémoire, vous ne ferez pas beaucoup mieux qu'une liste des pointeurs (4 octets) pour chaque balise. Si vous pouvez utiliser un dB ... Eh bien, d'autres ont déjà posté à ce sujet. En fonction de votre énorme "énorme", vous pouvez simplement rechercher certains $$$ pour ajouter de la RAM à la machine cible.
Si vous souhaitez conserver les données en mémoire, mais que vous voulez être ridiculement parsimonious avec la mémoire, vous pouvez essayer de transmettre les 4 octets par combinaison de recette de balise. Par exemple, conservez toutes les recettes dans un grand tableau et (en supposant que vous n'ayez pas plus d'environ un million) d'index de réseau de stockage dans 3 octets chacun.
Pour aller encore plus loin, vous pouvez diviser les recettes avec une étiquette donnée dans des "seaux" de taille égale (chacun occupant une zone contiguë de la grande matrice), stockez un index de départ pour chaque "godet" (en 3-4 octets), puis stockez une liste de valeurs Delta entre index de recettes consécutives avec la balise donnée. Encédez les valeurs Delta à l'aide d'un tableau d'octets, de telle manière qu'une seule valeur delta puisse utiliser quelque chose de 1 à 4 octets, selon les besoins.
Parce que le nombre de recettes dans un "godet" sera limité à un nombre constant, la récupération de récupération à l'aide de cette approche est toujours O (1).
(J'ai fait une programmation intégrée sur des micro-micro avec aussi peu que 256 octets de RAM ... Lorsque vous faites que vous commencez à penser à des moyens très créatifs de sauver les octets ou même des bits. Je suis sûr que ça va ne pas être nécessaire dans votre application, mais je pensais que c'était une idée intéressante.)
J'essayais de descendre ces lignes aussi, mais je suis arrivé à la conclusion que (l'utilisation de la mémoire sage), cela ne serait pas différent de mon idée de matrice multidimensionnelle. Par exemple, si les recettes de balises 5 ont été stockées entre l'index de la matrice 100 et 200 et que des recettes de balises 6 ont été stockées entre 201 et 230, une recette qui avait les deux balises 5 et 6 aurait encore besoin d'être stockées deux fois .
@Mikechristensen, je pense que vous n'avez peut-être pas complètement compris mon idée. Avec les "réseaux multidimensionnels", vous avez besoin d'un pointeur de 4 octets pour chaque combinaison de tag de recette. Cette idée est une représentation différente (codée de Delta) de la même structure, conçue pour appuyer sur le nombre d'octets par combinaison de balises de recette, peut-être 1 à 2 octets en moyenne. Si la différence entre les index des 1er et 2e recettes avec la balise 5 est inférieure à 255, vous pouvez stocker cette différence dans 1 octet, plutôt que de stocker 2 index de 4 octets. S'il était inférieur à 2 ^ 16, vous pouvez le stocker dans 2 octets, etc.
Afin d'utiliser différents nombres d'octets pour les valeurs Delta, vous pouvez utiliser un schéma similaire à UTF-8. (Au début de chaque personnage multi-octets, ils utilisent certains bits pour indiquer le nombre d'octets que ce caractère occupe.)
Ce devoir est-il? Je doute que tout programme de recette du monde réel exige o (1) accès aux balises et être trop lent pour utiliser une base de données. Je doute également que toute recette du monde réel aurait étiquettes numériques . Comprendre le vrai domaine peut aider à fournir une meilleure réponse.
Cependant, s'il s'agit vraiment de recettes et de balises numériques, et si vous n'avez que 256 tags, pourquoi ne choisissez-vous pas simplement une recette aléatoire 1 million de fois? Les chances de ne pas trouver de recette avec la balise requise sont minimes et la complexité est toujours O (1). Si vous n'aimez pas les chances, choisissez une recette aléatoire 10 ^ 20 fois. La complexité est toujours o (1).
mise à jour:
car ce n'est pas le O (1) Vous êtes inquiet, mais plutôt le temps nécessaire pour choisir une recette aléatoire, je vous suggère de laisser votre base de données pour vous gérer pour vous - la même base de données qui contient toutes les recettes de toute façon, et la même base de données que vous allez accéder à la recette aléatoire.
Vous pouvez Sélectionner un enregistrement aléatoire dans SQL Server de cette façon: SQL Server Trier aléatoire . Si vous utilisez une autre base de données, il existe d'autres manières: http: //www.petefretag. com / élément / 466.cfm . Assurez-vous simplement que votre où clause a tag = 17 .
Remarque: Je suis d'accord surtout que vous n'êtes toujours pas absolument sûr que cette technique produira une recette avec la balise appropriée, mais elle sera dans n'importe quel cas réel ...
Choisir de manière aléatoire une recette puis le jeter si cela ne correspond à aucune des balises souhaitées ralentira un peu la fonction, surtout si l'utilisateur n'autorise que 1 étiquette obscure (comme des plats africains). Il est préférable de créer un index des recettes par balise, puis des recettes valides de recherche dans O (1). Je me demandais simplement de la meilleure façon de le faire avec une utilisation minimale de la mémoire.
Je pensais que tu étais inquiet pour la complexité, pas la vitesse. Si c'est une vitesse, vous êtes inquiet, mettez le tout dans une base de données et laissez-le trier pour vous. Ça va être assez rapide.
Homme qui serait la mère de toutes les requêtes SQL :)
Quoi? Non, pas les sélections aléatoires 10 ^ 20, sélectionnez simplement les identifiants des recettes avec la balise et choisissez randomalement dans cette liste. Vous ne stockez pas vos recettes en mémoire tout le temps, non? Ils sont dans une base de données quand même .
Je am stocke mes recettes en mémoire tout le temps. Cette fonction particulière fait partie d'un algorithme plus vaste qui ne peut pas être résolu à l'aide d'une requête de base de données. La fonction qui choisit l'une de ces recettes aléatoires doit fonctionner plusieurs centaines de milliers de fois une seconde - je ne fais que faire plusieurs centaines de milliers de requêtes SQL une seconde.
Il ne s'agit pas de trouver une recette - il s'agit de trouver un ensemble de recettes correspondant à votre recherche. Dis que j'ai eu 1 000 recettes (j'ai beaucoup plus encore) et je voulais passer en revue tous les ensembles de 5. Cela seraient quelque 8,6 milliards de dollars pour évaluer - cela pourrait prendre un certain temps :)
Je pense que vous devriez reformuler votre question et demander ce que vous vraiment veux faire. Expliquez mieux la situation - ce que les données ressemblent à la recherche de la recherche de l'utilisateur et de ce que l'utilisateur attend en retour. Même si vous essayez un problème de sacs à dos (trouvez-moi des recettes pendant une semaine avec un total de 4 000 calories), il est encore plus facile de faire cela.
J'ai parfaitement indiqué la question. J'ai défini les structures et restrictions de données, et ce que je voulais résoudre. J'ai demandé à la question exacte que je voulais une réponse, et ce n'est pas que les gens de ma faute choisissent de voyager en dehors des limites de ces paramètres. Il vous suffira de faire confiance, je connais le domaine du problème beaucoup mieux que vous, et si le problème pourrait être mieux résolu par quelques requêtes SQL, je l'aurais fait. Avec cela, +1 pour votre réponse, car j'apprécie votre volonté d'aider.
Pourquoi ne pas utiliser simplement
sqlite ? Et récupérer les données en constante (autant que possible) temps.+1 Tigran - ressemble à un problème adapté à un dB.
Il me semble très étrange que vous utilisiez un tableau d'octets pour les balises, au lieu de quelque chose d'orienté objet, tel qu'une liste de références aux objets de balise. Avez-vous vraiment de telles contraintes de mémoire que vous devez réellement faire des hacks comme ça?
"Répéter les pointeurs de 4 octets" qui dépend de la mise en œuvre. Combien d'articles avez-vous? avec un nombre énorme d'éléments O (journal (n)) est presque O (1)
La mise en œuvre actuelle n'est pas exactement O (1). Chaque fois que vous souhaitez une entrée aléatoire avec une balise particulière, vous devez le traduire en indice entier correspondant. Vous pouvez utiliser des tables de hasch pour cela, mais ce n'est pas O (1), mais O (logn). La différence n'est pas exactement notable, mais toujours ... Il existe d'autres moyens plus propres pour atteindre O (logn), mais je ne suis pas au courant de l'approche O (1).
@Elkamina, son approche est O (1). Il pré-construit un vecteur des recettes avec chaque balise. La taille de chaque vecteur est connue. Pour choisir un élément aléatoire, il doit simplement générer un nombre aléatoire de 0 à la longueur de vecteur moins un et effectuer une opération d'indexation de tableau pour extraire l'élément à cet indice. L'indexation dans un tableau est O (1).
@Alexd Ma question est, étant donné une étiquette (par exemple, des vacances) Comment trouve-t-il la balise d'octet? Ce n'est pas possible dans O (1) heure.
@Elkamina: cela pourrait être o (k) ou o (lg k), ce n'est pas O (lg n)
Vraisemblablement, vous devez choisir de nombreuses recettes (plus que
Recettes * Tags Si vous êtes prêt à considérer cette initialisation à amortir à O (1) avec la sélection). Peut-être que si vous avez décrit l'opération de cueillette, nous pourrions suggérer un moyen d'obtenir l'intégralité de l'initialisation + tout la cueillette pour amortir à O (1) par choix.@Elkamina, Hâble n'est pas une sorte de tri. C'est exactement o (1).
Cas classique de rejeter le domaine. Aucun moyen que le monde ait suffisamment de recettes pour donner une machine moderne toute sorte de défi de la résolution de cela en temps humain.
@Tigran - Malheureusement, tout accès à base de dB est trop lent pour cet algorithme. Il doit fonctionner instantanément. De plus, je suis à peu près sûr qu'un dB ne trouverait pas les données de O (1) non plus.
@Elkamina - Déterminer si un
recipénode a une balise de certaines balises n'est pas nécessaire si j'expose mes tableaux par balise. Donc, nulle part dois-je interroger si la recette x a tag y dans O (1).@BenJackson - très perceptif de vous :) Cette "opération de cueillette" doit fonctionner plusieurs centaines de milliers de fois une seconde. L'algorithme n'est pas conçu pour trouver une seule recette, mais créer des ensembles optimaux de recettes répondant aux critères souhaités. Pensez-y en tant que multiple Knapack problématique: "J'ai 12 œufs, 1l de saumon et une tête de laitue - quelles recettes puis-je faire cette semaine qui l'utilisera?"
@Tigran Une base de données relationnelle n'est pas une baguette magique. Cela ne peut pas faire les choses plus efficacement juste à cause de ce que c'est. En fait, la sélection aléatoire d'une base de données relationnelle a tendance à être très inefficace, à moins que vous ne preniez des mesures spéciales.
@Nickjohnson: Utilisation du terme
aléatoire , tel quel, vous jamais peut Garantie LeO (1) Accès, Juste parce que c'est aléatoire. OP: WHANT'S '' CODE> O (1) ACEES (où il est possible), concerne la consommation de mémoire et la demande pose assez bien dans le concept de DB relationnelle. Oui, ceci n'est pas une baguette magique: il s'agit d'une solution appropriée (OMI Best) pour ce problème.Je suis à peu près sûr qu'aucun dB sur la planète ne va faire
Sélectionnez Receperid à partir de la commande de recettes par aléatoire () limite 1; dans O (1). Sans parler de la surcharge de fabrication d'un appel SQL en premier lieu n'est pas O (1) non plus. Où-commerecipénode r = _recipeliste [aléatoire.next (_recipelist.length)]; sera O (1) à chaque fois.@Mikechristensen: Donc, peut-être que je manque votre idée de hasard. J'ai compris que aléatoire (dans votre cas) n'est pas accès , mais le paramètre vous devez interroger sur, afin de trouver la liste des objets appropriés. Une fois, vous pouvez interroger pour la réception avec TAG = 5, une autre requête de temps pour la réception qui a -12 et ainsi de suite. L'exemple que vous fournissez dans le commentaire est naturely
O (1) accès (pas de doutes), mais cela ne me semble pas, c'est ce qui posait en question, causer ici vous tromper un index et pas un paramètre de recherche. Peut-être que je manque quelque chose ...@Tigran - Mettez simplement, je souhaite trouver une recette aléatoire qui a une étiquette X dans O (1), et cette opération est si fréquente que faire un appel DB à chaque fois n'est pas une option viable.