Каков предел размера для переключения с вектора на deque?

Question

Я недавно написал этот пост:
Как лучше хранить ОЧЕНЬ большой 2D список поплавков в c ++?Обработка ошибок?

Некоторые предположили, что я реализовал свою 2D-структуру типа списков как вектор, другие сказали, что deque.

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

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

1. float
2.int

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

например, я ищу ответ типа "Примерно 4 миллиона с плавающей запятой или 8 миллионов целых,Вы должны переключиться ... "... если возможно.

Answer 1

Ну, вот два мнения. Стандарт C ++ гласит (23.1.1 / 2):

vector - это тип последовательности, который должен использоваться по умолчанию.

list следует использовать при частых вставках и удалениях из середины последовательности.

deque - это выбранная структура данных, когда большинство вставок и удалений происходит в начале или в конце последовательности.

Херб Саттер утверждает следующее (статья содержит его обоснование и анализ эффективности):

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

Answer 2

Если вам нужны вставки в начале, то используйте deque.

В противном случае, я всегда хотел бы указать на эту статью о вектор против deque (в дополнение к тем, что здесь упоминал Джеймс МакНеллис). Предполагая реализацию deque, которая использует распределение на основе страниц , в этой статье есть хорошее сравнение времени выделения (и времени освобождения) для вектора с & без reserve () и deque. По сути, использование Reserve () делает время выделения вектора очень похожим на deque. Информативно и полезно, если вы можете угадать правильное значение, чтобы зарезервировать заранее.

Answer 3

Опять же, нет ограничения по размеру, выше которого deque или не лучше, чем вектор.Последствия фрагментации памяти практически одинаковы в любом случае, за исключением случаев, когда вы уже выполнили огромную нагрузку выделения / освобождения, и для большого вектора осталось недостаточно смежного пространства.Но этот случай очень редкий.Помните, что объем памяти составляет на процесс (Google для виртуальная память ).И вы можете исправить это, выделив память для вектора (методом reserve) до того, как произойдет беспорядок.

Компромисс в терминах , что вы хотите с ним сделать .Если структура в основном неизменна, и вы хотите получить к ней доступ / перезаписать ее только с помощью индекса, перейдите к вектору.

Deque - это когда вам нужно сделать вставки либо в конце, в начале или в середине,что-то, что вектор не может обработать естественным образом (за исключением вставки в конце).

Статьи Херба Саттера, в общем, отличного качества, но вы заметите, что когда вы выполняете «перехват чисел» в C ++, большинствоВас учат в книгах по «общему С ++», и к ним нужно относиться с особой осторожностью.Низкая производительность индексирования, с которой вы сталкиваетесь при запросах, возможно, важна для вашего приложения.В этом случае не используйте deque.

Answer 4

Вы переключаетесь после тестирования, и профилирование показывает, что один для вашего приложения хуже другого. Универсального ответа «вокруг N float или M ints» не существует.

Answer 5

Есть так много факторов, которые нужно учитывать, что невозможно дать четкий ответ. Объем памяти на машине, насколько она фрагментирована, насколько фрагментированной она может стать и т. Д. Я предлагаю просто выбрать один и использовать его. Если это вызывает проблемы, переключитесь. Скорее всего, вы все равно не попадете в эти крайние случаи.

Если вы действительно обеспокоены, то, возможно, вы могли бы реализовать своего рода псевдо PIMPL:

template<typename T>
class VectorDeque
{
private:
  enum TYPE { NONE, DEQUE, VECTOR };
  std::deque<T> m_d;
  std::vector<T> m_v;
  TYPE m_type;
  ...
public:
  void resize(size_t n)
  {
    switch(m_type)
    {
      case NONE:
      try
      {
        m_v.resize(n);
        m_type = VECTOR;
      }
      catch(std::bad_alloc &ba)
      {
        m_d.resize(n);
        m_type = DEQUE;
      }
      break;
    }
  }
};

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

Answer 6

Учитывая, что вы не вставляете после создания, вам, вероятно, следует либо использовать простой старый std::vector, либо, если фрагментация действительно становится проблемой, пользовательский вектор Sequence , реализованный в виде вектора илимассив указателей на массивы фиксированного размера.

Answer 7

Что касается памяти, я могу поделиться некоторым опытом, который может помочь вам решить, когда смежные блоки памяти (malloc или std :: vector) могут стать слишком большими:

Приложение, с которым я работаю, записывает данные измерений, в основном 4 байта float, и для этого выделяет внутренние буферы для хранения данных. Эти буферы сильно различаются по размеру, но типичный диапазон может быть, скажем, несколько десятков от 1-10 МБ и очень немногие из> 100 МБ. Буферы всегда выделяются с calloc, то есть одним большим фрагментом памяти. Если выделение буфера завершается неудачно, регистрируется ошибка, и у пользователя есть выбор повторить попытку.

Размеры буфера: допустим, вы хотите записать 1000 каналов при 100 Гц в течение 10 минут: 4 байта x 1000 x 100 x 60x10 == 228 МБ (приблизительно) ... или 100 каналов при 10 Гц в течение 12 часов == 41 МБ

У нас (почти) никогда не было проблем с выделением 40 МБ буферов (а это около 10 млн. Флотаций), и 200-300 МБ буферов время от времени отказывали - все это на обычных WinXP / 32-битных блоках с 4 ГБ ОЗУ. *