Программист-прагматик. Путь от подмастерья к мастеру - Хант Эндрю - Страница 83

83

Сбалансированное двоичное дерево содержит вдвое больше элементов на каждом уровне. Дерево глубиной D содержит 1+2+4+8 +… +2^(D-1), или 2^D – 1 элементов. Следовательно, дереву, состоящему из миллиона элементов, будет необходимо [lg(1000001], или 20 уровней.

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

Упражнение 36 из раздела "Скорость алгоритма"

Ответ: На ум приходит несколько процедур оптимизации. Программа printTree вызывает саму себя на вершинах дерева лишь для того, чтобы закончить работу при отсутствии потомков. Этот вызов увеличивает максимальную глубину стека примерно на 1000 байт. Можно также исключить рекурсию хвоста (второй рекурсивный вызов), хотя это и не будет затрагивать использование стека в наихудшем случае.

while (node) {

  if (node->left) printTree(node->left);

  getNodeAsString(node, buffer);

  puts(buffer);

  node = node->right;

}

Но самая большая выгода возникает при назначении одного-единственного буфера, доступ к которому осуществляется при всех обращениях к printTree. Если передать этот буфер в виде параметра для рекурсивных обращений, то будет назначено всего 1000 байт вне зависимости от глубины рекурсии.

void printTreePrivate(const Node *node, char *buffer) {

  if (node) {

    printTreePrivate(node->!eft, buffer);

    getNodeAsStringfnode, buffer);

    puts(buffer);

    printTreePrivate(node->right, buffer);

  }

}

void newPrintTree(const Node *node) {

  char buffer[1000];

  printTreePrivate(node, buffer);

)

Упражнение 37 из раздела "Скорость алгоритма"

Ответ: Это можно сделать двумя путями. Один из них заключается в том, чтобы перевернуть проблему с ног на голову. Если в массиве есть лишь один элемент, мы не осуществляем итерации в цикле. Каждая дополнительная итерация удваивает размер массива, в котором можно осуществлять поиск. Отсюда общая формула размера массива: n = 2^m, где m – число итераций. Если прологарифмировать обе части с основанием 2, получим выражение lg(n) = lg(2^m), которое из определения логарифма превращается в lg(n) =m.

Упражнение 38 из раздела "Реорганизация"

Ответ: Здесь мы могли бы предложить весьма умеренную реструктуризацию: убедитесь, что каждый тест выполняется лишь один раз, и сделайте все вычисления стандартными. Если выражение 2*basis (…)* 1.05 появляется в других местах программы, то, вероятно, его стоит сделать функцией. В данном случае мы этого делать не стали.

Мы добавили массив rate_lookup, инициализированный таким образом, что элементам, отличным от Texas, Ohio и Maine, присвоено значение 1. Этот подход облегчает добавление значений для других штатов в будущем. В зависимости от ожидаемой схемы использования мы могли бы сделать поле points также средством поиска в массиве.

rate = rate_lookup[state];

amt = base * rate;

calc = 2*basis(amt) + extra(amt)*1.05;

if (state == OHIO)

   points = 2;

Упражнение 39 из раздела "Реорганизация"

Ответ: Когда вы видите, что кто-либо использует перечислимые типы (или эквивалентные им в языке Java), для того чтобы провести различие между вариантами некоего типа, во многих случаях вы можете улучшить программу за счет создания подклассов:

public class Shape {

  private double size;

  public Shape(double size) {

     this.size = size;

  }

  public double getSize() {return size;)

}

public class Square extends Shape {

  public Square(double size) {

    super(size);

  }

  public double area() {

    double size = getSize();

    return size*size;

  }

)

public class Circle extends Shape {

  public Circle(double size) {

    super(size);

  }

  public double area() {

    double size = getSize();

    return Math.PI*size*size/4.0;

  }

}

// efc…

Упражнение 40 из раздела "Реорганизация"

Ответ: Этот случай интересен. На первый взгляд, кажется разумным, что у окна должна быть ширина и высота. Однако стоит подумать о будущем. Представим, что мы хотим обеспечить поддержку окон произвольной формы (что будет весьма трудно, если класс Window обладает всей информацией о прямоугольниках и их свойствах).

Мы бы предложили абстрагировать форму окна из самого класса Window.

public abstract class Shape {

//...

  public abstract boolean overlaps (Shape s);

  public abstract int getArea();

}

public class Window {

  private Shape shape;

  public Window(Shape shape)  {

     this.shape = shape;

     ...

}

public void setShape(Shape shape) {

   this.shape = shape;

   ...

}

public boolean overlaps(Window w) {

   return shape.overlaps(w.shape);

}

public int getArea() {

   return shape.getArea();

}

}

Заметим, что в этом подходе мы предпочли делегирование созданию подклассов: окно не является «разновидностью» формы – окно «имеет» форму. Оно использует форму для выполнения своей работы. Вы убедитесь, что во многих случаях делегирование оказывается полезным для реорганизации.

Мы могли бы расширить этот пример, внедрив интерфейс Java, указывающий на методы, которые должны поддерживаться неким классом для поддержания функций формы. Эта удачная идея означает, что, когда вы расширяете принцип формы, компилятор предупредит вас о классах, которые вы затронули. Мы рекомендуем использовать интерфейсы подобным способом при делегировании всех функций какого-либо другого класса.

Упражнение 41 из раздела "Программа, которую легко тестировать"

Ответ: Вначале добавим подпрограмму main, которая будет действовать как ведущий элемент модульного тестирования. В качестве аргумента она примет простой мини-язык: будет означать опорожнение блендера, – его наполнение, цифры 0–9 будут задавать скорость вращения ротора, и т. д.

public static void main(String args[]) {

// Create the blender to test

  dbc_ex blender = new dbc_ex();

// And test it according to the string on standard input

  try {

    int a;

    char c;

    while ((a = System.in.read())!= -1) {

       с = (char)a;

       if (Character.isWhitespace(c)) {

          continue;

       }

       if (Character.is Digit(с)) {

          blender.setSpeed(Character.digit(c, 10));

       }

      else {

         switch (c) {

          case 'F': blender.fi!l();

                       break;

          case 'E': blender.empty();

                       break;

          case 's': System.out.printlnfSPEED: " + blender.getSpeed());

                       break;

          case 'f': System.out.println( + blender.isFull());

                       break;

          default: throw new RuntimeException(

                       "Unknown Test directive");

   }

 }

}

catch (java.io.lOException e) {

  System.err.println("Tesf jig failed: " + e.getMessage());

}

System.err.println("Completed blending\n");

System.exit(0);

}

Затем появится сценарий оболочки для управления тестированием.

#!/bin/sh

CMD="java dbc.dbc_sx"

failcount=0

expect okay() {

  if echo "$*" | $CMD #>/dev/null 2>&1

  then

  ...

  else

     echo "FAILED! $*"

     failcount='expr $failcount + 1'

  fi

}

expect_fail() {

if echo "$*" | SCMD>/dev/null 2> &1

then

  echo "FAILED! (Should have failed): $*"

   failcount='expr $failcount + 1'