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

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

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

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

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

c++ input runtime big-o
person Name Last    schedule 14.02.2011    source источник
comment
io, скорее всего, оооочень медленный. сделать сначала, возможно, с cplusplus.com/reference/clibrary/cstdlib/realloc   -  person Anycorn    schedule 14.02.2011

Ответы (1)


arrow_upward
1
arrow_downward

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

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

person Gabe    schedule 14.02.2011
comment
Черт... +2 в SO невозможно :-) - person mmmmmmmm; 14.02.2011