Ich arbeite mit einer spärlichen Matrix und bekomme eine Textdatei wie diese:

0 3 1.2
2 5 3.2
3 0 2.1
3 5 4.2
4 5 2.2
0 0 5.2

Grundsätzlich funktioniert es so, dass die Zahl 1.2 an der Position [0] [3] steht und die Elemente der Matriz, die nicht erwähnt werden, bei 0 bleiben. In diesem Fall sollte es also so aussehen:

5.2 0 0 1.2 0 0
0 0 0 0 0 0
0 0 0 0 0 3.2
2.1 0 0 0 0 4.2
0 0 0 0 0 2.2
-1
MuchoG 19 Apr. 2018 im 00:38

5 Antworten

Beste Antwort

OP schrieb dies in den Kommentaren:

Es tut mir so leid, aber mein Lehrer hat gerade alles geklärt ... es stellt sich heraus, dass für jede Zeile die erste Zahl die Zeile, die zweite die Spalte und die dritte das Element ist. Mit dem obigen Beispiel {{X0} } muss in die Position [0][3] gehen. Die Matrix muss nicht quadratisch sein.

Das macht alles anders. Wenn Sie die Dimensionen der Matrix nicht kennen, müssen Sie zuerst alles lesen, dann die Matrixdimensionen berechnen, Platz für die Matrix zuweisen und sie dann mit den Werten füllen.

Ich würde das tun:

#include <stdio.h>
#include <stdlib.h>

#define BLOCK 1024

struct matrix_info {
    int col;
    int row;
    double val;
};

void free_matrix(double **matrix, size_t rows)
{
    if(matrix == NULL)
        return;

    for(size_t i = 0; i < rows; ++i)
        free(matrix[i]);
    free(matrix);
}

double **readmatrix(const char *fname, size_t *rows, size_t *cols)
{
    if(fname == NULL || rows == NULL || cols == NULL)
        return NULL;

    double **matrix = NULL;
    struct matrix_info *info = NULL;
    size_t mi_idx = 0; // matrix info index
    size_t mi_size = 0;

    FILE *fp = fopen(fname, "r");
    if(fp == NULL)
    {
        fprintf(stderr, "Cannot open %s\n", fname);
        return NULL;
    }

    *rows = 0;
    *cols = 0;

    for(;;)
    {
        if(mi_idx >= mi_size)
        {
            struct matrix_info *tmp = realloc(info, (mi_size + BLOCK) * sizeof *info);
            if(tmp == NULL)
            {
                fprintf(stderr, "not enough memory\n");
                free(info);
                fclose(fp);
                return NULL;
            }

            info = tmp;
            mi_size += BLOCK;
        }

        int ret = fscanf(fp, "%d %d %lf", &info[mi_idx].row, &info[mi_idx].col,
                    &info[mi_idx].val);

        if(ret == EOF)
            break; // end of file reached

        if(ret != 3)
        {
            fprintf(stderr, "Error parsing matrix\n");
            free(info);
            fclose(fp);
            return NULL;
        }

        if(*rows < info[mi_idx].row)
            *rows = info[mi_idx].row;

        if(*cols < info[mi_idx].col)
            *cols = info[mi_idx].col;

        mi_idx++;
    }

    fclose(fp);

    // mi_idx is now the length of info
    // *cols and *rows have the largest index
    // for the matrix, hence the dimension is (rows + 1) x (cols + 1)
    (*cols)++;
    (*rows)++;

    // allocating memory

    matrix = calloc(*rows, sizeof *matrix);
    if(matrix == NULL)
    {
        fprintf(stderr, "Not enough memory\n");
        free(info);
        return NULL;
    }

    for(size_t i = 0; i < *rows; ++i)
    {
        matrix[i] = calloc(*cols, sizeof **matrix);
        if(matrix[i] == NULL)
        {
            fprintf(stderr, "Not enough memory\n");
            free(info);
            free_matrix(matrix, *rows);
            return NULL;
        }
    }

    // populating matrix

    for(size_t i = 0; i < mi_idx; ++i)
    {
        int r,c;
        r = info[i].row;
        c = info[i].col;
        matrix[r][c] = info[i].val;
    }

    free(info);
    return matrix;
}

int main(void)
{
    const char *fn = "/tmp/matrix.txt";

    size_t rows, cols;

    double **matrix = readmatrix(fn, &rows, &cols);

    if(matrix == NULL)
        return 1;

    for(size_t i = 0; i < rows; ++i)
    {
        for(size_t j = 0; j < cols; ++j)
            printf("%0.3f ", matrix[i][j]);

        puts("");
    }

    free_matrix(matrix, rows);
    return 0;
}

Die Ausgabe ist (für eine Datei mit Ihren Beispieldaten)

5.200 0.000 0.000 1.200 0.000 0.000 
0.000 0.000 0.000 0.000 0.000 0.000 
0.000 0.000 0.000 0.000 0.000 3.200 
2.100 0.000 0.000 0.000 0.000 4.200 
0.000 0.000 0.000 0.000 0.000 2.200

Also eine kurze Erklärung, was ich tue:

Ich lese die Datei und speichere die Informationen in einem dynamisch zugewiesenen Array über die Spalte, die Zeile und den Wert. Diese Informationen werden in der gespeichert struct matrix_info *info.

Die Idee ist, dass ich jede Zeile lese und die drei Werte extrahiere. Während ich die Datei lese, speichere ich auch den größten Index für die Spalte und die Zeile

    ...

    if(*rows < info[mi_idx].row)
        *rows = info[mi_idx].row;

    if(*cols < info[mi_idx].col)
        *cols = info[mi_idx].col;

    ...

Wenn die Datei gelesen wird, kenne ich die Abmessungen der Matrix. Nun alle Werte mit ihrer Zeile und Spalte werden im info Array gespeichert, der nächste Schritt ist also Ordnen Sie Speicher für die Matrix zu und füllen Sie die Werte basierend auf info[i] Einträge.

for(size_t i = 0; i < mi_idx; ++i)
{
    int r,c;
    r = info[i].row;
    c = info[i].col;
    matrix[r][c] = info[i].val;
}

Am Ende gebe ich den Speicher für info frei und gebe die Matrix zurück.

Ein weiterer interessanter Teil ist folgender:

    if(mi_idx >= mi_size)
    {
        struct matrix_info *tmp = realloc(info, (mi_size + BLOCK) * sizeof *info);
        if(tmp == NULL)
        {
            fprintf(stderr, "not enough memory\n");
            free(info);
            fclose(fp);
            return NULL;
        }

        info = tmp;
        mi_size += BLOCK;
    }

Weil Sie erwähnt haben, dass das einzige, was Sie über die Matrix wissen, ist, dass es kann bis zu 10000 Elemente enthalten, dann kann die Eingabedatei sehr groß sein. Anstatt Speicher für die info Elemente in jeder Schleife neu zuzuweisen, ordne ich zu Blöcke von 1024 (BLOCK) info Elementen gleichzeitig. Sobald also ein Block voll ist, Der nächste Block wird zugewiesen und so weiter. Also rufe ich realloc nur alle 1024 an Iterationen.

3
Pablo 18 Apr. 2018 im 22:46

Sie müssen zuerst verwenden:

float* sparseMatrix = malloc(sizeof(float) * 10000); 

Sie beginnen mit dem Lesen der Datei und nach dem Lesen der ersten Zeile kennen Sie die Anzahl der Spalten und die Anzahl der Zeilen die Anzahl der gelesenen Zeilen. Danach können Sie die Matrix reduzieren, wenn Sie möchten.

free(sparseMatrix );
sparseMatrix = malloc(sizeof(float) * nbRow*nbColum); 
2
Alban Santolaria 18 Apr. 2018 im 22:06

Sie haben einfach nicht genug Informationen, um eine geeignete Matrix zu erstellen. In Ihrem zitierten Fall wissen Sie, dass Sie MINDESTENS 5 Zeilen und MINDESTENS 6 Spalten haben, aber Sie wissen nicht genau, wie viele Zeilen m und Spalten vorhanden sind n befinden sich in Ihrer Matrix. Also für Ihre gegebene Eingabe:

0 3 1.2
2 5 3.2
3 0 2.1
3 5 4.2
4 5 2.2
0 0 5.2

Sie könnten eine 5x6-Matrix haben als:

5.2  0.0  0.0  1.2  0.0  0.0
0.0  0.0  0.0  0.0  0.0  0.0
0.0  0.0  0.0  0.0  0.0  3.2
2.1  0.0  0.0  0.0  0.0  4.2
0.0  0.0  0.0  0.0  0.0  2.2

Oder Sie könnten eine 10x6-Matrix haben als:

5.2  0.0  0.0  1.2  0.0  0.0
0.0  0.0  0.0  0.0  0.0  0.0
0.0  0.0  0.0  0.0  0.0  3.2
2.1  0.0  0.0  0.0  0.0  4.2
0.0  0.0  0.0  0.0  0.0  2.2
0.0  0.0  0.0  0.0  0.0  0.0
0.0  0.0  0.0  0.0  0.0  0.0
0.0  0.0  0.0  0.0  0.0  0.0
0.0  0.0  0.0  0.0  0.0  0.0
0.0  0.0  0.0  0.0  0.0  0.0

Diese Mehrdeutigkeit ist ein Problem, da sich die erste Matrix stark von der zweiten unterscheidet.

Außerdem geht es bei einer spärlichen Matrix darum, den Speicher und / oder die Verarbeitungszeit effizient zu gestalten. Wenn Sie ein vollständiges Array von m Zeilen und n Spalten zuweisen, haben Sie stattdessen eine dichte Matrix -Darstellung.

1
MFisherKDX 18 Apr. 2018 im 22:41

Es gibt keine wirkliche Möglichkeit zu wissen, was in einer Datei enthalten ist, wenn Sie die Datei nicht zuerst selbst vollständig gelesen haben.

Da Sie wissen, dass es maximal 10.000 Elemente gibt, können Sie statisch zuerst ein Array dieser Größe zuweisen und dann die Zahlen in das laden, bis Sie einen EOF analysieren.

float sparseMatrix[10000];

Dies bedeutet lediglich, dass Ihr Programm immer den Speicherplatz für 10.000 Elemente zuweist, unabhängig davon, wie viele Elemente sich tatsächlich im Array befinden. Wenn Sie davon ausgehen, dass jedes Element 4 Byte belegt, verwenden Sie nur ~ 40 KB Speicher. Dies ist wahrscheinlich die einfachste Lösung.

Die andere Möglichkeit wäre, die Datei vollständig zu lesen, die erforderliche Größe herauszufinden und diese Größe dynamisch zuzuweisen und dann die gesamte Datei erneut zu lesen, während die Elemente ausgefüllt werden.

// Assume numberOfElements was determined by reading through the file first
float* sparseMatrix = malloc(sizeof(float) * numberOfElements); 

Obwohl diese Methode weniger Speicher benötigt, sind zwei vollständige Lesevorgänge der Datei + der Aufwand für den Aufruf von malloc erforderlich.

0
ReckoningReckoner 18 Apr. 2018 im 21:55

Sie können die Anzahl der Zeilen und Spalten messen und dann Ihr 2D-Array definieren. Dies erhöht natürlich die zeitliche Komplexität! Wenn Sie sich nicht für die Größe des Speichers interessieren, können Sie Ihr Array mit den maximalen Spalten und Zeilen definieren! Sie sollten also zwischen großer Zeitkomplexität und großer Speichergröße wählen.

0
marc_s 22 Apr. 2018 im 08:47