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

Question

В основном мне интересно, что было бы более быстрым способом обработки ввода со стандартного ввода:

Метод первый: объявление массива произвольного размера, чтение в массив, и если входное значение больше, чемsize, выделите новый массив в два раза больше, скопируйте содержимое в новый массив и освободите предыдущий массив.

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

1. Я не использую векторы.пожалуйста, не говорите просто использовать векторы ...
2. они не будут вводить ввод, он будет перенаправлен из командной строки в файл.Сродни ./program < input.txt
3. Я понимаю, что первый метод более неэффективен с точки зрения пространства, но быстрее ли он, чем метод два?если да, то сколько?метод 2 по существу занимает 2n времени, чтобы закончить.Я хочу знать, увеличит ли первый метод время выполнения моего кода.

Answer 1

Оба метода O (n).Однако вы читаете из stdin, поэтому нет способа перемотать его обратно в начало, если только уже не хранит данные где-то, поэтому я не вижу, как вы могли бы использовать метод 2.

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