Какой самый быстрый способ найти, если массив байтовых массивов содержит другой байтовый массив? - PullRequest
Новая
       18

Какой самый быстрый способ найти, если массив байтовых массивов содержит другой байтовый массив?

2 голосов
/ 10 июня 2009

У меня есть код, который очень медленно работает. Я знал, что так будет и сейчас. По сути, я читаю файлы из нескольких каталогов. Имена файлов меняются, а данные - нет. Чтобы определить, прочитал ли я файл, я хэширую его байты и сравниваю его со списком хэшей уже обработанных файлов. В каждом каталоге содержится около 1000 файлов, и выяснение того, что нового в каждом каталоге, занимает около минуты (и затем начинается обработка). Вот основной код: 

public static class ProgramExtensions
{
    public static byte[] ToSHA256Hash(this FileInfo file)
    {
        using (FileStream fs = new FileStream(file.FullName, FileMode.Open))
        {
            using (SHA256 hasher = new SHA256Managed())
            {
                return hasher.ComputeHash(fs);
            }
        }
    }
    public static string ToHexString(this byte[] p)
    {

        char[] c = new char[p.Length * 2 + 2];

        byte b;

        c[0] = '0'; c[1] = 'x';

        for (int y = 0, x = 2; y < p.Length; ++y, ++x)
        {
            b = ((byte)(p[y] >> 4));

            c[x] = (char)(b > 9 ? b + 0x37 : b + 0x30);

            b = ((byte)(p[y] & 0xF));

            c[++x] = (char)(b > 9 ? b + 0x37 : b + 0x30);
        }

        return new string(c);

    }
}

class Program
{
    static void Main(string[] args)
    {
        var allFiles = new DirectoryInfo("c:\\temp").GetFiles("*.*");

        List<string> readFileHashes = GetReadFileHashes();

        List<FileInfo> filesToRead = new List<FileInfo>();

        foreach (var file in allFiles)
        {
            if (readFileHashes.Contains(file.ToSHA256Hash().ToHexString()))
                filesToRead.Add(file);
        }

        //read new files
    }
}

Есть ли способ ускорить процесс?

Ответы [ 7 ]

8 голосов
/ 10 июня 2009

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

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

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

  • Либо выполняйте двоичное сравнение с ранним прерыванием, когда первый байт отличается (экономит чтение всего файла, что может быть очень значительным улучшением, если ваши файлы обычно имеют большой размер, любой алгоритм хеширования будет читать весь файл. то, что первый байт отличается, спасает вас от прочтения остальной части файла). Если ваш список файлов поиска, вероятно, содержит много файлов одинакового размера, поэтому вам, скорее всего, придется выполнить двоичное сравнение с несколькими файлами, вместо этого рассмотрите:

  • хэширование в блоках по 1 МБ каждый. Сначала проверяйте первый блок только по предварительно вычисленному хешу 1-го блока в вашем поиске. Сравнивайте только 2-й блок, если 1-й блок одинаков, в большинстве случаев сохраняет чтение за 1-м блоком для разных файлов. Обе эти опции действительно стоят усилий, когда ваши файлы большие.

Я сомневаюсь, что изменение самого алгоритма хеширования (например, первая проверка с использованием CRC, как предложено) имело бы какое-либо существенное значение. Ваше узкое место, скорее всего, связано с дисковым вводом-выводом, а не с процессором, поэтому избежание дискового ввода-вывода принесет вам наибольшее улучшение. Но, как всегда в исполнении, do measure.

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

1 голос
/ 10 июня 2009

  • Используйте структуру данных для вашего хранилища readFileHashes, которая имеет эффективные возможности поиска (хеширование или двоичный поиск). Я думаю, что HashSet или TreeSet послужат вам лучше здесь.

  • Используйте соответствующую функцию контрольной суммы (хэш-суммы). SHA256 - криптографический хеш, который, вероятно, излишний. CRC менее затратен в вычислительном отношении, изначально предназначен для улавливания непреднамеренных / случайных изменений (ошибок при передаче), но допускает изменения, которые спроектированы / предназначены для скрытия. Каковы различия между файлами, которые вы сканируете?

    См. http://en.wikipedia.org/wiki/List_of_checksum_algorithms#Computational_costs_of_CRCs_vs_Hashes

    Будет ли работать действительно простая контрольная сумма с помощью выборки (например, контрольная сумма = (первые 10 байтов и последние 10 байтов))?

1 голос
/ 10 июня 2009
  • Создать список файлов
  • Сортировка списка по размеру файла
  • Исключить файлы с уникальными размерами из списка
  • Теперь сделайте хэширование (быстрый хеш может также улучшить производительность)
0 голосов
/ 10 июня 2009

обновлено: Определенно НЕ проверяйте размер файла. Если ваша версия ОС позволяет использовать FileInfo.LastWriteTime

Я реализовал нечто подобное для собственного компилятора / упаковщика проекта. У нас более 8 тыс. Файлов, поэтому мы храним последние измененные даты и хэш-данные в базе данных SQL. затем при последующих запусках мы сначала запрашиваем дату изменения для любого конкретного файла, и только затем для хеш-данных ... таким образом, мы вычисляем только новые хеш-данные для тех файлов, которые, по-видимому, были изменены ...

.net имеет способ проверить дату последнего изменения в классе FileInfo. Я предлагаю вам проверить это. РЕДАКТИРОВАТЬ: вот ссылка LastWriteTime

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

0 голосов
/ 10 июня 2009

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

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

Так что все дело в компромиссе с временной памятью (дисковой памятью ввода / вывода). Вы должны найти способ между чтением всех файлов в группе в память и сравнением их побайтно (высокая потребность в памяти, быстрый последовательный доступ, но возможно чтение большого количества данных) и чтением файлов побайтно и сравнением только последнего байта чтение (нехватка памяти, медленный произвольный доступ, чтение только необходимых данных). Кроме того, если группы очень велики, сравнение файлов побайтно становится медленнее - сравнение одного байта из n файлов - операция O (n) - и может оказаться более эффективным сначала вычислить значения хеша, а затем сравнить только хеш значения.

0 голосов
/ 10 июня 2009

Ваше описание проблемы все еще недостаточно ясно.

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

Возможно, вы захотите попробовать найти время модификации, которое не изменяется при изменении имени файла:

http://msdn.microsoft.com/en-us/library/ms724320(VS.85,loband).aspx

Или вы можете отслеживать папку на наличие новых изменений файла:

http://www.codeguru.com/forum/showthread.php?t=436716

0 голосов
/ 10 июня 2009

Сначала я бы сделал быструю проверку хэша CRC, так как это дешевле. если CRC не совпадает, продолжайте с более «надежным» хэш-тестом, таким как SHA

...