Задачи на собеседованиях: односвязные списки

Простая задача на понимание односвязных списков. Однако, несмотря на то, что задача несложная, многие кандидаты пугаются и начинают путаться в показаниях.

Дано: односвязный список N₁->N₂->N₃->...->N_n и указатель на его голову N₁.

Нужно: развернуть список за один проход так, чтобы стало N_n->N_n-1->N_n-2->...->N₁.

Цитата: Павич

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

Милорад Павич, "Хазарский словарь"

Кстати о GCC

Неделю назад вышла очередная версия компилятора GCC — 4.4.

В новой версии расширены возможности оптимизации кода, ключ -Wconversion теперь выводит предупреждение при некорректных попытках привести целочисленный тип к enum, а также включена экспериментальная поддержка стандарта C++0x. И много чего другого не менее интересного...

suncc в качестве подручного инструмента

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

Наверное, самый лучший способ достичь этого — изучать алгоритмы и приемы оптимизации кода. Но будь ты хоть семи пядей во лбу, когда рядом есть "подручные средства" — грех не воспользоваться ими.

Я хочу рассказать, как использовать компилятор Sun для того, чтобы повысить производительность вашего кода. У этого компилятора есть замечательная особенность — при выполнении оптимизации он может вставлять свои комментарии в объектные файлы, которые можно потом использовать для дальнейшего улучшения кода. Компилятор Sun прилагается к пакету Sun Studio, который является бесплатным и доступен для скачивания с http://developers.sun.com

В качестве примера рассмотрим простую программу:

int main ()
{
  int c = 0;
  int size = 10000;
  int *a = new int[size * size];

  for (int i = 0; i < size; ++i)
  {
    for (int j = 0; j < size; ++j)
    {
      a[j * size + i] = c++;
    }
  }

  delete [] a;
  return 0;
}

Эта программа создает квадратную матрицу размером size на size, и заполняет ее числами от 0 до N по столбцам. Для матрицы 10 на 10 это будет выглядеть так:

0 10 20 30 40 50 60 70 80 90
1 11 21 31 41 51 61 71 81 91
2 12 22 32 42 52 62 72 82 92
3 13 23 33 43 53 63 73 83 93
4 14 24 34 44 54 64 74 84 94
5 15 25 35 45 55 65 75 85 95
6 16 26 36 46 56 66 76 86 96
7 17 27 37 47 57 67 77 87 97
8 18 28 38 48 58 68 78 88 98
9 19 29 39 49 59 69 79 89 99

Проход по столбцам матрицы заведомо неэффективен, поэтому на такой программе должны быть хорошо видны результаты оптимизации. Попробуем замерить усредненное время выполнения программы для size=10000, скомпилированной с помощью g++ и sunCC:

g++ без оптимизации (g++ -O0 a.cpp): 2.6 сек
g++ c оптимизацией (g++ -O2 a.cpp): 2.0 сек

sunCC без оптимизации (sunCC a.cpp): 3.2 сек
sunCC c оптимизацией (sunCC -fast a.cpp): 0.4 сек

Опция -fast в suncc анализирует окружение и подбирает набор опций компилятора для максимального быстродействия. Видно, что sunCC в режиме оптимизации дает результаты в разы лучше, чем g++. А именно — в 5 раз. Хм...

Цель данной статьи совсем не в том, чтобы принизить возможности GCC. Для замеров использовался GCC версии 4.1. На данный момент существуют более новые версии этого компилятора, которые могут показать лучшие результаты оптимизации этого кода.

Давайте посмотрим, что же делает sunCC при оптимизации. Для этого необходимо использовать при компиляции опцию -g0. Эта опция сохраняет в объектном файле отладочную информацию (в том числе и комментарии компилятора), но не запрещает инлайнить функции. Для просмотра комментариев нужно использовать программу er_src, которая также поставляется с Sun Studio.

$ sunCC -g0 -fast a.cpp
$ er_src a.o

Source file: ./a.cpp
Object file: ./a.o
Load Object: ./a.o

1. int main ()

2. {
3. int c = 0;
4. int size = 10000;
5. int *a = new int[size * size];
6.

Source loop below has tag L1
Induction variable substitution performed on L1
L1 interchanged with L2

7. for (int i = 0; i < size; ++i)
8. {

Source loop below has tag L2
Induction variable substitution performed on L2
L2 interchanged with L1

9. for (int j = 0; j < size; ++j)
10. {
11. a[j * size + i] = c++;
12. }
13. }
14.
15. delete [] a;
16. return 0;
17. }

Итак, что же мы видим? Компилятор обнаружил в программе два цикла L1 и L2, которые поддаются оптимизации, о чем и сообщил в комментариях. Давайте попробуем улучшить программу, используя подсказки компилятора.

Подсказка "Induction variable substitution performed" говорит нам о том, что компилятор обнаружил индукционную переменную и произвел ее замену. Это значит, что значение какой-то переменной может быть вычислено через значения итераторов циклов. После недолгого изучения кода заменяем строку "a[j * size + i] = c++;" строкой "a[j * size + i] = i * size + j;". И прогоняем компиляцию еще раз.

Видим, что сообщение об индукционной переменной пропало, но осталось другое сообщение: "L1 interchanged with L2". Это сообщение говорит нам о том, что компилятор поменял циклы местами, то есть заменил проход по столбцам проходом по строкам матрицы. Меняем циклы местами и снова прогоняем компиляцию. И убеждаемся, что сообщения о том, что компилятор что-то оптимизировал, пропали. То есть, оптимизировать больше нечего.

После наших изменений программа приняла вот такой вид:

int main ()
{
  int c = 0;
  int size = 10000;
  int *a = new int[size * size];

  for (int j = 0; j < size; ++j)
  {
    for (int i = 0; i < size; ++i)
    {
      a[j * size + i] = i * size + j;
    }
  }

  delete [] a;
  return 0;
}

Давайте теперь замерим время выполнения программы после всех наших изменений:

g++ без оптимизации (g++ -O0 a.cpp): 1.0 сек
g++ c оптимизацией (g++ -O2 a.cpp): 0.4 сек

sunCC без оптимизации (sunCC a.cpp): 0.6 сек
sunCC c оптимизацией (sunCC -fast a.cpp): 0.4 сек

На мой взгляд, получилось просто прекрасно! :)

Подробнее почитать о комментариях компилятора Sun можно здесь: http://docs.sun.com/app/docs/doc/819-5264/afapn?a=view

Задачи на собеседованиях: синхронизация

Предположим, что из доступных средств синхронизации у нас есть только бинарные семафоры (мьютексы). При этом семафоры поддерживают только операции lock() и unlock().

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

Операция чтения может выполняться одновременно несколькими потоками, то есть когда один поток читает из ресурса, другие потоки тоже могут читать из этого ресурса, но писать в него не могут. Операция записи должна выполняться в эксклюзивном режиме, то есть во время записи никакие другие потоки не могут ни читать, ни писать.

Необходимо создать механизм синхронизации доступа к разделяемому ресурсу, который бы обеспечивал эксклюзивный доступ к ресурсу для записывающих потоков и одновременный доступ для читающих потоков, используя мьютексы. Количество используемых в решении мьютексов — на усмотрение разработчика.

После решения задачи, попытаться найти в решении недостатки и предложить более продвинутый вариант.

Подсказка:

Другими словами нужно самостоятельно реализовать аналог pthread_rwlock. Поэтому для начала нужно определить методы доступа к механизму синхронизации и отталкиваться уже от них. Например, пусть для потоков записи это будут функции writerLock() и writerUnlock(); для потоков чтения - readerLock() и readerUnlock(). Смысл этих функций аналогичен функциям lock() и unlock() для семафоров.

Кодоформатная паранойя

Есть у меня история из древности :)

Давным-давно программисты на Си при объявлении и определении функций не ставили пробелы между именем функции и открывающей круглой скобкой, а при вызове функций — ставили.

Для чего? Для того, чтобы grep'ом можно было легко найти или все вызовы функции или ее объявления.

Почему именно так ставили пробелы, а не наоборот? Потому, что иначе с define'ами была бы проблема. Ведь не напишешь же — "#define FUNC (A) ...". Только так — "#define FUNC(A) ...".

Возможно, некоторые моменты в этой истории спорные, но в общем история кажется мне вполне разумной.

Предупреждения GCC

Как я уже писал, компилятор gcc-4.3 умеет сообщать о потенциальной потере данных при преобразовании типов.

В дополнение к этому, в версии 4.3 появилось предупреждение о том, что объявление вида 'char *str = "abcd";' устарело и больше не должно использоваться. Причем предупреждение появляется даже без флагов -Wall, -Wextra и прочих. Как известно, использование в программе таких объявлений может привести к непредсказуемым последствиям. Вместо этого нужно использовать 'const char *str = "abcd";'. И это правильно.

UPD: Несмотря на дату, это не шутка :)

VMWare Tools и Ubuntu 8.10

На гостевую Ubuntu 8.10 инструментарий VMWare Tools устанавливается без особых проблем. Однако после перезагрузки не работает копирование/вставка и автоматическое смена разрешения при переключении в полноэкранный режим — несмотря на то, что vmware-user прописывается в автозапуск, то ли запуска не происходит, либо что-то не срабатывает, я не разбирался.

Как я понял, такая проблема не только у меня и решение есть только временное — либо при перезагрузке запускать vmware-user руками, либо прописать его в System->Preferences->Sessions.

Использование GCOV: ошибка при линковке

При сборке программы с включенными опциями для GCOV можно получить ошибку на этапе линковки следующего вида:

/usr/bin/ld: ./a.out: hidden symbol `__gcov_merge_add' in /usr/lib/gcc/i486-linux-gnu/4.1.3/libgcov.a(_gcov_merge_add.o) is referenced by DSO
/usr/bin/ld: final link failed: Nonrepresentable section on output

Скорее всего причина заключается в том, что к исполняемому модулю линкуются библиотеки, которые тоже были скомпилированы с опциями -fprofile-arcs -ftest-coverage.

Простой пример, иллюстрирующий проблему.

Даны два файла:

=== a.cpp
#include <stdio.h>

extern unsigned long myfunc ();

int main (int argc, char **argv)
{
  unsigned long z = myfunc();
  printf("%08x\n", z);
  return 0;
}

=== b.cpp
#include <time.h>

unsigned long myfunc ()
{
  return time(0);
}


Из файла b.cpp делаем статическую библиотеку libmy.a, а из файла a.cpp — исполняемый модуль a.out:

g++ -c -fprofile-arcs -ftest-coverage b.cpp
g++ -shared -o libmy.a ./b.o
g++ -c -fprofile-arcs -ftest-coverage a.cpp
g++ -o a.out a.o -L. -lmy


Получаем ошибку вида "undefined reference to `__gcov_init'" — забыли подключить библиотеку libgcov.a.

Подключаем к сборке требуемую библиотеку как обычно:

g++ -c -fprofile-arcs -ftest-coverage b.cpp
g++ -shared -o libmy.a ./b.o
g++ -c -fprofile-arcs -ftest-coverage a.cpp
g++ -o a.out a.o -L. -lmy -lgcov


Вот здесь-то и получаем странную ошибку:

/usr/bin/ld: ./a.out: hidden symbol `__gcov_merge_add' in /usr/lib/gcc/i486-linux-gnu/4.1.3/libgcov.a(_gcov_merge_add.o) is referenced by DSO
/usr/bin/ld: final link failed: Nonrepresentable section on output


Исправить это просто. Нужно подключить библиотеку libgcov.a не только к сборке исполняемого модуля, но и к сборке статической библиотеки:

g++ -c -fprofile-arcs -ftest-coverage b.cpp
g++ -shared -o libmy.a ./b.o -lgcov
g++ -c -fprofile-arcs -ftest-coverage a.cpp
g++ -o a.out a.o -L. -lmy -lgcov


Вот и всё. Так нужно поступить с каждой библиотекой, исходный код которой скомпилирован с опциями -fprofile-arcs -ftest-coverage.

Цветные diff'ы и less

Можно сделать работу с кодом в консоли более удобной, если раскрасить diff'ы. Это сделает текст более наглядным, а значит, упростит работу и увеличит производительность :)

Для этого нужно установить в системе пакет colordiff. После установки можно пользоваться командой colordiff точно так же, как и обычным diff'ом:

colordiff file1 file2

или использовать пайпы

diff file1 file2 | colordiff


Либо просто прописать алиас в .bashrc, если кого устраивает такой вариант:

alias diff=colordiff.


Тем, кто работает с CVS или SVN можно прописать в .bashrc или .profile следующие функции:

# color diffs for CVS
function cvsdiff () {
  if [ "$1" != "" ]; then
    cvs diff $@ | colordiff;
  else
    cvs diff | colordiff;
  fi
}

# color diffs for SVN
function svndiff () {
  if [ "$1" != "" ]; then
    svn diff $@ | colordiff;
  else
    svn diff | colordiff;
  fi
}


Настройка colordiff осуществляется через файл ~/.colordiffrc (настройки по умолчанию находятся в /etc/colordiffrc).

Чтобы использовать новые возможности вместе с командой less нужно заставить less понимать коды цветов. Для этого существует ключ -R:

colordiff file1 file2 | less -R


Для того, чтобы этот ключ использовался по умолчанию, нужно указать его в переменной окружения LESS:

export LESS="-R"


Вот и все.

Подсмотрено у drupal.org и rha7dotcom, а также в man colordiff.