Каков наиболее эффективный способ хранения серии значений с неизвестным размером? - PullRequest
Новая
       29

Каков наиболее эффективный способ хранения серии значений с неизвестным размером?

1 голос
/ 01 марта 2011

У меня есть функция (скажем, с именем next_entity), которая генерирует значения size_t.Функция действует как генератор, то есть она выдает новое значение при каждом вызове и, наконец, возвращает 0 в качестве часового.

В другой функции, которая вызывает next_entity, мне нужно сохранитьзначения где-то.Я не знаю количество значений до того, как я получу дозорного, поэтому я не могу malloc или статически выделить массив для хранения этих значений до того, как они поступят.

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

После этого значения больше не нужны.

Я пытался использовать GHashTable из glib.h во время итерации, чтобы сохранить значения в качестве ключей, но проблема с GHashTable заключается в том, что указатели на ключи, передаваемые в функцию g_hash_table_insert, должны оставатьсяживой в течение жизненного цикла хеш-таблицы, поэтому для каждого нового значения мне нужно сделать что-то вроде malloc(sizeof(size_t)).

Это работает, но кажется неэффективным, поскольку malloc отнимает много времени,

Есть ли лучший способ сделать это?

Я могу опубликовать реальный код, если он необходим, но я не думаю, что проблема в коде.

Любая помощь будет оценена, спасибо заранее!

Ответы [ 4 ]

2 голосов
/ 01 марта 2011

Другие предложили realloc. Вместо этого рассмотрите возможность использования связанного списка неправильно расположенных блоков, где каждый блок содержит большой массив чисел; когда вы заполняете блок, выделяете другой и связываете предыдущий с ним ... или связываете его с предыдущим, а затем переворачиваете список перед выводом. Дело в том, что вам не нужно хранить ваши значения в непрерывной памяти, поэтому вам не нужно использовать realloc. realloc копирует предыдущий массив, который вы можете избежать и который будет медленным для очень больших массивов, и он может даже исчерпать память, если не сможет найти достаточно большой непрерывный блок, тогда как выделение отдельных блоков более устойчиво. Недостатком является то, что для управления связанным списком требуется больше работы.

==== Изменить для использования GHashTable:

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

2 голосов
/ 01 марта 2011

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

Например, в C ++ многие реализации std::vector обычно делают именно это.

1 голос
/ 01 марта 2011

Ключами в хеш-таблице являются void *, а void * всегда по меньшей мере равен size_t.

Все, что вам нужно сделать, это вместо malloc (sizeof (size_t)) использовать g_hash_table_new (NULL, NULL), чтобы использовать g_direct_hash в качестве метода хеширования. Затем сделайте это: 

g_hash_table_replace(table, GSIZE_TO_POINTER(value), GSIZE_TO_POINTER(value))

Чтобы перебрать ключи, используйте GPOINTER_TO_SIZE, чтобы вернуться к size_t.

Вы всегда можете сделать это для любого целочисленного типа вместо malloc'ing. (используйте GINT_TO_POINTER, GUINT_TO_POINTER вместо GSIZE_TO_POINTER при необходимости)

1 голос
/ 01 марта 2011

Обычный способ - умножить пространство, используемое на константу (2, 1,69, 1,618, 1,5, ...).

Мне нравится золотое сечение:) 

arr = malloc(elems * sizeof *arr);
{
    /* ... */
    elems = elems * 13 / 8; /* approximate golden ratio */
    tmparr = realloc(arr, elems * sizeof *arr);
    if (tmparr == NULL) /* deal with error */;
    arr = tmparr;
    /* ... */
}
free(arr);
...