|
Mit Hilfe von expl3 will ich auf eine große Menge (ca. 5000) konstanter, gleich gearteter Objekte zugreifen, wobei jedes Objekt aus zwei Teildaten besteht. Man mag etwa an eine Menge Bücher denken, für die Buchtitel und ISBN erfasst sind, oder an Personen, von denen Name und Telefonnummer bekannt sind, oder Ähnliches. Die natürliche Implementierung einer solchen Struktur wäre ein Verbund (auch unter den englischen Bezeichnungen record oder struct bekannt). Da expl3 so etwas anscheinend nicht direkt unterstützt, ist mein bisheriger Zugang die Realisierung der Datenstruktur mit Hilfe von zwei Komma-separierten Listen (expl-Datentyp Die konkrete Anforderung ist, das Vorhandensein eines Werts in der ersten Liste zu überprüfen und im positiven Fall den entsprechenden Wert aus der zweiten Liste auszugeben. Im Beispiel heißt das, dass für einen gegebenen Buchtitel überprüft werden soll, ob er erfasst ist, und dann die zugehörige ISBN ausgegeben werden soll. Die Erstellung der Listen ist nicht das Problem, alle Daten liegen in der erforderlichen Form vor. Eine prinzipiell funktionsfähige Realisierung ist mir auch gelungen, doch ist diese sehr ineffizient, wenn der gesuchte Wert erst am Ende der Liste steht (die Kompilierung der entsprechenden Stelle dauert über 10 Sekunden). Das Hauptproblem dabei ist meines Erachtens, dass es zwar einen Befehl gibt, mit dem das Vorkommen eines Werts in einer Liste schnell überprüft werden kann ( \documentclass{article} \usepackage{xparse} \ExplSyntaxOn % geordnete Listen mit konstanten Werten: \clist_const:Nn \c_meinmodul_erste_liste_clist {ab, cd, ef, gh, ij, kl, mn, op, qr, st} \clist_const:Nn \c_meinmodul_zweite_liste_clist {101, 102, 103, 104, 105, 106, 107, 108, 109, 110} \cs_new:Npn \meinmodul_suche_zweiten_wert:n #1 { % überprüfe, ob der angegebene Wert in der ersten Liste steht: \clist_if_in:NnTF \c_meinmodul_erste_liste_clist {#1} { % lege eine Kopie der zweiten Liste an: \clist_set_eq:NN \l_tmpa_clist \c_meinmodul_zweite_liste_clist % durchlaufe die erste Liste, der momentane Wert ist ##1: \clist_map_inline:Nn \c_meinmodul_erste_liste_clist { % poppe den ersten Wert aus der Kopie der zweiten Liste und speichere ihn: \clist_pop:NN \l_tmpa_clist \l_tmpa_tl % überprüfe, ob der angegebene Wert der momentante Wert der ersten Liste ist: \tl_if_eq:nnT {#1} {##1} { % brich die Schleife ab und gib den zuletzt gepoppten Wert zurück: \clist_map_break:n {\l_tmpa_tl} } } } { Wert~fehlt } } \NewDocumentCommand \Wertsuche {m} { #1:~\meinmodul_suche_zweiten_wert:n {#1} } \ExplSyntaxOff \begin{document} \Wertsuche{ef} \Wertsuche{st} \Wertsuche{za} \end{document} |
|
Ich würde ja versuchen zu vermeiden, dass dauernd die Liste neu durchsucht werden musst. Wenn deine Werte wie in deinem Beispiel "einfach" sind, würde ich eher sowas machen (wenn dort auch TeX-Befehle auftauchen können, musst du sie halt mit tl_to_str:n vereinfachen): \documentclass{article} \usepackage{xparse} \ExplSyntaxOn % geordnete Listen mit konstanten Werten: \clist_const:Nn \c_meinmodul_erste_liste_clist {ab, cd, ef, gh, ij, kl, mn, op, qr, st} \clist_const:Nn \c_meinmodul_zweite_liste_clist {101, 102, 103, 104, 105, 106, 107, 108, 109, 110} \clist_set_eq:NN\l_tmpa_clist\c_meinmodul_erste_liste_clist \clist_set_eq:NN\l_tmpb_clist\c_meinmodul_zweite_liste_clist \clist_map_inline:Nn \l_tmpa_clist { \clist_pop:NN\l_tmpb_clist\l_tmpb_tl \tl_new:c {l_meinmodul_wert_#1_value_tl} \tl_set:cV{l_meinmodul_wert_#1_value_tl}{\l_tmpb_tl} %\tl_show:c {l_meinmodul_wert_#1_value_tl} } \NewDocumentCommand \Wertsuche {m} { #1:~\tl_if_exist:cTF {l_meinmodul_wert_#1_value_tl}{\tl_use:c{l_meinmodul_wert_#1_value_tl}}{gibt~es~nicht} } \ExplSyntaxOff \begin{document} \Wertsuche{ef} \Wertsuche{st} \Wertsuche{za} \end{document}
|
|
Der TeX-Interpreter hat intern Hash-Tables, die er für den Lookup von definierten Makros benutzt. Daher halte ich es für klug für jeden Eintrag in der Liste ein Makros zu definieren und beim holen des Werts zu prüfen, ob das Makro existiert. (Der ganze Spaß geht sogar ohne e-TeX-Extensions) Die Performance habe ich evaluiert, indem ich eine Liste angelegt habe in der Key=Value ist (zwar nutzlos, aber ein einfaches Beispiel). \documentclass{article} \usepackage{xparse} \ExplSyntaxOn \int_step_inline:nnnn { 1 } { 1 } { 5000 } { \cs_new:cpn { lookup_table_#1 } { #1 } } \NewDocumentCommand \Wertsuche {m} { #1:~ \cs_if_exist:cTF { lookup_table_#1 } { \use:c { lookup_table_#1 } } { kein~Wert } } \ExplSyntaxOff \begin{document} \Wertsuche{500} \end{document} Der LaTeX-Aufruf dauert $ time pdflatex test.tex real 0m0.321s user 0m0.300s sys 0m0.016s Dasselbe mit Clemens' Lösung: \documentclass{article} \usepackage{expl3,xparse} \ExplSyntaxOn \tl_new:N \l_meinmodul_tmpa_tl \prop_new:N \l_meinmodul_liste_prop \int_step_inline:nnnn { 1 } { 1 } { 5000 } { \prop_put:Nnn \l_meinmodul_liste_prop { #1 } { #1 } } \cs_new_protected:Npn \meinmodul_wertsuche:n #1 { \prop_get:NnNTF \l_meinmodul_liste_prop {#1} \l_meinmodul_tmpa_tl { \tl_use:N \l_meinmodul_tmpa_tl } {kein~ Wert} } \NewDocumentCommand \Wertsuche {m} { #1:~ \meinmodul_wertsuche:n {#1} } \ExplSyntaxOff \begin{document} \Wertsuche{500} \end{document} Hier dauert es $ time pdflatex test.tex real 0m5.964s user 0m5.920s sys 0m0.016s |
|
Mit Lua dürfte man auch 5000 Paaren noch ordentliche Performance erwarten. \documentclass{article} \directlua{ list = { ab = 101, cd = 102, ef = 103, gh = 104, ij = 105, kl = 106, mn = 107, op = 108, qr = 109, st = 110 } function get_value(key) value = list[key] if value == nil then tex.sprint("kein Wert") else tex.sprint(value) end end } \def\Wertsuche#1{% #1: \directlua{get_value("\luaescapestring{#1}")}% } \begin{document} \Wertsuche{ef} \par \Wertsuche{st} \par \Wertsuche{za} \end{document}
|
|
Ich glaube, dass Du hier so was wie eine property list suchst: \documentclass{article} \usepackage{expl3,xparse} \ExplSyntaxOn \tl_new:N \l_meinmodul_tmpa_tl \prop_new:N \l_meinmodul_liste_prop \prop_put:Nnn \l_meinmodul_liste_prop {ab} {101} \prop_put:Nnn \l_meinmodul_liste_prop {cd} {102} \prop_put:Nnn \l_meinmodul_liste_prop {ef} {103} \prop_put:Nnn \l_meinmodul_liste_prop {gh} {104} \prop_put:Nnn \l_meinmodul_liste_prop {ij} {105} \prop_put:Nnn \l_meinmodul_liste_prop {kl} {106} \prop_put:Nnn \l_meinmodul_liste_prop {mn} {107} \prop_put:Nnn \l_meinmodul_liste_prop {op} {108} \prop_put:Nnn \l_meinmodul_liste_prop {qr} {109} \prop_put:Nnn \l_meinmodul_liste_prop {st} {110} \cs_new_protected:Npn \meinmodul_wertsuche:n #1 { \prop_get:NnNTF \l_meinmodul_liste_prop {#1} \l_meinmodul_tmpa_tl { \tl_use:N \l_meinmodul_tmpa_tl } {kein~ Wert} } \NewDocumentCommand \Wertsuche {m} { #1:~ \meinmodul_wertsuche:n {#1} } \ExplSyntaxOff \begin{document} \Wertsuche{ef} \par \Wertsuche{st} \par \Wertsuche{za} \end{document} Wenn ich mich recht erinnere, dürftest Du bei 5000 Datenpaaren allerdings auch mit einer property list Performance-Probleme haben.
(07 Jun '16, 00:38)
cgnieder
Danke für den Vorschlag, die property list scheint grundsätzlich gut geeignet, um die Datenstruktur zu beschreiben, auch wenn es sich hier nicht um einen Verbund im eigentlichen Sinne handelt. Allerdings gibt es für den konkreten Anwendungsfall auch deutliche Nachteile: Das Anlegen der einzelnen Einträge ist aufwändiger als bei einer clist und die Performance nicht optimal.
(07 Jun '16, 22:51)
Cletus
@Cletus: Für das Anlegen hat @Clemens ja noch gar kein Benutzerinterface angegeben. Ein solches hängt schließlich von den Anforderungen daran an, die Du gar nicht formuliert hast. So könnte man beispielsweise die Daten einfach aus einer CSV-Datei lesen, eine Liste verarbeiten, einen Befehl zur Eingabe einzelner Wertepaare implementieren u. v. m. Du hast aber nur spezifiziert, wie auf die Daten zugegriffen wird und nicht, wie sie tatsächlich vorliegen.
(08 Jun '16, 07:36)
saputello
@Cletus was @saputello sagt :)
(08 Jun '16, 10:38)
cgnieder
|
Die lineare Suche, die du durchführst ist hier auch sehr ungeeignet.
Schon klar, aber wie könnte ich in diesem Fall eine binäre Suche implementieren?