| 2:48p |
Взял числа от 1 до 9 (без перестановок), четыре арифметические операции (+, -, *, /) и построил декартов квадрат: все возможные размещения операций на все возможные расстановки скобок. И этот сучок не влазит в 32 гига рамы! Не пойму, мощность квадрата = C_8 * 4^8 = 93'716'480 ~ 100 млн. Это что, одна формула занимает больше 3*10^10 / 10^8 = 300 байт?
Формула - во вложенном списке, т.е. 9 + 8 = 17 элементов. Ну, добавим терминаторы +8 = 25. Это что, по 12 байт на элемент? Что за оверхед. Ну, возможно racket лочит память в стиле коллекций дотнета, c выравниванием до 2^n. Вполне возможно, если хранить списки в массивах.
Ладно, хуй с ним, снял лимит по памяти. Тот елозил свопом всю ночь, но так и не доелозил. А для 8 элементов за 2 минуты считается, и занимает 5-6 Гб. Это C_7 * 4^7 = ~7 млн формул. Ну, понятно, что по мегабайту такие маленькие списки не могут занимать, просто сборки мусора не было. Но всё равно, слишком много, мне кажется.
Теперь два-три варианта вижу, или переложить алгоритм на ... Немерле? Хаскелл бы хорошо, но думаю, там по памяти не лучше, чем Схема будет. Или проиндексировать квадрат и оставлять только индексы. Размещения индексируются естественным образом по два байта (4^8 = 2^16). Для скобок (двоичных деревьев с 9 листьями) естественной нумерации не знаю, но можно индексировать через рекурсию, которой они строятся (она ведь детерминированная). Или ещё проще, вдоль одного измерения квадрата - индексировать, вдоль второго - нет. Наверное, так и сделаю.
А у бразильца-то было 6 операций в конце, а не 4. Так что мощность будет C_8 * 6^8 = ~2.4 млрд, однако. И хотя, если делать то же, что и бразилец (поиск разложения числа, анализ лакун), то прямое произведение хранить не нужно, и достаточен лишь перебор, но я хочу построить 3-мерный график на этом квадрате и, вообще, посмотреть на все возможные способы разложения, пересчитать варианты и т. д. Здесь, однако, надо начинать с упрощённых случаев. |