Может ли неизменный быть болотом памяти?

Ответ 1

Если этот класс является неизменным, не займет ли он огромного объема памяти?

Обычно ваши требования к памяти для этого единственного объекта могут удвоиться, потому что вы можете иметь "старую копию" и "новую копию" сразу. Таким образом, вы можете просмотреть это явление в течение всего жизненного цикла программы, поскольку у вас есть еще один крупный объект, который вы могли бы использовать в типичной императивной программе. (Объекты, которые не "работают", просто сидят там, с теми же требованиями к памяти, что и на любом другом языке.)

Как обрабатывать такую ​​ситуацию на функциональном языке?

Ничего не делать. Или, точнее, выделить новые объекты в хорошем состоянии. Если вы используете реализацию, предназначенную для функционального программирования, распределитель и сборщик мусора почти наверняка настроены на высокие уровни распределения, и все будет хорошо. Если у вас есть несчастье попытаться запустить функциональный код на JVM, то производительность не будет такой же хорошей, как при использовании на заказ, но для большинства программ все равно будет хорошо.

Можете ли вы предоставить более подробную информацию?

Конечно. Я приведу исключительно простой пример: 1000x1000 оттенков серого с 8 бит на пиксель, повернутый на 180 градусов. Вот что мы знаем:

• Для представления изображения в памяти требуется 1 МБ.

• Если изображение изменчиво, можно повернуть на 180 градусов, выполнив обновление на месте. Количество необходимого временного пространства достаточно для хранения одного пикселя. Вы пишете двойной вложенный цикл, который равен

  for (i in columns) do
    for (j in first half of rows) do {
       pixel temp := a[i, j]; 
       a[i, j] := a[width-i, height-j]; 
       a[width-i, height-j] := tmp
    }
  

• Если изображение неизменно, оно требует создания всего нового изображения, и вам временно придется висеть на старом изображении. Код выглядит примерно так:

  new_a = Image.tabulate (width, height) (\ x y -> a[width-x, height-y])
  

  Функция tabulate выделяет весь неизменный массив 2D и инициализирует его содержимое. Во время этой операции старое изображение временно занимает память. Но когда tabulate завершается, старое изображение a больше не должно использоваться, и его память теперь бесплатна (то есть имеет право на рециркуляцию сборщиком мусора). Таким образом, требуется количество временного пространства для хранения одного изображения.

• Пока происходит поворот, нет необходимости иметь копии объектов других классов; временное пространство необходимо только для поворота изображения.

N.B. Для других операций, таких как масштабирование или вращение (не квадратного) изображения на 90 градусов, вполне вероятно, что даже когда изображения изменяются, временная копия всего изображения будет необходима, поскольку размеры изменяются. С другой стороны, преобразования цветового пространства и другие вычисления, которые выполняются пикселем за пикселем, могут быть выполнены с использованием мутации с очень небольшим временным пространством.

Ответ 2

Да. Неизменность является компонентом вечного компромисса в пространстве-времени в вычислительной технике: вы жертвуете памятью в обмен на увеличенную скорость обработки, которую вы получаете в parallelism, выбирая блокировки и другие параллельные меры контроля доступа.

Функциональные языки обычно обрабатывают такие операции, разбивая их на очень мелкие зерна. Класс Image на самом деле не содержит логические биты данных изображения; скорее, он использует указатели или ссылки на гораздо меньшие неотменяемые сегменты данных, которые содержат данные изображения. Когда операции должны выполняться над данными изображения, меньшие сегменты клонируются и мутируются, и новая копия изображения возвращается с обновленными ссылками - большинство из которых указывают на данные, которые не были скопированы или изменены и остались неизменными.

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

Ответ 3

В некоторых случаях неизменяемость заставляет вас клонировать объект и требует выделения большего объема памяти. Это не обязательно занимает память, потому что старые копии могут быть отброшены. Например, сборщик мусора CLR очень хорошо справляется с этой ситуацией, поэтому это не обычно (обычно) большое дело.

Однако цепочка операций на самом деле не означает клонирование объекта. Это, безусловно, относится к функциональным спискам. Когда вы используете их обычным способом, вам нужно только выделить ячейку памяти для одного элемента (при добавлении элементов в начало списка).

Ваш пример обработки изображений может быть также реализован более эффективным способом. Я использую синтаксис С#, чтобы код был понятным, не зная какого-либо FP (но он выглядел бы лучше на обычном функциональном языке). Вместо фактического клонирования изображения вы можете просто сохранить операции, которые вы хотите сделать с изображением. Например, что-то вроде этого:

class Image { 
  Bitmap source;
  FileFormat format;
  float newWidth, newHeight;
  float rotation;

  // Public constructor to load the image from a file
  public Image(string sourceFile) { 
    this.source = Bitmap.FromFile(sourceFile); 
    this.newWidth = this.source.Width;
    this.newHeight = this.source.Height;
  }

  // Private constructor used by the 'cloning' methods
  private Image(Bitmap s, float w, float h, float r, FileFormat fmt) {
    source = s; newWidth = w; newHeight = h; 
    rotation = r; format = fmt;
  }

  // Methods that can be used for creating modified clones of
  // the 'Image' value using method chaining - these methods only
  // store operations that we need to do later
  public Image Rotate(float r) {
    return new Image(source, newWidth, newHeight, rotation + r, format);
  }
  public Image Resize(float w, float h) {
    return new Image(source, w, h, rotation, format);
  }
  public Image ConvertTo(FileFormat fmt) {
    return new Image(source, newWidth, newHeight, rotation, fmt);
  }

  public void SaveFile(string f) { 
    // process all the operations here and save the image
  }
}

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

 var i = new Image("file.jpg");
 i.Resize(500, 800).Rotate(90).ConvertTo(Gif).SaveFile("fileNew.gif");

Таким образом, код выглядит так, будто вы клонируете объект, и каждый раз, когда вы вызываете какую-либо операцию, вы создаете новую копию класса Image. Однако это не означает, что операция является дорогостоящей памятью - это может быть скрыто в функциональной библиотеке, которая может быть реализована различными способами (но при этом сохраняется важная ссылочная прозрачность).

Ответ 4

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

Возможно, вы заметили, что постоянные структуры данных, используемые в функциональных программах, склонны избегать массивов. Это связано с тем, что постоянные структуры данных обычно повторно используют большинство своих компонентов, когда они "модифицируются". (Они, конечно, не модифицированы, новая структура данных возвращается, но старая такая же, как и она.) Посмотрите это изображение, чтобы получить представление о том, как работает совместное использование структуры. В общем, древовидные структуры предпочтительнее, потому что новое неизменяемое дерево может быть создано из старого неизменяемого дерева, только переписывая путь от корня до node. Все остальное можно повторно использовать, делая процесс эффективным как во времени, так и в памяти.

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

Я не хочу утверждать, что неизменность - это всегда и везде ответ - правда и праведность функционального программирования в конце концов должны быть смягчены прагматизмом.

Ответ 5

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

Ответ 6

Короткий, тангенциальный ответ: на языке FP я знаком с (scala, erlang, clojure, F #), а для обычных структур данных: массивами, списками, векторами, кортежами, вам нужно понимать мелкие/глубокие копии и как они реализованы:

например.

Scala, метод clone() и конструктор копирования

Выполняет ли Scala AnyRef.clone мелкую или глубокую копию?

Erlang: сообщение, передающее структуру с неполной копией данных, может взорвать процесс:

http://groups.google.com/group/erlang-programming/msg/bb39d1a147f72800