# Неэффективность last\(\) в реальном мире

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

Началось все с жалобы, что статический анализатор Viva64 зависает при анализе одного из проектов, а вернее на одном из файлов проекта\. Анализ показал, что на самом деле не зависает, а очень даже усердно работает\. Очень усердно и очень долго\. Я думаю даже он успешно его сможет проанализировать, часов так через 5\-10 :\)\. Но это стало ясно уже потом и естественно такое поведение можно считать ошибкой\.

Честно говоря, в начале меня подобное поведение сильно удивило\. Анализатор Viva64 работает весьма быстро\. И среднее время анализа одного файла занимает всего несколько секунд\. И время его работы значительно меньше, чем тратится на предварительное препроцессирование файлов\. Препроцессирование выполняется за счет компилятора Visual C\+\+ и здесь мы убыстрить процесс пока никак не можем\. Поэтому, грубо говоря, время проверки проекта близко к времени препроцессирования всех файлов\. И вдруг обнаруживается такая огромная неэффективность в алгоритме анализа\!

Расследования показали, что зависание происходит на файле, который содержит некие ресурсы из библиотеки Qt\. А именно массив "static const unsigned char qt\_resource\_data\[\]", размером\.\.\. размер массива не знаю, но знаю что это самый большой массив, который я видел в своей жизни\. Выглядит он так:

```cpp
static const unsigned char qt_resource_data[] = {
  0x0,0x0,0x0,0xc5,
  0x51,
  0x46,0x72,0x61,0x6d,0x65,0x20,0x7b,
  0xd,0xa,0x20,0x20,0x20,0x20,0x6d,0x69,0x6e,
  0x2d,0x77,0x69,0x64,0x74,0x68,0x3a,0x20,
  0x36,0x70,0x78,0x3b,0xd,0xa,0x20,0x20,
  0x20,0x20,0x6d,0x69,0x6e,0x2d,0x68,0x65,
  0x69,0x67,0x68,0x74,0x3a,0x20,0x36,0x30,
  . . .
```

Занимает этот массив в файле около 9 мегабайт\. Много, но это не повод анализатору так плохо себя вести\.

Проблема оказалась в уже упомянутой функции last\(\)\. Анализатор Viva64 построен на библиотеке VivaCore\. А VivaCore построена в свою очередь на библиотеке OpenC\+\+, от которой она унаследовала представление данных в виде деревьев и списков\. Кстати, обработка данных в OpenC\+\+ \(и VivaCore\) весьма напоминает lisp программу\. Имеется множество функций вида Eq, Car, Cdr, First, Rest, Second, Nth, List и так далее\.

И есть функция last\(\), которая используется при создании списка элементов для инициализации массива\. В псевдокоде это выглядит так:

```cpp
while (еще есть элементы)
{
  Ptree *e = взять очередной элемент;
  Ptree *last = Last(eList);
  last->SetCdr(Cons(e, 0));
}
```

Общий смысл \- берем очередной элемент массива и добавляем его в хвост списка\. Чтобы найти хвост для простоты используется функцию last\(\)\. Автор OpenC\+\+ явно не предполагал, что алгоритму будет подсунута инициализация массива из миллионов элементов\. На маленьких массивах все замечательно, но время подобного алгоритма растет пропорционально квадрату количества элементов \(а, если быть точным \- треугольному числу: 0\.5 \* n \* \(n \+ 1\) , где n \- количество элементов\)\.

Простейшая оптимизация, заключающаяся в хранении указателя на последний элемент списка, \(что позволяет не вызывать функцию last\(\)\) сотворила буквально чудо\. Обработка файла, которая ранее занимала больше 3 часов \(больше 3 часов я ждать не вытерпел :\), стала занимать несколько секунд\.

Что сказать \- будьте аккуратнее, прежде чем использовать функции подобные last\(\)\. Нельзя угадать, что захотят рано или поздно подсунуть вашему алгоритму\. Удачи в оптимизации\!