Каковы преимущества использования хеш-таблицы для хранения методов внутри класса?

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

Примерный класс выглядит так:

class Foo
{
    var bar
    {
       function get { return bar; }
       function set(value) { bar = value; }
    }

    function f1() {...}
    function f2() {...}
}

Переменные экземпляра, объявленные внутри класса, защищены, и к ним могут обращаться функции установки/получения. Функции, объявленные внутри класса, являются общедоступными.

Во время выполнения переменные экземпляра могут храниться в массиве, поэтому в этом примере bar будет храниться в индексе 0 этого массива, и компилятор будет генерировать правильную инструкцию LOAD 0 в своей функции-получателе.

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

Каковы преимущества использования хеш-таблицы для хранения методов вместо обычного массива?


bytecode compiler-construction compiler-optimization interpreter vm-implementation
person Marco    schedule 19.01.2015    source источник
comment
Если он динамически типизирован, как компилятор узнает, какой индекс является правильным для данного имени члена? Например, если есть второй класс с элементами foo, bar, baz, то соответствует ли obj.bar где-то еще в коде LOAD 0 или LOAD 1?   -  person    schedule 19.01.2015
comment
Не путайте термины. Сначала вам нужно решить, основано ли ваше решение на массиве/списке (читай: индекс) или на основе карты (читай: имя). Только если вы решите использовать карту на основе карты, вы можете подумать о том, должна ли карта быть основана на хэше. В конце концов, существует больше алгоритмов отображения, чем хеширования, и для типичного количества функций в объекте хеширование не обязательно является самым эффективным выбором.   -  person Holger    schedule 20.01.2015

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

Итак, чтобы ответить на ваш вопрос, хеш-таблицы будут иметь то преимущество, что время поиска метода не будет расти, когда люди помещают большое количество методов (100, 1000) в один класс.

Недостаток хеш-таблиц состоит в том, что они могут увеличивать время поиска метода для классов с небольшим количеством методов (предположительно, менее нескольких десятков).

person Andru Luvisi    schedule 15.07.2015