Ich habe eine Liste von Rezepten, die aus einer Datenbank stammen, die wie folgt aussieht:
%Vor% RecipeNode hat unter anderem eine Eigenschaft, die auf ein oder mehrere Tags verweist (z. B. Abendessen , Frühstück , Seite ). Vegetarier , Urlaub und ungefähr 60 andere).
Das Finden eines zufälligen Rezepts von _recipeList in O (1) wäre natürlich einfach, aber was ich tun muss, ist ein zufälliges Rezept zu finden, das zB 5 in Tags in O (1) hat.
Im Moment ist meine einzige Idee, ein Array von List<RecipeNodes> zu erstellen, das per Tag getaggt wird. Zum Beispiel:
Dann würde _recipeListByTag[5] eine Liste aller Rezepte enthalten, die im Array Tags eine 5 haben. Ich könnte dann ein zufälliges Tag und ein zufälliges Rezept innerhalb dieses Tags in O (1) auswählen.
Der Nachteil dieses Ansatzes ist, dass die Größe dieses multidimensionalen Arrays Recipes * Tags ist (zB die Summe der Tags.length über alle Rezepte), was viel Speicherplatz in Anspruch nimmt, da ich ein potentielles Objekt speichere riesige Anzahl von Rezepten in diesem Array. Da RecipeNode ein Referenztyp ist, wiederhole ich natürlich nur die 4-Byte-Zeiger auf die Rezepte, so dass dies immer noch der beste Weg ist.
Gibt es eine effizientere Datenstruktur oder einen Algorithmus, den ich verwenden könnte, um ein zufälliges Rezept zu finden, das ein bestimmtes zulässiges Tag enthält? Danke!
List<RecipeNode>[] _recipeListByTag ist wahrscheinlich der beste Ansatz für Sie, und seine Größe ist nicht Recipes * Tags , da jede Liste im Array nur so viele Rezepte enthält wie ein Tag und nicht mehr. Seine Größe würde Recipes * Tags werden, wenn jedes einzelne Rezept jedes einzelne Tag enthält.
Wenn Ihnen die von Ihren Datenstrukturen belegte Speicherkapazität so sehr am Herzen liegt, vergessen Sie nicht, List.TrimExcess () aufzurufen, nachdem Sie jede Liste ausgefüllt haben.
Sind das Hausaufgaben? Ich bezweifle, dass ein reales Rezeptprogramm O (1) Zugriff auf Tags erfordert und für die Verwendung einer Datenbank zu langsam ist. Ich bezweifle auch, dass irgendein reales Rezept numerische -Tags haben würde. Das Verständnis der realen Domäne kann helfen, eine bessere Antwort zu geben.
Wenn es jedoch wirklich um Rezepte und numerische Tags geht und Sie nur 256 Tags haben, warum wählen Sie nicht einfach ein zufälliges Rezept 1 Million Mal? Die Wahrscheinlichkeit, ein Rezept mit dem erforderlichen Tag nicht zu finden, ist minimal und die Komplexität ist immer noch O (1). Wenn Sie die Chancen nicht mögen, wählen Sie ein zufälliges Rezept 10 ^ 20 mal. Die Komplexität ist noch O (1).
UPDATE:
Da es nicht das O (1) ist, um das du dich sorgst, sondern die Zeit, die du brauchst, um ein zufälliges Rezept auszuwählen, schlage ich vor, dass deine Datenbank dies für dich erledigt - die gleiche Datenbank, die sowieso alle Rezepte enthält, und die gleiche Datenbank, auf die du zugreifen wirst, um das zufällige Rezept anzuzeigen.
Sie können SELECT einen zufälligen Datensatz in SQL Server auf diese Weise erstellen: SQL Server Random Sort . Wenn Sie eine andere Datenbank verwenden, gibt es andere Möglichkeiten: Ссылка . Stellen Sie nur sicher, dass Ihre WHERE -Klausel Tag=17 enthält.
Wenn Sie die Daten im Speicher behalten wollen, werden Sie nicht viel besser als eine Liste von (4 Byte) Zeigern für jedes Tag tun. Wenn du eine DB benutzen kannst ... haben andere schon darüber geschrieben. Je nachdem, wie groß "riesig" ist, können Sie etwas Geld ausgeben, um dem Zielrechner RAM hinzuzufügen.
Wenn Sie die Daten im Speicher behalten möchten, aber sparsam mit Speicher arbeiten möchten, können Sie versuchen, die 4 Bytes pro Tag-Rezept-Kombination zu drücken. Zum Beispiel, behalten Sie alle Rezepte in einem großen Array und (vorausgesetzt, Sie haben nicht mehr als etwa eine Million) speichern Array-Indizes in jeweils 3 Bytes.
Um noch weiter zu gehen, können Sie die Rezepte mit einem bestimmten Tag in gleich große "Eimer" aufteilen (die jeweils einen zusammenhängenden Bereich des großen Arrays belegen), einen Startindex für jeden "Eimer" speichern (in 3-4 Bytes), und speichern Sie dann eine Liste von Delta-Werten zwischen Indizes von aufeinander folgenden Rezepten mit dem gegebenen Tag. Kodieren Sie die Delta-Werte mit einem Array von Bytes, so dass ein einzelner Delta-Wert je nach Bedarf zwischen 1 und 4 Byte verwenden kann.
Da die Anzahl der Rezepte in einem "Bucket" auf eine konstante Zahl beschränkt ist, ist das Abrufen mit diesem Ansatz immer noch O (1).
(Ich habe Embedded-Programmierung auf Mikros mit nur 256 Bytes RAM gemacht ... wenn Sie das tun, denken Sie über sehr kreative Möglichkeiten nach, um Bytes oder sogar Bits zu speichern. Ich bin mir sicher, dass es zu solchen Längen kommen wird nicht notwendig in Ihrer Bewerbung, aber ich dachte, das war eine interessante Idee.)
Ich würde einen Export von der Quellliste in eine andere machen mit Verweisen auf alle Elemente, die zu Ihnen passen. Dort treffen Sie eine zufällige Auswahl und nehmen ein Element aus der Quellenliste, entsprechend der Referenz. Wenn die Möglichkeit besteht, dass Sie die gleiche abgeleitete Liste erneut verwenden könnten, fügen Sie solche Listen in eine größere Liste ein. (Natürlich hängt der gewählte Algorithmus von den tatsächlichen Statistiken Ihrer Liste ab.)
Wenn Sie nur einen Parameter verwenden, können Sie Ihre Liste nach diesem Parameter sortieren und sich in einer anderen Liste B daran erinnern, wo die Elemente mit dem gleichen Parameterwert beginnen. Später könnte man einfach im Intervall (B [4]; b [5] -1) zufällig wählen. Dies würde die Geschwindigkeit einer zufälligen Auswahl gleich O (const) machen.
In diesem Fall würde ich mich persönlich für die SQlite Lösung entscheiden (da ich persönlich weiß, dass es dann besser ist) Andere). Ich sehe, dass Sie sich um einen Speicherplatz sorgen und nicht um die Geschwindigkeit, aber in Bezug auf die konstante Wiederherstellungszeit sorgen Sie sich auch um die Flexibilität des Datenzugriffs. Imo, in diesem Fall SQlite ist weit weg.
Entwerfen Sie Ihre kleine Datenbank so, wie Sie es möchten, und führen Sie Abfragen und Verknüpfungen auf die von Ihnen gewünschte Weise aus.
Dies ist alt, aber immer ein gültiges Beispiel, wie Sie können benutze es. Es gibt natürlich auch eine ORM-Lösung (zum Beispiel LINQ-Treiber), aber für mich persönlich scheint es eine Art Overhead zu sein.
Hoffe, das hilft.
Tags und Links algorithm c# data-structures