Текст книги "Программирование мобильных устройств на платформе .NET Compact Framework"
Автор книги: Иво Салмре
Жанр:
Программирование
сообщить о нарушении
Текущая страница: 24 (всего у книги 69 страниц)
Управление памятью на микроскопическом "уровне алгоритма"
Современные языки программирования, библиотеки классов и управляемые среды времени выполнения позволили значительно повысить продуктивность написания программ. В то же время, избавляя программиста от необходимости задумываться о низкоуровневом распределении памяти, в котором нуждаются алгоритмы, они невольно создают предпосылки для написания неэффективного кода. Неэффективность кода может быть обусловлена причинами двоякого рода:
1. Вычислительная неэффективность алгоритма. Этот вид неэффективности наблюдается в тех случаях, когда спроектированный вами алгоритм предусматривает интенсивные вычисления или выполнение большего количества циклов, чем это объективно необходимо, от чего можно было бы избавиться, используя более эффективные алгоритмы. В качестве классического примера можно привести сортировку массива данных. Иногда у вас может появляться возможность выбирать между несколькими возможными вариантами алгоритмов сортировки, отдельными частными случаями которых могут, например, быть алгоритмы "порядка N" (линейная зависимость времени вычислений от количества сортируемых элементов), "порядка N*Log(N)" (зависимость времени вычислений от количества сортируемых элементов отличается от линейной, но остается все же лучшей, чем экспоненциальная) или "порядка N^2" (экспоненциальная зависимость времени вычислений от количества сортируемых элементов). Кроме вышеперечисленных "порядков" возможно множество других (например, N^3). Выбор наиболее подходящего алгоритма зависит от объема данных, с которыми вы работаете, объема доступной памяти и ряда других факторов, например, от состояния рабочих данных. Отдельные стратегии, например, предварительная обработка данных перед отправкой их на устройство или хранение данных в формате, специфическом для использования памяти в качестве хранилища, способны обеспечить значительное повышение производительности алгоритма. Существует огромное количество компьютерной литературы, посвященной проектированию эффективных алгоритмов и оценке их быстродействия, поэтому никаких попыток более подробного анализа этих вопросов в данной книге не делается. Необходимо только отметить, что чем больше объем обрабатываемых данных, тем ответственнее необходимо отнестись к принятию решения относительно выбора вычислительного алгоритма. Во всех затруднительных случаях тщательно анализируйте алгоритм и обращайтесь к существующей литературе по этому вопросу. Очень часто оказывается так, что кто-то другой уже прошел этот путь, и вам остается лишь перенять их опыт.
2. Неэффективное распределение памяти. После того как вы определитесь со стратегией алгоритма, следующим фактором, от которого в значительной степени за висит производительность приложения, является способ реализации этого алгоритма. При этом едва ли не наибольшие усилия вы должны приложить к тому, чтобы избежать распределения лишних объемов памяти, особенно если память распределяется в циклах. В данном разделе этой книги основное внимание уделяется именно этому вопросу.
Вашей целью должно быть распределение "нулевых объемов памяти" внутри циклов в написанном вами коде. Существуют случаи, когда это является неизбежным, как, например, при построении дерева объектов, которое требует размещения в памяти новых узлов для помещения их в иерархическую структуру. Во многих других случаях эффективность приложения можно существенно повысить, тщательно анализируя распределение памяти для каждого объекта и рассматривая альтернативные решения. Чего, как правило, следует избегать – так это выполнения операций размещения объектов в памяти и удаления их из памяти внутри алгоритмических циклов.
Пишите аккуратные алгоритмы: не сорите!Как и в реальной жизни, сор в программировании – это отходы производственной деятельности, которые должны выбрасываться. Обычно сор появляется в результате неряшливости и неаккуратности. Стремление к получению кратковременных удобств часто порождает долговременные проблемы. При создании в алгоритмах мусора в виде временных объектов, необходимости в которых на самом деле нет, работа приложения замедляется в результате воздействия непосредственных и косвенных факторов:
1. Непосредственные факторы. Каждый раз, когда вы создаете объект, перед его использованием должна быть распределена и инициализирована память. Это прямые предварительные расходы, которые должен оплатить ваш алгоритм.
2. Косвенные факторы. После того как приложение освободило объект, он становится "мусором" Этот мусор накапливается в приложении, пока его не соберется так много, что для последующего распределения памяти для новых объектов потребуется ее предварительная очистка от старых. Конечно же, именно это и называется сборкой мусора. На сборку мусора уходит определенное время, и если мусора много, то эта операция заметно затормозит работу вашего приложения. Чем больше вы сорите, тем больше накапливается мусора и тем чаще приходится тратить время на уборку!
В процессе программирования вы всегда должны стараться "сорить" как можно меньше. Нет ничего плохого в том, чтобы создать экземпляр объекта, если это помогает решить какую-то очень важную задачу; если же объект является короткоживущим и задача может быть решена без него, то вы только создаете мусор. Не будьте "неряхой"!
Пишите экономные алгоритмы: разумно расходуйте память и повторно используйте объекты"Структуры" и .NET Compact Framework
Во многих случаях, если вы хотите инкапсулировать некоторые простые данные, то для локальных переменных внутри функций гораздо эффективнее использовать не объекты, а структуры. Структура – это просто удобный способ сгруппировать в одном пакете взаимосвязанные данные, а не передавать их в виде отдельных переменных.
Структуры обладают более простыми свойствами по сравнению с объектами, но могут "упаковываться" в объекты и передаваться внутри программы так же, как они, если в этом возникает необходимость. Использование структур предоставляет определенные удобства и может привести к некоторому увеличению производительности (по сравнению с вариантом, когда используются объекты), но поскольку они выглядят, а во многих случаях и действуют подобно объектам и могут заключаться в объекты-оболочки, необходимо тщательно взвешивать, когда их следует использовать, чтобы избежать дополнительных накладных расходов и не создать лишнего мусора. В сомнительных случаях тестируйте алгоритмы, используя как отдельные переменные (например, базовые типы, подобные int, string, double), так и структуры, чтобы сравнить производительность приложения в обоих случаях и убедиться в том, что она остается примерно одинаковой.
Более подробную информацию по этому вопросу вы можете получить, обратившись к разделам справочной документации .NET Compact Framework, посвященным типам значений ("value types") и структурам ("struct"). Ниже приводится пример с объявлениями структуры и класса:
//Примечание. В VB.NET это был бы тип (type), а не структура (struct)
//Это структура
struct MyRect_Type {
public int x;
public int у;
}
//Это класс
class MyRect_Class {
public int x;
public int у;
}
//Код примера
class TestClass {
public void foo() {
//Требуется распределять как объект
MyRect_Class myRectClass = new MyRect_Class();
myRectClass.x = 1;
myRectClass.y = 2;
//Этот оператор распределяет новый объект
myRectClass = new MyRect_Class();
//Можно объявить как скалярный тип
MyRect_Type myRectType;
myRectType.x = 1;
myRectType.y = 2;
//Этот оператор обнуляет значения в структуре, но не
//распределяет память для нового объекта!
myRectType = new MyRect_Type();
}
Представленный ниже пример иллюстрирует несколько различных вариантов реализации одного и того же базового алгоритма. Алгоритм предназначен для обработки массива строк. Каждая строка в массиве состоит из трех частей, разделенных символом подчеркивания (например, big_shaggy_dog). Алгоритм предполагает просмотр каждого из элементов массива и проверку того, не является ли его средняя часть словом blue (например, my_blue_car). Если это так, то слово blue заменяется словом orange (например, my_blue_car становится my_orange_car).
Кроме того, в каждом из описанных алгоритмов используется вспомогательный класс, упрощающий разбиение строк и получение данных, содержащихся в каждом из трех сегментов. Первый алгоритм (листинги 8.3 и 8.4) представляет собой некое разумное первое приближение, а следующие два алгоритма (листинги 8.5 и 8.6 и листинги 8.7 и 8.8) – его оптимизированные варианты, улучшающие первоначальную тактику. Целью оптимизации являлось непосредственное улучшение производительности, а также уменьшение количества "мусора", вырабатываемого каждым из алгоритмов.
Листинг 8.2. Общий код, используемый во всех приведенных ниже вариантах тестов
//Желаемое число повторений теста
const int LOOP_SIZE = 8000;
//–
//Эта функция переустанавливает содержимое нашего тестового
//массива, что обеспечивает возможность многократного
//выполнения тестового алгоритма
//–
private void ResetTestArray(ref string[] testArray) {
if (testArray == null) {
testArray =new string[6];
}
testArray[0] = "big_blue_duck";
testArray[1] = "small_yellow_horse";
testArray[2] = "wide_blue_cow";
testArray[3] = "tall_green_zepplin";
testArray[4] = "short_blue_train";
testArray[5] = "short_purple_dinosaur";
}
Листинг 8.3. Тестовый пример, демонстрирующий неэкономное распределение памяти (типичный первоначальный вариант реализации интересующей нас функции)
Примечание. В этом примере используется класс PerformanceSampling, определенный ранее в данной книге.
private void button2_Click(object sender, System.EventArgs e) {
//Вызвать сборщик мусора, чтобы быть уверенными в том,
//что тест начнется с чистого состояния.
//ПРИБЕГАЙТЕ К ЭТОЙ МЕРЕ ТОЛЬКО В ЦЕЛЯХ ТЕСТИРОВАНИЯ! Вызовы
//сборщика мусора в программах вручную будут приводить к снижению
//общей производительности приложений!
System.GC.Collect();
string [] testArray = null;
//–
//Просмотреть элементы массива и найти
//те из них, в которых средним словом является
//"blue". Заменить "blue" на "orange"
//–
//Запустить секундомер для нашего теста!
PerformanceSampling.StartSample(0, "WastefulWorkerClass");
WastefulWorkerClass workerClass1;
int outerLoop;
for (outerLoop = 0; outerLoop < LOOP_SIZE; outerLoop++) {
//Присвоить элементам массива значения, которые мы хотим
//использовать при тестировании
ResetTestArray(ref testArray);
int topIndex = testArray.Length – 1;
for (int idx = 0; idx <= topIndex; idx++) {
//–
//Создать экземпляр вспомогательного класса,
//который расчленяет строку на три части
//
//Это неэкономный способ!
//–
workerClass1 = new WastefulWorkerClass(testArray[idx]);
//Если средним словом является "blue", заменить его на "orange"
if (workerClass1.MiddleSegment == "blue") {
//Заменить средний сегмент
workerClass1.MiddleSegment = "orange";
//Заменить слово
testArray[idx] = workerClass1.getWholeString();
}
} //конец внутреннего цикла for
}//конец внешнего цикла for
//Получить время окончания теста
PerformanceSampling.StopSample(0);
System.Windows.Forms.MessageBox.Show(PerformanceSampling.GetSampleDurationText(0));
}
Листинг 8.4. Рабочий класс для первого тестового примера
using System;
public class WastefulWorkerClass {
private string m_beginning_segment;
public string BeginSegment {
get { return m_beginning_segment; }
set { m_beginning_segment = value; }
}
private string m_middle_segment;
public string MiddleSegment {
get { return m_middle_segment; }
set { m_middle_segment = value; }
}
private string m_end_segment;
public string EndSegment {
get { return m_end_segment; }
set { m_end_segment = value; }
}
public WastefulWorkexClass(string in_word) {
int index_segment1;
//Осуществляем поиск символов подчеркивания ("_") в строке
index_segment1 = in_word.IndexOf("_",0);
//B случае отсутствия символов "_" все, что нам нужно, это первый сегмент
if (index_segment1 == -1) {
m_beginning_segment = in_word;
m_middle_segment = "";
m_end_segment = "";
return;
}
//Если присутствует символ "_", усечь его
else {
//Если первым символом является "_", то первым сегментом будет ""
if (index_segment1 == 0) {
m_beginning_segment = "";
} else {
//Первый сегмент
m_beginning_segment = in_word.Substring(0, index_segment1);
}
//Найти второй символ "_"
int index_segment2;
index_segment2 = in_word.IndexOf("_", index_segment1 + 1);
//Второй символ "_" отсутствует
if (index_segment2 == -1) {
m_middle_segment = "";
m_end_segment = in_word.Substring(index_segment1 + 1);
return;
}
//Установить последний сегмент
m_middle_segment = in_word.Substring(index_segment1 + 1, index_segment2 – index_segment1 -1);
m_end_segment = in word.Substring(index segment2 + 1);
}
//Возвращает все три сегмента, объединенные символами "_"
public string getWholeString() {
return m_beginning_segment + "_" + m_middle_segment + "_" + m_end_segment;
}
} //конец класса
Создание экземпляра вспомогательного класса в каждой итерации цикла обработки является большим расточительством. Несмотря на относительно малые размеры объекта, содержащего всего лишь несколько элементов данных, его обработка приводит к дополнительным накладным расходам. Кроме того, каждый раз, когда создается очередной экземпляр объекта, прежний экземпляр освобождается. В результате этого образуется мусор, который впоследствии должен быть убран. От напрасного размещения объектов в памяти мы можем легко избавиться.
Листинг 8.5. Тестовый пример, демонстрирующий уменьшение объема памяти, распределяемой для объектов (типичный образец улучшения первоначального варианта реализации интересующей нас функции)
Примечание. В этом примере используется класс PerformanceSampling, определенный ранее в данной книге.
private void button3_Click(object sender, System.EventArgs e) {
//Вызвать сборщик мусора, чтобы тест
//начинался с чистого состояния.
//ПРИБЕГАЙТЕ К ЭТОЙ МЕРЕ ТОЛЬКО В ЦЕЛЯХ ТЕСТИРОВАНИЯ! Вызовы
//сборщика мусора в программах вручную будут приводить к снижению
//общей производительности приложений!
System.GC.Collect();
string[] testArray = null;
//–
//Просмотреть элементы массива и найти
//те из них, в которых средним словом является
//"blue". Заменить "blue" на "orange"
//–
//Запустить секундомер!
PerformanceSampling.StartSample(1, "LessWasteful");
//–
//БОЛЕЕ ЭКОНОМНЫЙ СПОСОБ: Распределить память
//для объекта до вхождения в цикл
//–
LessWastefulWorkerClass workerClass1;
workerClass1 = new LessWastefulWorkerClass();
int outerLoop;
for (outerLoop = 0; outerLoop < LOOP_SIZE; outerLoop++) {
//Присвоить элементам массива значения, которые
//мы хотим использовать при тестировании
ResetTestArray(ref testArray);
int topIndex = testArray.Length – 1;
for(int idx = 0; idx <= topIndex; idx++) {
//–
//Теперь вместо повторного распределения памяти для объекта
//нам достаточно лишь повторно воспользоваться им
//–
//workerClass1 = new WastefulWorkerClass(
// testArray[topIndex]);
workerClass1.ReuseClass(testArray[idx]);
//Если средним словом является "blue", заменить его на "orange"
if (workerClass1.MiddleSegment == "blue") {
//Заменить средний сегмент
workerClass1.MiddleSegment = "orange";
//Заменить слово
testArray[idx] = workerClass1.getWholeString();
}
}
}
//Остановить секундомер!
PerformanceSampling.StopSample(1);
System.Windows.Forms.MessageBox.Show(PerformanceSampling.GetSampleDurationText(1));
}
Листинг 8.6. Рабочий класс для второго тестового примера
using System;
public class LessWastefulWorkerClass {
private string m_beginning_segment;
public string BeginSegment {
get { return m beginning_segment; }
set { m_beginning_segment = value; }
}
private string m_middle_segment;
public string MiddleSegment {
get { return m_middle_segment; }
set { m_middle segment = value; }
}
private string m_end_segment;
public string EndSegment {
get { return m_end_segment; }
set { m_end_segment = value; }
}
public void ReuseClass(string in word) {
//–
//Для повторного использования класса необходимо
//полностью очистить внутреннее состояние
//–
m_beginning_segment = "";
m_middle_segment = "";
m_end_segment = "";
int index_segment1;
//Осуществляем поиск символов подчеркивания (" ") в строке
index segment1 = in_word.IndexOf(" ",0);
//B случае отсутствия символов " " все, что нам нужно, это первый сегмент
if (index_segment1 == -1) {
m_beginning_segment = in_word;
return;
}
//Если присутствует символ " ", усечь его
else {
if (index_segment1 == 0) {
} else {
m_beginning_segment = in_word.Substring(0, index_segment1);
}
int index_segment2;
index_segment2 = in_word.IndexOf("_", index_segment1 + 1);
if (index_segment2 == -1) {
m_end_segment = in_word.Substring(index_segment1 + 1);
return;
}
//Установить последний сегмент
m_middle_segment = in_word.Substring(index_segment1 + 1, index_segment2 – index_segment1 – 1);
m_end_segment = in_word.Substring(index_segment2 + 1);
}
}
public string getWholeString() {
return m_beginning_segment + "_" + m_middle_segment + "_" + m_end_segment;
}
}
Избегайте размещения в памяти лишних объектовПредшествующий код оставляет возможности для внесения дальнейших улучшений
Предыдущий подход все еще демонстрирует значительную напрасную трату ресурсов, поскольку мы постоянно размещаем и освобождаем строки. Если мы собираемся создать код, обеспечивающий высокую производительность, то от создания лишних строковых объектов следует избавиться.
Обратите внимание на то, что в приведенном выше коде мы часто вычисляем множество величин, которые нам не нужны. В частности, мы генерируем в каждой итерации цикла, по крайней мере, три новых строки: одну для первого сегмента, одну для среднего сегмента и одну для конечного сегмента исходной строки. Например, строка big_blue_boat разбивается на три различных строки: big, blue и boat. Для создания этих строк требуется определенное время, а, кроме того, впоследствии мы должны освободить занимаемую ими память.
В алгоритме выполняется проверка только среднего сегмента, в ходе которой устанавливается, совпадает ли он с некоторым конкретным значением (blue). Если совпадения нет. дальнейшая обработка не требуется. Это означает, что большую часть времени мы напрасно распределяем память для строк, предназначенных для размещения среднего и конечного сегментов, даже если они используются алгоритмом всего лишь для того, чтобы вновь собрать целую строку из отдельных кусочков. Что если вместо создания целых строк из кусочков старой строки в каждой итерации цикла мы будем просто сохранять символьные индексные значения, которые указывают нам, где находятся символы подчеркивания (_) в строке? Мы можем сохранять эти данные в виде целых чисел, накладные расходы для которых должны быть значительно меньше, чем при размещении новых строк. Если мы поступим именно таким образом, то сможем использовать исходные строковые и индексные значения для сравнения строк, начиная с первого символа подчеркивания и доходя до второго символа подчеркивания (например, blue_). Лишь в тех случаях, когда обнаруживается совпадение, нам потребуется создавать дополнительную строку для замены среднего сегмента. В большинстве случаев ситуация для нас намного улучшится и нам не надо будет распределять память для каких-либо объектов или строк. Лишь в тех случаях, когда обнаруживается совпадение средних сегментов, нам потребуется выполнять дополнительные строковые операции, но в любом случае нам придется выполнить не больше операций, чем выполнялось ранее. Как бы то ни было, хуже не будет.
Листинг 8.7. Тестовый пример, демонстрирующий значительное уменьшение объема памяти, распределяемой для объектов (типичный образец существенной алгоритмической оптимизации первоначального варианта реализации интересующей нас функции)
Примечание. В этом примере используется класс PerformanceSampling, определенный ранее в данной книге.
private void button5_Click(object sender, System.EventArgs e) {
//Вызвать сборщик мусора, чтобы тест //начинался с чистого состояния.
//ПРИБЕГАЙТЕ К ЭТОЙ МЕРЕ ТОЛЬКО В ЦЕЛЯХ ТЕСТИРОВАНИЯ! Вызовы
//сборщика мусора в программах вручную будут приводить к снижению
//общей производительности приложений!
System.GC.Collect();
string[] testArray = null;
//–
//Просмотреть элементы массива и найти
//те из них, в которых средним словом является
//"blue". Заменить "blue" на "orange"
//–
//Запустить секундомер перед началом выполнения теста
PerformanceSampling.StartSample(2, "DefferedObjects");
//–
//БОЛЕЕ ЭКОНОМНЫЙ СПОСОБ: Распределить память для
//объекта до вхождения в цикл
//–
LessAllocationsWorkerClass workerClass1;
workerClass1 = new LessAllocationsWorkerClass();
int outerLoop;
for (outerLoop = 0; outerLoop < LOOP_SIZE; outerLoop++) {
//Присвоить элементам массива значения, которые
//мы хотим использовать при тестировании
ResetTestArray(ref testArray);
int topIndex = testArray.Length – 1;
for(int idx = 0; idx <= topIndex; idx++) {
//–
//Более экономный способ:
//Теперь вместо повторного распределения памяти для объекта
//нам достаточно лишь повторно воспользоваться им
//Кроме того: в этом варианте реализации дополнительные
// строки НЕ создаются
//–
//workerClass1 = new WastefulWorkerClass(
// testArray[topIndex]);
workerClass1.ReuseClass(testArray[idx]);
//Если средним словом является "blue", заменить его на "orange"
//–
//Более экономный способ:
//При таком способе сравнения не требуется создавать
//никаких дополнительных строк
//–
if (workerClass1.CompareMiddleSegment("blue") == 0) {
//Заменить средний сегмент workerClass1.MiddleSegment = "orange";
//Заменить слово
testArray[idx] = workerClass1.getWholeString();
}
}
}
//Остановить секундомер!
PerformanceSampling.StopSample(2);
System.Windows.Forms.MessageBox.Show(PerformanceSampling.GetSampleDurationText(2));
}
Листинг 8.8. Рабочий класс для третьего тестового примера
using System;
public class LessAllocationsWorkerClass {
public string MiddleSegment {
set { m_middleSegmentNew= value; }
}
private string m_middleSegmentNew;
private int m_index_1st_undscore;
private int m_index_2nd undscore;
private string m_stringIn;
public void ReuseClass(string in_word) {
//–
//Для повторного использования класса необходимо
//полностью очистить внутреннее состояние
//–
m_index_1st_undscore = -1;
m_index_2nd_undscore = -1;
m_middleSegmentNew= null;
m_stringIn = in_word; //Это не приводит к созданию копии строки
//Осуществляем поиск символов подчеркивания ("_") в строке
m_index_1st_undscore = in_word.IndexOf("_",0);
//B случае отсутствия символов "_" все, что нам нужно, это первый сегмент
if (m_index_1st_undscore == -1) {
return;
}
//Найти второй символ " "
m_index 2nd_undscore = in_word.IndexOf(" ", m_index_1st_undscore + 1);
}
public int CompareMiddleSegment(string compareTo) {
//B случае отсутствия второго символа "_" отсутствует и средний сегмент
if (m_index_2nd_undscore < 0) {
//Если мы сравниваем с пустой строкой,
//то это означает совпадение
if((compareTo == null) || (compareTo == "")) {return 0;}
return -1;
}
//Сравнить средний сегмент с первым и вторым сегментами
return System.String.Compare(
m_stringIn, m_index_1st_undscore + 1, compareTo, 0, m_index_2nd_undscore – m_index_1st_undscore -1);
}
public string getWholeString() {
//Если полученный средний сегмент не является новым,
//возвратить исходный сегмент
if (m_middleSegmentNew == null) {
return m_stringIn;
}
//Создать возвращаемую строку
return m_stringIn.Substring(0, m_index_1st_undscore + 1) +
m_middleSegmentNew +
m_stringIn.Substring(m_index_2nd_undscore, m_stringIn.Length – m_index_2nd_undscore);
}
}
