Effizientes Durchlaufen einer negativen Menge

Konrad Rudolph

Hallo,

ich habe eine Menge an Symbolen (konkret: Zeichen) in einer Menge M . Außerdem habe ich ein Alphabet Σ. Das Alphabet ist einfach als Bereich von 0 bis ValueSize<alphabet_t>::VALUE gegeben.

Ich muss jetzt über die Menge Σ\ M iterieren (konkret: Es handelt sich um eine negative Zeichenklasse und ich konstruiere ein Bitmuster für einen finiten Automaten, welcher einen regulären Ausdruck repräsentiert). Im Moment mache ich das einfach folgendermaßen (die Menge ist dabei als Vektor gegeben):

for (char_t c = 0; c <= ValueSize<char_t>::VALUE; ++c)
    if (std::find(M.begin(), M.end(), c) == M.end())
        // Ausgeben.

… ist natürlich nicht besonders effizient. Jetzt ist die Frage, ob die Verwendung von 'std::set_difference' schneller wäre (ich iteriere nur *einmal* über die Menge, allerdings mache ich das mit mehreren Mengen und das Alphabet bleibt dasselbe) und insbesondere, ob 'std::set_difference' eventuell für einige Datentypen spezialisiert ist (ich könnte mir z.B. vorstellen, dass es effizienter auf einem 'std::set' läuft, da die Werte hier sortiert sind).

Weiß da jemand mehr drüber? Die SGI-Doku schweigt sich aus.

Konrad Rudolph

Nachtrag: SGI hat natürlich doch etwas dazu zu sagen (man muss nur richtig schauen) … aber eventuell hat ja jemand konkrete Infos. Ich würde eigentlich sofort nach dieser Lösung greifen aber die Konstruktion eines Sets dauert ja auch seine Zeit ….

Gast++

Dein Alphabet hat doch eine konstante Länge, oder?

Wie wärs dann die Teilmengen gleich bei der Konstruktion auf

std::bitset<ValueSize<alphabet_t>::VALUE >

(n. Zeichen => Bit n-1)

abzubilden? Die Negationen sind dann jeweils die Differenzmengen.

Das müsste schneller als eine allgemine Sortierung sein.

Grüsse

*this

Konrad Rudolph

Hi,

Gast++ schrieb:

Dein Alphabet hat doch eine konstante Länge, oder?

Wie wärs dann die Teilmengen gleich bei der Konstruktion auf
std::bitset<ValueSize<alphabet_t>::VALUE >
(n. Zeichen => Bit n-1)

abzubilden? Die Negationen sind dann jeweils die Differenzmengen.

Das ist korrekt, aber inwiefern hilft das hier? Diese Bitsets müsste ich dann ja trotzdem in Mengen packen und eine Mengendifferenz bilden. Das dürfte nicht schneller laufen, als wenn ich die Differenz von den Char-Arrays bilde (es ist ja dasselbe, nur dass ich als Datentyp 'char_t' halt 'std::bitset' einsetzen würde). Oder habe ich Dich da falsch verstanden?

(Abgesehen davon nutzt mir die Repräsentation als 'bitset' nicht, da ich mit anderen Datenstrukturen arbeite.)

Gast++

Das Bitset repräsentiert die Auswahl aus der Gesamtmenge; und hat deshalb jeweils soviele Bit wie Sigma Zeichen hat.

1 bei Bit n-1 bedeutet "Zeichen n von Sigma" in Teilmenge v.h.
0 nicht v.h.

Grüsse

*this

Konrad Rudolph

Hi,

alles klar, der Tip ist gut. So werde ich es machen.

PS: Vielen Dank.