Схема эффективности эффективности

Question

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

Очевидно, что ячейка cons хороша, чтобы сделать простую структуру данных, например, связанный список и деревья, но я думаю, что это может привести к замедлению кода в некоторых случаях, например, если вы хотите получить доступ к объекту cadr. Это ухудшится с структурой данных со многими другими элементами ...

Это может быть схема car и cdr настолько эффективна, что она не намного медленнее, чем наличие смещения регистра в C++, например.

Мне было интересно, нужно ли было реализовать специальную структуру данных, которая выделяет собственный блок памяти. Нечто похожее на использование malloc. Я говорю о чистой схеме, а не о FFI.

Answer 1

Как я понимаю, единственной реальной структурой данных в схеме является ячейка cons.

Это не так.

R5RS, R6RS и R7RS схема все включают в себя векторы и байты, а также пары/списки, которые являются смежными блоками памяти, на которые вы ссылаетесь.

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

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

Answer 2

Во-первых. Существует много примитивных типов и множество различных типов соединений и даже описанных пользователем типов в Схеме.

В C++ модель памяти и способы сохранения значений являются важной частью the standard. В Scheme у вас нет доступа к внутренним языкам в качестве стандарта, но реализация может сделать это, чтобы иметь более высокий процент реализации, написанной на Схеме.

Стандарт не мешает тому, как реализация решает хранить данные, поэтому, несмотря на то, что многие имитируют друг друга с введением примитивных значений в адрес, и в противном случае каждое другое значение является объектом в куче, ему не нужно , Использование пар в качестве реализации векторов (массивы в C++) подталкивает его и делает для очень непопулярной реализации, если не просто смешная шутка.

С R6RS вы можете сделать свои собственные типы, он даже расширяемой с records:

(define-record-type (node make-node node?) 
    (fields 
    (immutable value node-value) 
    (immutable left node-left)) 
    (immutable right node-right))) 

node? бы не пересекались и, таким образом, никакие другие значения не будет #t кроме значений, сделанных с помощью конструктора make-node и это имеет 3 поля вместо того, чтобы использовать два cons, чтобы сохранить их.

В настоящее время C++, пожалуй, является краеугольным камнем по умолчанию, когда речь идет о хранении элементов одного и того же типа в массиве, но вы можете во многом обойти это. Например. используйте тот же трюк, который вы видите в this video about optimizing java for memory usage. Я бы начал с создания хорошего моделирования данных с помощью записей и довольно беспокоился о производительности, когда они стали проблемой.