Создание контрольной суммы на графе объектов

Ответ 1

Что вы думаете об этом подходе:

• перемещаться по графику, а объект foreach в графе создает стандартный хэш-код с использованием этого алгоритма (но исключает элементы ссылочного типа, представляющие узлы на графике).
• Добавить каждый хэш-код в целочисленный список
• Преобразование целочисленного списка в массив байтов
• Создайте хэш в массиве байтов, используя MD5, CRC или аналогичный

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

хэширования

Учитывая, что вы предпочитаете скорость над точностью и что хэш-код с int для каждого элемента оставляет много места для предотвращения коллизий, выбор алгоритма hashcode кажется правильным. Исключение ссылочных типов, которые участвуют в графике, означает, что мы отбрасываем некоторую информацию; подробнее см. ниже.

Улучшение хеша node

Идея не учитывать другие узлы, связанные с node, мы хешируем правильно, но, может быть, мы можем сделать лучше, чем просто выбросить всю эту информацию? Мы не хотим учитывать хэш-коды других узлов (они тоже будут хэшировать), но мы отбрасываем информацию, предоставленную графами здесь: хэш-код для node с внутренними данными X подключен для N других узлов не должно быть одинаковым для node с данными X, связанными с M другими узлами.

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

Агрегатирование хэш-кодов

Создание списка хэш-кодов было бы подходом среднего уровня между суммированием хэш-кодов в одном long (очень быстрым и сохраняющим некоторую дополнительную информацию по суммированию в int) и созданием списка хэш-кодов, зависящих от общего числа порядок элементов на графике. Если вы ожидаете большого количества элементов на графике, то суммирование может быть более подходящим (я попытался бы это сделать первым и посмотреть, достаточно ли он достаточно коллизии); если граф не имеет много элементов (скажем, < 1000), тогда я сначала попытаюсь использовать метод общего порядка. Не забудьте выделить достаточное количество памяти для списка (или просто использовать массив) при его создании; вы уже знаете его окончательную длину, чтобы увеличить скорость.

Создание хеша фиксированного размера

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

Улучшение конечного хеш-качества

После получения этого "финального" хэша я добавлю или добавлю к нему количество элементов хэшированного графика в виде строки с шестнадцатеричным размером фиксированного размера, потому что:

• Это может помочь уменьшить коллизии (насколько это зависит от характера графиков)
• Мы уже знаем количество элементов на графике (мы просто хэшируем каждый из них), поэтому он выполняет операцию O (1)

Определение полного порядка

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

Для борьбы с этим вам необходимо обработать узлы в графике в определенном порядке. Это может быть порядок, который легко получить из структуры данных узлов (например, как обход предлога на дереве) и/или другую информацию (например, имена классов или node типы для каждого node, node идентификаторы if такие существуют и т.д.).

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

Ответ 2

Вместо двоичной сериализации вы можете использовать http://code.google.com/p/protobuf-net/, а затем вычислить криптографический хэш. Протобуф считается более компактным, чем Bin Ser (см., например, http://code.google.com/p/protobuf-net/wiki/Performance).

Я добавлю это, учитывая, что вам не нужно сериализовать. Было бы лучше использовать Reflection и "перемещаться" по объектам, вычисляющим ваш хэш (так же, как различные сериализаторы "пересекают" ваш объект). См. Например Использование отражения в С# для получения свойств вложенного объекта

После долгих размышлений и слуха о том, что сказал @Jon, я могу сказать, что моя "вторичная" идея (с использованием Reflection) ОЧЕНЬ ОЧЕНЬ ОЧЕНЬ сложна, если вы не хотите потратить неделю на запись парсера объектов. Да, это выполнимо... Но какое представление вы бы дали данным перед вычислением Хэша? Чтобы быть ясным:

two strings
"A"
"B"

ясно "A", "B"!= "AB", "". Но MD5 ( "A" ) в сочетании с MD5 ( "B" ) == MD5 ( "AB" ) в сочетании с MD5 (""). Вероятно, лучше всего добавить длину (так, используя нотацию Pascal/BSTR)

И null значения? Что такое "сериализованная" ценность? Еще один вопрос. Ясно, что если вы сериализуете строку как длину + строку (поэтому для решения предыдущей проблемы), вы можете сериализовать нуль просто как "null" (без длины)... И объекты? Вы добавили бы идентификатор типа объекта? Было бы лучше. В противном случае объекты переменной длины могут создавать те же беспорядки, что и строки.

Используя BinaryFormatter (или даже protobuf-net), вам действительно не нужно сохранять где-то сериализованный объект, потому что они поддерживают потоковое... Пример

public class Hasher : Stream
{
    protected readonly HashAlgorithm HashAlgorithm;

    protected Hasher(HashAlgorithm hash)
    {
        HashAlgorithm = hash;
    }

    public static byte[] GetHash(object obj, HashAlgorithm hash)
    {
        var hasher = new Hasher(hash);

        if (obj != null)
        {
            var bf = new BinaryFormatter();
            bf.Serialize(hasher, obj);
        }
        else
        {
            hasher.Flush();
        }

        return hasher.HashAlgorithm.Hash;
    }

    public override bool CanRead
    {
        get { throw new NotImplementedException(); }
    }

    public override bool CanSeek
    {
        get { throw new NotImplementedException(); }
    }

    public override bool CanWrite
    {
        get { return true; }
    }

    public override void Flush()
    {
        HashAlgorithm.TransformFinalBlock(new byte[0], 0, 0);
    }

    public override long Length
    {
        get { throw new NotImplementedException(); }
    }

    public override long Position
    {
        get
        {
            throw new NotImplementedException();
        }
        set
        {
            throw new NotImplementedException();
        }
    }

    public override int Read(byte[] buffer, int offset, int count)
    {
        throw new NotImplementedException();
    }

    public override long Seek(long offset, SeekOrigin origin)
    {
        throw new NotImplementedException();
    }

    public override void SetLength(long value)
    {
        throw new NotImplementedException();
    }

    public override void Write(byte[] buffer, int offset, int count)
    {
        HashAlgorithm.TransformBlock(buffer, offset, count, buffer, offset);
    }
}

static void Main(string[] args)
{
    var list = new List<int>(100000000);

    for (int i = 0; i < list.Capacity; i++)
    {
        list.Add(0);
    }

    Stopwatch sw = Stopwatch.StartNew();
    var hash = Hasher.GetHash(list, new MD5CryptoServiceProvider());
    sw.Stop();
    Console.WriteLine(sw.ElapsedMilliseconds);
}

Я определяю класс Hasher, который получает сериализацию объекта (часть за раз) и вычисляет хэш в режиме "потоковой передачи". Использование памяти - O (1). Очевидно, что время O (n) (с n "размером" сериализованного объекта).

Если вы хотите использовать protobuf (но имейте в виду, что для сложных объектов он должен быть помечен его атрибутами (или с атрибутами WCF или...))

public static byte[] GetHash<T>(T obj, HashAlgorithm hash)
{
    var hasher = new Hasher(hash);

    if (obj != null)
    {
        ProtoBuf.Serializer.Serialize(hasher, obj);
        hasher.Flush();
    }
    else
    {
        hasher.Flush();
    }

    return hasher.HashAlgorithm.Hash;
}

Единственные "большие" различия заключаются в том, что protobuf не Flush поток, поэтому мы должны это сделать и что он ИСТИННО хочет, чтобы на него был наложен корневой объект, а не простой "объект".

Ох... и для вашего вопроса:

Как я должен сериализовать объект? Это должен быть быстрым и не слишком много потреблять Память. Также он должен всегда надежно быть сериализованы таким же образом. Если я использую сериализация .NET по умолчанию я могу действительно убедитесь, что созданный двоичный файл поток всегда один и тот же, если acutal данные одинаковы? Я в этом сомневаюсь.

List<int> l1 = new List<int>();

byte[] bytes1, bytes2;

using (MemoryStream ms = new MemoryStream())
{
    new BinaryFormatter().Serialize(ms, l1);
    bytes1 = ms.ToArray();
}

l1.Add(0);
l1.RemoveAt(0);

using (MemoryStream ms = new MemoryStream())
{
    new BinaryFormatter().Serialize(ms, l1);
    bytes2 = ms.ToArray();
}

Debug.Assert(bytes1.Length == bytes2.Length);

Скажем так: Debug.Assert не удастся. Это потому, что List "сохраняет" некоторый внутренний статус (например, версию). Это очень сложно для двоичного сериализации и сравнения. Вам будет лучше использовать "программируемый" сериализатор (например, proto-buf). Вы говорите ему, какие свойства/поля сериализуются, и он сериализует их.

Итак, каков будет альтернативный способ сериализации, который не займет много времени?

Прото-buf... или DataContractSerializer (но это довольно медленно). Как вы можете себе представить, нет никакой серебряной пули для сериализации данных.

Ответ 3

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

Один из способов сделать это - определить отношение между объектами, всегда "<" или " > ", если объекты не содержат одинакового содержимого (в этом случае объекты "==" в соответствии с отношением) [примечание: это не учитывает тот факт, что дуги из идентичных объектов содержимого могут позволять их различать как "<" или " > "; если это имеет значение для вас, также определите канонический порядок на дугах] Теперь перечислим все объекты в графе и отсортируем по этому отношению. Обработайте объекты в отсортированном порядке и составьте их хэши.

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

Ответ 4

Здесь подход, который я использую:

1. Сериализовать с помощью ServiceStack TypeSerializer

Это сериализует объекты для JSV, которые я смутно описываю как "JSON с меньшим количеством кавычек", поэтому он меньше и подразумевается (автором) примерно в 5 раз быстрее, чем сериализация JSON. Основное преимущество над BinaryFormatter и Protobuff (которое в противном случае было бы моим первым выбором) заключается в том, что вам не нужно обойти аннотирование или описание всех типов, которые вы хотите сериализовать. Я ленив, и это просто работает с любым poco.

2. Вычислить хеш MD5

Это для меня "хороший" подход с точки зрения производительности и характеристик столкновения. Если бы я слишком улучшил его, я бы, скорее всего, пошел с MurmurHash3, который имеет аналогичные характеристики столкновения, такие как MD5, но намного быстрее. Он не подходит для криптографических целей, но, похоже, это не является обязательным требованием. Единственная причина, по которой я пошел с MD5, - это испечь в BCL, и это достаточно быстро для моих целей.

Здесь все в качестве метода расширения:

using System.Text;
using System.Security.Cryptography;
using ServiceStack.Text;

public static byte[] GenerateHash(this object obj) {
    var s = TypeSerializer.SerializeToString(obj);
    return MD5.Create().ComputeHash(Encoding.UTF8.GetBytes(s));
}

Объекты, которые я использую с этим, относительно малы (обычно не более нескольких сотен символов), и я никогда не сталкивался с проблемами конфликтов. YMMV.

Ответ 5

Как отметила Ира Бакстер, вы хотите перестроить (отсортировать) объекты на графике в определенном каноническом порядке. Затем вы можете перейти к вычислению хэшей и уменьшить (как в "map-reduce" ) их до одного хэша.

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

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

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

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

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

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

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