Блог

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

Я нашел два способа:

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

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

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

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

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

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

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

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

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

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

Дональд Кнут

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

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