Realloc Vs Сканирование связанного списка

Question

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

Я нашел два пути:

1. Использовать realloc каждый раз, когда япрочитайте строкуТаким образом, фаза выделения медленная, но фаза вычислений легче благодаря доступу к индексу.

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

Что лучше с точки зрения сложности?

Answer 1

Как часто вы будете просматривать связанный список?Если это только один раз, перейдите на связанный список.Еще несколько вещей: будет ли много мелких ассигнований?Вы можете сделать несколько меньших буферов, скажем, на 10 строк и связать их вместе.Но это все вопрос профилирования.

Сначала я сделаю самую простую вещь и посмотрю, подходит ли это только моим потребностям, а затем я подумаю об оптимизации.

Иногда человек тратит слишком много временидумать об оптимальном, даже когда второе лучшее решение также идеально соответствует потребностям.

Answer 2

Без дополнительных подробностей о том, как вы собираетесь использовать информацию, сложно сказать о сложности.Тем не менее, вот несколько соображений:

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

Answer 3

как уже заявили другие пользователи:

Преждевременная оптимизация - корень зла

Дональд Кнут

У меня есть другое предложение, использующееrealloc: в C ++ STL контейнер std::vector увеличивается каждый раз, когда вставляется объект, и недостаточно свободного места.Размер увеличения зависит от текущего предварительно выделенного размера, но зависит от конкретной реализации.Например, вы можете сохранить фактическое количество предварительно выделенных объектов.Если размер заканчивается, вы вызываете reallocate с двойным количеством места, выделенным в данный момент.Я надеюсь, что это было несколько понятно!

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