Я написал этот код Хемминга для класса. Почему это так медленно?
Я написал это для моего класса ОС:
#include <iostream>
#include <fstream>
//encodes a file using the (8,4) Hamming Code.
//usage : HammingEncode.out < inputFile > outputFile
int main() {
unsigned char const codebook[] = {0x00, 0x1E, 0x2D, 0x33, 0x4B, 0x55, 0x66, 0x78, 0x87, 0x99, 0xAA, 0xB4, 0xCC, 0xD2, 0xE1, 0xFF};
unsigned char in, nextByte;
unsigned char const leftMask = 0xF0, rightMask = 0x0F;
in = std::cin.get();
while (!std::cin.eof()) {
nextByte = (in & leftMask) >> 4;
std::cout << codebook[nextByte];
nextByte = in & rightMask;
std::cout << codebook[nextByte];
in = std::cin.get();
}
}
Затем я решил проверить его скорость (просто чтобы увидеть) на ветхозаветной форме Библии короля Иакова. Это был наш стандартный тестовый файл для класса структур данных, который преподавался на Java, и мы могли его отсортировать, и Хаффман зашифровал его практически за короткое время, но для его кодирования требуется довольно много времени. Что здесь происходит?
Решение
std::cin открыт в текстовом режиме и постоянно ищет все, что нужно искать (например, переводы строк и т. д.).
Учитывая постоянный характер нюхает std::cin входной поток, я не удивлен, что это занимает больше времени, но это кажется немного чрезмерным. следующее, минуя iostream и используя FILE Прямой поток, вероятно, будет делать то, что вы ожидали:
#include <cstdlib>
#include <cstdio>
int main(int argc, char *argv[])
{
static unsigned char const codebook[] =
{
0x00, 0x1E, 0x2D, 0x33, 0x4B, 0x55, 0x66, 0x78,
0x87, 0x99, 0xAA, 0xB4, 0xCC, 0xD2, 0xE1, 0xFF
};
for (int c = std::fgetc(stdin); c!=EOF; c=std::fgetc(stdin))
{
std::fputc(codebook[c >> 4], stdout);
std::fputc(codebook[c & 0x0F], stdout);
}
return EXIT_SUCCESS;
}
Я проверил точный код выше для случайного файла 10 МБ, загруженного с символами в диапазоне от a в zи результаты были смехотворно длинными при использовании std::cin а также std::cout, С использованием FILE напрямую, разница была огромный. Весь код в этом ответе был протестирован с Apple LLVM version 5.1 (clang-503.0.38) (based on LLVM 3.4svn) с помощью -O3 оптимизация.
С помощью FILE потоки
time ./hamming < bigfile.txt > bigfile.ham
real 0m1.855s
user 0m1.812s
sys 0m0.041s
С помощью std::cin а также std::cout
time ./hamming < bigfile.txt > bigfile.ham
real 0m23.819s
user 0m7.416s
sys 0m16.377s
С помощью std::cin а также std::cout с std::cout.sync_with_stdio(false);
time ./hamming < bigfile.txt > bigfile.ham
real 0m24.867s
user 0m7.705s
sys 0m17.118s
В итоге, ой. Следует отметить время, проведенное в система. Если я получу возможность обновить это с std::istream::get() а также put() методы я буду, но, честно говоря, я не ожидаю каких-либо чудес на этот счет. Если не существует какого-то волшебного (для меня, а не для других) пути превращения от IO XLAT из std::cin FILE потоки могут быть разумной альтернативой. Я еще не исследовал, хлебать ли std::cin«s rdbuf() Это также жизнеспособный вариант, но он также может иметь обещание.
Редактировать: Использование std::istreambuf_iterator<char>
Использование класса итератора streambuf значительно улучшилось, так как он по существу обходит весь мусор встроенного предкрылка, но все же не так эффективен, как FILE потоки:
#include <iostream>
#include <cstdlib>
#include <cstdio>
int main(int argc, char *argv[])
{
static unsigned char const codebook[] =
{
0x00, 0x1E, 0x2D, 0x33, 0x4B, 0x55, 0x66, 0x78,
0x87, 0x99, 0xAA, 0xB4, 0xCC, 0xD2, 0xE1, 0xFF
};
std::istreambuf_iterator<char> cin_it(std::cin), cin_eof;
std::for_each(cin_it, cin_eof, [](char c)
{
std::cout.put(static_cast<char>(codebook[static_cast<unsigned char>(c) >> 4]));
std::cout.put(static_cast<char>(codebook[static_cast<unsigned char>(c) & 0x0F]));
});
return EXIT_SUCCESS;
}
Результаты:
time ./hamming < bigfile.txt > bigfile.ham
real 0m6.062s
user 0m5.795s
sys 0m0.053s
Обратите внимание, что system теперь сопоставим с FILE результаты потока, но накладные расходы от остальных шаблонов iostream в user кажется больной вопрос (но все же лучше, чем другие iostream Попытки). Вы выиграли, некоторые проиграли = P
Изменить: небуферизованный системный ввод-вывод
Стремясь быть полностью честным, обходя всю буферизацию во время выполнения и полагаясь исключительно на системные вызовы, чтобы сделать это безумие, также стоит отметить следующее:
#include <cstdlib>
#include <cstdio>
#include <unistd.h>
int main(int argc, char *argv[])
{
static unsigned char const codebook[] =
{
0x00, 0x1E, 0x2D, 0x33, 0x4B, 0x55, 0x66, 0x78,
0x87, 0x99, 0xAA, 0xB4, 0xCC, 0xD2, 0xE1, 0xFF
};
unsigned char c;
while (read(STDIN_FILENO, &c, 1)> 0)
{
unsigned char duo[2] =
{
codebook[ c >> 4 ],
codebook[ c & 0x0F ]
};
write(STDOUT_FILENO, duo, sizeof(duo));
}
return EXIT_SUCCESS;
}
Результаты, как и следовало ожидать, были ужасны:
time ./hamming < bigfile.txt > bigfile.ham
real 0m26.509s
user 0m2.370s
sys 0m24.087s
Другие решения
Я приблизился к улучшению на порядок, сделав 2 небольших изменения.
- Добавление
std::ios_base::synch_with_stdio(false)(нет заметной разницы, хотя влияние часто зависит от реализации) - Буферизация вывода перед записью (это имело наибольшее значение)
Обновленный код выглядит так:
int main()
{
//encodes a file using the (8,4) Hamming Code.
//usage : HammingEncode.out < inputFile > outputFile
unsigned char const codebook[] = { 0x00, 0x1E, 0x2D, 0x33, 0x4B, 0x55, 0x66, 0x78, 0x87, 0x99, 0xAA, 0xB4, 0xCC, 0xD2, 0xE1, 0xFF };
unsigned char in, nextByte;
unsigned char const leftMask = 0xF0, rightMask = 0x0F;
std::stringstream os;
std::ios_base::sync_with_stdio(false);
in = std::cin.get();
while (std::cin) {
nextByte = (in & leftMask) >> 4;
os.put(codebook[nextByte]);
nextByte = in & rightMask;
os.put(codebook[nextByte]);
in = std::cin.get();
}
std::cout << os.rdbuf();
}
Обновить
Я попробовал еще одну реализацию — используя базовый std::streambuf,
В моей системе исходный код 14 секунд обработать полную Библию короля Джеймса — около 4,3 МБ
Код в моей первоначальной попытке занял около 2,1 секунды обрабатывать.
Эта новая реализация заняла 0,71 секунды обрабатывать тот же документ.
int main()
{
//encodes a file using the (8,4) Hamming Code.
//usage : HammingEncode.out < inputFile > outputFile
unsigned char const codebook[] = { 0x00, 0x1E, 0x2D, 0x33, 0x4B, 0x55, 0x66, 0x78, 0x87, 0x99, 0xAA, 0xB4, 0xCC, 0xD2, 0xE1, 0xFF };
unsigned char in, nextByte;
unsigned char const leftMask = 0xF0, rightMask = 0x0F;
std::stringstream os;
std::ios_base::sync_with_stdio(false);
std::streambuf * pbuf = std::cin.rdbuf();
do {
in = pbuf->sgetc();
nextByte = (in & leftMask) >> 4;
os << codebook[nextByte];
nextByte = in & rightMask;
os << codebook[nextByte];
} while (pbuf->snextc() != EOF);
std::cout << os.rdbuf();
}
У iostreams C ++ плохое мнение о том, что он довольно неэффективен, хотя разные цифры указывают на то, что это скорее проблема качества реализации, чем недостатка iostream.
В любом случае, просто чтобы быть уверенным, что это не что-то вроде медленного жесткого диска, вы можете сравнить время выполнения, например, с.
cat file1 > file2
Конечно cat будет немного быстрее, так как это не удваивает размер ваших данных.
Затем попробуйте сравнить эффективность вашего кода со следующими:
#include <stdio.h>
#include <unistd.h>
int main()
{
unsigned char buffer[1024*1024]; // 1MB buffer should be enough
while (!eof(STDIN_FILENO)){
size_t len = read(STDIN_FILENO, &buffer[0], 1024*1024);
write(STDOUT_FILENO, &buffer[0], len);
write(STDOUT_FILENO, &buffer[0], len);
}
return 0;
}
РЕДАКТИРОВАТЬ:
Извините, это моя ошибка. Пытаться
#include <stdio.h>
#include <unistd.h>
int main()
{
unsigned char buffer[1024*1024]; // 1MB buffer should be enough
size_t len = read(STDIN_FILENO, &buffer[0], 1024*1024);
while(len > 0){
write(STDOUT_FILENO, &buffer[0], len);
write(STDOUT_FILENO, &buffer[0], len);
len = read(STDIN_FILENO, &buffer[0], 1024*1024);
}
return 0;
}
Если я правильно понимаю, для каждого прочитанного вами байта вы пишете 2 байта. Таким образом, выходной файл будет иметь двойной размер ввода. Если ваш ввод достаточно велик — общее время ввода / вывода (чтение + 2 * запись) будет значительным.
В кодировании Хаффмана это не так — поскольку вы обычно пишете меньше, чем читаете, и общее время ввода-вывода будет намного меньше.
РЕДАКТИРОВАТЬ:
Как Blorgbeard сказал, что это может быть разница в буферизации. C ++ также выполняет буферизацию, но буферы по умолчанию могут быть намного меньше, чем в Java. Кроме того, тот факт, что головка жесткого диска должна постоянно переключаться между чтением файла в одном месте и последующей записью в другом, существенно влияет на общую производительность ввода-вывода.
В любом случае кодирование должно выполняться фрагментами, чтобы обеспечить последовательное чтение и запись больших блоков.