3

Сейчас изучаю динамические массивы. Дал себе задание: считать из файла данные в динамический массив структур . Как лучше выделять память? Есть 2 варианта:

  1. Посчитать количество строк в файле и дать место под массив malloc'ом. Минусы этого метода, что по файлу надо пробигаться 2 раза: первый это подсчёт количества строк, второй заполнение массива.
  2. При считывании из файла расширять выделяемую память realloc'ом. Минусы этого метода, что realloc - ресурсозатратное средство. Но можно немного обойти этот минус и выделять раз в 3 итерации сразу память для трёх элементов.

Итак, что же использовать лучше? Или возможно всё зависит от размера файла?
UPD:
1. OC - Windows
2. Формат данных в фалйе: Название(char)|количество(int)\n
И структура из двух элементов name(char[255]) и count(int). Кол-во данных не фиксированное, может быть как 100 элементов так и 1000. Или всё-таки ввести максимум и выделять максимум памяти вначале, а потом сокращать? Или узнать сколько весит 1 эелемент этой структуры, проверить размер файла, разделить его на вес 1го элемента и так мы получим кол-во элементов, для которых надо выделять память?

9
  • "Или возможно всё зависит от размера файла?" Или, возможно, зависит от того, чем Вы больше дорожите: ресурсами или скоростью.
    – BuilderC
    12 апр 2014 в 14:36
  • Можно использовать vector. Или посмотреть его реализацию. Допустим если писать свой vector, то можно при добавлении элемента, если достигли предела выделенной памяти, то выделять еще память с запасом и так далее. Получится надо будет выделять память не под каждый айтем, но зато будет немного больше памяти использвано.
    – Deadkenny
    12 апр 2014 в 15:34
  • @iproger, попробуйте конкретизировать задачу (похоже, в такой постановке она не вызывает живого обсуждения). - Какой формат данных в файле? - Что из него Вы хотите хранить в памяти? - О какой ОС идет речь? Если размер структуры фиксирован и в ней нет указателей на динамически размещаемые элементы, то в Linux я бы посмотрел размер файла в байтах, прикинул максимальное количество структур, которые могут из него получиться, выделил под них память одним вызовом malloc и за одно чтение файла заполнил этот массив структур, а потом вызвал realloc для его сокращения до актуального размера.
    – avp
    12 апр 2014 в 19:25
  • @avp, спасибо, ответил апдейтом
    – iproger
    13 апр 2014 в 9:31
  • 1
    количество это просто элемент структуры. Т.е. например наименование "Вода Кувака|100". Да, не получится делить размер файла ,чтобы узнать кол-во, т.к. наименование и кол-во разной длины
    – iproger
    13 апр 2014 в 14:38

4 ответа 4

2

а с чего вы взяли что "количество строк" == "размер файла" ?

яркий пример 2 файла в одном 2 строки в каждой 10 символов и втором 2 строки и в каждой 1000 символов...

у любого файла есть мета информация о размере, времени создания, времени чтения, etc...

  1. узнаём размер файла
  2. узнаём размер памяти
  3. узнаём сколько свободно памяти
  4. используем полученную инфу...
2
  • Мм, а как именно использовать данную информацию? Ну вот допустим размер файла 2МБ, свободно памяти 1ГБ. Какой вариант выбирать? Или просто в начале выделять столько памяти, сколько весит файл?
    – iproger
    13 апр 2014 в 9:34
  • а если памяти 700мб а файл 4гб ? зная размер файла, памяти, и объём свободной памяти прикидываем размер буфера (на вкус и цвет). читаем sizeof("буфер") из файла, запоминаем позицию, обрабатываем данные и снова читаем sizeof("буфер") из файла. 13 апр 2014 в 9:57
0
  1. Спрашиваеш у файловой системы размер файла в байтах.
  2. просишь у malloc ровно столько байт
  3. прочитываеш в этот чанк свой файл
  4. считаешь число строк в памяти(число eol и \0)
  5. просишь у malloc вот такого размер массива указателей на char сколько насчитал строк
  6. однократным сканированием выставляеш указатели на начала строк и заменяеш все переводы на \0
3
  • 1
    мало того, что памяти выделиться в два раза больше, чем нужно, так и на 2 пункте можно получить oom или просто тихое рыдание винта (свопиться будет).
    – KoVadim
    14 апр 2014 в 19:00
  • память выделится только на размер файла байт + размер_ указателя*(число_переводов_строк+1) 4 пунт подсчёт , а не второе считывание.
    – qulinxao
    15 апр 2014 в 5:46
  • @qulinxao, а зачем автору вообще вектор указателей на строки файла, если его цель массив структур, содержащих данные из строк файла? Действительно, из одной строки получается одна структура в памяти, но хранить-то эти строки одновременно с построенными структурами не требуется.
    – avp
    15 апр 2014 в 7:29
0

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

Посмотрите код фреймворка для юнит-тестирования CuTest, там своя реализация строк CuString примерно так и сделана.

0

Лучше сделать на базе односвязанного списка (или одномерным массивом с realloc). И читать посимвольно. В псевдокоде примерно так:

offset = 0
while (!eof)
{
  while (fgetc() !=  \n); // читаем до конца строки

  s.offset = offset
  s.size = fseek() - offset
  list_add(s)
  offset = fseek()
}

а потом по надобности читать из файла строку по нужному смещению

4
  • односвязный список (при условии, что на каждый элемент будет выделятся память) не будет оптимальным по использованию памяти. Дело в том, что просто так выделить 3 байта или 15 нельзя. Память все равно выделяется кратной как минимум 4 байтам (а то и все 16). Хвосты будут просто простаивать.
    – KoVadim
    21 апр 2014 в 15:11
  • он будет неоптимальным, если длина строк в среднем по файлу >8 символов (для x86). Строки меньше 4 символов можно хранить в значении offset. В простом случае все выравнено на 4: указатель на следующий элемент (4), смещение в файле (4/8), размер (4)
    – Veliant
    21 апр 2014 в 16:30
  • Пример готового кода, написанного на коленке pastebin.com/wFHCETLC
    – Veliant
    21 апр 2014 в 17:18
  • @Veliant, а зачем автору вопроса список дескрипторов строк в файле? Он вроде бы написал Дал себе задание: считать из файла данные в динамический массив структур И при этом интересуется, какой из способов построения массива (с данными из файла) наименее ресурсозатратный. -- А минимальный конечный расход памяти для задачи в Вашей интерпретации -- это массив из n + 1 элемента (n -- количество строк). Каждый элемент -- смещение. Последний элемент массива -- смещение на конец файла. Длины строк хранить не надо. Длина i-ой строки вычисляется как a[i + 1] - a[i].
    – avp
    21 апр 2014 в 17:42

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.