Табуляцией транспонировать таблицу в C


Я посмотрел в интернете для транспонирования программы, но обнаружили, что они имеют экстремальное использование памяти для больших таблиц. Использование оперативной памяти настолько сильным, что я не могу выполнить большинство работ на моем ноутбуке. У меня тоже есть Перл программе, это использует меньше памяти, чем онлайн-инструменты, но в памяти остается крайним (~50 ГБ на 8 ГБ файл) или очень медленно (от нескольких дней до запуска, это занимает несколько секунд, в зависимости от размера входных данных).

Я написал программу в GNU99 C, которая работает так:

./2tranpose -i in.tsv -o out.tsv

и исходный код для 2transpose.С выглядит следующим образом:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define GNU_SOURCE

void help () {
    puts("This program is run thus:");
    puts("./transpose -i infile -o outfile");
}

int main(int argc, char * argv[]) {
    unsigned short int infile = 0, outfile = 0;
//I didn't like getopt's version of reading files, this is my own design
    for (unsigned short int loop = 1; loop < argc; loop++) {
        if (strcmp(argv[loop], "-i") == 0) {
            if (loop == (argc-1)) {//prevents segfault on argv
                printf("the '%s' option requires something to come after it.\n", argv[loop]);
                printf("Failed at %s line %u\n", __FILE__, __LINE__);
                exit(EXIT_FAILURE);
            }
            infile = loop+1;
            loop++;
        } else if (strcmp(argv[loop], "-o") == 0) {
            if (loop == (argc-1)) {//prevents segfault on argv
                printf("the '%s' option requires something to come after it.\n", argv[loop]);
                printf("Failed at %s line %u\n", __FILE__, __LINE__);
                exit(EXIT_FAILURE);
            }
            outfile = loop+1;
            loop++;
        } else {
            printf("%s isn't a recognized option.\n", argv[loop]);
            exit(EXIT_FAILURE);
        }
    }

    if (infile == 0) {
        puts("infile not defined.");
        help();
        exit(EXIT_FAILURE);
    }
    if (outfile == 0) {
        puts("outfile not defined.");
        help();
        exit(EXIT_FAILURE);
    }

    FILE *restrict fh = fopen(argv[infile], "r");
    if (fh == NULL) {
        printf("failed to read %s\n", argv[infile]);
        perror("");
        exit(EXIT_FAILURE);
    }

    unsigned int nrow = 0, ncol = 0;
    char *line = NULL;
    size_t len = 0;
    ssize_t read = 0;

    size_t ALL_DATA_size = sizeof(char);
    char ***restrict ALL_DATA = malloc(sizeof(char));

    while ((read = getline ( &line, &len, fh)) != -1) {
        char *restrict tmp_string = NULL;
        char * tmp_pointer = NULL;
        tmp_string = strtok_r(line, "\t ", &tmp_pointer);
        size_t this_row_size = sizeof(char) * strlen(tmp_string) + sizeof(char*);
        ALL_DATA_size += this_row_size;
        ALL_DATA       = realloc(ALL_DATA, ALL_DATA_size);
        if (ALL_DATA == NULL) {
            printf("ALL_DATA failed realloc at %s line %u at %s line %u\n", __FILE__, __LINE__, argv[infile], nrow+1);
            perror("");
            exit(EXIT_FAILURE);
        }
        ALL_DATA[nrow] = malloc(this_row_size);
        if (ALL_DATA[nrow] == NULL) {
            printf("ALL_DATA[%u] failed realloc at %s line %u at %s line %u\n", nrow, __FILE__, __LINE__, argv[infile], nrow+1);
            perror("");
            exit(EXIT_FAILURE);
        }
        ALL_DATA[nrow][0] = malloc(this_row_size);
        if (ALL_DATA[nrow][0] == NULL) {
            printf("failed to realloc ALL_DATA[%u][0] @ %s line %u\n", nrow, __FILE__, __LINE__);
            perror("");
            exit(EXIT_FAILURE);
        }
        strcpy(ALL_DATA[nrow][0], tmp_string);
        ncol = 1;
        while (tmp_string != NULL) {
            tmp_string = strtok_r(NULL, "\t ", &tmp_pointer);
            if (tmp_string == NULL) {
                break;
            }
            const unsigned int STR_LENGTH = sizeof(char)*strlen(tmp_string) + sizeof(char*);
            this_row_size += STR_LENGTH ;
            ALL_DATA_size += STR_LENGTH ;

            ALL_DATA = realloc(ALL_DATA, ALL_DATA_size);
            if (ALL_DATA == NULL) {
                printf("failed to realloc ALL_DATA for row %u @ %s line %u w/ string %s with length %u\n", nrow, __FILE__, __LINE__, tmp_string, STR_LENGTH);
                perror("");
                exit(EXIT_FAILURE);
            }
            ALL_DATA[nrow] = realloc(ALL_DATA[nrow], this_row_size);
            if (ALL_DATA[nrow] == NULL) {
                printf("failed to realloc ALL_DATA[%u] @ %s line %u\n", nrow,__FILE__, __LINE__);
                perror("");
                exit(EXIT_FAILURE);
            }
            ALL_DATA[nrow][ncol] = malloc(STR_LENGTH);
            if (ALL_DATA[nrow][ncol] == NULL) {
                printf("failed to realloc ALL_DATA[%u][%u] @ %s line %u\n", nrow, ncol, __FILE__, __LINE__);
                perror("");
                exit(EXIT_FAILURE);
            }
            strcpy(ALL_DATA[nrow][ncol], tmp_string);
            ncol++;
        }
        const unsigned int LENGTH = strlen(ALL_DATA[nrow][ncol-1]);
        if (ALL_DATA[nrow][ncol-1][LENGTH-1] == '\n') {
            ALL_DATA[nrow][ncol-1][LENGTH-1] = '\0';
        }
        nrow++;
    }
    fclose(fh);
    free(line); line = NULL;

    FILE *restrict out = fopen(argv[outfile], "w");

    if (out == NULL) {
        printf("failed to write %s\n", argv[outfile]);
        perror("");
        exit(EXIT_FAILURE);
    }

    for (unsigned int row = 0; row < ncol; row++) {
        fprintf(out, "%s", ALL_DATA[0][row]);
        for (unsigned int col = 1; col < nrow; col++) {
            fprintf(out, "\t%s", ALL_DATA[col][row]);
        }
        fprintf(out, "\n");
    }
    fclose(out);
    for (unsigned int row = 0; row < nrow; row++) {
        for (unsigned int col = 0; col < ncol; col++) {
            free(ALL_DATA[row][col]); ALL_DATA[row][col] = NULL;
        }
        free(ALL_DATA[row]); ALL_DATA[row] = NULL;
    }

    free(ALL_DATA); ALL_DATA = NULL;
    return 0;
}

насколько я могу судить, эта программа работает, но я хотел бы продолжать использовать ОЗУ как минимум (что и было целью программы).

В целом, программа не сложная, она сохраняет струн в массивных 2Д массив, а затем переключается строк со столбцами. Но, дьявол кроется в деталях.

Это хороший стиль кодирования в C? возможно, этот процесс можно сделать более эффективным?



149
5
задан 28 марта 2018 в 01:03 Источник Поделиться
Комментарии
2 ответа

при компиляции, всегда включить предупреждения, а затем исправить эти предупреждения. ( для НКУ, как минимум использовать: -стены -Wextra -Wconversion -педантичным -с std=gnu11 ) написал код заставляет компилятор выдавать несколько предупреждений.

для облегчения читаемости и понимания:


  1. следите за аксиому: только один оператор на строке и (в большинстве) одной переменной в заявлении.

  2. отдельных блоков кода: ( for if else while do...while switch case default ) через одну пустую строку.

  3. Есть несколько причин, чтобы использовать все шапки в целом все крышечки
    рассмотрела орать. Однако, типичное использование макроса с именами и
    с элементами enum заявление.

===============

Функции: strlen() возвращает size_t (который, в зависимости от реализации будет либо unsigned long int или unsigned int
так вот эту строку:

const unsigned int LENGTH = strlen(ALL_DATA[nrow][ncol-1]);

лучше бы написал как:

size_t length = strlen(ALL_DATA[nrow][ncol-1]);

=============

этот код:

if (ALL_DATA[nrow][ncol-1][LENGTH-1] == '\n') {
ALL_DATA[nrow][ncol-1][LENGTH-1] = '\0';
}

очень 'ненадежный'

предлагаю использовать более подходящее логики, например:

char * newline;
EDIT: //if( strchr( ALL_DATA[nrow][ncol-1], '\n' ) )
if( (newline = strchr( ALL_DATA[nrow][ncol-1], '\n' ) ) != NULL )
{
*newline = '\0';
}

Примечание: одна из функций string.h можете проделать ту же операцию в одном заявлении.

===========

в отношении:

ALL_DATA[nrow][ncol] = malloc(STR_LENGTH);
if (ALL_DATA[nrow][ncol] == NULL) {
printf("failed to realloc ALL_DATA[%u][%u] @ %s line %u\n", nrow, ncol, __FILE__, __LINE__);
perror("");
exit(EXIT_FAILURE);

значение errno изменен вызов printf()
И все сообщения об ошибках должны быть выведены на stderrне stdout так это заявление:

printf("failed to realloc ALL_DATA[%u][%u] @ %s line %u\n", nrow, ncol, __FILE__, __LINE__);

должно быть:

fprintf( stderr, "failed to realloc ALL_DATA[%u][%u] @ %s line %u\n", nrow, ncol, __FILE__, __LINE__);

И призыв к malloc() не realloc ALL_DATA скорее это попытка выделить еще одну строку, в 2 мерный массив ALL_DATA[][]

=============

При звонке realloc()всегда назначать возвращаемое значение temp переменной, проверьте temp переменная заверить это не нуль, and only then assign to the target variable. Otherwise, when the function:realloc()` не выполняется, что и исходный указатель будет потеряно, что привело к утечке памяти

=================

Это выражение:

sizeof(char)

определяется в стандарте как 1. Все умножения на 1 не имеет никакого эффекта.

Использование этого выражения: в:

const unsigned int STR_LENGTH = sizeof(char)*strlen(tmp_string) + sizeof(char*);

просто загромождает код, делая его более сложным для понимания, отладки и т. д.

4
ответ дан 28 марта 2018 в 03:03 Источник Поделиться

Вот некоторые вещи, которые могут помочь вам улучшить ваш код.

Понять функцию тестирования макросов

Функция тестирования макросы используются для обеспечения контроля программиста над определениями в системных заголовочных файлов. Как на man-страницах feature_test_macros говорит:


Примечание: Для того, чтобы быть эффективными, макрос тестирования свойств должны быть определены перед всеми остальными заголовочными файлами.

Это означает, что ваш #define GNU_SOURCE должен прийти прежде в #includes, чтобы быть эффективными. Также, на моем компьютере, это не правильное название, во всяком случае. На man-страницах getline говорит:


getline(), getdelim():
Since glibc 2.10:
_POSIX_C_SOURCE >= 200809L
Before glibc 2.10:
_GNU_SOURCE

Разбить программу на более мелкие процедуры

В текущий код, все делается в main. Что делает код труднее понять и поддержать. Вместо этого, сломать код в управляемые логические функции. Например, аргументом командной строки интерпретации infile и outfile почти идентичен. Вместо этого, я бы рекомендовал называть функцию, которая возвращает const char * который является имя файла. (Впрочем, я бы, наверное, просто использовать infile = argv[1] и outfile = argv[2] устраняя все, что нужно для разбора командной строки.) Первый переписать ваш код выглядит теперь выглядит так:

int main(int argc, char * argv[]) {
if (argc != 3) {
help();
return 1;
}
unsigned rows;
unsigned cols;
char ***ALL_DATA = readCSV(argv[1], &rows, &cols);
writeCSV(argv[2], ALL_DATA, rows, cols);
}

Не утечка памяти

Этой программе утечки памяти, потому что не каждый вызов malloc верно подобранная к вызову free. Это должно быть исправлено.

Понимаю стандарт C

В C стандарт, sizeof(char) определяется как 1. Всегда. Так что sizeof(char) разбросанных по всему ваш код только делает код труднее читать.

Лучше использовать имена переменных

Имена row и col хороши тем, что они являются описательными намерения, но такие имена, как fh и ALL_DATA нет. Кроме того, традиционно, имя буквами, например ALL_DATA будет означать макрос определение. Я бы рекомендовал выбирать последовательную схему именования и использовать его.

Понять restrict сайта

Есть небольшой пункт с использованием restrict в большинстве мест это в настоящее время используется. Понимаю, что это предназначается, чтобы быть компилятор оптимизации подсказку, но что он также возлагает ответственность на вас, программиста, чтобы гарантировать, что нет никаких алиасов для указателей, которые будут нарушать смысл restrict.

Использовать именованные константы

Похоронены глубоко внутри кода является тот факт, что разделители на самом деле и Tab и Пробел. Я сделаю, что гораздо более очевидным путем создания именованных констант, как это:

static const char *delimiters = "\t ";

Корректно обрабатывать входные данные

Одна проблема с использованием strtok_r в этом контексте заключается в том, что, как сказано в MAN-странице,


последовательность из двух или более непрерывных байты-разделители в анализируемой строке считается одним разделителем

Это означает, что если есть какие-либо пустые поля во входном файле, то программа скорее всего приведет к краху, потому что он попытается разыменовать в unitialized памяти. Можно использовать BSD-стиля, нестандартные рутины strsep или написать свой собственный эквивалент.

Рассмотрим другой алгоритм

Нынешняя программа хранит всю парсится файл в память сразу, так что чем больше файл, тем больше использовать памяти. Альтернатива, вдохновленный еще в те времена, когда данные хранились на 9-дорожечных лент и 32К памяти был "большой" - это компромисс между использованием памяти для скорости ввода-вывода. Поэтому вместо того, чтобы читать файл один раз, а затем писать все, старый метод школы будет для обработки входных данных несколько раз; каждый раз выбирать только области интереса. Кроме того, создать один выходной файл для каждого столбца, добавление данных для каждого, как вы идете, а затем объединить все файлы вместе в конце.

2
ответ дан 30 марта 2018 в 05:03 Источник Поделиться