Массивы переменной длины в Си

← →
Галинка © (2007-09-18 14:27) [0]

У Кернигана и Ричи прочитала, что если объявлять квази-двумерный массив, как одномерный массив указателей заданного типа, то под каждым указателем можно хранить векторы разной длинны.

Все логично. Хочу попробовать прочитать числа из файла в массив. Количество чисел в каждой строке разное. Т.е. условие как бы соблюдается.

Внимание, вопрос: нужно ли (с моей точки зрения несомненно) постоянно перевыделять память под текущий указатель, перед созранением в текущий вектор нового значения?

← →
umbra © (2007-09-18 14:32) [1]

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

← →
Игорь Шевченко © (2007-09-18 14:32) [2]

может тебе форум по С поискать ?

← →
Rouse_ © (2007-09-18 14:57) [3]

> может тебе форум по С поискать ?

array of PDWORD уже относится к Си? :)

> нужно ли (с моей точки зрения несомненно) постоянно перевыделять
> память под текущий указатель

Можно по аналогу TList выделять память сразу с запасом...

← →
celades © (2007-09-18 14:58) [4]

> нужно ли (с моей точки зрения несомненно) постоянно перевыделять
> память под текущий указатель

да. используя realloc например

← →
tesseract © (2007-09-18 15:06) [5]

> да. используя realloc например

Это школничество память перераспределять постоянно. Обычно хапаеться с избытком, при превышении лимита выделяеться ещё блок. Как например в Tlist.

← →
Галинка © (2007-09-18 17:21) [6]

т.е. никто "не экономит на спичках"?

← →
tesseract © (2007-09-18 17:35) [7]

> т.е. никто "не экономит на спичках"?

Выделение памяти - очень медленный процесс. Поэтому так и поступают.

← →
sdubaruhnul (2007-09-18 18:06) [8]

Постоянный realloc гадит память и постепенно снижает её эффективность, хотя с этим и борются.

← →
Галинка © (2007-09-18 18:15) [9]

а как расчивается, какой кусок будет с избытком?

← →
Kerk © (2007-09-18 18:18) [10]

> [9] Галинка © (18.09.07 18:15)

Прикинь в среднем сколько обычно нужно, столько и выделяй

← →
Галинка © (2007-09-18 18:54) [11]

а как потом лишнее обрезать? и нужно ли?

Если мне надо прочитать из файла строки с целыми значениями, но в одной 7, в другой - 27, в третьей - 15 и т.д. То как прикидывать? Можно как то кратно? Или нужно максимальное брать?

← →
Zeqfreed © (2007-09-18 19:26) [12]

> Галинка © (18.09.07 18:54) [11]

Если ты знаешь максимальное кол-во заранее и оно немногим больше среднего, то выделяй сразу максимум. Иначе см. [5].

← →
tesseract © (2007-09-18 22:28) [13]

> Если мне надо прочитать из файла строки с целыми значениями,
> но в одной 7, в другой - 27, в третьей - 15 и т.д. То как
> прикидывать? Можно как то кратно? Или нужно максимальное
> брать?

Почитай про алгоритм конечного автомата - про память вопросы отсохнут как листья.

← →
celades © (2007-09-18 22:51) [14]

> Это школничество память перераспределять постоянно.

А обучение С это и есть школьничество

← →
palva © (2007-09-18 22:56) [15]

> Галинка © (18.09.07 18:15) [9]
>
> а как расчивается, какой кусок будет с избытком?

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

← →
Kerk © (2007-09-18 22:57) [16]

> [15] palva © (18.09.07 22:56)

Кстати да. А размер общего массива легко прикинуть по размеру файла

← →
Zeqfreed © (2007-09-18 22:59) [17]

> palva © (18.09.07 22:56) [15]

В realloc нет смысла, если он перемещает начало участка памяти.

← →
Галинка © (2007-09-19 10:59) [18]

Спасибо всем. В palva © (18.09.07 22:56) [15] вчера убедилась собственноручно. Кроме Access Violution ничего не дает. Пока выбрала такой алгоритм:
1) "максимальную длину" строки в нужных нам юнитах выбираем заранее и определяем через макро. Типа #define MAXVALS 200
2) максимальное число строк так же определяем заранее как #define MAXLINES 25
3) при первичной инициализации массива делаем примерно так:
int *my_arr[MAXLINES]; for(i=0; i<MAXLINES; i++) my_arr[i] = (int *)malloc(MAXVALS*sizeof(int));

пока вроде логично. Остается одно НО. Отслеживание реального конца строки, за которым уже идет мусор, так как заранее выделено больше памяти. Вот тут пока проблема. Пока самый простой выход - таскать за собой длину строки. Но тогда как ее хранить? Может в первом элементе. Но если массив не целых, то как тогда быть?

Короче, может кто-то примерно знает как устроены в дельфи array of ... . Там же вроде можно переустанавливать длину с помощью SetLength()? Или там тоже где-то храниться Count и просто он увеличивается?

← →
Ricko © (2007-09-19 11:29) [19]

В C строки заканчиваются символом "\0"

← →
Галинка © (2007-09-19 11:32) [20]

Ricko © (19.09.07 11:29) [19]

извини, я не корректно выразилась. Я имела в виду строку матрицы конечно.

← →
palva © (2007-09-19 11:47) [21]

> вчера убедилась собственноручно. Кроме Access Violution ничего не дает.
Вы просто не умеете их готовить (c) Если вам не для трейнинга, а для дела, могу помочь написать правильный код. Можете посмотреть в каких-нибудь книгах по графам. Графы обычно хранят в массивах подобных вашему и при вводе графа возникают те же трудности. С языком си это никак не связано.

> Или там тоже где-то храниться Count
Конечно же где-то хранится. При реализации на си это тоже нужно где-то хранить. Можно не хранить, если само содержимое массива позволяет судить о размере. Например параметры функции main информируют о параметрах командной строки. Первый параметр - количество слов, второй параметр - как раз и есть подобный нашему "ломаный" массив символов(терминология C#). Количество символов в слове здесь не хранится, поскольку достаточно хранить в конце слова нуль-терминатор.

← →
evvcom © (2007-09-19 11:57) [22]

Так ты в какой среде пишешь? В Си или все-таки в Delphi? Если среда от борланда, то можешь смело использовать array of array of type. Если даже возникнет необходимость увеличения размерности в какой-то строке, все корректно перевыделится, скопируется, если надо и т.п.

> определяем через макро. Типа #define MAXVALS 200

если это значение по умолчанию, так и пиши DEFVALS или DEFAULT_VALS, иначе первое, что придет в голову незнакомому с твоими идеями, твоим стилем, что это действительно максимальное значение.

← →
palva © (2007-09-19 12:05) [23]

palva © (19.09.07 11:47) [21]
Про графы я там зря написал. Я посмотрел сейчас. Там везде перед вводом очередной строки (содержащей номера вершин, смежных данной) идет количество вершин, что снимает вопросы с тем, какого размера память выделять.

← →
Галинка © (2007-09-19 12:25) [24]

palva © (19.09.07 11:47) [21]

можно на Ты. Это во-первых. Пока я только тренируюсь. И постараюсь таки "научиться их готовить" ))

А вот второй пункт можно подробнее. Массив вроде не класс, и не структура. тогда как можно хранить в одном месте разнотипные данные? Например, в дельфи насколько мне помнится было что-то подобное:
var koeff_ty : array of float; max_k, i : integer; basis_koeff: float; begin write("Введите длину массива: "); readln(max_k); i=0; while(i<max_k) begin SetLength(koeff_ty, i+1); koeff_ty[i] = basis_koeff + .0025; i++; end; end;

или для матрицы
var myFile : TextFile; koeff_ty : array of array of float; i, j : integer; c_str, str_chis: string; begin i=0; j=0; AssignFile(myFile, "koeef_ty.dat"); while(not EOF(myFile)) begin readln(myFile, c_str); SetLength(koeff_ty, i+1); while(pos(" ", c_str) <> 0) begin SetLength(koeff_ty[i], j+1); str_chis = copy(c_str, 0, pos(" ", c_str) - 1); koeff_ty[i, j] = StrToFloat(str_chis); c_str = copy(c_str, pos(" ", c_str) + 1, length(c_str) - pos(" ", c_str)); j++; end; i++; end; end;

(за правильность кода не ручаюсь, на дельфи уже года четыре не пишу).

Так вот как это может быть реализовано?

← →
Галинка © (2007-09-19 12:27) [25]

я пишу на Си в Eclipse.

← →
palva © (2007-09-19 13:33) [26]

Галинка © (19.09.07 12:25) [24]
Массив должен хранить однотипные данные. На то он и массив. Для хранения разнотипных данных предназначены структуры в си и записи в делфи. Для хранения твоей строки можно использовать такую структуру:

struct {int n; float *f;}
Здесь n будет хранить количество чисел в строке, f - указатель на первое число.

Твоя матрица должна быть по сути массивом указателей на такие структуры. Память под эту матрицу надо тоже выделять динамически.

Как это реализовать - это я сейчас попробую набросать пример на Borland c.

← →
Галинка © (2007-09-19 14:03) [27]

Спасибо тебе большое.

Я так поняла, мне надо будет еще некоторое время привыкать, что записи:

int y[5];

&

int *y = malloc(5*sizeof(int));

отражают один и тот же процесс. И в результате в обоих случаях допустимо потом обращение y[index] при index<5.

← →
Галинка © (2007-09-19 14:05) [28]

И кстати, насколько критично долго идет перераспределение памяти на современном железе?

palva © (19.09.07 13:33) [26]
#include <stdio.h> #include <stdlib.h> #include <alloc.h> #include <string.h> int main() { struct zeile {int n; double *r;} *mat; int i, k, n, ii, jj; char buf[200], *pch; printf("Input number of string: "); gets(buf); n = atoi(buf); mat = malloc(n * sizeof(*mat)); printf("Now input strings.\n"); for(ii = 0; ii < n; ii++) { gets(buf); k = 0; /* count of numbers in string */ for(i = 0; buf[i]; i++) if(buf[i]!=" " && (i==0 || buf[i-1]==" ")) k++; if(!k) break; mat[ii].n = k; mat[ii].r = malloc(k*sizeof(double)); pch = strtok (buf," "); jj = 0; while (pch != 0) { mat[ii].r[jj++] = atof(pch); pch = strtok(NULL, " "); } } /* end of input */ /* test of input (may be another) */ printf("%lf\n", mat[0].r[0]); printf("%lf\n", mat[1].r[1]); /* free memory */ for(i=0; i<n; i++) free(mat[i].r); free(mat); return 0; }

> И кстати, насколько критично долго идет перераспределение
> памяти на современном железе?

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

> отражают один и тот же процесс. И в результате в обоих случаях допустимо потом обращение y[index] при index<5.

Обращение такое допустимо в том и другом случае. Но процессы это разные. В первом случае память под массив выделяется в стеке. Во втором случае в стеке выделяется память под указатель на массив, а память под массив выделяется в куче. В первом случае память автоматически освободится при выходе из функции. Во втором случае необходимо позаботиться об освобождение памяти, которая взята из кучи, то есть явно написать free(y);

> И кстати, насколько критично долго идет перераспределение памяти на современном железе?
Не думаю, что надо обращать внимание на время этого действия, если это происходит вместе с такой медленной операцией как ввод. Другое дело, что может возникнуть сильная фрагментация кучи, но это зависит от того, как реализован менеджер кучи.

А как делать дефрагментацию? И можно ли? Пока нашла, что за это под виндой в большей степени отвечает менеджер кучи компилятора. А где найти, как с этой проблемой справляется gcc? Потому как пишу под ним, в теории под Линухом.

И все же в варианте нахождения подстроки, например, мне видится только перераспределение памяти. Например вот так:
char *substrcpy(char *src, int start, int count){ char *new_line = NULL; int cc = start; int i = 1; while(src[cc] != "\n" && src[cc] != 0 && cc<start+count){ new_line = realloc(new_line, i*sizeof(char)); if(!new_line) exit(1); new_line[i-1]= src[cc]; cc++; i++; } new_line[i-1] = "\0"; return new_line; }

Кажется очень правильным такое решение. Поругайте, если что не так ))

palva © (19.09.07 14:39) [29]
> mat[ii].r = malloc(k*sizeof(double));

У меня здесь ошибка. Надо так.
mat[ii].r = malloc(k*sizeof(struct zeile));

> А как делать дефрагментацию? И можно ли?
Нельзя, не предусмотрено. Не изменять же после дефрагментации все полученные указатели на память и все, что вычислялось с их помощью. Всякие искусственные приемы применяются, и даже функции есть, которые помогают уменьшить дефрагментацию. Но эти функции не стандартизованы.

> Кажется очень правильным такое решение.
Мне тоже кажется правильным. Большинство менеджеров кучи пытается сделать realloc на том же месте. Но все же стоит по возможности избегать realloc, и если есть возможность предварительно вычислить размер, то вычислить, даже если алгоритм такого вычисления будет нетривиальным.

> Галинка © (19.09.07 18:56) [33]

Гм. Как я понимаю, ф-ция возвращает подстроку не более count символов начиная со start до первого перевода строки?

#define _GNU_SOURCE #include <stdio.h> #include <stdlib.h> #include <string.h> char *substr(char *src, int offset, int count) { char *start = src + offset; char *p = start; while (p - start < count && *p != "\n" && *p != 0) p++; return strndup(start, p - start); }

> Zeqfreed © (19.09.07 21:21) [35]
>
> > Галинка © (19.09.07 18:56) [33]
>
> Гм. Как я понимаю, ф-ция возвращает подстроку не более count
> символов начиная со start до первого перевода строки?
>

ну не совсем. Просто если встречается символ перевода строки или ноль, то не нужно считать дальше count, так как строка все равно кончилась. Т.е. если из строки длинной в 10 скажем символов, хотят вырезать пять, начиная с 7, то вырежут только 4. Чтобы мусор не таскать за собой. Потому что строки из файла пока читала через fgets. А там нужна фиксированная длина. Ну в смысле с запасом на самую длинную строку.

Вот что нашла в королевстве:

http://www.delphikingdom.com/asp/viewitem.asp?catalogid=1011

Это полезно? Стоит поковыряться и разобраться?

Если еще кто что встретит, то киньте ссылкой. Почитать и понять хочется. пока пошла читать исходник на дельфи?

ПыСы:
- На каких иностранных языках говорите?
- Си, Паскаль, Ява...

:-))))

> Галинка © (19.09.07 23:13) [36]

Подход из [35] отбраковала? Ну-ну, пиши тогда менеджер памяти :)

А для твоей задачи совсем не нужно его писать. По двум причинам: 1) готовый лучше 2) он достаточно неплох.

Приведи полностью твою задачу. Я вечерком хоть пальцы разомну :)

← →
имя (2007-09-20 09:58) [40]

Удалено модератором

Массивы переменной длины в Си Найти похожие ветки