Обычно можно повысить производительность, увеличив размер буфера.

Сразу после построения ifstream, Вы можете установить его внутренний буфер, используя:

char LocalBuffer[4096]; // buffer

std::ifstream wordListFile("dictionary.txt");

wordListFile.rdbuf()->pubsetbuf(LocalBuffer, 4096);

Примечание: результат rdbuf гарантированно не будет равен нулю, если построение ifstream удалось

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

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

Gcc 3.4.2 на SLES 10 (sp 3)
C : 9.52725 e+06
C++: 1.11238 e+07
разница: 1.59655 e+06

Что дает замедление улюлюканья 17%.

При этом учитываются:

• автоматическое управление памятью (без переполнения буфера)
• автоматическое управление ресурсами (отсутствие риска для забудьте закрыть файл)
• обработка locale

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

---

соответствующий код, где benchmark - это моя собственная небольшая утилита, которая измеряет время повторного выполнения (здесь запускается на 50 итераций) с помощью gettimeofday.

#include <fstream>
#include <iostream>
#include <iomanip>

#include <cmath>
#include <cstdio>

#include "benchmark.h"

struct CRead
{
  CRead(char const* filename): _filename(filename) {}

  void operator()()
  {
    FILE* file = fopen(_filename, "r");

    int count = 0;
    while ( fscanf(file,"%s", _buffer) == 1 ) { ++count; }

    fclose(file);
  }

  char const* _filename;
  char _buffer[1024];
};

struct CppRead
{
  CppRead(char const* filename): _filename(filename), _buffer() {}

  enum { BufferSize = 16184 };

  void operator()()
  {
    std::ifstream file(_filename);
    file.rdbuf()->pubsetbuf(_buffer, BufferSize);

    int count = 0;
    std::string s;
    while ( file >> s ) { ++count; }
  }

  char const* _filename;
  char _buffer[BufferSize];
};


int main(int argc, char* argv[])
{
  size_t iterations = 1;
  if (argc > 1) { iterations = atoi(argv[1]); }

  char const* filename = "largefile.txt";

  CRead cread(filename);
  CppRead cppread(filename);

  double ctime = benchmark(cread, iterations);
  double cpptime = benchmark(cppread, iterations);

  std::cout << "C  : " << ctime << "\n"
               "C++: " << cpptime << "\n";

  return 0;
}

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

Действительно ли 0.25 s-это проблема? Если вы не собираетесь загружать намного большие файлы, есть ли необходимость делать это быстрее, если это делает его менее читаемым?

Моя система (3.2.0-52-общая, г++-4.7 (Убунту/организацией Linaro 4.7.3-2ubuntu1~12.04) 4.7.3, скомпилированный с -О2 если параметр не указан, процессор: модель процессора: i3-2125)

В моих тестовых случаях я использовал словарь 295068 слов (таким образом, в нем на 100 тысяч больше слов, чем в вашем): http://dl.dropboxusercontent.com/u/4076606/words.txt

С точки зрения сложности времени:

• худший вариант сложности вашей программы: O (n*n)=O(n [чтение данных]*n[вставка в unordered_set])
• средний случай сложность вашей программы: O (n)=O (n[read data]*1[insert into unordered_set])

Практические советы:

• большинство простых структур данных имеют меньшие временные затраты. Простой массив быстрее вектора. массив символов быстрее строки. В интернете есть много информации об этом.

Мои измерения:

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

sync; sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'

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

Мой код:

---

14-16 ms для чтения из файла и вставки данных в массив 2D-символов (read & insert) n раз

65-75 ms для поиска с помощью двоичного поиска всех слов (Поиск n раз):

Итого=79-91 МС

---

61-78 ms для чтения из файла и вставки данных в a unordered_set char array (read & insert) n раз

7-9 ms to Поиск по хэшу n раз

Итого=68-87 МС

---

Если вы выполняете поиск больше раз, чем вставляете, выберите hash table (unordered_set) в противном случае бинарный поиск (с простым массивом).

---

Ваш исходный код (поиск и вставка):

Скомпилировано с -O2: 157-182 МС

Скомпилирован с-O0 (если вы опустите флаг-O, уровень"- O " по умолчанию также равен 0): 223-248 МС

Таким образом, параметры компилятора также имеют значение, в данном случае это означает 66 ms speed boost. Вы не указали ни одного из них. Так что, по-моему, вы им не пользовались. Как я пытаюсь ответить на ваш главный вопрос.

---

Что вы можете сделать наиболее простым, но лучше всего с вашим текущим кодом?

1. [лучшее использование API высокого уровня] используйте "getline (wordListFile, word) "Вместо" wordListFile > > word". Кроме того, я думаю, что "getline" более удобочитаем, чем ">>" оператор.

Компилируется с-O2: 142-170 МС. ~ 12-15 МС ускорение по сравнению с исходным кодом.

Скомпилирован с-O0 (если вы опустите флаг-O, уровень "-O" по умолчанию также равен 0): 213-235 МС. ~ 10-13 МС увеличение скорости по сравнению с вашим исходным кодом.

1. [лучшее использование API высокого уровня] избегайте повторения с "dict.reserve (XXXXXX);", @David Rodríguez-dribeas также упоминал об этом. Если ваш словарь статичен или если вы можете угадать свой размер словаря (например, размер файла, деленный на среднюю длину слова). Первый запуск без "резерва" и выдается параметра bucket_count (соиь

Скомпилировано с -O2: 99-121-[137] ms. ~ 33-43 - [49] MS speed boost по сравнению с исходным кодом.

Что вы можете сделать более продвинутого, чтобы ускорить его?

Реализуйте свою собственную хэш-функцию для вашего конкретный ввод данных. Используйте массив char вместо строки STL. После того, как вы это сделали, только тогда напишите код с прямым вводом/выводом ОС, как вы заметили (из моих измерений также видно), что структура данных является узким местом. Если носитель очень медленный, но процессор очень быстрый, сожмите файл распакуйте его в вашей программе.

---

Мой код не совершенен, но все же он лучше, чем все, что можно увидеть выше: http://pastebin.com/gQdkmqt8 (хэш-функция из интернета, можно также сделать лучше)

---

Не могли бы вы предоставить более подробную информацию о том, для какой системы (одной или диапазона) вы планируете оптимизировать?

Информация о временных сложностях: Должны быть ссылки... Но у меня не так много репутации, как у новичка в stackoverflow.

Мой ответ все еще имеет отношение к чему-нибудь? Пожалуйста, добавьте комментарий или проголосуйте, так как нет PM, как я вижу.

Библиотеки C++ и C одинаково быстро считывают информацию с диска и уже буферизованы, чтобы компенсировать задержку ввода-вывода диска. Вы не сделаете его быстрее, добавив больше буферизации.

Самое большое различие заключается в том, что потоки C++ выполняют множество манипуляций, основанных на локале. Символьные преобразования / пунктуационные и т. д.

В результате библиотеки C будут работать быстрее.

Заменено Мертвое Звено

По какой-то причине связанный вопрос был удален. Так и есть. перемещение соответствующей информации сюда. Связанный вопрос касался скрытых функций в C++.

---

Хотя и не является технической частью STL.
Библиотека streams является частью стандартных библиотек C++.

Для потоков:

Локали.

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

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

Примеры:

• знаете ли вы, что локали изменят '.- в десятичном числе к любому другому символу автоматически.
• знаете ли вы, что локали будут добавлять", " каждую третью цифру, чтобы сделать его легко читаемым.
• знаете ли вы, что локали можно использовать для манипулирования текстом по пути (то есть преобразования из UTF-16 в UTF-8 (когда запись в файл).

И т.д.

Примеры:

• добавление запятой для каждых трех цифр
• использование пространства в качестве разделителя
• установите десятичный разделитель
• простой выходной фильтр
• установите текущую локаль
• количество символов, отправленных на вывод
• отступ каждой строки
• UTF-16 (поток) - > UTF-16 (внутренний) Конвертер (непроверенный)

Правильная реализация библиотеки ввода-вывода будет кэшировать данные для вас, избегая чрезмерных обращений к диску и системных вызовов. Я рекомендую вам использовать инструмент уровня системных вызовов (например, strace, если вы находитесь под Linux), чтобы проверить, что на самом деле происходит с вашим IO.

Очевидно, что dict.insert(xxx) также может быть помехой, если он не позволяет вставлять O(1).

К сожалению, вы мало что можете сделать для повышения производительности при использовании fstream.

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

Единственный способ добиться больших улучшений - это использовать функции ввода-вывода вашей ОС. Например, в Windows открытие файла с флагом FILE_FLAG_SEQUENTIAL_SCAN может ускорить чтение, как а также использование асинхронного чтения для захвата данных с диска и параллельного их анализа.

Если вы действительно хотите быстро, бросьте istream и string и создайте тривиальный класс Read_Only_Text вокруг const char* & size, затем карта памяти файла и вставка в unordered_set<Read_Only_Text> со ссылками на вложенные строки. Это будет означать, что вам незачем хранить файл размером 2 МБ, хотя количество уникальных ключей может быть намного меньше, но он будет очень, очень быстро заполняться. Я знаю, что это больно, но я делал это несколько раз для различных задач, и результаты очень хорошие.

Хотите верьте, хотите нет, но производительность потока stdlib при чтении данных намного ниже, чем у подпрограмм библиотеки C. Если вам нужна максимальная производительность чтения ввода-вывода, не используйте потоки c++. Я обнаружил это трудным путем на сайтах конкурентов алгоритмов - мой код попадал в тестовый тайм-аут, используя потоки c++ для чтения stdin, но заканчивал его за много времени, используя простые операции с файлами C.

Edit: просто попробуйте эти две программы На некоторых примерах данных. Я запустил их на Mac OS X 10.6.6, используя g++ i686-apple-darwin10-g++-4.2.1 (GCC) 4.2.1 (Apple Inc. build 5664) на файле с 1 миллионом строк "howdythere", и версия scanf работает последовательно в 5 раз быстрее, чем версия cin:

#include <stdio.h>

int main()
{
    int count = 0;
    char buf[1024];
    while ( scanf("%s", buf) == 1 )
        ++ count;

    printf( "%d lines\n", count );
}

И

#include <iostream>

int main()
{
    char buf[1024];
    int count = 0;

    while ( ! std::cin.eof() )
    {
        std::cin.getline( buf, 1023 );
        if ( ! std::cin.eof() )
            ++count;
    }
   std::cout << count << " lines" << std::endl;
}

Edit: изменил файл данных на "howdythere", чтобы устранить разницу между двумя случаями. Результаты хронометража не изменились.

Edit: я думаю, что сумма процентов (и понижения) в этом ответе показывает, насколько противоположна популярному мнению реальность. Люди просто не могут поверить, что простой случай чтения входных данных как в C, так и в потоках может быть настолько разным. Прежде чем вы понизите голос: Идите и измерьте его сами. Дело не в том, чтобы установить тонны состояний (которые обычно никто не устанавливает), а просто код, который люди чаще всего пишут. Мнение ничего не значит в исполнении: мера, мера, мера-вот все, что имеет значение.