Ответ 1

Быстрое профилирование в моей системе (linux-2.6.37, gcc-4.5.2, скомпилированное с -O3) показывает, что ввод-вывод не является узким местом. Используя fscanf в массиве char, за которым следуют dict.insert() или operator>>, как в вашем точном коде, требуется примерно одно и то же время (155 - 160 мс, чтобы прочитать файл слова 240k).

Замена gcc std::unordered_set на std::vector<std::string> в вашем коде сокращает время выполнения до 45 мс (fscanf) - 55 мс (operator>>) для меня. Попробуйте профилировать IO и установить вставку отдельно.

Ответ 2

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

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

char LocalBuffer[4096]; // buffer

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

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

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

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

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

gcc 3.4.2 на SLES 10 (sp 3)
C: 9.52725e + 06
С++: 1.11238e + 07
разница: 1.59655e + 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;
}

Ответ 3

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

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

Ответ 4

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

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

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

Заменена мертвая ссылка

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

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

Для потоков:

Locales.

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

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

Примеры:

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

и др.

Примеры:

• Добавление запятой для каждых трех цифр
• Использование пространства в качестве разделителя
• Установите десятичный разделитель
• Простой выходной фильтр
• Установить текущий язык
• Подсчитайте количество символов, отправленных на вывод
• Отступы в каждой строке
• UTF-16 (поток) → UTF-16 (внутренний) конвертер (непроверенный)

Ответ 5

Моя система (3.2.0-52-generic, g++ - 4.7 (Ubuntu/Linaro 4.7.3-2ubuntu1 ~ 12.04) 4.7.3, скомпилировано с -O2, если не указано, CPU: i3-2125 )

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

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

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

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

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

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

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

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

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

Мой код (чтение из файла и вставка данных; поиск по всем словам):

14–16 мс для чтения из файла & вставлять данные в массив двумерных символов (читать и вставлять) n раз

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

Всего =79-91 мс

61-78 мс для чтения из файла & вставлять данные в массив символов unordered_set (читать и вставлять) n раз

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

Всего =68-87 мс

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

Ваш оригинальный код (поиск и вставка):

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 6

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

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

Ответ 7

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

Изменить: просто попробуйте эти две программы на некоторых образцах данных. Я запускал их в 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;
}

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

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

Ответ 8

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

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

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

Ответ 9

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