Хорошие примеры, статьи и книги по сортировке

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

Хорошо, что при работе с веб-сервисами разумными способами являются такие технологии, как XML-RPC или JSON-RPC. Однако это не относится к встроенным устройствам, таким как смарт-карты. Для оптимизации использования памяти и достижения хорошей производительности вам необходимо использовать некоторые бинарные форматы.

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

Что вы порекомендовали бы?

UPD. Я использую C и С++ в Linux, но речь идет о информации об алгоритмах маршаллинга вообще.

Ответы

Ответ 1

Вы можете посмотреть ASN.1 как общее решение для сериализации. Есть бесплатные книги и бесплатные реализации: asn1c, a2c, snacc.

Но ASN.1 является огромным. Более простой protobuf или xdr может быть достаточно хорошим для вашей задачи.

Ответ 2

Google Протобуф

Чтобы начать, я различаю маршалинг и RPC (который использует маршалинг). Google Protobuf предоставляет лучшее решение для маршалинга по сети. Он имеет минимальную площадь и кодирует/декодирует с молниеносной скоростью.

Если вы все еще заинтересованы в том, как реализовать эффективную маршалинную проверку документации для кодирования protobuf.
Одним из примеров на странице кодирования является varint. Varint - это то, как protobuf кодирует целые числа без знака в двоичном формате. Varint оптимизирован для небольших чисел. например, 1 использует только один байт на проводе, а 300 использует два байта.
Конечно, разработчики протобуфа поняли, что часто мы используем целые числа в виде бит-масок и т.д. Таким образом, они также предоставляют целочисленный тип данных, который всегда равен четырем байтам (в этом случае маски с установленными битами msb не потребляют лишнее пространство).

Существует также полная документация о том, как реализовать RPC с protobufs.

Ответ 3

Вы также можете посмотреть на Messagepack (http://msgpack.org). Он утверждает, что он в 4 раза быстрее, чем Protobuf. Кроме того, в отличие от Protobuf, эта библиотека поддерживает наследование.

Ответ 4

В вашем вопросе о том, какая платформа/язык, на который вы нацеливаетесь, не так много контекста.

Самыми популярными были (есть?) DCOM и CORBA. Существует встроенная CORBA..... вы можете использовать что-то вроде TAO из (библиотеки ACE TAO)

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

Ответ 5

сериализация/сортировка и древовидная структура данных вместе звучат как довольно большая проблема. Вот некоторые аспекты того, как я начну его решать:

  • рассмотрим кодирование данных. 4 байта для int transfer или transfer as ascii?
  • рассмотрим, нужно ли переносить целые данные или просто синхронизировать между двумя структурами данных дерева.
  • каждый бит данных должен знать, где он находится в древовидной структуре. Идентификация бит данных очень сильно поможет в этой проблеме.
  • рассмотрите, что нужно передать?
    • только данные внутри узлов дерева?
    • изменяется на древовидную структуру?
    • все дерево?
    • местоположение/идентификатор данных?
  • идентификационные данные
    • использовать пути от корня до дерева node?
    • использовать поддеревья?
    • использовать простые узлы данных
    • идентификационные элементы внутри дерева node?
  • рассмотрите, как публиковать данные в дереве
    • может быть интерфейс записи, который выдает все данные?
    • Вы можете рекурсивно пройти все данные с помощью алгоритма
    • Есть ли указатели внутри данных, которые не могут быть легко переданы?

Очевидно, что некоторые библиотеки, такие как goob protobuf, могут помочь...

Ответ 6

Возможно, вы захотите перейти с Thrift.