Во время чтения книги Страуструпа "Язык программирования С++" я обратил внимание на ключевое слово explicit, которое периодически встречалось в примерах кода, представленных в книге. Это ключевое слово используется для запрещения создания конвертирующего конструктора. Поясню на примере:

class String {
public: 
String (int n);//выделить n байт для создания объекта 
String(const char *p); // инициализировать объект из C-строки 
}

При этом если выполнить следующий код:

String s = 'x';

то 'x' преобразуется в int и будет вызван конструктор String(int). Это совсем не то поведение, которое можно было бы ожидать. Для избежания таких ситуаций и используется ключевое слово explicit:

class String {
public: 
explicit String (int n);//выделить n байт для создания объекта 
String(const char *p); // инициализировать объект из C-строки 
}

Таким образом, объявление конструктора с одним аргументом (или с несколькими аргументами, где все, кроме первого имеют значения по умолчанию) explicit гарантирует неиспользование его в качестве оператора приведения типа.

Некоторое время назад приобрел себе Amazon Kindle 3. Поскольку устройство не продается в России пришлось заказывать через shipito и ждать около 3-х недель. Но обо всем по порядку.

Как купить?

Купить Amazon Kindle можно напрямую на сайте производителя. Версия c Wi-Fi обойдется в $139, версия с 3G будет стоить на $50 дороже. Я для себя выбрал версию c Wi-Fi по следующим причинам: во-первых она дешевле, во-вторых я не вижу никакого смысла в 3G. Даже при том условии, что он будет работать где угодно(как обещает Amazon). Книжки в устройство можно закачать и при наличии Wi-Fi а пользоваться браузером для проверки почты на таком устройстве мне лично неудобно, хотя Kindle и снабжен клавиатурой, так что в теории можно отвечать на электронные письма находясь в поездке. 

Поскольку доставки в Россию нет, я воспользовался сайтом shipito.com, который за небольшую плату предоставляет адрес в США и осуществляет пересылку в страну назначения. Сразу после регистрации сайт просит внести $8.50, которые затем будут потрачены на пересылку. Адрес, предоставленный shipito нужно указать как адрес доставки при заказе на Amazon. После того как заказ будет доставлен, придёт письмо от shipito. Доставка с Amazon до shipito будет бесплатной (есть Amazon Prime, который стоит $80 в год, при этом его можно попробовать первые 2 недели ничего не платя).

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

 

Таким образом доставка в россию обошлась в $45. Посылка в Питер шла больше двух недель:

 

 

Использование устройства

Среди поддерживаемых форматов у Kindle заявлены pdf, mobi, mp3, html, doc, jpeg и внутренний амазоновский формат специфичный для Kindle(AZW). Главное отличие pdf состоит в том, что в pdf нельзя менять размер шрифта, количество слов на странице и междустрочный интервал. Кроме этого нельзя воспользоваться функцией Text-To-Speech и заставить Kindle читать книжку за вас. При этом существует простой способ сконвертировать pdf во внутренний формат Kindle. Для этого устройство нужно зарегистрировать. После этого у устройства появится адрес в домене @kindle.com. Чтобы сконвертировать pdf нужно отправить письмо по этому адресу, приложив файл, который нужно сконвертировать и указав в теме "convert". Помимо pdf можно отправлять ещё doc и html, после конвертации эти файлы будут автоматически закачаны в Kindle. Стоит заметить, что читать например техническую литературу в pdf в вертикальной ориентации очень трудно из-за мелкого размера шрифта, поэтому часто приходится пользоваться горизонтальной ориентацией.

Экран выглядит не похожим на обычные LCD экраны, и при длительном чтении не возникает такого неприятного ощущения в глазах, как при использовании LCD. Ощущение такое, как будто читаешь обычную книгу или газету. Всего памяти 4 Гб, из них доступно для книг около 3 Гб.

Фотографии устройства

 

 

 

Файловая система NTFS на сегодняшний день используется на большинстве компьютеров под управлением Microsoft Windows. Она заменила использовавшуюся в MS-DOS и ранних версиях Microsoft Windows файловую систему FAT. NTFS это восстанавливаемая, надёжная и эффективная файловая система. Помимо этого она поддерживает ряд дополнительных интересных возможностей:

• множественные потоки данных
• универсальный механизм индексации
• динамическое переназначение плохих кластеров
• сжатие и разреженные файлы
• протоколирование изменений
• квоты томов, индивидуальные для каждого пользователя
• шифрование
• отслеживание ссылок
• дефрагментация
• поддержка POSIX
• жесткие связи

Альтернативные потоки данных - что это?

Остановимся более подробно на множественных потоках данных(Alternate Data Streams или иногда альтернативные потоки данных). В NTFS каждая единица информации, сопоставленная с файлом реализована в виде атрибута файла. Каждый атрибут состоит из одного потока данных, т.е. из одной последовательности байтов. Это позволяет легко добавлять к файлу новые атрибуты(и новые потоки соответственно).

В любом файле NTFS всегда есть один безымянный поток данных. При создании альтернативного потока данных для несуществующего файла автоматически будет создан безымянный поток нулевой длины. Соответственно при удалении безымянного потока будет удалён весь файл.

При этом атрибуты файла принадлежат файлу целиком, не только безымянному потоку. Например, ни один поток нельзя открыть на запись если стоит атрибут только для чтения(read-only).

Когда приложение открывает какой-то файл оно на самом деле открывает его безымянный поток. Указать альтернативный поток можно следующим образом: file.ext:stream2 здесь file.ext это имя файла а stream2 имя альтернативного потока. Альтернативные потоки данных могут иметь также и папки. Доступ к ним осуществляется аналогичным образом. Единственное отличие состоит в том, что при попытке прочитать безымянный поток данных папки произойдёт ошибку Access denied error.

Поддержка ADS в системе

Windows Explorer поддерживает альтернативные потоки данных в том смысле, что он корректно копирует файлы, содержащие несколько потоков. Кроме того, когда вы щёлкаете правой кнопкой мыши и выбираете команду Properties а затем вкладку Summary Windows Explorer показывает информацию из альтернативного потока данных. На этом его возможности заканчиваются. Аналогичная ситуация и с консольной утилитой copy:

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

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

Программирование ADS

Как проверить поддерживает ли система альтернативные потоки данных?

#define MAX_PATH 100

void main( )
{
    char szVolName[MAX_PATH], szFSName[MAX_PATH];
    DWORD dwSN, dwMaxLen, dwVolFlags;
    GetVolumeInformation("C:\\", szVolName, MAX_PATH, &dwSN, &dwMaxLen, &dwVolFlags, szFSName, MAX_PATH);

    if (dwVolFlags & FILE_NAMED_STREAMS) {
        printf("File system supports named streams");
    }
    else {
        printf("Named streams are not supported");
    }
}

Открыть или создать именованный поток можно с помощью функции CreateFile:

HANDLE hFile = CreateFile("file.txt:stream2", ...

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

Гораздо больший интерес представляет копирование потоков. Самый простой способ - воспользоваться функцией CopyFile(или CopyFileEx). Однако эти функции предназначены для копирования файлов, поэтому существуют некоторые тонкости.

• Копирование из безымянного потока в безымянный. Рассматривается как файловая операция, т.е. все именованные потоки также будут скопированы. При этом если целевой файл уже существует, его содержимое будет заменено.
• Копирование из именованного потока в безымянный. Также рассматривается как файловая операция, однако скопирован будет только один поток. Если целевой файл уже существует, то он будет удалён.

Можно облегчить себе жизнь следующим образом:

void main( )
{
    HANDLE hInFile = CreateFile("file.txt:stream2", GENERIC_READ, FILE_SHARE_READ, NULL,
             OPEN_EXISTING, FILE_FLAG_SEQUENTIAL_SCAN, NULL);
    HANDLE hOutFile = CreateFile("new.txt:newstream", GENERIC_WRITE, FILE_SHARE_READ, NULL,
             CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL | FILE_FLAG_SEQUENTIAL_SCAN, NULL);

    BYTE buf[64*1024];
    DWORD dwBytesRead, dwBytesWritten;

    do {
        ReadFile(hInFile, buf, sizeof(buf), &dwBytesRead, NULL);
        if (dwBytesRead) 
            WriteFile(hOutFile, buf, dwBytesRead, &dwBytesWritten, NULL);
    } while (dwBytesRead == sizeof(buf));

    CloseHandle(hInFile);
    CloseHandle(hOutFile);
}

Получить список потоков можно с помощью функции WinAPI NtQueryInformationFile.

// Открытие файла и получение информации о потоках данных

BYTE InfoBlock[64 * 1024]; 
PFILE_STREAM_INFORMATION pStreamInfo = (PFILE_STREAM_INFORMATION)InfoBlock;
IO_STATUS_BLOCK ioStatus;

HANDLE hFile = CreateFile(szPath, 0, FILE_SHARE_READ | FILE_SHARE_WRITE,
                            NULL, OPEN_EXISTING, 0, NULL);
NtQueryInformationFile(hFile, &ioStatus, InfoBlock,
                       sizeof(InfoBlock), FileStreamInformation);
CloseHandle(hFile);

Хотя этот способ является недокументированным и не рекомендуется к использованию.

Прочие факты об альтернативных потоках данных

• Размер альтернативного потока не ограничен.
• В альтернативном потоке может храниться не только текстовая информация. Любой поток может содержать в себе бинарные данные, JPEG или MPEG и вообще всё что угодно. Эта возможность широко используется вирусописателями и прочими злонамеренными личностями.
• Альтернативные потоки сами по себе не имеют атрибутов. Это значит что если запись в файл запрещена, то и добавить альтернативный поток в этот файл не получится.
• Протоколы передачи данных(такие как SMTP или FTP) не поддерживают альтернативные потоки данных. Единственный способ передать файл с ADS по сети это использовать локальную сеть и пересылать файл с диска на диск NTFS.

Ссылки

Inside Win2k NTFS

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

LADS - list alternate data streams

Библиотека Parallel Extensions, изначально разработанная как исследовательский проект вошла в состав .Net 4.0. Целью её создания было упростить программирование под многоядерные архитектуры.

Данная библиотека содержит множество средств для автоматического распараллеливания кода. Остановимся поподробнее на методе Parallel.For.

Это статический метод с 3-мя агрументами. Библиотека содержит сложные алгоритмы динамического распределения работы и автоматически приспосабливается к конкретной машине. В то же время примитивы библиотеки позволяют только указать на возможный параллелизм, но не гарантируют параллельного исполнения. Например, на однопроцессорной машине параллельный цикл будет выполнен последовательно. Скорость его выполнения будет очень близка к скорости выполнения последовательного кода. Однако на двухъядерном компьютере библиотека задействует два потока для параллельного выполнения цикла. Можно сразу включить инструкции параллельного выполнения в код, тогда при наличии нескольких процессоров приложение автоматически начнет их использовать. При этом код будет быстро работать и на однопроцессорных машинах.

Для примера рассмотрим классическую задачу из теории чисел - т.н. гипотезу Колатца. Она заключается в слелующем:

Рассмотрим следующий алгоритм генерации последовательности чисел. Начнем с целого числа n. Если n четно, то разделим n на 2.Если n нечетно, то умножим на 3 и добавим 1. Будем повторять этот процесс с новыми полученным n, пока n не станет равным 1. Например, для n = 22 будет сгенерирована следующая последовательность чисел:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Длина этой последовательности равна 16. До сих пор не доказано, что для любого числа такая последовательность закончится единицей.

Попробуем найти число в пределах от 1 до 1000000, которое генерирует последовательность наибольшей длины:

using System;
using System.Collections.Generic;
using System.Text;

namespace _14
{
    class Program
    {
        static long Max;
        static long MaxNum;
        
        static void calc(long a)
        {
            long ans = 1;
            long tmp_a = a;
            
            while (a != 1)
            {
                if (a % 2 == 0)
                    a /= 2;
                else
                    a = 3 * a + 1;
                ans++;
            }
            
            if (Max < ans)
            {
                MaxNum = tmp_a;
                Max = ans;
            }
        }

        static void Main(string[] args)
        {
            Max = -1;
            MaxNum = 0;
            
            DateTime startTime = DateTime.Now;
            for (int i = 1; i <= 1000000; i++)
                calc(i);
            
            DateTime stopTime = DateTime.Now;

            TimeSpan elapsed = stopTime - startTime;
            Console.WriteLine("elapsed seconds: {0}", elapsed.Seconds);
            Console.WriteLine("elapsed milliseconds: {0}", elapsed.Milliseconds);
            Console.WriteLine(MaxNum);
        }
    }
}

Вышеприведённый код использует для вычислений тип long чтобы избежать переполнения(элементы последовательности могут быть гораздо больше 1000000).

Время работы на моей машине с процессором Core 2 Duo 2,6 Ггц - 3 секунды и 232 миллисекунды.

Заметим, что вычисление длины последовательности для конкретного числа не зависит ни от каких других вычислений, поэтому эту задачу можно эффективно распараллелить. Для этого воспользуемся методом Parallel.For:

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

namespace _14
{
    class Program
    {
        static long Max;
        static long MaxNum;
        
        static void calc(long a)
        {
            long ans = 1;
            long tmp_a = a;
            
            while (a != 1)
            {
                if (a % 2 == 0)
                    a /= 2;
                else
                    a = 3 * a + 1;
                ans++;
            }
            
            if (Max < ans)
            {
                MaxNum = tmp_a;
                Max = ans;
            }
        }

        static void Main(string[] args)
        {
            Max = -1;
            MaxNum = 0;
            
            DateTime startTime = DateTime.Now;
            System.Threading.Tasks.Parallel.For(1, 1000000, i =>
            {
                calc(i);
            }
            );

            DateTime stopTime = DateTime.Now;

            TimeSpan elapsed = stopTime - startTime;
            Console.WriteLine("elapsed seconds: {0}", elapsed.Seconds);
            Console.WriteLine("elapsed milliseconds: {0}", elapsed.Milliseconds);
            Console.WriteLine(MaxNum);
            Console.ReadKey();
        }
    }
}

Понадобилось немного изменить всего одну строчку и время работы уменьшилось до 1 секунды и 738 миллисекунд, т.е. примерно в 2 раза.

BigInteger

В грядущей версии .NET Framework 4.0 наконец-то появится поддержка длинной арифметики. Новый тип BigInteger позволит работать с числами любого размера, ограниченного только объёмом имеющейся памяти. Помимо этого добавлен тип для работы с комплексными числами.

Новый класс  BigInteger находится в новом пространстве имен System.Numeric. ЧТобы его использовать нужно подключить библиотеку System.Numerics.dll(и лишний раз порадоваться скорости работы Add Reference в Visual Studio 2010)

 

 Новый объект класса BigInteger можно создать несколькими способами:

• Используя оператор new. При этом в конструкторе можно передать любой интегральный тип или тип с плавающей точкой языка C#. При этом при использовании типов с плавающей точкой значащие цифры после десятичной точки будут отброшены:

BigInteger a = new BigInteger(123.99);
Console.WriteLine(a);
BigInteger b = new BigInteger(123456789);
Console.WriteLine(b);

•  Объявив переменную типа BigInteger и присвоить ей значение любой другой переменной интегрального типа:

Int64 longValue = 6315489358112;
BigInteger bi = longValue;
Console.WriteLine(bi);

• Чтобы присвоить объекту типа BigInteger переменную с плавающей точкой нужно воспользоваться операцией приведения типов:

double doubleValue = 4354548.9233;
BigInteger a = (BigInteger)doubleValue;
Console.WriteLine(a);
decimal decimalValue=345454.343m;
BigInteger b = (BigInteger)decimalValue;
Console.WriteLine(b);

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

• Передать конструктору BigInteger массив типа byte. Этот конструктор может быть использован только для положительных значений:

byte[] byteArray = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
BigInteger newBigInt = new BigInteger(byteArray);
Console.WriteLine("The value of newBigInt is {0} (or 0x{0:x}).", newBigInt);

• Конвертировать из строки с помощью методов Parse или TryParse:

string positiveString = "91389681247993671255432112000000";
string negativeString = "-90315837410896312071002088037140000";
BigInteger posBigInt = 0;
BigInteger negBigInt = 0;

try {
   posBigInt = BigInteger.Parse(positiveString);
   Console.WriteLine(posBigInt);
}
catch (FormatException)
{
   Console.WriteLine("Unable to convert the string '{0}' to a BigInteger value.", 
                     positiveString);
}

if (BigInteger.TryParse(negativeString, out negBigInt))
  Console.WriteLine(negBigInt);
else
   Console.WriteLine("Unable to convert the string '{0}' to a BigInteger value.", 
                      negativeString);

• Использовать статический метод класса BigInteger для вычисления некоторого значения из числового выражения. Следующий код вычисляет куб максимального значения типа Int64:

BigInteger number = BigInteger.Pow(Int64.MaxValue, 3);
Console.WriteLine(number);

Неинициализированное значение BigInteger равно Zero.

Класс BigInteger перегружает основные математические операции, такие как сложение, вычитание, умножение, деление, унарный минус. Чтобы сравнить два объекта BigInteger можно использовать привычные операторы > или <. Так же как и другие числовые типы BigInteger поддерживает битовые операции и, или, исключающее или, и операции побитового сдвига. Помимом этого класс BigInteger поддерживает множество других математических операций с помощью статических методов класса. В их число входят следующие операции:

• Abs (возвращает абсолютное значение для данного BigInteger)
• Compare (выполняет сравнение двух BigInteger)
• Divide (возвращает частное от деления двух BigInteger)
• DivRem (возвращает частное и остаток от деления двух BigIntegers)
• Equals (возвращает значение «истина», если два BigInteger имеют одинаковое значение)
• GreatestCommonDivisor (возвращает наибольший общий делитель двух BigInteger)
• ModPow (возвращает результат возведения одного BigInteger в степень другого BigInteger по модулю третьего; показатель степени не может быть отрицательным)
• Pow (возвращает результат возведения одного BigInteger в степень другого; показатель степени не может быть отрицательным)
• Remainder (возвращает остаток от деления одного BigInteger на другое)
• Sign (возвращает знак BigInteger)

При работе с BigInteger важно помнить что тип BigInteger является неизменяемым(mutual). Это значит что при изменении значения объекта выделяется память под новый объект, туда копируется старый объект, и над ним производятся какие-либо действия. Старый объект уничтожается сборщиком мусора. Пример:

 

BigInteger number = BigInteger.Multiply(Int64.MaxValue, 3);
number++;
Console.WriteLine(number);

В этом коде значение переменной number увеличивается на единицу, что кажется тривиальной операцией. На самом деле CLR создаёт новый объект класса BigInteger и присваивает ему увеличенное значение. Точно так же ведёт себя тип string, который тоже является неизменяемым. Но поскольку BigInteger не имеет явной верхней или нижней границы при очень большом размере числа может возникнуть OutOfMemoryException. Чтобы проиллюстрировать это можно посчитать массив факториалов первых 50000 чисел:

 

using System;
using System.Numerics;
using System.Timers;

namespace BigIntegerTest
{
    class Program
    {
        static void calcFact(BigInteger a)
        {
            BigInteger[] array = new BigInteger[(int)a];

            BigInteger res = 1;
            for (int i = 2; i < a; i++)
            {
                res *= i;
                array[i] = res;
            }
        }

        static void Main(string[] args)
        {
            BigInteger a = new BigInteger(50000);
            try
            {
                calcFact(a);
            }
            catch (OutOfMemoryException e)
            {
                Console.WriteLine("Not enough memory");
            }
         }
    }
}

На моей машине с Win 7 x64 и 4 гигабайтами оперативной памяти возникает OutOfMemoryException. Чтобы отследить что происходит при этом я вопспользовался профайлером Visual Studui 2010. Чтобы его запустить нужно воспользоваться пунктом меню Analyze-> Launch Performance Wizard. Появится такое окошко:

  

Затем нужно выбрать свой проект для профилировки:

 

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

 

Соответственно в данном конктетном случае больше всего памяти вызывал метод op_Multiply, который судя по названию занимается перемножением двух больших чисел. При этом всего было выделено порядка 1,4 Гб: