Для того, что удалить пробелы в конце строк в файле можно воспользоваться стандартным диалогом Replace в Visual Studio:
В строку Find what нужно ввести :Zs#$, а Replace with оставить пустой. Не забудьте поставить галку Use Regular expressions. Далее можно нажать Replace All.
Данную операцию можно включить в макрос, который запускается при сохранении файлов, чтобы удаление происходило автоматически. Это позволит сократить количество бесполезных изменений кода в репозитарии и на ревью кода.
понедельник, 26 декабря 2011 г.
Remove trailing spaces
Posted by
Kirill V. Lyadvinsky
обновлено:
2015-12-16T11:39:35Z
Labels:
programming
,
VisualStudio
вторник, 20 декабря 2011 г.
Первичное интервью
или что вас ждет на собеседовании на вакансию программист С++
Набралось информации о том, как проходит первичное интервью на вакансию C++ разработчика в тех или иных компаниях.
Posted by
Kirill V. Lyadvinsky
обновлено:
2017-06-08T10:20:40Z
среда, 9 ноября 2011 г.
Как написать программу на C++ для Android.
Часть 3: Используем С++ класс и STL
Часть 1 | Часть 2 | Часть 3 | Часть 4 | Часть 5 (Mac OS)
В предыдущей части мы убедились, что из Java программы можно довольно просто вызывать C++ функции. В этой статье рассмотрим более сложный пример с C++ классами. На C++ будем считать статистику по картинке получаемой со встроенной видеокамеры устройства (насколько я знаю, все Android устройства имеют хотя бы одну видеокамеру).
В предыдущей части мы убедились, что из Java программы можно довольно просто вызывать C++ функции. В этой статье рассмотрим более сложный пример с C++ классами. На C++ будем считать статистику по картинке получаемой со встроенной видеокамеры устройства (насколько я знаю, все Android устройства имеют хотя бы одну видеокамеру).
Posted by
Kirill V. Lyadvinsky
обновлено:
2022-05-17T09:06:16Z
вторник, 1 ноября 2011 г.
Многопроцессорный HAL в Windows
Работая с виртуалками постоянно забываю что-то настроить важное в VirtualBox и ставлю систему с дефолтными настройками, т.е. процессор в виртуальной машине имеет только одно ядро. Потом, даже если поставить больше ядер у процессора, Windows XP и Vista не увидят их, т.к. используют однопроцессорный HAL. Проблему можно решить с помощью утилиты devcon. В командной строке набираем:
После перезагрузки Windows начинает видеть много ядер.
devcon sethwid @ROOT\ACPI_HAL\0000 := +acpiapic_mp !acpiapic_up devcon update c:\windows\inf\hal.inf acpiapic_mp
После перезагрузки Windows начинает видеть много ядер.
Posted by
Kirill V. Lyadvinsky
обновлено:
2011-11-01T09:43:36Z
Labels:
programming
,
VirtualBox
,
Windows
понедельник, 31 октября 2011 г.
Наводнение в Тайланде
Вчера SMART отрапортовал, что мой Seagate на 1.5 Gb стремительно умирает и нужно срочно забэкапить данные. «Не проблема», подумал я и пошел смотреть где купить новый HDD. Поискав аналог на 1.5—2 Gb я был сильно удивлен ценами на жесткие диски. Экземпляры, которые стоили около 4000 руб., стали стоить около 8000 руб. Поиск по новостям выявил, что скачущий валютный курс вовсе не причем. Оказалось, что 25% мировых производственных мощностей заблокированы наводнением в Тайланде, где расположены заводы основных производителей (пруфлинк).
Новости не очень радостные в том плане, что цены уже выросли и ещё в том, что и дальше будут расти. Для читателей эта новость означает, что 3-я часть цикла статей про Android задерживается до покупки нового HDD и восстановления системы. Надеюсь, что на это уйдет не больше недели.
P.S. 5-ти летняя гарантия Seagate на жесткие диски оказалась пшиком. На сайте написано, что гарантия действует, но из России оформить возврат мне не удалось, поэтому Seagate покупать не советую.
Posted by
Kirill V. Lyadvinsky
обновлено:
2011-11-07T07:39:43Z
четверг, 20 октября 2011 г.
Как написать программу на C++ для Android.
Часть 2: Используем простейшую С++ функцию.
Часть 1 | Часть 2 | Часть 3 | Часть 4 | Часть 5 (Mac OS)
В предыдущей части я рассказал как настроить окружение для разработки программ на C++ под Android. В этой части попробуем создать простейший проект с примитивным C++ кодом.
В предыдущей части я рассказал как настроить окружение для разработки программ на C++ под Android. В этой части попробуем создать простейший проект с примитивным C++ кодом.
Posted by
Kirill V. Lyadvinsky
обновлено:
2016-02-09T10:15:38Z
суббота, 15 октября 2011 г.
Как написать программу на C++ для Android.
Часть 1: настраиваем среду разработки.
Часть 1 | Часть 2 | Часть 3 | Часть 4 | Часть 5 (Mac OS)
Google Developers Day, который я анонсировал, завершился. Несмотря на то, что доклады оставляли желать лучшего (в отличии от прошлого года), на Android секции было столько народу, что приходилось сидеть в проходах. Это говорит о том, что существует немалый интерес к этой теме. Видео с докладами обещали выложить на YouTube, но так и не выложили.
Все это совпало с выходом Ubuntu 11.10, которую хотелось посмотреть. Итогом стала идея написать несколько статей на тему разработки на C++ под Android. В этой части, надеюсь, не последней, я опишу как с нуля настроить окружение для разработки. Любителям Windows могу сообщить, что там процесс настройки среды разработки очень похож и местами даже проще, а уж код и вовсе не будет отличаться.
Итак, устанавливаем Ubuntu 11.10:
Google Developers Day, который я анонсировал, завершился. Несмотря на то, что доклады оставляли желать лучшего (в отличии от прошлого года), на Android секции было столько народу, что приходилось сидеть в проходах. Это говорит о том, что существует немалый интерес к этой теме. Видео с докладами обещали выложить на YouTube, но так и не выложили.
Все это совпало с выходом Ubuntu 11.10, которую хотелось посмотреть. Итогом стала идея написать несколько статей на тему разработки на C++ под Android. В этой части, надеюсь, не последней, я опишу как с нуля настроить окружение для разработки. Любителям Windows могу сообщить, что там процесс настройки среды разработки очень похож и местами даже проще, а уж код и вовсе не будет отличаться.
Итак, устанавливаем Ubuntu 11.10:
Posted by
Kirill V. Lyadvinsky
обновлено:
2017-01-25T11:06:59Z
вторник, 11 октября 2011 г.
Как купить новый стандарт C++
Уже много кто написал, что вышел долгожданный стандарт C++. Почему-то часто упоминается, что его можно купить за 18$. Это неправда. Новый стандарт ISO/IEC 14882:2011 можно купить на сайте ISO за 352 швейцарских франка (примерно 387 долларов США).
Что касается $18, которые везде упоминаются, то Саттер у себя в блоге написал, что ANSI опубликовала старый стандарт и продает его за эти деньги (на самом деле, можно убедиться, что сайте ANSI указана цена $30). Новый стандарт ANSI уже продает за $403.
Удачных покупок!
Что касается $18, которые везде упоминаются, то Саттер у себя в блоге написал, что ANSI опубликовала старый стандарт и продает его за эти деньги (на самом деле, можно убедиться, что сайте ANSI указана цена $30). Новый стандарт ANSI уже продает за $403.
Удачных покупок!
Posted by
Kirill V. Lyadvinsky
обновлено:
2013-09-09T11:55:22Z
четверг, 6 октября 2011 г.
Windows 8 работает на процессорах ARM
Posted by
Kirill V. Lyadvinsky
обновлено:
2011-10-05T20:03:29Z
понедельник, 26 сентября 2011 г.
Куда пойти осенью в Москве
На этой неделе Microsoft приглашает на очередной Microsoft Innovation Day. Зарегистрироваться можно по ссылке. Надеюсь там услышать из первых рук небольшой into для Windows 8 и Visual Studio 11, которые уже доступны для скачивания на портале MSDN. Также интересно послушать про новинки в SQL Server 11 "Denali".
Google также организует традиционный Google Developer Day в Москве 10 октября. Регистрация кажется ещё идет. Тут рассчитываю услышать про TV от Google и как планируется двигать Android в сторону устройств с HD экранами.
Google также организует традиционный Google Developer Day в Москве 10 октября. Регистрация кажется ещё идет. Тут рассчитываю услышать про TV от Google и как планируется двигать Android в сторону устройств с HD экранами.
Posted by
Kirill V. Lyadvinsky
обновлено:
2016-02-09T04:58:05Z
Labels:
разное
понедельник, 5 сентября 2011 г.
XML Schema в SQL Server
Я уже как-то писал про то, что в SQL можно читать элементы XML прямо из столбца с соответствующим типом. Для того, чтобы SQL сервер контролировал правильность этого поля, используется специальный язык описания правил — XML Schema. Рассмотрим простейший пример такой схемы (сегодня все примеры для Microsoft SQL Server 2008):
<xsd:schema xmlns:xsd="http://www.w3.org/2001/XMLSchema"> <xsd:complexType name="PointType"> <xsd:attribute name="X" type="xsd:int" /> <xsd:attribute name="Y" type="xsd:int" /> <xsd:attribute name="Z" type="xsd:int" use="optional" /> </xsd:complexType> <xsd:element name="Point" type="PointType" /> </xsd:schema>Данная схема разрешает только XML следующих видов:
<Point X="100" Y="100" /> <!-- или --> <Point X="100" Y="100" Z="500"/>При этом атрибуты X и Y являются обязательными, а Z — опциональным. Для атрибутов допускается только тип int. В MS SQL Server создание подобной схемы будет выглядеть так:
CREATE XML SCHEMA COLLECTION test AS ' <xsd:schema xmlns:xsd="http://www.w3.org/2001/XMLSchema"> <xsd:complexType name="PointType"> <xsd:attribute name="X" type="xsd:int" /> <xsd:attribute name="Y" type="xsd:int" /> <xsd:attribute name="Z" type="xsd:int" use="optional" /> </xsd:complexType> <xsd:element name="Point" type="PointType" /> </xsd:schema> ' GOДалее можно попробовать создать xml с данной схемой (ниже используется переменная для того, чтобы этот код можно было легко скопировать и попробовать, но тоже самое верно и для столбца в таблице):
-- объявляем переменную @xml с ранее созданной схемой test DECLARE @xml xml(test) -- заполняем тестовыми данными SET @xml='<Point X="10" Y="10" />' -- делаем выборку SELECT @xml.value('(/Point/@X)[1]','int'), @xml.value('(/Point/@Y)[1]','int')При попытке записать невалидные данные SQL Server выдаст ошибку:
-- пробуем задать невалидный XML SET @xml='<WrongPoint X="10" Y="10" />' -- получаем ошибку -- XML Validation: Declaration not found for element 'WrongPoint'. Location: /*:WrongPoint[1]Таким образом, наличие схемы гарантирует валидность данных и нет необходимости обрабатывать возможные ошибки самостоятельно.
Ссылки:
Posted by
Kirill V. Lyadvinsky
обновлено:
2017-06-08T10:04:37Z
понедельник, 15 августа 2011 г.
Автоматический выбор типа
В библиотеке Boost есть набор средств для выбора типов. Например, можно выбрать наименьший тип с не менее чем N бит:
typedef boost::int_t<N>::least my_int_t;Или тип, который точно сможет уместить в себя все числа в диапазоне от 0 до V:
typedef boost::int_max_value_t<V>::last my_int_t;Или ещё целый беззнаковый тип, который может работать с числами от 0 до V и, при этом, самый быстрый на данной платформе:
typedef boost::uint_value_t<V>::fast my_uint_t;
Полный список можно посмотреть в документации.
Posted by
Kirill V. Lyadvinsky
обновлено:
2015-12-16T11:42:29Z
пятница, 12 августа 2011 г.
ЭЛВИС-НеоТек нанимает на работу
Компания ЭЛВИС-НеоТек приглашает на работу разработчиков.
Posted by
Kirill V. Lyadvinsky
обновлено:
2017-06-08T09:59:42Z
вторник, 9 августа 2011 г.
ternary operator (?:)
Интересный факт: тернарный оператор (?:) может стоять не только в правой части выражения, но и в левой. Пример:
int a = 5; int b = 10; (a > b ? a : b) = 100; // большему из a и b присвоим 100 cout << "a=" << a << " b=" << b << endl; // result will be: a=5 b=100
Posted by
Kirill V. Lyadvinsky
обновлено:
2015-12-16T11:43:05Z
Labels:
Cplusplus
пятница, 5 августа 2011 г.
Безопасны ли безопасные функции в Windows?
Visual C++ при компиляции ANSI функций работы со строками постоянно выдает предупреждение о том, что есть более безопасные версии и использовать нужно именно их. Однако, по набору параметров они могут вовсе не отличаться, что не позволяет заметить разницу на этапе компиляции. Например, имеем следующий код:
Если почитать документацию более внимательно, то находим следующее небольшое замечание:
Это означает, что теперь после каждого строкового параметра нужно передавать размер буфера, т. е. код должен выглядеть следующим образом:
В этой ситуации плохо то, что функция стала работать хуже, чем небезопасный оригинал. Я ни в коем случае не агитирую за использование опасных фукнций, просто нужно учитывать, что механическая замена одних на другие приводит к ошибкам.
int main(int argc, char *argv[]) { const char* stLine = "s=Media Presentation\n"; std::vector<char> param(1024); _snscanf( stLine, 20, "s=%[^\r\n]", ¶m[0] ); return 0; }Код этот отлично работает, но при компиляции выдается предупреждение, что стоит использовать фунуцию _snscanf_s. Смотрим документацию и на первый взгляд отличий никаких. Хорошо, меняем на _snscanf_s:
_snscanf_s( stLine, 20, "s=%[^\r\n]", ¶m[0] );В результате программа отлично компилируется теперь уже без предупреждений, но падает в процессе выполнения. В чем же дело?
Если почитать документацию более внимательно, то находим следующее небольшое замечание:
The buffer size parameter is required with the type field characters c, C, s, S, and [. For more information, see scanf Type Field Characters.
Это означает, что теперь после каждого строкового параметра нужно передавать размер буфера, т. е. код должен выглядеть следующим образом:
_snscanf_s( stLine, 20, "s=%[^\r\n]", ¶m[0], param.size() );
В этой ситуации плохо то, что функция стала работать хуже, чем небезопасный оригинал. Я ни в коем случае не агитирую за использование опасных фукнций, просто нужно учитывать, что механическая замена одних на другие приводит к ошибкам.
Posted by
Kirill V. Lyadvinsky
обновлено:
2015-12-16T11:43:52Z
вторник, 26 июля 2011 г.
Зачем в checked_delete столько кода?
Если посмотреть на реализацию функции checked_delete в библиотеке Boost, то можно увидеть следующий код:
Для чего нужны такие сложности и почему упрощение приведет к регрессу? Дело вот в чем: чтобы корректно удалить объект, его тип должен быть полностью определен (complete type). Проверяется это в несколько этапов:
Ссылки:
template<class T> inline void checked_delete(T * x) { // intentionally complex - simplification causes regressions typedef char type_must_be_complete[ sizeof(T)? 1: -1 ]; (void) sizeof(type_must_be_complete); delete x; }
Для чего нужны такие сложности и почему упрощение приведет к регрессу? Дело вот в чем: чтобы корректно удалить объект, его тип должен быть полностью определен (complete type). Проверяется это в несколько этапов:
- Вызов оператора sizeof для неопределенного типа приведет к ошибке компиляции.
- На случай, если sizeof вернет 0 (в случает нестандартного расширения в компиляторе), создается массив с отрицательной длинной, что запрещено во всех компиляторах.
- Вторая строка нужна для компилятора Metrowerks CodeWarrior, который не будет инстанцировать первый typedef, пока он не используется.
- Преобразование результата sizeof к void нужно, чтобы избежать предупреждений во время компиляции.
Ссылки:
Posted by
Kirill V. Lyadvinsky
обновлено:
2017-06-08T09:55:50Z
вторник, 21 июня 2011 г.
operator& (address-of)
C++ позволяет переопределять в своих классах ряд операторов, и в их числе — оператор взятия адреса. Попробуем воспользоваться этой возможностью:
Теперь, если попробовать взять адрес экземпляра класса nonaddressable, то получим ошибку:
Для разрешения этой ситуации в C++ существует крайне кривой механизм. Можно написать следующий код:
struct useless_type {}; class nonaddressable { useless_type operator&() const; };Пример класса, где переопределен operator& — это CComPtr.
Теперь, если попробовать взять адрес экземпляра класса nonaddressable, то получим ошибку:
nonaddressable* xpe = &x; /* error */Ошибка может возникнуть по двум причинам: во-первых, в примере оператор взятия адреса приватный, во-вторых — он возвращает экземпляр useless_type, а вовсе не указатель на nonaddressable.
Для разрешения этой ситуации в C++ существует крайне кривой механизм. Можно написать следующий код:
nonaddressable* xp = reinterpret_cast<nonaddressable*>( &reinterpret_cast<char&>( x ) );Стандарт гарантирует, что это будет работать, но выглядит все равно ужасно. К счастью, в библиотеке Boost существует обертка над этим механизмом — функция boost::addressof, которая учитывает возможные const-volatile. Пользоваться просто:
nonaddressable* xp = boost::addressof(x);
Posted by
Kirill V. Lyadvinsky
обновлено:
2014-02-17T06:06:10Z
четверг, 16 июня 2011 г.
Ошибка сети в Empathy
С 10 июня Empathy, стандартный мессанджер в Ubuntu 11.04, начал выдавать сообщение Ошибка сети (или Network error в английской версии) при попытке подключения аккаунта ICQ. Странно, что поиск в Google выдает кучу решений, которые не работают в версии 11.04.
Проблема описана в баг-трэкере Empathy (ошибка №795932). Если то, что выдает поиск Google не помогает, то решается путем написания в консоли следующих команд:
Проблема описана в баг-трэкере Empathy (ошибка №795932). Если то, что выдает поиск Google не помогает, то решается путем написания в консоли следующих команд:
user@home:~$ mc-tool list | grep icqВыдается что-то типа haze/icq/_31102050910. То, что выдалось подставляем в следующие команды:
user@home:~$ mc-tool update haze/icq/_31102050910 string:encryption=no_encryption user@home:~$ mc-tool update haze/icq/_31102050910 bool:use-clientlogin=0Перезапускаем Empathy и все работает. Если нет, то отписываемся в баг-трэкере.
Posted by
Kirill V. Lyadvinsky
обновлено:
2011-06-16T19:38:16Z
понедельник, 23 мая 2011 г.
Partial template specialization for pointers to __stdcall functions
Если мы хотим написать частичную специализацию шаблона, например, для указателя на функцию, то обычно пишем что-то вроде следующего кода:
Ссылки по теме:
template<typename F> class TFunction; template<typename R, typename T0> class TFunction<R(*)(T0)> { };Здесь мы пытаемся специализировать шаблон TFunction для указателя на функцию одного аргумента. Далее имеем два указателя:
typedef bool (*my_function_f)(int); // (1) typedef bool (__stdcall *my_function_f2)(int); // (2)Для (1) специализация, которая написана выше вполне подходит, а вот для (2) — нет. По умолчанию, предполагается что функция использует соглашение вызова __cdecl. Если мы хотим передавать указатели на функции с соглашением вызова __stdcall, то необходимо для этого случая написать отдельную специализацию:
template<typename R, typename T0> class TFunction<R(__stdcall *)(T0)> { };Кажется, этого достаточно. Однако, при компиляции кода под x64 процессоры ключевое слово __stdcall, которое обозначает порядок вызова функций, игнорируется. Обычно это незаметно, но если вы пытаетесь написать частичную специализацию шаблона, то проявляются неприятные эффекты. А именно, две специализации, которые написаны выше, получаются абсолютно одинаковыми, что приводит к ошибке компиляции. Решением будет отключить компиляцию второй специализации, например, так:
#ifndef _M_X64 template<typename R, typename T0> class TFunction<R(__stdcall *)(T0)> { }; #endifМакрос _M_X64 предопределен для x64 процессоров.
Ссылки по теме:
Posted by
Kirill V. Lyadvinsky
обновлено:
2014-02-17T06:06:47Z
Labels:
Cplusplus
,
template
,
VisualStudio
среда, 18 мая 2011 г.
Пап, что ты делаешь на работе
Как объяснить маленькому ребенку (4-5 лет), что папа/мама на работе разрабатывают софт? У меня возникла только одна аналогия для этого возраста — папа пишет книжки на специальном волшебном языке для компьютеров... Ну да, компы их читают и делают то, что там написано. Волшебный язык, конечно, знают не все люди... Книжки бывают разные: в играх много картинок, а есть скучные книжки-программы — совсем без картинок. Кстати, при загрузке Ubuntu пишется сначала куча текста, а потом уже появляется красивый интерфейс (ага, комп дочитал до нужного места, в книжках тоже не сразу понятно где находятся герои), что подтверждает аллегорию.
Понятно, что мой вариант не окончательное описание для википедии, в реальной жизни он эволюционирует с возрастом и по мере накопления опыта — от примитивного до более сложного. Не потому, что дети идиоты, а потому что им не интересны до какого-то возраста сложные объяснения, на каждом этапе свой уровень абстракции.
А у вас возникала необходимость объяснить чем вы занимаетесь?
Понятно, что мой вариант не окончательное описание для википедии, в реальной жизни он эволюционирует с возрастом и по мере накопления опыта — от примитивного до более сложного. Не потому, что дети идиоты, а потому что им не интересны до какого-то возраста сложные объяснения, на каждом этапе свой уровень абстракции.
А у вас возникала необходимость объяснить чем вы занимаетесь?
Posted by
Kirill V. Lyadvinsky
обновлено:
2011-05-20T04:48:07Z
Labels:
разное
пятница, 13 мая 2011 г.
sum of pairs
Вы когда нибудь пробовали получить сумму элементов контейнера, который хранит элементы типа std::pair? Если да, то вы заметили, что std::pair не определяет operator+. На помощь приходит новый стандарт, в котором пишем лямбда-функцию, или библиотека boost::lambda с которой получаем следующий прекрасный но сложноперевариваемый код:
#include <deque> #include <boost/lambda/bind.hpp> #include <boost/lambda/construct.hpp> template<typename T> void summarize() { typedef std::pair<T, T> pt_t; std::deque<pt_t> xs; using namespace boost::lambda; // fill xs with stuff pt_t res = std::accumulate( xs.begin(), xs.end(), std::make_pair(T(),T()), bind( constructor<pt_t>(), bind( std::plus<T>(), bind(&pt_t::first,_1), bind(&pt_t::first,_2) ), bind( std::plus<T>(), bind(&pt_t::second,_1), bind(&pt_t::second,_2) ) ) ); }
Posted by
Kirill V. Lyadvinsky
обновлено:
2014-02-17T06:07:07Z
суббота, 23 апреля 2011 г.
Find sum of elements in the array
Наткнулся на задачу, которую предлагают в Yandex на собеседовании:
Остальные варианты пока нам не интересны, их можно посмотреть тут (кстати, в последнем варианте бесконечный цикл). Зачем тут лишняя сортировка ясно сразу — предполагается, что точности double не хватит для расчетов. Ведь если суммировать числа от больших к меньшим, то сумма быстро растёт, и, когда мы дойдём до маленьких чисел, они могут быть денормализованы с огромной ошибкой.
Чтобы оценить о каком порядке ошибки идет речь посмотрим на следующий пример:
Итого, простое суммирование чисел в худшем случае имеет ошибку, которая растет пропорционально \(n\), и среднеквадратичную ошибку, которая растет как \(\sqrt n\) на случайных данных.
Однако, хочется суммировать без ошибок и при этом делать это не за линейно-логарифмическое время \(O(n\log n)\), а за линейное \(O(n)\). Это нам позволяет алгоритм автора стандарта IEEE 754, Уильяма Мортона Кэхэна (Kahan). Он разработал алгоритм для минимизации ошибки при сложении чисел в представлении IEEE 754, который был назван в его честь. Предыдущий пример с учетом алгоритма Кэхэна:
При суммировании с компенсацией в худшем случае ошибка не зависит от \(n\), поэтому большие числа могут быть сложены с ошибкой, которая зависит только от точности типа с плавающей точкой. Видимо, это то решение, которое ожидается от кандидата.
Ниже приведены три варианта суммирования чисел с плавающей точкой (предполагается, что числа в массиве только положительные).
double sum1(std::vector<double>& v) { if (v.empty()) { return 0.0; } for(size_t i = 0; i < v.size() - 1; ++i) { std::sort(v.begin()+i, v.end()); v[i+1] += v[i]; } return v.back(); }<...>
Остальные варианты пока нам не интересны, их можно посмотреть тут (кстати, в последнем варианте бесконечный цикл). Зачем тут лишняя сортировка ясно сразу — предполагается, что точности double не хватит для расчетов. Ведь если суммировать числа от больших к меньшим, то сумма быстро растёт, и, когда мы дойдём до маленьких чисел, они могут быть денормализованы с огромной ошибкой.
Чтобы оценить о каком порядке ошибки идет речь посмотрим на следующий пример:
const double x = 0.01; double s = 1000000000.; // initial sum for (int i = 0; i < 10000; ++i ) { s = s + x; } const double e = 1000000100. - s; std::cout << e << std::endl;На моей машине он выдает результат: 9.53674e-05
Итого, простое суммирование чисел в худшем случае имеет ошибку, которая растет пропорционально \(n\), и среднеквадратичную ошибку, которая растет как \(\sqrt n\) на случайных данных.
Однако, хочется суммировать без ошибок и при этом делать это не за линейно-логарифмическое время \(O(n\log n)\), а за линейное \(O(n)\). Это нам позволяет алгоритм автора стандарта IEEE 754, Уильяма Мортона Кэхэна (Kahan). Он разработал алгоритм для минимизации ошибки при сложении чисел в представлении IEEE 754, который был назван в его честь. Предыдущий пример с учетом алгоритма Кэхэна:
const double x = 0.01; double c = 0; // keep error here, initial error is zero double s = 1000000000.; // initial sum for (int i = 0; i < 10000; ++i ) { const double y = x - c; const double t = s + y; c = (t - s) - y; // Beware eagerly optimising compilers! s = t; } const double e = 1000000100. - s; std::cout << e << std::endl;В итоге выдает 0.
При суммировании с компенсацией в худшем случае ошибка не зависит от \(n\), поэтому большие числа могут быть сложены с ошибкой, которая зависит только от точности типа с плавающей точкой. Видимо, это то решение, которое ожидается от кандидата.
Posted by
Kirill V. Lyadvinsky
обновлено:
2022-11-11T14:21:04Z
Labels:
Cplusplus
,
programming
понедельник, 11 апреля 2011 г.
Autocomplete или как измерить расстояние Левенштейна
На днях встал вопрос сделать функцию для подсказки завершения слов. Самый простой вариант — сравнивать введенную часть слова с первыми буквами слов из словаря и выдавать все слова, у которых совпадает начало. На маленьких словарях это работает, в целом, неплохо, но люди делают опечатки и хотелось бы предлагать исправленные варианты слов, т. е. нужно выдавать похожие слова. Про меру «похожести» последовательностей 0–1 ещё в 1965 году упомянул советский математик Владимир Иосифович Левенштейн, что позже дало имя расстоянию Левенштейна.
Расстояние Левенштейна — это минимальное количество операций вставки, замены и удаления одного символа, необходимых для превращения одной строки в другую.
Это уже почти то, что нужно, но в расстоянии Левенштейна перестановки не учитываются. На наше счастье товарищ Дамерау (Damerau) не только добавил к указанным операциями ещё одну — перестановку двух соседних символов, но и утверждал, что 80% ошибок при наборе текста дают как раз указанные четыре операции. Расстояние, которое учитывает эти операции назвали, как можно догадаться, расстоянием Дамерау–Левенштейна. Результаты этих работ теперь используются не только в бесполезных спеллчекерах, которые убивают грамотность, но и в исследованиях ДНК.
Мне же эти исследования пригодились для решения поставленной задачи. Ниже показана функция на C++, которая вычисляет расстояние Дамерау–Левенштейна:
int damerauLevenshteinDistance( const std::vector<char>& a, const std::vector<char>& b ) { const int a_size = static_cast<int>( a.size() ); const int b_size = static_cast<int>( b.size() ); const int INF = a_size + b_size; std::vector<std::vector<int> > H( a.size()+2, std::vector<int>( b.size()+2 ) ); H[0][0] = INF; for ( int i = 0; i <= a_size; ++i ) { H[i+1][1] = i; H[i+1][0] = INF; } for ( int j = 0; j <= b_size; ++j ) { H[1][j+1] = j; H[0][j+1] = INF; } const int alphabet_size = std::numeric_limits<char>::max(); std::vector<char> DA( alphabet_size ); for ( int d = 0; d < alphabet_size; ++d ) DA[d] = 0; for ( int i = 1; i <= a_size; ++i ) { size_t DB = 0; for ( int j = 1; j <= b_size; ++j ) { const int i1 = DA[ b[j-1] ]; const int j1 = DB; const int d = (a[i-1]==b[j-1]) ? 0 : 1; if ( d == 0 ) DB = j; H[i+1][j+1] = std::min( std::min(H[i][j]+d, H[i+1][j]+1), std::min(H[i][j+1]+1, H[i1][j1] + (i-i1-1) + 1 + (j-j1-1) ) ); } DA[ a[i-1] ] = i; } return H[a.size()+1][b.size()+1]; }Тема последних дней — поиск Муаммара Каддафи. Расчет расстояния от этого слова (Gadaffi) до всех слов английского словаря размером 329380 слов занимает порядка 2 секунд на моем домашнем Core2Duo 2.13GHz, т. е. функция работает довольно быстро.
Поскольку в моем словаре слов на несколько порядков меньше и выбирает их пользователь, то моя задача оказалась решена. Однако, существуют и другие варианты хранения словарей, например, префиксное дерево (trie), в котором каждый узел хранит первые буквы строк, потом пары букв и так далее. См. картинку из Википедии:
В таком дереве поиск подходящих окончаний происходит очень быстро. Этот метод также применяется в спелчекерах (например, встречается сотовых телефонах).
Стоит отметить, что автозавершение слов — это встроенная функция Windows и разработчикам предлагаются интерфейсы IAutoComplete и IACList, пользоваться которыми, на первый взгляд, оказалось не очень удобно и они реализуют самый простой вариант автозавершения, что тоже не подходит.
Ссылки по теме:
- SimMetrics — an open source extensible library of Similarity or Distance Metrics, e.g. Levenshtein Distance, L2 Distance, Cosine Similarity, Jaccard Similarity etc.
- Damerau–Levenshtein distance
- Trie
- GNU Aspell is a Free and Open Source spell checker
- Implementing an autocompleting Combobox
- Using Autocomplete in Windows
Posted by
Kirill V. Lyadvinsky
обновлено:
2016-12-29T06:02:14Z
Labels:
algorithms
,
Cplusplus
,
Levenshtein distance
,
programming
,
trie
вторник, 29 марта 2011 г.
Нам нужно нарисовать семь красных линий, все они должны быть строго перпендикулярны...
Петров пришел во вторник на совещание. Ему там вынули мозг, разложили по блюдечкам и стали есть, причмокивая и вообще выражая всяческое одобрение. Начальник Петрова, Недозайцев, предусмотрительно раздал присутствующим десертные ложечки. И началось.Отсюда.
— Коллеги, — говорит Морковьева, — перед нашей организацией встала масштабная задача. Нам поступил на реализацию проект, в рамках которого нам требуется изобразить несколько красных линий. Вы готовы взвалить на себя эту задачу?
— Конечно, — говорит Недозайцев. Он директор, и всегда готов взвалить на себя проблему, которую придется нести кому-то из коллектива. Впрочем, он тут же уточняет: — Мы же это можем?
Начальник отдела рисования Сидоряхин торопливо кивает:
— Да, разумеется. Вот у нас как раз сидит Петров, он наш лучший специалист в области рисования красных линий. Мы его специально пригласили на совещание, чтобы он высказал свое компетентное мнение.
— Очень приятно, — говорит Морковьева. — Ну, меня вы все знаете. А это — Леночка, она специалист по дизайну в нашей организации.
Леночка покрывается краской и смущенно улыбается. Она недавно закончила экономический, и к дизайну имеет такое же отношение, как утконос к проектированию дирижаблей.
— Так вот, — говорит Морковьева. — Нам нужно нарисовать семь красных линий. Все они должны быть строго перпендикулярны, и кроме того, некоторые нужно нарисовать зеленым цветом, а еще некоторые — прозрачным. Как вы считаете, это реально?
— Нет, — говорит Петров.
— Давайте не будем торопиться с ответом, Петров, — говорит Сидоряхин. — Задача поставлена, и ее нужно решить. Вы же профессионал, Петров. Не давайте нам повода считать, что вы не профессионал.
— Видите ли, — объясняет Петров, — термин «красная линия» подразумевает, что цвет линии — красный. Нарисовать красную линию зеленым цветом не то, чтобы невозможно, но очень близко к невозможному…
— Петров, ну что значит «невозможно»? — спрашивает Сидоряхин.
— Я просто обрисовываю ситуацию. Возможно, есть люди, страдающие дальтонизмом, для которых действительно не будет иметь значения цвет линии, но я не уверен, что целевая аудитория вашего проекта состоит исключительно из таких людей.
— То есть, в принципе, это возможно, мы правильно вас понимаем, Петров? — спрашивает Морковьева.
Петров осознает, что переборщил с образностью.
— Скажем проще, — говорит он. — Линию, как таковую, можно нарисовать совершенно любым цветом. Но чтобы получилась красная линия, следует использовать только красный цвет.
— Петров, вы нас не путайте, пожалуйста. Только что вы говорили, что это возможно.
Петров молча проклинает свою болтливость.
— Нет, вы неправильно меня поняли. Я хотел лишь сказать, что в некоторых, крайне редких ситуациях, цвет линии не будет иметь значения, но даже и тогда — линия все равно не будет красной. Понимаете, она красной не будет! Она будет зеленой. А вам нужна красная.
Наступает непродолжительное молчание, в котором отчетливо слышится тихое напряженное гудение синапсов.
— А что если, — осененный идеей, произносит Недозайцев, — нарисовать их синим цветом?
— Все равно не получится, — качает головой Петров. — Если нарисовать синим — получатся синие линии.
Опять молчание. На этот раз его прерывает сам Петров.
— И я еще не понял… Что вы имели в виду, когда говорили о линиях прозрачного цвета?
Морковьева смотрит на него снисходительно, как добрая учительница на отстающего ученика.
— Ну, как вам объяснить?.. Петров, вы разве не знаете, что такое «прозрачный»?
— Знаю.
— И что такое «красная линия», надеюсь, вам тоже не надо объяснять?
— Нет, не надо.
— Ну вот. Вы нарисуйте нам красные линии прозрачным цветом.
Петров на секунду замирает, обдумывая ситуацию.
— И как должен выглядеть результат, будьте добры, опишите пожалуйста? Как вы себе это представляете?
— Ну-у-у, Петро-о-ов! — говорит Сидоряхин. — Ну давайте не будем… У нас что, детский сад? Кто здесь специалист по красным линиям, Морковьева или вы?
— Я просто пытаюсь прояснить для себя детали задания…
— Ну, а что тут непонятного-то?.. — встревает в разговор Недозайцев. — Вы же знаете, что такое красная линия?
— Да, но…
— И что такое «прозрачный», вам тоже ясно?
— Разумеется, но…
— Так что вам объяснять-то? Петров, ну давайте не будем опускаться до непродуктивных споров. Задача поставлена, задача ясная и четкая. Если у вас есть конкретные вопросы, так задавайте.
— Вы же профессионал, — добавляет Сидоряхин.
— Ладно, — сдается Петров. — Бог с ним, с цветом. Но у вас там еще что-то с перпендикулярностью?..
— Да, — с готовностью подтверждает Морковьева. — Семь линий, все строго перпендикулярны.
— Перпендикулярны чему? — уточняет Петров.
Морковьева начинает просматривать свои бумаги.
— Э-э-э, — говорит она наконец. — Ну, как бы… Всему. Между собой. Ну, или как там… Я не знаю. Я думала, это вы знаете, какие бывают перпендикулярные линии, — наконец находится она.
— Да конечно знает, — взмахивает руками Сидоряхин. — Профессионалы мы тут, или не профессионалы?..
— Перпендикулярны могут быть две линии, — терпеливо объясняет Петров. — Все семь одновременно не могут быть перпендикулярными по отношению друг к другу. Это геометрия, 6 класс.
Морковьева встряхивает головой, отгоняя замаячивший призрак давно забытого школьного образования. Недозайцев хлопает ладонью по столу:
— Петров, давайте без вот этого: «6 класс, 6 класс». Давайте будем взаимно вежливы. Не будем делать намеков и скатываться до оскорблений. Давайте поддерживать конструктивный диалог. Здесь же не идиоты собрались.
— Я тоже так считаю, — говорит Сидоряхин.
Петров придвигает к себе листок бумаги.
— Хорошо, — говорит он. — Давайте, я вам нарисую. Вот линия. Так?
Морковьева утвердительно кивает головой.
— Рисуем другую… — говорит Петров. — Она перпендикулярна первой?
— Ну-у…
— Да, она перпендикулярна.
— Ну вот видите! — радостно восклицает Морковьева.
— Подождите, это еще не все. Теперь рисуем третью… Она перпендикулярна первой линии?..
Вдумчивое молчание. Не дождавшись ответа, Петров отвечает сам:
— Да, первой линии она перпендикулярна. Но со второй линией она не пересекается. Со второй линией они параллельны.
Наступает тишина. Потом Морковьева встает со своего места и, обогнув стол, заходит Петрову с тыла, заглядывая ему через плечо.
— Ну… — неуверенно произносит она. — Наверное, да.
— Вот в этом и дело, — говорит Петров, стремясь закрепить достигнутый успех. — Пока линий две, они могут быть перпендикулярны. Как только их становится больше…
— А можно мне ручку? — просит Морковьева.
Петров отдает ручку. Морковьева осторожно проводит несколько неуверенных линий.
— А если так?..
Петров вздыхает.
— Это называется треугольник. Нет, это не перпендикулярные линии. К тому же их три, а не семь.
Морковьева поджимает губы.
— А почему они синие? — вдруг спрашивает Недозайцев.
— Да, кстати, — поддерживает Сидоряхин. — Сам хотел спросить.
Петров несколько раз моргает, разглядывая рисунок.
— У меня ручка синяя, — наконец говорит он. — Я же просто чтобы продемонстрировать…
— Ну, так может, в этом и дело? — нетерпеливо перебивает его Недозайцев тоном человека, который только что разобрался в сложной концепции и спешит поделиться ею с окружающими, пока мысль не потеряна. — У вас линии синие. Вы нарисуйте красные, и давайте посмотрим, что получится.
— Получится то же самое, — уверенно говорит Петров.
— Ну, как то же самое? — говорит Недозайцев. — Как вы можете быть уверены, если вы даже не попробовали? Вы нарисуйте красные, и посмотрим.
— У меня нет красной ручки с собой, — признается Петров. — Но я могу совершенно…
— А что же вы не подготовились, — укоризненно говорит Сидоряхин. — Знали же, что будет собрание…
— Я абсолютно точно могу вам сказать, — в отчаянии говорит Петров, — что красным цветом получится точно то же самое.
— Вы же сами нам в прошлый раз говорили, — парирует Сидоряхин, — что рисовать красные линии нужно красным цветом. Вот, я записал себе даже. А сами рисуете их синей ручкой. Это что, красные линии по-вашему?
— Кстати, да, — замечает Недозайцев. — Я же еще спрашивал вас про синий цвет. Что вы мне ответили?
Петрова внезапно спасает Леночка, с интересом изучающая его рисунок со своего места.
— Мне кажется, я понимаю, — говорит она. — Вы же сейчас не о цвете говорите, да? Это у вас про вот эту, как вы ее называете? Перпер-чего-то-там?
— Перпендикулярность линий, да, — благодарно отзывается Петров. — Она с цветом линий никак не связана.
— Все, вы меня запутали окончательно, — говорит Недозайцев, переводя взгляд с одного участника собрания на другого. — Так у нас с чем проблемы? С цветом или с перпендикулярностью?
Морковьева издает растерянные звуки и качает головой. Она тоже запуталась.
— И с тем, и с другим, — тихо говорит Петров.
— Я ничего не могу понять, — говорит Недозайцев, разглядывая свои сцепленные в замок пальцы. — Вот есть задача. Нужно всего-то семь красных линий. Я понимаю, их было бы двадцать!.. Но тут-то всего семь. Задача простая. Наши заказчики хотят семь перпендикулярных линий. Верно?
Морковьева кивает.
— И Сидоряхин вот тоже не видит проблемы, — говорит Недозайцев. — Я прав, Сидоряхин?.. Ну вот. Так что нам мешает выполнить задачу?
— Геометрия, — со вздохом говорит Петров.
— Ну, вы просто не обращайте на нее внимания, вот и все! — произносит Морковьева.
Петров молчит, собираясь с мыслями. В его мозгу рождаются одна за другой красочные метафоры, которые позволили бы донести до окружающих сюрреализм происходящего, но как назло, все они, облекаясь в слова, начинаются неизменно словом «Блять!», совершенно неуместным в рамках деловой беседы.
Устав ждать ответа, Недозайцев произносит:
— Петров, вы ответьте просто — вы можете сделать или вы не можете? Я понимаю, что вы узкий специалист и не видите общей картины. Но это же несложно — нарисовать какие-то семь линий? Обсуждаем уже два часа какую-то ерунду, никак не можем прийти к решению.
— Да, — говорит Сидоряхин. — Вы вот только критикуете и говорите: «Невозможно! Невозможно!» Вы предложите нам свое решение проблемы! А то критиковать и дурак может, простите за выражение. Вы же профессионал!
Петров устало изрекает:
— Хорошо. Давайте я нарисую вам две гарантированно перпендикулярные красные линии, а остальные — прозрачным цветом. Они будут прозрачны, и их не будет видно, но я их нарисую. Вас это устроит?
— Нас это устроит? — оборачивается Морковьева к Леночке. — Да, нас устроит.
— Только еще хотя бы пару — зеленым цветом, — добавляет Леночка. — И еще у меня такой вопрос, можно?
— Да, — мертвым голосом разрешает Петров.
— Можно одну линию изобразить в виде котенка?
Петров молчит несколько секунд, а потом переспрашивает:
— Что?
— Ну, в виде котенка. Котеночка. Нашим пользователям нравятся зверюшки. Было бы очень здорово…
— Нет, — говорит Петров.
— А почему?
— Нет, я конечно могу нарисовать вам кота. Я не художник, но могу попытаться. Только это будет уже не линия. Это будет кот. Линия и кот — разные вещи.
— Котенок, — уточняет Морковьева. — Не кот, а котенок, такой маленький, симпатичный. Коты, они…
— Да все равно, — качает головой Петров.
— Совсем никак, да?.. — разочарованно спрашивает Леночка.
— Петров, вы хоть дослушали бы до конца, — раздраженно говорит Недозайцев. — Не дослушали, а уже говорите «Нет».
— Я понял мысль, — не поднимая взгляда от стола, говорит Петров. — Нарисовать линию в виде котенка невозможно.
— Ну и не надо тогда, — разрешает Леночка. — А птичку тоже не получится?
Петров молча поднимает на нее взгляд и Леночка все понимает.
— Ну и не надо тогда, — снова повторяет она.
Недозайцев хлопает ладонью по столу.
— Так на чем мы остановились? Что мы делаем?
— Семь красных линий, — говорит Морковьева. — Две красным цветом, и две зеленым, и остальные прозрачным. Да? Я же правильно поняла?
— Да, — подтверждает Сидоряхин прежде, чем Петров успевает открыть рот.
Недозайцев удовлетворенно кивает.
— Вот и отлично… Ну, тогда все, коллеги?.. Расходимся?.. Еще вопросы есть?..
— Ой, — вспоминает Леночка. — У нас еще есть красный воздушный шарик! Скажите, вы можете его надуть?
— Да, кстати, — говорит Морковьева. — Давайте это тоже сразу обсудим, чтобы два раза не собираться.
— Петров, — поворачивается Недозайцев к Петрову. — Мы это можем?
— А какое отношение ко мне имеет шарик? — удивленно спрашивает Петров.
— Он красный, — поясняет Леночка.
Петров тупо молчит, подрагивая кончиками пальцев.
— Петров, — нервно переспрашивает Недозайцев. — Так вы это можете или не можете? Простой же вопрос.
— Ну, — осторожно говорит Петров, — в принципе, я конечно могу, но…
— Хорошо, — кивает Недозайцев. — Съездите к ним, надуйте. Командировочные, если потребуется, выпишем.
— Завтра можно? — спрашивает Морковьева.
— Конечно, — отвечает Недозайцев. — Я думаю, проблем не будет… Ну, теперь у нас все?.. Отлично. Продуктивно поработали… Всем спасибо и до свидания!
Петров несколько раз моргает, чтобы вернуться в объективную реальность, потом встает и медленно бредет к выходу. У самого выхода Леночка догоняет его.
— А можно еще вас попросить? — краснея, говорит Леночка. — Вы когда шарик будете надувать… Вы можете надуть его в форме котенка?..
Петров вздыхает.
— Я все могу, — говорит он. — Я могу абсолютно все. Я профессионал.
Posted by
Kirill V. Lyadvinsky
обновлено:
2016-04-06T07:14:25Z
Labels:
разное
понедельник, 21 марта 2011 г.
Работа с XML в SQL запросах
В современных проектах XML встречается довольно часто. Несмотря на избыточность, этот язык разметки данных стал очень популярным из-за своей универсальности. Если нам нужно распарсить какой-то конфиг файл на XML, то практически в каждом языке программирования есть удобная библиотека. В C++ мне нравится Xerces-C++ своей кроссплатформенностью, однако, готов согласиться, если кто-то скажет, что это, местами, не самый удобный инструмент.
Сейчас я хочу рассмотреть сценарий работы с данными в виде XML, которые могут храниться в базе данных. Современные серверы БД поддерживают, в разной степени, тип данных XML. Я буду приводить примеры в MySql, т. к. под рукой в данный момент есть только он. Например, у нас есть таблица xmltest:
Если мы хотим получить атрибут элемента, то показываем это символом @:
Стоит отметить, что для разных реализаций SQL синтаксис запроса будет отличаться, например, в MS SQL Server последний запрос будет выглядеть так:
Поля XML можно не только выводить, но и использовать в условиях поиска, например:
В такой маленькой статье невозможно рассмотреть все возможности работы с XML в SQL запросах, поэтому даю список ресурсов, с которыми стоит познакомиться:
Сейчас я хочу рассмотреть сценарий работы с данными в виде XML, которые могут храниться в базе данных. Современные серверы БД поддерживают, в разной степени, тип данных XML. Я буду приводить примеры в MySql, т. к. под рукой в данный момент есть только он. Например, у нас есть таблица xmltest:
CREATE TABLE `xmltest` ( `conf` varchar(500) CHARACTER SET utf8 COLLATE utf8_unicode_ci NOT NULL ) ENGINE=MyISAM DEFAULT CHARSET=latin1Далее, будем считать, что в поле conf хранятся данные каждого пользователя системы следующего вида:
<Root> <CoreOptions> <Option type="str" value="test" /> </CoreOptions> <UserOptions> <Favorites> <Page id="1">http://www.codeatcpp.com</Page> <Page id="2">http://www.google.com</Page> <Page id="3">http://www.yandex.ru</Page> <Page id="4">http://www.stackoverflow.com</Page> </Favorites> </UserOptions> </Root>Итак, можно загрузить все данные пользователей и каждый конфиг разобрать своим любимым парсером XML, но что, если мы всего лишь хотим посмотреть сколько у каждого пользователя любимых сайтов? Это можно узнать за один SQL запрос используя язык XQuery+XPath:
SELECT ExtractValue(conf, 'count(/Root[1]/UserOptions[1]/Favorites[1]/Page)') FROM `xmltest`Этот запрос для каждого пользователя выдаст количество элементов Page в поле conf. Поскольку в XML элементы не уникальны и могут повторятся, то указываем в квадратных скобках, что нужен первый по порядку элемент. Если это не указать, то запрос вернет набор элементов, как в случае с Page.
Если мы хотим получить атрибут элемента, то показываем это символом @:
SELECT ExtractValue(conf, '/Root[1]/UserOptions[1]/Favorites[1]/Page[1]/@id') FROM `xmltest`Такой запрос выдаст идентификатор первой страницы для каждого пользователя.
Стоит отметить, что для разных реализаций SQL синтаксис запроса будет отличаться, например, в MS SQL Server последний запрос будет выглядеть так:
SELECT conf.value('/Root[1]/UserOptions[1]/Favorites[1]/Page[1]/@id', 'int') FROM xmltest
Поля XML можно не только выводить, но и использовать в условиях поиска, например:
SELECT ExtractValue(conf, '/Root[1]/CoreOptions[1]/Option[1]/@value') FROM `xmltest` WHERE ExtractValue(conf, 'count(/Root[1]/UserOptions[1]/Favorites[1]/Page)') > 0Такой запрос выдаст параметр Option из раздела CoreOptions для всех пользователей, у которых есть закладки.
В такой маленькой статье невозможно рассмотреть все возможности работы с XML в SQL запросах, поэтому даю список ресурсов, с которыми стоит познакомиться:
- Методы типа данных XML в MS SQL Server.
- XML функции сервера MySQL.
- xpathtester.com — сайт, где можно проверить свои XPath запросы.
- Вопросы и ответы по использованию XML в SQL запросах.
Posted by
Kirill V. Lyadvinsky
обновлено:
2015-12-16T11:48:40Z
четверг, 10 марта 2011 г.
Visual Studio 2010 SP1
Наконец-то вышел релиз SP1 для Visual Studio 2010. До этого приходилось пользоваться бэтой из-за страшных багов, вроде утечки памяти при использовании std::vector<std::string>. При этом Intel Parallel Studio не хотела работать с бэтой и суппорт Интела не хотел ничего делать... теперь им не отмазаться.
В данном выпуске те же новшества, что были в SP1 Beta: Direct2D в MFC и поддержка Intel AVX инструкций. Почитать про другие плюшки, а также посмотреть список исправленных багов, можно тут. Скачать SP1 можно тут, а подписчики MSDN могут качать из MSDN, чем стоит воспользоваться, т. к. ссылка очень медленная (хотя, может, только у меня).
Если у вас был установлен отдельно Windows SDK для Windows 7, то стоит почитать эту статью, т.к. при установке сервис пака могут быть проблемы.
В данном выпуске те же новшества, что были в SP1 Beta: Direct2D в MFC и поддержка Intel AVX инструкций. Почитать про другие плюшки, а также посмотреть список исправленных багов, можно тут. Скачать SP1 можно тут, а подписчики MSDN могут качать из MSDN, чем стоит воспользоваться, т. к. ссылка очень медленная (хотя, может, только у меня).
Если у вас был установлен отдельно Windows SDK для Windows 7, то стоит почитать эту статью, т.к. при установке сервис пака могут быть проблемы.
Posted by
Kirill V. Lyadvinsky
обновлено:
2013-09-09T11:55:22Z
Labels:
Cplusplus
,
programming
,
VisualStudio
,
Windows
вторник, 1 марта 2011 г.
Regex is simple
Регулярные выражения — очень удобное средство для валидации, поиска и замены строк. Пользоваться ими не сложно, хотя, ходят упорные слухи, что инструмент сложный и больше путает, чем помогает. Но, волков бояться — в лес не ходить, поэтому рекомендую к использованию. Например, простейший пример с использованием Boost.Regex будет выглядеть так:
// regex_test.cpp #include <iostream> #include <boost/regex.hpp> int main() { // правило поиска boost::wregex exrp( L"(https?:\\/\\/[\\w\\-_]+(?>\\.[\\w\\-_]+)+" L"(?>[\\w\\-\\.,@?^=%&:/~\\+#]*[\\w\\-\\@?^=%&/~\\+#]))" ); boost::match_results<std::wstring::const_iterator> what; // входная строка std::wstring input = L"My homepage is http://jia3ep.blogspot.com"; // поиск if( regex_search( input, what, exrp ) ) { // ога, нашли что-то std::wstring found( what[1].first, what[1].second ); // выводим std::wcout << found << std::endl; } return 0; } // в Boost немного вещей требуют линковки и Regex — одна из них, // поэтому в Ubuntu компилим этот пример так: // g++ -lboost_regex regex_test.cppДанный код найдет и выдаст Веб-адрес в заданной строке. Как сравочник синтаксиса можно использовать MSDN (мне тут нравится табличка, но аналогов в сети полно), а поискать готовые выражения можно, например, тут (правда, по ссылке встречаются и неработающие примеры).
Бывают, конечно, примеры в жизни и посложнее, чем приведенный. Например, вот более 6Кб кода для проверки email адреса соответствию стандарту RFC822. Но, к счастью, этот пример уже написан и его можно взять и скопировать.
Posted by
Kirill V. Lyadvinsky
обновлено:
2015-12-16T11:49:16Z
вторник, 22 февраля 2011 г.
Запуск процесса с повышенным уровнем привилегий
Это, наверное, и так все знают, но я забываю, поэтому запишу тут. Если нужно запустить процесс с повышением уровня привилегий (run elevated process), то можно применить следующий подход: берем структуру SHELLEXECUTEINFO, заполняем как обычно, потом добавляем опцию lpVerb как показано в примере:
SHELLEXECUTEINFO shExecInfo; shExecInfo.cbSize = sizeof(shExecInfo); shExecInfo.fMask = SEE_MASK_NOCLOSEPROCESS; shExecInfo.hwnd = NULL; shExecInfo.lpVerb = L"runas"; // start with elevated privileges shExecInfo.lpFile = filename.c_str(); shExecInfo.lpParameters = args.c_str(); shExecInfo.lpDirectory = NULL; shExecInfo.nShow = SW_SHOW; shExecInfo.hInstApp = NULL;Затем запускаем через ShellExecuteEx:
if ( TRUE == ShellExecuteEx(&shExecInfo) ) { WaitForSingleObject( shExecInfo.hProcess, PROPER_TIMEOUT ); CloseHandle( shExecInfo.hProcess ); }Это все. Если на компьютере включен UAC, то появится диалог с вопросом пользователю — можно ли. Если пользователь одобрит, то ваш процесс запустится в God mode.
Posted by
Kirill V. Lyadvinsky
обновлено:
2015-12-16T11:49:49Z
Labels:
Cplusplus
,
programming
,
Windows
четверг, 17 февраля 2011 г.
Развлечение на Bash. Финал.
Продолжая небольшой эксперимент на Bash, оформил предыдущие скрипты в виде одного. Добавлено удаление картинок, которые создались с ошибкой. Также, обратите внимание на наличие функции, которая принимает аргумент (имя файла) и возвращает результат.
Скрипт выложен на https://github.com/jia3ep/samsungthumbnailer и развиваться будет там.
Скрипт выложен на https://github.com/jia3ep/samsungthumbnailer и развиваться будет там.
Posted by
Kirill V. Lyadvinsky
обновлено:
2015-12-16T11:51:24Z
Labels:
bash
,
programming
воскресенье, 13 февраля 2011 г.
Развлечение на Bash
На днях занимался генерацией превьюшек для фильмов. Почти все современные ТВ умеют смотреть фильмы по сети через DLNA сервис, мой же, с пропатченной прошивкой, смотрит фильмы, которые расшарены через самбу(Samba). Превьюшки телек генерит неумело и кадр выбирает как попало, к тому же хранит их у себя в памяти, которой не очень-то и много.
Итак, задача нагенерить jpeg-файлов. Особенность в том, что расширение jpeg-файла должно быть размером соответсвующего ему видеофайла, который поделили на 1000. Если размер больше 4Гб, то надо сначала вычесть 232 из размера, а потом делить. Думал, писать программку на C++, но подумалось,что скриптовые языки тоже не зря придумали. Результатом стали два скрипта на bash, которые можно видеть в конце.
Для геренации превьюшек существует небольшой опенсорс проект — FFMpegThumbnailer. Интересен он тем, что там реализован алгоритм выбора удачного кадра. В отличие от тех сложных идей, с которыми приходилось встречаться ранее, вроде поиска лица, кожи и т.п., тут реализована очень простая идея. Считается гистограмма по сотне кадров и усредняется. Потом выбирается кадр, гистограмма которого наиболее близка к средней. Работает алгоритм на удивление хорошо.
Скрипт генерации одной превьюшки:
Генерация сразу для кучи файлов рекурсивно (используется предыдущий):
Все исходные коды проекта доступны на GitHub.
Итак, задача нагенерить jpeg-файлов. Особенность в том, что расширение jpeg-файла должно быть размером соответсвующего ему видеофайла, который поделили на 1000. Если размер больше 4Гб, то надо сначала вычесть 232 из размера, а потом делить. Думал, писать программку на C++, но подумалось,что скриптовые языки тоже не зря придумали. Результатом стали два скрипта на bash, которые можно видеть в конце.
Для геренации превьюшек существует небольшой опенсорс проект — FFMpegThumbnailer. Интересен он тем, что там реализован алгоритм выбора удачного кадра. В отличие от тех сложных идей, с которыми приходилось встречаться ранее, вроде поиска лица, кожи и т.п., тут реализована очень простая идея. Считается гистограмма по сотне кадров и усредняется. Потом выбирается кадр, гистограмма которого наиболее близка к средней. Работает алгоритм на удивление хорошо.
Скрипт генерации одной превьюшки:
#!/bin/bash # gen_th.sh FILENAME=$1 # get file size in bytes printf "$FILENAME\t" FILESIZE=$(stat -c%s "$FILENAME" 2>/dev/null) if [ $? -ne 0 ] ; then echo "[FAIL]" # no file or access denied exit 1 fi # generate file extension, so Samsung TV could use thumbnail if [ $FILESIZE -lt 4294967296 ] ; then EXT=$(( $FILESIZE / 1000 )) else EXT=$(( ($FILESIZE - 4294967296) / 1000)) fi NEWFN="${FILENAME%.*}.$EXT" if [ -f "$NEWFN" ] ; then echo "[SKIP]" # already exist exit 3 else ffmpegthumbnailer -s230 -cjpeg -i"$FILENAME" -o"$NEWFN" 2>/dev/null if [ $? -eq 0 ] ; then echo "[OK]" exit 0 else echo "[FAIL]" exit 1 fi fi
Генерация сразу для кучи файлов рекурсивно (используется предыдущий):
#!/bin/bash # gen_all.sh # Absolute path to this script. /home/user/bin/foo.sh SCRIPT=$(readlink -f "$0") # Absolute path this script is in. /home/user/bin SCRIPTPATH=`dirname "$SCRIPT"` FAILED=0 OK=0 SKIPPED=0 count=0 # set custom delimiter for the strings IFS=$'\n' # process each file for NAME in $(find $1/ -type f -regex ".*\.\(avi\|mkv\|ts\)$") do "$SCRIPTPATH/gen_th.sh" "$NAME" ecode=$? # keep exit code here because every command will change $? if [ "${ecode}" -eq "1" ] ; then let "FAILED+=1"; fi if [ "${ecode}" -eq "0" ] ; then let "OK+=1"; fi if [ "${ecode}" -eq "3" ] ; then let "SKIPPED+=1"; fi let "count+=1" done # display results echo "Total files processed: $count" echo "Skipped: $SKIPPED" echo "Failed: $FAILED" echo "Images generated: $OK"
Все исходные коды проекта доступны на GitHub.
Posted by
Kirill V. Lyadvinsky
обновлено:
2016-04-18T10:41:21Z
Labels:
bash
,
programming
понедельник, 24 января 2011 г.
Наследие OLE DB
С давних времен в коде различных проектов остались строки следующего вида для работы с OLE DB:
Как всегда виноваты макросы. Если посмотреть на декларацию BLOB_ENTRY_LENGTH_STATUS, то можно увидеть, что там запоминается адрес переменной m_BLOBDATA_LENGTH и позже используется как ULONG в 32-битной сборке, и как ULONGLONG в 64-битной. Т.е. несмотря на тип, который мы используем, по указанному адресу писаться будет 4 или 8 байт соответственно. В лучшем случае будет затираться m_BLOBDATA_STATUS, которая часто идет следом за m_BLOBDATA_LENGTH, а в худшем... в худшем — это UB.
Выход из ситуации следующий: нужно вместо ULONG использовать DBLENGTH и DBSTATUS.
ULONG m_BLOBDATA_LENGTH; ULONG m_BLOBDATA_STATUS; // ... BLOB_ENTRY_LENGTH_STATUS(4, IID_ISequentialStream, STGM_READ, m_data, m_BLOBDATA_LENGTH, m_BLOBDATA_STATUS)Откуда это пошло — не ясно: из MSDN или из книжек Круглински про MFC 4.0. Так или иначе, это все годами работало без сбоев... Пока не настала эра 64-битных приложений. Неприятность в том, что при сборке такого кода ошибок нет, да и работает он вроде. Но не всегда корректно.
Как всегда виноваты макросы. Если посмотреть на декларацию BLOB_ENTRY_LENGTH_STATUS, то можно увидеть, что там запоминается адрес переменной m_BLOBDATA_LENGTH и позже используется как ULONG в 32-битной сборке, и как ULONGLONG в 64-битной. Т.е. несмотря на тип, который мы используем, по указанному адресу писаться будет 4 или 8 байт соответственно. В лучшем случае будет затираться m_BLOBDATA_STATUS, которая часто идет следом за m_BLOBDATA_LENGTH, а в худшем... в худшем — это UB.
Выход из ситуации следующий: нужно вместо ULONG использовать DBLENGTH и DBSTATUS.
Posted by
Kirill V. Lyadvinsky
обновлено:
2014-09-02T09:48:36Z
Labels:
Cplusplus
,
MFC
,
OLEDB
,
programming
,
Windows
суббота, 1 января 2011 г.
explicit constructor
Давайте рассмотрим как отличаются явные и неявные конструкторы. Многие посмотрев на код ниже подумают, что различий между инициализацией a и b не очень много:
Cледующий пример поможет продемонстрировать как эта разница может проявиться в виде ошибки на практике:
Запись вида «sss ddd( 7 );» является явным вызовом конструктора, а «sss xxx = 7;» — неявным. Если бы конструктор с int был в private секции, то была бы выдана ошибка. Но ключевое слово explicit скывает конструктор так незаметно, что даже предупреждения компилятор не выдаст. Если скомпилировать и запустить пример, то окажется, что во втором случает будет вызван конструктор, принимающий double. Это может оказаться довольно неожиданным поворотом событий, если не разбираться в формах вызовов конструкторов. Часто разработчики не придают особого значения как они конструируют объект.
Если написать explicit для обоих конструкторов, то ошибки можно будет избежать — компилятор подскажет где ошибка. Поэтому explicit следует писать для всех конструкторов с одним параметром, если специально не предполагается другое поведение. Мне кажется, что это стоило делать по умолчанию в стандарте, а для других случаев ввести что-то вроде nonexplicit.
class SomeClass { public: SomeClass( int ); }; int main() { SomeClass a( 5 ); SomeClass b = 5; // если конструктор помечен explicit, то тут будет ошибка return 0; }Я имею ввиду, что в случае инициализации b не будет вызываться оператор копирования, как думают многие начинающие разработчики. Обе этих строчки вызывают конструктор с той лишь разницей, что в первом случае — это явный(explicit) вызов, в во втором — неявный(implicit).
Cледующий пример поможет продемонстрировать как эта разница может проявиться в виде ошибки на практике:
#include <iostream> class sss { public: explicit sss( int ) { std::cout << "int" << std::endl; } sss( double ) { std::cout << "double" << std::endl; } }; int main() { sss ddd( 7 ); sss xxx = 7; return 0; }Известно, что все целые числа по стандарту автоматически имеют тип int, если иного явно не указано. Т.е. число 7 в примере выше имеет тип int. Поэтому, кажется на первый взгляд, что в обоих случаях будет вызван конструктор принимающий int. Однако, это не так.
Запись вида «sss ddd( 7 );» является явным вызовом конструктора, а «sss xxx = 7;» — неявным. Если бы конструктор с int был в private секции, то была бы выдана ошибка. Но ключевое слово explicit скывает конструктор так незаметно, что даже предупреждения компилятор не выдаст. Если скомпилировать и запустить пример, то окажется, что во втором случает будет вызван конструктор, принимающий double. Это может оказаться довольно неожиданным поворотом событий, если не разбираться в формах вызовов конструкторов. Часто разработчики не придают особого значения как они конструируют объект.
Если написать explicit для обоих конструкторов, то ошибки можно будет избежать — компилятор подскажет где ошибка. Поэтому explicit следует писать для всех конструкторов с одним параметром, если специально не предполагается другое поведение. Мне кажется, что это стоило делать по умолчанию в стандарте, а для других случаев ввести что-то вроде nonexplicit.
Posted by
Kirill V. Lyadvinsky
обновлено:
2015-12-16T11:52:35Z
Labels:
Cplusplus
,
programming
Подписаться на:
Сообщения
(
Atom
)