Как импортировать большое количество числовых данных

Question

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

Учитывая, что количество данных может варьироваться (не все файлы импорта имеют одинаковый размер), поэтому в одном файле может быть 100 чисел, в другом - 1 миллион чисел, и они в формате ASCII, я подумал, что прежде чем задавать размер массива для хранения данных, я должен знать сколько данных заполнит его.

Я не смогу заранее определить размер массива, если не знаю, сколько данных go попадет в этот массив. Таким образом, я мог прочитать данные из файла и, когда они читаются, использовать инструкцию reallo c для изменения размера массива каждый раз (однако при этом, как мне кажется, я теряю системные ресурсы, поскольку, если файл состоит из миллионов чисел, он вынужден изменить размер массива 1 миллион раз).

Или (но я думаю, что это было бы хорошо, если бы он был в двоичном формате), понять размер файла, узнать, какой разделитель между числа, а затем рассчитать, исходя из этого, размер массива.

Или еще раз, если файл, как я уже сказал, в формате ASCII, сначала прочитайте количество разделителей (например, они могут быть пробелами или запятые), и на основании этого понимают количество элементов и соответственно размер массива.

Я не знаю, какой метод будет лучшим.

Answer 1

Одна вещь, которую вы могли бы сделать, это не хранить данные в массиве, а в связанном списке , хранящем один фрагмент данных на узел списка. Таким образом, вы можете добавлять элементы в связанный список по своему усмотрению, без необходимости что-либо изменять. Однако это имеет следующие недостатки:

• Динамическое c выделение памяти происходит довольно медленно.
• Связанные списки не кэшируются, а также массивы, что отрицательно сказывается на производительности.
• Это не очень экономно. Например, в 64-битной системе указатели обычно имеют длину 8 байт. Таким образом, если каждый узел содержит 32-битный int в качестве данных, у вас будет 4 байта данных на узел и 8 байтов служебной информации от указателя (16 байтов, если связанный список является двусвязным). Это означает, что больше половины пространства тратится впустую. Кроме того, сам распределитель памяти, вероятно, имеет несколько байтов внутренних издержек для каждого выделения памяти, поэтому еще больше места теряется.

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

Однако это эффективное решение также является более сложным. Следовательно, если упомянутые выше недостатки приемлемы для вас, то простой связанный список, хранящий один фрагмент данных на узел списка, вероятно, будет самым простым и гибким решением.

Альтернативой может быть выделение одного массива. и при необходимости разверните его, используя realloc большими шагами в несколько килобайт (вместо одного раза для каждого нового элемента). Это будет значительно быстрее, чем вызывать realloc один раз для каждого нового элемента. Однако по сравнению с решением со связанным списком у него есть два следующих недостатка:

• Если недостаточно места для расширения массива, весь массив должен быть скопирован в новое место с большим количеством места , Даже если это внутренне обрабатывается realloc (поэтому вам не нужно программировать его самостоятельно), это может ухудшить производительность.
• Если память слишком фрагментирована , Распределитель может не найти нигде места для достаточно большого массива для хранения всех элементов.

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

Answer 2

Вот пример realloc динамического c подхода к изменению размера [как упомянул Бодо] из некоторого кода, который я лежал без дела. Обратите внимание, что ary_grow может быть установлен на то, что вы хотите.

// qwklib/ary.c -- quick dynamic array control

#include <string.h>
#include <stdlib.h>

typedef void (*aryinit_p)(void *);

typedef struct {
    void *ary_base;                     // base address
    int ary_siz;                        // size of elements

    int ary_cnt;                        // current count
    int ary_max;                        // maximum count

    int ary_grow;                       // amount to grow
    aryinit_p ary_init;                 // initialization
} ary_t;
typedef ary_t *ary_p;

// aryinit -- initialize the array
ary_p
aryinit(ary_p ary,int siz,int grow)
{

    memset(ary,0,sizeof(ary_t));

    ary->ary_siz = siz;
    ary->ary_grow = grow;

    return ary;
}

static inline void *
aryloc(ary_p ary,int idx)
{
    void *ptr;

    ptr = ary->ary_base;
    ptr += (ary->ary_siz * idx);

    return ptr;
}

// arypush -- add to dynamic array
void *
arypush(ary_p ary)
{
    aryinit_p init;
    int cnt;
    void *ptr;

    do {
        // got enough space already
        if (ary->ary_cnt < ary->ary_max)
            break;

        if (ary->ary_siz == 0)
            ary->ary_siz = 1;

        // get number of elements to grow by
        if (ary->ary_grow == 0)
            ary->ary_grow = 10;

        // add to allocated space
        ary->ary_max += ary->ary_grow;

        ptr = realloc(ary->ary_base,ary->ary_max * ary->ary_siz);
        ary->ary_base = ptr;

        ptr += ary->ary_cnt;
        cnt = ary->ary_max - ary->ary_cnt;
        memset(ptr,0,ary->ary_siz * cnt);

        init = ary->ary_init;
        if (init == NULL)
            break;

        for (;  cnt > 0;  --cnt, ptr += ary->ary_siz)
            init(ptr);
    } while (0);

    // get pointer to first available slot
    ptr = aryloc(ary,ary->ary_cnt);

    // advance count for next time
    ary->ary_cnt += 1;

    return ptr;
}

// arytrim -- trim allocated array size to in-use size
void
arytrim(ary_p ary)
{
    void *ptr;

    ary->ary_max = ary->ary_cnt;
    ptr = realloc(ary->ary_base,ary->ary_max * ary->ary_siz);
    ary->ary_base = ptr;
}

// aryclean -- free up storage
void
aryclean(ary_p ary)
{

    free(ary->ary_base);
}

Обратите внимание, что для полноты вы можете sh использовать size_t вместо int для некоторых переменных, если ваш массив индексы могут переполнять 32-битное число, а также добавлять правильную проверку ошибок для realloc