Эффективное сравнение данных побайтно (с C ++)

Question

Есть ли более эффективный способ побайтного сравнения данных, чем использование сравнения оператор контейнера списка C ++?

Я должен сравнить [большой? 10 кБайт <размер <500 кБайт] объем данных для побайтной проверки целостности внешних устройств хранения. </p>

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

typedef boost::shared_ptr< list< unsigned char > > = contentPtr;
namespace boost::filesystem = fs;

contentPtr GetContent( fs::path filePath ){
 contentPtr actualContent (new list< unsigned char > );       
 // Read the file with a stream, put read values into actual content
return actualContent;

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

void CompareContent() throw( NotMatchingException() ){
 // this part is very fast, below 50ms
 contentPtr contentA = GetContent("/fileA");
 contentPtr contentB = GetContent("/fileB");
 // the next part takes about 2secs with a file size of ~64kByte
 if( *contentA != *contentB )
      throw( NotMatchingException() );
}

Моя проблема заключается в следующем:
С увеличением размера файла сравнение списков происходит очень медленно. При работе с файлами размером около 100 кБайт для сравнения содержимого потребуется до двух секунд. Увеличивается и уменьшается с размером файла ....

Есть ли более эффективный способ сделать это сравнение? Это проблема использованного контейнера?

Answer 1

Не используйте std::list Используйте std::vector.

std::list - это связанный список, элементы не гарантированно хранятся непрерывно.

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

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

Answer 2

Мой первый совет - профилировать ваш код .

Причина, по которой я это говорю, заключается в том, что независимо от того, насколько медленным является ваш код сравнения, я подозреваю, что время ввода-вывода вашего файла превосходит его. Вы не хотите тратить дни, пытаясь оптимизировать часть своего кода, которая занимает только 1% времени выполнения как есть.

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

Answer 3

Когда вы пишете, вы сравниваете содержимое двух файлов. Затем вы можете использовать файлы mapped_files для boost. Вам действительно не нужно читать весь файл. Вы можете читать «на лету» (оптимизированным способом, как это делает boost) и останавливаться, когда найдете первый неравный байт ...

Точно так же, как очень элегантное решение в ответе Кубби: http://www.cplusplus.com/forum/general/94032/ Обратите внимание, что чуть ниже он также добавляет некоторые тесты, которые ясно показывают, что это самый быстрый способ. Я просто немного перепишу его ответ и добавлю проверку нулевого размера файла, которая в противном случае выдает исключение, и вложу тест в функцию, чтобы извлечь выгоду из ранних возвратов:

#include <iostream>
#include <algorithm>
#include <boost/iostreams/device/mapped_file.hpp>
#include <boost/filesystem.hpp>

namespace io = boost::iostreams;
namespace fs = boost::filesystem;

bool files_equal(const std::string& path1, const std::string& path2)
{
    fs::path f1(path1);
    fs::path f2(path2);

    if (fs::file_size(f1) != fs::file_size(f2))
        return false;

    // zero-sized files cannot be opened with mapped_file_source
    // hence we consider all zero-sized files equal
    if (fs::file_size(f1) == 0)
        return true;

    io::mapped_file_source mf1(f1.string());
    io::mapped_file_source mf2(f1.string());
    return std::equal(mf1.data(), mf1.data() + mf1.size(), mf2.data());
}

int main()
{
    if (files_equal("test.1", "test.2"))
        std::cout << "The files are equal.\n";
    else
        std::cout << "The files are not equal.\n";
}

Answer 4

Если с содержимым этих файлов ничего не поделаешь (похоже, вы собираетесь разрешить их удаление с помощью shared_ptr в конце области действия CompareContent ()), почему бы не сравнить файлы с помощью итераторов, не создает никаких контейнеров вообще?

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

// compare files
if (equal(std::istreambuf_iterator<char>(local_f),
          std::istreambuf_iterator<char>(),
          std::istreambuf_iterator<char>(host_f)))
{
    // we're good: move table to OutPath, remove other files

РЕДАКТИРОВАТЬ: если вам нужно хранить содержимое, я думаю, что std::deque может быть несколько более эффективным, чем std::vector по причинам, объясненным в GOTW # 54 .. или нет - профилирование покажет. И все же, было бы необходимо загрузить только один из двух идентичных файлов в память - я бы прочитал один в deque и сравнил с istreambuf_iterator другого файла.

Answer 5

В интересах объективности в обсуждении memcmp-vs-equal я предлагаю следующую тестовую программу, чтобы вы могли сами убедиться, что, если таковые имеются, быстрее в вашей системе.Он также проверяет оператор ==.В моей системе (Borland C ++ 5.5.1 для Win32):

std :: равно: 1375 тактов
оператор ==: 1297 тактов
memcmp: 1297 тактов

Что происходит в вашей системе?

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

static char* buff ;
static vector<char> v0, v1 ;

static int const BufferSize = 100000 ;

static clock_t StartTimer() ;
static clock_t EndTimer (clock_t t) ;

int main (int argc, char** argv)
  {
  // Allocate a buffer
  buff = new char[BufferSize] ;

  // Create two vectors
  vector<char> v0 (buff, buff + BufferSize) ;
  vector<char> v1 (buff, buff + BufferSize) ;

  clock_t t ;

  // Compare them 10000 times using std::equal
  t = StartTimer() ;
  for (int i = 0 ; i < 10000 ; i++)
    if (!equal (v0.begin(), v0.end(), v1.begin()))
      cout << "Error in std::equal\n", exit (1) ;
  t = EndTimer (t) ;
  cout << "std::equal: " << t << " clock ticks\n" ;

  // Compare them 10000 times using operator==
  t = StartTimer() ;
  for (int i = 0 ; i < 10000 ; i++)
    if (v0 != v1)
      cout << "Error in operator==\n", exit (1) ;
  t = EndTimer (t) ;
  cout << "operator==: " << t << " clock ticks\n" ;

  // Compare them 10000 times using memcmp
  t = StartTimer() ;
  for (int i = 0 ; i < 10000 ; i++)
    if (memcmp (&v0[0], &v1[0], v0.size()))
      cout << "Error in memcmp\n", exit (1) ;
  t = EndTimer (t) ;
  cout << "memcmp: " << t << " clock ticks\n" ;

  return 0 ;
  }

static clock_t StartTimer()
  {
  // Start on a clock tick, to enhance reproducibility
  clock_t t = clock() ;
  while (clock() == t)
    ;
  return clock() ;
  }

static clock_t EndTimer (clock_t t)
  {
  return clock() - t ;
  }

Answer 6

Безумно использовать для сравнения что-либо кроме memcmp. (Если вы не хотите, чтобы это было еще быстрее, в этом случае вы можете захотеть закодировать его на ассемблере.)

Answer 7

std :: list является монументально неэффективным для элемента char - для каждого элемента предусмотрена дополнительная нагрузка, облегчающая вставку и удаление O (1), что на самом деле не то, что требуется для вашей задачи.

Если вам нужно использовать STL, то предпочтительнее std :: vector или предложенный итераторный подход, чем std :: list, но почему бы просто не прочитать данные в символ *, завернутый в какой-нибудь умный указатель по вашему выбору и использовать memcmp