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 clist).

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 (\clist_if_in), jedoch keine einfache Möglichkeit, die Stelle des Vorkommens (natürliche Zahl) festzustellen.

Open in Online-Editor
\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}

gefragt 06 Jun '16, 23:06

Cletus's gravatar image

Cletus
1.6k45566
Akzeptiert-Rate: 75%

bearbeitet 06 Jun '16, 23:08

Die lineare Suche, die du durchführst ist hier auch sehr ungeeignet.

(07 Jun '16, 10:39) Henri

Schon klar, aber wie könnte ich in diesem Fall eine binäre Suche implementieren?

(07 Jun '16, 14:39) Cletus

Ich glaube, dass Du hier so was wie eine property list suchst:

Open in Online-Editor
\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}
Permanenter link

beantwortet 07 Jun '16, 00:29

cgnieder's gravatar image

cgnieder
22.1k243463
Akzeptiert-Rate: 60%

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

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).

Open in Online-Editor
\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

Open in Online-Editor
$ time pdflatex test.tex
real    0m0.321s
user    0m0.300s
sys     0m0.016s

Dasselbe mit Clemens' Lösung:

Open in Online-Editor
\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

Open in Online-Editor
$ time pdflatex test.tex
real    0m5.964s
user    0m5.920s
sys     0m0.016s
Permanenter link

beantwortet 07 Jun '16, 10:52

Henri's gravatar image

Henri
15.7k133943
Akzeptiert-Rate: 46%

bearbeitet 07 Jun '16, 11:07

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):

Open in Online-Editor
\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}

alt text

Permanenter link

beantwortet 07 Jun '16, 11:04

Ulrike%20Fischer's gravatar image

Ulrike Fischer
3.6k23
Akzeptiert-Rate: 52%

Mit Lua dürfte man auch 5000 Paaren noch ordentliche Performance erwarten.

Open in Online-Editor
\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}

alt text

Permanenter link

beantwortet 07 Jun '16, 10:16

Henri's gravatar image

Henri
15.7k133943
Akzeptiert-Rate: 46%

Deine Antwort
Vorschau umschalten

Folgen dieser Frage

Per E-Mail:

Wenn sie sich anmelden, kommen Sie für alle Updates hier in Frage

Per RSS:

Antworten

Antworten und Kommentare

Markdown-Grundlagen

  • *kursiv* oder _kursiv_
  • **Fett** oder __Fett__
  • Link:[Text](http://url.com/ "Titel")
  • Bild?![alt Text](/path/img.jpg "Titel")
  • nummerierte Liste: 1. Foo 2. Bar
  • zum Hinzufügen ein Zeilenumbruchs fügen Sie einfach zwei Leerzeichen an die Stelle an der die neue Linie sein soll.
  • grundlegende HTML-Tags werden ebenfalls unterstützt

Frage-Themen:

×13
×2
×1

gestellte Frage: 06 Jun '16, 23:06

Frage wurde gesehen: 8,275 Mal

zuletzt geändert: 08 Jun '16, 10:38