Мы реализуем библиотеку сжатия матрицы на основе модифицированного синтаксиса двумерной грамматики. Теперь у нас есть два подхода к нашим типам данных - какой из них будет лучше в случае использования памяти? (мы хотим что-то сжать;)).
Грамматики содержат нетерминалы с ровно 4 продукцией или терминалом с правой стороны. Нам понадобятся имена Productions для проверки равенства и минимизации грамматики.
Первое:
-- | Type synonym for non-terminal symbols
type NonTerminal = String
-- | Data type for the right hand side of a production
data RightHandSide = DownStep NonTerminal NonTerminal NonTerminal NonTerminal | Terminal Int
-- | Data type for a set of productions
type ProductionMap = Map NonTerminal RightHandSide
data MatrixGrammar = MatrixGrammar {
-- the start symbol
startSymbol :: NonTerminal,
-- productions
productions :: ProductionMap
}
Здесь наши данные RightHandSide сохраняют только строковые имена для определения следующих производств, и здесь мы не знаем, как Haskell сохраняет эти строки. Например, матрица [[0, 0], [0, 0]] имеет 2 произведения:
a = Terminal 0
aString = "A"
b = DownStep aString aString aString aString
bString = "B"
productions = Map.FromList [(aString, a), (bString, b)]
Итак, вопрос здесь в том, как часто действительно сохраняется строка «А»? Один раз в aString, 4 раза в b и один раз в спектаклях или только один раз в aString, а остальные просто содержат «более дешевые» ссылки?
Секунда:
data Production = NonTerminal String Production Production Production Production
| Terminal String Int
type ProductionMap = Map String Production
здесь термин «Терминал» немного вводит в заблуждение, потому что это фактически производство, которое имеет терминал с правой стороны. Та же матрица:
a = Terminal "A" 0
b = NonTerminal "B" a a a a
productions = Map.fromList [("A", a), ("B", b)]
и аналогичный вопрос: как часто продукция сохраняется внутри Haskell? Возможно, мы будем отбрасывать имена внутри производств, если они нам не нужны, но сейчас мы не уверены в этом.
Допустим, у нас есть грамматика с около 1000 произведений. Какой подход потребляет меньше памяти?
Наконец, вопрос о целых числах в Haskell: в настоящее время мы планируем иметь имя как Strings. Но мы могли бы легко переключиться на целочисленные имена, потому что с 1000 продукций у нас будут имена с более чем 4 символами (который я предполагаю, является 32-разрядным?). Как Хаскелл справляется с этим? Всегда ли Int 32-разрядный, а Integer выделяет память, которая ему действительно нужна?
Я также прочитал это: Разработка теста семантики значения / ссылки в Haskell - но я не могу понять, что именно это означает для нас - я скорее обязательный ребенок java, чем хороший функциональный программист: P
источник