*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

среда, 24 февраля 2010 г.

Простое понимание, что возвращает sizeof

Чтобы просто и понятно осознать, что возвращает sizeof в С++ для сложных составных типов (структур и классов) и сходу не вдаваться в детали выравнивания -- надо запомнить, что sizeof возвращает число, равное разности адресов двух соседних элементов массива, хранящего экземпляры вашего типа.

Печать контейнера с разделителями

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

Простейшее решение выглядит так:

#include <iostream>
#include <vector>

int main(int argc, char* argv[]) {
  int a[] = { 1, 2, 3, 4, 5 };
  std::vector<int> v(a, a + 5);

  for (int i = 0; i < v.size(); ++i) {
    std::cout << v[i];
    if (i < v.size() - 1)
      std::cout << ", ";
  }
  std::cout << std::endl;

  return 0;
}

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

#include <iostream>
#include <vector>

int main(int argc, char* argv[]) {
  int a[] = { 1, 2, 3, 4, 5 };
  std::vector<int> v(a, a + 5);

  for (std::vector<int>::const_iterator i = v.begin(); i != v.end(); ++i) {
    std::cout << *i;
    if (v.end() - i > 1)
      std::cout << ", ";
  }
  std::cout << std::endl;

  return 0;

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

#include <iostream>
#include <vector>

int main(int argc, char* argv[]) {
  int a[] = { 1, 2, 3, 4, 5 };
  std::vector<int> v(a, a + 5);

  typedef std::vector<int>::const_iterator iterator;
  for (iterator i = v.begin(); i != v.end(); ++i) {
    std::cout << *i;
    if (std::distance<iterator>(i, v.end()) > 1)
      std::cout << ", ";
  }
  std::cout << std::endl;
  return 0;
}

Шаблонный класс std::distance умеет рассчитывать расстояние между итераторами, и даже для тех, которые не поддерживают операции сложения и вычетания. Для таких итераторов будет делаться пошаговый обход от одного к другому для подсчета расстояния. На первый взгляд получается, что вычислительная сложность такого простого цикла будет уже не линейной, а квадратической. Еше надо таскать за собой описание типа дважды — чтобы создать итератор цикла и экземпляр std::distance. Например, Visual Studio 2008 требует указывать тип итератора для шаблона std::distance и не может "угадать" его из параметров (другие компиляторы могут вести себя иначе). Получается, на ровном месте навернули какую-то ерунду.

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

#include <iostream>
#include <vector>

int main(int argc, char* argv[]) {
  int a[] = { 1, 2, 3, 4, 5 };
  std::vector<int> v(a, a + 5);

  for (std::vector<int>::const_iterator i = v.begin(); i != v.end(); ++i) {
    std::cout << *i;
    if (i != --v.end())
      std::cout << ", ";
  }
  std::cout << std::endl;

  return 0;
}

Трюк с оператором "--" позволяет эффективно проверить на последний элемент контейнера.

суббота, 13 февраля 2010 г.

Проект поддержки библиотеки cmockery

Открыл проект для обкатки новых возможностей и "горячих" багфиксов для cmockery (замечательной библиотеки unit-тестирования для языка C) — cmockery staging.

В целом не планируется заменить основной репозиторий, но хочется несколько оживить процесс внесения новых патчей. Для начала я туда заправил свой мини-патч для вывода результатов тестирования похожим на Google Test образом, и несколько багфиксов.

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

Посты по теме:

четверг, 11 февраля 2010 г.

Формат 32nd (thirty seconds)

В работе с трейдинговыми системами наткнулся на необычный формат представления чисел, представляющих котировки ценных бумаг, в частности для государственных облигаций правительства США. Например, цена, представленная как 100-31 далеко не означает 100 долларов и 31 цент, или 100-127 вообще имеет мало смысла, так как в одном долларе всего 100 центов, а не 1000, и нет необходимости резервировать под дробную часть три знака после запятой.

Вся хитрость тут в том, что это не привычная десятичная запись. Например, 100-31 в десятичной форме равно 100.97265625, а 100-127 соответствует 100.40234375.

Итак, данный формат записи дробных чисел называется «thirty seconds» или 32nd. Для визуального удобства и явного отличия от десятичной формы вместо точки в качестве разделителя используется маленькая черточка. А само число имеет в общем следующий формат:

AAA.XXY

где AAA - это целая часть числа, имеющая такой же смысл, как и в десятичной системе. XX - это количество 1/32-х долей от дробной части, а Y - это количество восьмушек (1/8) в последней 1/32 доле. Несмотря на туманное описание, формула перевода числа AAA.XXY в формате 32nd в десятичный формат весьма проста:

D = AAA + (XX + Y * 1/8) * 1/32
или
D = AAA + XX * (1/32) + Y * (1/256)

то есть для числа 100-127 ААА=100, XX=12, Y=7, поэтому:

D = 100 + 12/32 + 7/256 = 100.40234375

Чтобы формула была корректной, XX может принимать значения только от 00 до 31, а Y от 0 до 7. Также при записи Y число 4 может быть заменено на +, а 0 на пробел. То есть 100-31 в полной форме записи равно 100-310, а 100-12+ эквивалентно 100-124.

Видно, что в трех дробных разрядах кодируется не 1000 долей, как в десятичной системе, а только 256 (32 * 8).

Итак, еще раз: если написано 100-12+, то это 100.39062500 в десятичной системе.

Формула обратного перевода из десятичного представления в формат 32nd не многим сложнее. Пусть D десятичное число:

A = TRUNC(D)
XX = TRUNC((D - A) * 32)
Y = ((D - A) * 32 - XX) * 8

TRUNC - это функция взятия целой части.

Если Y равно 0, то можно этот разряд не писать, а если 4, то можно заменить на +.

Компонента Y должна получиться обязательно целочисленной. Иначе, наличие дробной части у Y - это признак, того, что исходное десятичное число D не имеет отображения в формат 32nd (только 256 значений дробной части из всех 1000 возможных могут иметь соответствие в формате 32nd).

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

Формат странный, но знать его приходится.