Framework .Net и универсальность

Универсальность принадлежит к основным механизмам языка. Ее введение в язык C# не могло не сказаться на всех его основных свойствах. Как уже говорилось, классы и все частные случаи стали обладать этим свойством. Введение универсальности не должно было ухудшить уже достигнутые свойства языка – статический контроль типов, динамическое связывание и полиморфизм. Не должна была пострадать и эффективность выполнения программ, использующих универсальные классы.

Решение этих задач потребовало введения универсальности не только в язык C#, но и поддержки на уровне каркаса Framework .Net и языка IL, включающем теперь параметризованные типы. Универсальный класс C# не является шаблоном, на основе которого строится конкретизированный класс, компилируемый далее в класс (тип) IL. Компилятору языка C# нет необходимости создавать классы для каждой конкретизации типов универсального класса. Вместо этого происходит компиляция универсального класса C# в параметризованный тип IL. Когда же CLR занимается исполнением управляемого кода, то вся необходимая информация о конкретных типах извлекается из метаданных, сопровождающих объекты. Read more »

Массивы. Семантика присваивания

Преобразования между классами массивов и родительскими классами Array и Object уже рассматривались. А существуют ли другие преобразования между классами массивов? Что происходит при присваивании x=e; (передаче аргументов в процедуру), если x и e – это массивы разных классов? Возможно ли присваивание? Ответ на этот вопрос положительный, хотя накладываются довольно жесткие ограничения на условия, когда такие преобразования допустимы. Известно, например, что между классами Int и Object существуют взаимные преобразования – в одну сторону явное, в другую неявное. А вот между классами Int[] и Object[] нет ни явных, ни неявных преобразований. С другой стороны, такое преобразование существует между классами String[] и Object[]. В чем же тут дело, и где логика? Запомните, главное ограничение на возможность таких преобразований состоит в том, что элементы массивов должны иметь ссылочный тип. А теперь притянем сюда логику. Крайне желательно обеспечить возможность проведения преобразований между массивами, элементы которых принадлежат одному семейству классов, связанных отношением наследования. Такая возможность и была реализована. А вот для массивов с элементами значимых типов подобную же возможность не захотели или не смогли реализовать. Read more »

Быстрая сортировка Хоара

Продолжая тему рекурсии, познакомимся с реализацией на C# еще одного известного рекурсивного алгоритма, применяемого при сортировке массивов. Описанный ранее рекурсивный алгоритм сортировки слиянием имеет один существенный недостаток – для слияния двух упорядоченных массивов за линейное время необходима дополнительная память. Разработанный Ч. Хоаром метод сортировки, получивший название быстрого метода сортировки – QuickSort, не требует дополнительной памяти. Хотя этот метод и не является самым быстрым во всех случаях, но на практике он обеспечивает хорошие результаты. Нужно отметить, что именно этот метод сортировки встроен в класс System.Array.

Идея алгоритма быстрой сортировки состоит в том, чтобы выбрать в исходном массиве некоторый элемент M, затем в начальной части массива собрать все элементы, меньшие M. Так появляются две подзадачи размерности – k и n-k, к которым рекурсивно применяется алгоритм. Если в качестве элемента M выбирать медиану сортируемой части массива, то обе подзадачи имели бы одинаковый размер и алгоритм быстрой сортировки был бы оптимальным по времени работы. Но расчет медианы требует своих затрат времени и усложняет алгоритм. Поэтому обычно элемент M выбирается случайным образом. В этом случае быстрая сортировка оптимальна лишь в среднем, а для плохих вариантов (когда в качестве M всякий раз выбирается минимальный элемент) имеет порядок n2.

Несмотря на простоту идеи, алгоритм сложен в своей реализации, поскольку весь построен на циклах и операторах выбора. Я проводил построение алгоритма параллельно с обоснованием его корректности, введя инварианты соответствующих циклов. Текст обоснования встроен в текст метода. Приведу его, а затем дам некоторые объяснения. Вначале, как обычно, приведу нерекурсивную процедуру, вызывающую рекурсивный метод: Read more »