String-Index rückwirkend bestimmen

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
DaveX
Beiträge: 13
Registriert: Fr Okt 31, 2014 2:33 pm
Wohnort: Stuttgart

Re: String-Index rückwirkend bestimmen

Beitrag von DaveX » Sa Nov 01, 2014 3:40 pm

Ja sehr gerne. Sobald ich mich in diesem Bereich noch tiefer eingearbeitet habe, liebend gerne. :) :) :)

nufan
Wiki-Moderator
Beiträge: 2557
Registriert: Sa Jul 05, 2008 3:21 pm

Re: String-Index rückwirkend bestimmen

Beitrag von nufan » Sa Nov 01, 2014 3:41 pm

DaveX hat geschrieben:Ja sehr gerne. Sobald ich mich in diesem Bereich noch tiefer eingearbeitet habe, liebend gerne. :) :) :)
Sehr schön :)
Wenn du soweit bist einfach kurz im Tutorials-Board absprechen.

DaveX
Beiträge: 13
Registriert: Fr Okt 31, 2014 2:33 pm
Wohnort: Stuttgart

Re: String-Index rückwirkend bestimmen

Beitrag von DaveX » Sa Nov 01, 2014 3:46 pm

Okay. :) Würde mich sehr freuen. Es ist eine tolle Sache, Wissen auch weiterzugeben. ;)
Ihr seid wirklich super!!! Dankeschön. Bis bald. ;)

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: String-Index rückwirkend bestimmen

Beitrag von Xin » Sa Nov 01, 2014 11:08 pm

DaveX hat geschrieben:Ja sehr gerne. Sobald ich mich in diesem Bereich noch tiefer eingearbeitet habe, liebend gerne. :) :) :)
*daumen hoch*

Vergiss es nicht gleich wieder, würde mich nämlich freuen, über OpenMP zu lesen. ;-)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

DaveX
Beiträge: 13
Registriert: Fr Okt 31, 2014 2:33 pm
Wohnort: Stuttgart

Re: String-Index rückwirkend bestimmen

Beitrag von DaveX » Mo Nov 03, 2014 4:02 pm

Hallo Xin, sorry das ich erst jetzt antworte. Habe erst eben gesehen, dass du auch geantwortet hast. Keine Sorge ;), ich vergesse es nicht. Ich will mich nur noch etwas tiefer in die Materie rein arbeiten, bevor ich soweit bin etwas darüber zu schreiben. :) Grüße DaveX :)

DaveX
Beiträge: 13
Registriert: Fr Okt 31, 2014 2:33 pm
Wohnort: Stuttgart

Re: String-Index rückwirkend bestimmen

Beitrag von DaveX » Mi Nov 05, 2014 8:16 pm

@dani93: Hallo :), ich hoffe es ist okay wenn ich hier noch folgenden Eintrag hinzufüge. Ich bräuchte wenn möglich nochmal kurz Hilfe.
Ich habe ein kleines Testprogramm geschrieben um deine Formel anzuwenden. Das Programm (dank deiner Formel) funktioniert soweit auch ganz gut. Nur tritt bei einer String-Länge von 12 Stellen ein seltsamer Fehler auf. Der Wert der in Index gespeichert und anschließend ausgegeben wird, stimmt nicht. So als wenn die Variable den Wert nicht speichern könnte. Aber die Index-Variable ist vom Typ uint64_t und sollte eigentlich in der Lage sein Werte bis einschließlich 18446744073709551615U zu speichern. Doch schon bei Werten, die deutlich drunter sind kommt es zu falschen Ergebnissen. Ich poste mal den Code.

Code: Alles auswählen

#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <math.h>
 
const char     Literals[] = "abcdefghijklmnopqrstuvwxyz";
const unsigned NLiterals  = sizeof( Literals) - 1;
 
int main()
{
    const char TestString[] = "caaaaaaaaaaa"; // Mit diesem String kommt es schon zu einem falschen Index
                                                                                // obwohl der Index deutlich unter 18446744073709551615U liegt!
    size_t     StrLgth      = strlen( TestString );
    int        pos[64]      = { 0 };                // Zum indexieren der Zeichen in Literals[]
    int        LitAsNum[17] = { 0 };                // Zur Speicherung der gemappten Zeichen in TestString[]
    uint64_t   Index        = 0U;                   // String-Index
    int        MinCount     = StrLgth;              // Zur Berechnung des String-Indexes
 
    for( unsigned i = 0; i < NLiterals; i++ )
        pos[( int )Literals[i]] = i;                // Zeichen in Literals[] indexieren
 
    for( unsigned i = 0; i < StrLgth; i++ )
        LitAsNum[i] = pos[( int )TestString[i]];    // Zeichen in TestString[] mappen und speichern
 
    /*
     * Hier wird nun der Index des Strings berechnet.
     */
    for( unsigned i = 0; i < StrLgth; i++ )
    {
        Index += pow( NLiterals, MinCount-1 ) * LitAsNum[i];
        MinCount--;
        if( MinCount == 0 )
            Index += 1;
    }
 
    /*
     * Hier werden alle Möglichkeiten mit weniger Stellen hinzu addiert.
     */
    for( unsigned i = 1; i < StrLgth; i++ )
        Index += pow( NLiterals, i );
 
    printf( "Index = %ju\n", Index );
 
    return 0;
}
Ansonsten stimmt das Ergebnis bis zu einer String-Länge von 11 grundsätzlich immer.
Woran könnte das liegen?

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: String-Index rückwirkend bestimmen

Beitrag von Xin » Do Nov 06, 2014 12:59 pm

Lass Dir mal das Ergebnis von pow ausgeben. Ich vermute, dass bricht bei i = 12 zusammen. Du bist bei pow() mit einer Double unterwegs, das sind 53 Bit Mantisse.

Versuch (anschließend) mal:

Code: Alles auswählen

Index += pow( static_cast<long double>( NLiterals ), static_cast<long double>( MinCount-1) ) * LitAsNum[i];
Damit solltest Du u.U. noch ein paar Bits bekommen können.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

DaveX
Beiträge: 13
Registriert: Fr Okt 31, 2014 2:33 pm
Wohnort: Stuttgart

Re: String-Index rückwirkend bestimmen

Beitrag von DaveX » Do Nov 06, 2014 6:12 pm

Vielen Dank für deine Antwort. Ich habe nun folgendes gemacht:

Code: Alles auswählen

uint64_t pow_u64( uint64_t base, uint64_t pow )
{
    if( pow ==  0 )
        return 1;

    if( pow < 0 )
        return 0;   // No negative power is an integer

    uint64_t result = 1;

    for( uint64_t i = 0; i < pow; i++ )
        result *= base;

    return result;
}
Das funktioniert soweit. Werde aber für mein Vorhaben womöglich das hier nutzen müssen: https://gmplib.org/.
Dankeschön. ;)

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: String-Index rückwirkend bestimmen

Beitrag von Xin » Fr Nov 07, 2014 11:11 am

DaveX hat geschrieben:Vielen Dank für deine Antwort. Ich habe nun folgendes gemacht:

Code: Alles auswählen

uint64_t pow_u64( uint64_t base, uint64_t pow )
{
...
    if( pow < 0 )
        return 0;   // No negative power is an integer
}
pow kann nicht negativ sein, da Du ein uint verlangst.

Da Deine 'base' fix ist, würde ich ebenfalls eine Tabelle vorschlagen, die Du einmalig berechnest - im Idealfall vor dem kompilieren und diese Funktion nur aufrufst, wenn Du die Beschränkungen Deiner Tabelle überschreitest.
DaveX hat geschrieben:Das funktioniert soweit. Werde aber für mein Vorhaben womöglich das hier nutzen müssen: https://gmplib.org/.
Dankeschön. ;)
Darf ich fragen, warum Du den Index im Dezimalsystem verwendest? Vielleicht bietet sich zum Beispiel das 26er-Zahlensystem verwendest und als Ziffern könntest Du dann die Buchstaben verwenden? Daraus würde sich eine vergleichsweise einfache Abbildung ergeben...
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

DaveX
Beiträge: 13
Registriert: Fr Okt 31, 2014 2:33 pm
Wohnort: Stuttgart

Re: String-Index rückwirkend bestimmen

Beitrag von DaveX » Fr Nov 07, 2014 8:12 pm

Xin hat geschrieben:Darf ich fragen, warum Du den Index im Dezimalsystem verwendest? Vielleicht bietet sich zum Beispiel das 26er-Zahlensystem verwendest und als Ziffern könntest Du dann die Buchstaben verwenden? Daraus würde sich eine vergleichsweise einfache Abbildung ergeben...
Könntest du mir ein kleines Beispiel zeigen, wie du das genau meinst? Habe es nicht ganz verstanden. Klingt aber Interessant. Mir fiel eben keine Alternative ein, wie ich das sonst machen sollte als den Index im Dezimalsystem anzuzeigen bzw. auszugeben.

Antworten