Попалась на глаза книжка "Порождающее программирование" и возникла идея применить принципы, описанные в книге, при реализации эффективной реализации списков.
Принцип порождающего программирования состоит в том, пользователь (программист) может получить конкретную реализацию нужной ему системы, указав ее свойства (естественно, в ограниченных пределах). Для этого формируется надсистема, которая учитывает возможный настройки пользователя и создает конкретную эффективную реализацию системы на основе предъявленных к ней требований. Причем конкретная реализация формируется автоматически (без участия пользователя) из "строительных блоков", заложенных в надсистеме.
В общем, в той или иной мере это все пересекается с MDA, DSL и прочими интересным вещами
Т.е. в нашем случае необходимо сформировать не одну конкретную реализацию списка (на массивах, на указателях и т.п.), а некоторую общую реализацию, которая может быть подстроена к требованиям пользователя. Указав требования (например, оценку по времени добавления и удаления элементов, оценку требований к памяти) мы сможем получить конкретную эффективную реализацию списка, удовлетворяющего этим требованиям. Причем конкретная реализация должна формироваться автоматически.
Например:
— указав, что наш список имеет фиксированную длину и операции вставки и удаления не предвидятся, должна быть сформирована реализация списка на основе массива
— наоборот, указав, что предвидится большое количество вставок будет сформирована реализация на основе связный список и т.п.
Для воплощения всего этого в жизнь надо:
1. Определиться с какими-то элементарными операциями над списками. Например:
— вставка элемента в начало/конец/конкретную позицию
— удаление элемента из начала/конца/конкретной позиции
— обновление элемента в начале/конце/конкретной позиции
— соединение списков
— разделение списков
— ... добавьте свое, удалите лишнее и пр.
2. Определиться с возможными "строительными блоками", например:
— реализация на основе массива (всегда полностью заполненный массив). Легко читать и обновлять, но если требуется вставка или удаление приходится копировать массив в другое место
— реализация на основе не полностью заполненного массива (т.е. длина массива больше или равна длине списка). Здесь при вставке и удалении не приходится копировать массив, но все же если количество элементов превысит размер массива, то его также придется копировать (добавив некоторые количеством дополнительных элементов)
— реализация на основе односвязного списка
— реализация на основе двусвязного списка
— ... добавьте свое, удалите лишнее и пр.
— а также большое количество различных комбинаций: массив массивов, список массивов, массив списков, список списков с любыми уровнями вложенности.
3. Определиться со способом задания требований:
— на основе нужно/не нужно: вставка будет, удаление нет, обновление будет
— по количеству операций: вставка столько-то % от всех операций, обновление столько-то %
— по оценкам: память не больше O(10n), время вставки O(1)
— ... добавьте свое, удалите лишнее и пр.
В итого должен получиться класс (допустим), который должен проанализировать п.3, и эффективно реализовать п.1 на основе п.2.
Кто-что думает по этому поводу?. Ну и критика/комментарии п.1, п.2, п.3
P.S. Только не спрашивайте зачем это нужно
Во-первых, это может быть еще кому-то интересно.
Во-вторых, возможно, такие вещи можно использовать в компиляторах языков, активно работающих со списками. Например на основе анализа кода или же прямых указаний пользователя происходят некоторые оптимизации работы со списками.
Хотя, может уже все придумано?
B>Кто-что думает по этому поводу?. Ну и критика/комментарии п.1, п.2, п.3
B>P.S. Только не спрашивайте зачем это нужно B>Во-первых, это может быть еще кому-то интересно.
Попробуй оценить "экономический эффект". Время твоей разработки, время на изменение типичной программы на списках на другую структуру данных, количество таких программ и эффект от оптимизации.
Например, я часто использую ассоциативные списки. Так мне их заменить на отображения — раз плюнуть. Поэтому я заморачиваться на порождающее программирование не буду. По крайней мере, в этом случае.
B>Во-вторых, возможно, такие вещи можно использовать в компиляторах языков, активно работающих со списками. Например на основе анализа кода или же прямых указаний пользователя происходят некоторые оптимизации работы со списками. B>Хотя, может уже все придумано?
Здравствуйте, thesz, Вы писали:
T>Попробуй оценить "экономический эффект". Время твоей разработки, время на изменение типичной программы на списках на другую структуру данных, количество таких программ и эффект от оптимизации.
Зачем? Ведь я не призываю быстренько переписать программы используя СуперПуперСписок
T>Например, я часто использую ассоциативные списки. Так мне их заменить на отображения — раз плюнуть. Поэтому я заморачиваться на порождающее программирование не буду. По крайней мере, в этом случае.
Фишка в том, что можно конструировать списки с любыми комбинациями свойств.
Библиотеки же содержат 2-3 предопределенных реализации списков. Когда чего-то не хватает, приходится придумывать свою структуру данных, которая в большинстве повторяет то, что уже есть с небольшими отличиями. А здесь не надо придумывать, оно все само
Хочу быстро добавлять в середину — LinkedList (есть в стандартной библиотеке).
Хочу отсортированный список и быстро добавлять — SortedLinkedList (есть в стандартной библиотеке).
Хочу отсортированный список, быстро добавлять, и O(log n) для чтения — придется писать самому.
Кроме того, списками можно и не ограничиваться. Ввести свойство "обращение не по номеру, а по ключу", и вот теперь умеем создавать Map, в т.ч. обычный и отсортированный. В общем, множество реализаций контейнеров пересекаются, так почему не извлечь из этого пользу.
В любом случае, вопрос скорее теоретический. Как должны выглядеть п.1, п.2, п.3 для списков?
И во вторую очередь мне бы хотелось увидеть, как может выглядеть обобщенная реализация всего этого дела для конкретных этих пунктиков.
T>
T>>Попробуй оценить "экономический эффект". Время твоей разработки, время на изменение типичной программы на списках на другую структуру данных, количество таких программ и эффект от оптимизации. B>Зачем? Ведь я не призываю быстренько переписать программы используя СуперПуперСписок
Просто есть более полезные области, не более того.
T>>Например, я часто использую ассоциативные списки. Так мне их заменить на отображения — раз плюнуть. Поэтому я заморачиваться на порождающее программирование не буду. По крайней мере, в этом случае. B>Фишка в том, что можно конструировать списки с любыми комбинациями свойств. B>Библиотеки же содержат 2-3 предопределенных реализации списков. Когда чего-то не хватает, приходится придумывать свою структуру данных, которая в большинстве повторяет то, что уже есть с небольшими отличиями. А здесь не надо придумывать, оно все само
Само ли?
B>Хочу быстро добавлять в середину — LinkedList (есть в стандартной библиотеке). B>Хочу отсортированный список и быстро добавлять — SortedLinkedList (есть в стандартной библиотеке). B>Хочу отсортированный список, быстро добавлять, и O(log n) для чтения — придется писать самому. B>Кроме того, списками можно и не ограничиваться. Ввести свойство "обращение не по номеру, а по ключу", и вот теперь умеем создавать Map, в т.ч. обычный и отсортированный. В общем, множество реализаций контейнеров пересекаются, так почему не извлечь из этого пользу.
Что-то мне ничего в голову не идёт, окромя зависимых типов данных.
И вообще, здесь проблем возникает не меньше, чем решается.
B>В любом случае, вопрос скорее теоретический. Как должны выглядеть п.1, п.2, п.3 для списков?
Нельзя объять необъятное.
В твоём случае они вот так и должны выглядеть.
B>И во вторую очередь мне бы хотелось увидеть, как может выглядеть обобщенная реализация всего этого дела для конкретных этих пунктиков.
Можешь на этом остановиться и начинать реализовывать.
Здравствуйте, Beam, Вы писали:
B>3. Определиться со способом задания требований: B>- на основе нужно/не нужно: вставка будет, удаление нет, обновление будет B>- по количеству операций: вставка столько-то % от всех операций, обновление столько-то % B>- по оценкам: память не больше O(10n), время вставки O(1) B>- ... добавьте свое, удалите лишнее и пр.
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, Beam, Вы писали:
B>>3. Определиться со способом задания требований: B>>- на основе нужно/не нужно: вставка будет, удаление нет, обновление будет B>>- по количеству операций: вставка столько-то % от всех операций, обновление столько-то % B>>- по оценкам: память не больше O(10n), время вставки O(1) B>>- ... добавьте свое, удалите лишнее и пр.
BZ>ага. Волшебная Палочка 2.0
Не понимаю сарказма.
Есть требования. На основе них надо выбрать конкретную реализацию, или сформировать новую реализацию на основе каких-то правил.
Допустим требования задаются в виде нужно/не нужно.
Требования: вставка будет, удаление нет, обновление будет => выбираем реализацию на массивах
Это будет, это нет -> здесь лучше всего подойдет ...
Допустим требования по количеству операций: вставка столько-то % от всех операций, обновление столько-то %
Выбираем реализацию:
Если вставка > 50% => linkedList
Если вставка > 10% ?? обновление > 50% => список массивов по столько-то элементов
В остальных случаях => Обычный массив
Допустим требования задаются оценками:
время вставки O(1) => выбираем реализацию на LinkedList
время вставки ..., поиск элемента .., выбор отсортированного ... => Реализация на основе ...
Вставка O(1), поиск O(1) => реализация с такими требованиями невозможна
В итоге. Имеем требования => Выбрали подходящую комплексную реализацию (например, массив списков) => Собрали комплексную реализацию из маленьких реализаций (например, массив, двунаправленный связный список) => Получили реализацию с данными свойствами
Мне кажется, что хоть это хорошая идея, но она вряд ли получит широкое практическое применение.
1. Как вы представляете формализацию требований? Сама по себе это очень сложная задача, программисту можно объяснить на пальцах и он поймет, воспользовавшись огромным опытом, а вот с машинным описанием все намного сложнее. Игрушечные примеры — типа реализации сортировки или списка не в счет. Основываясь на своем опыте рискну предположить, что затраты на реализацию таких конструкций как раз ничтожны.
2. Как вы представляете себе описание этой "надсистемы" (базы знаний для реализации программных конструкций на основе входных требований)? Во сколько раз дороже реализация такого монстра чем просто кодирование?
3. В конце концов как выполнять отладку всей системы? Каким образом предполагается отслеживание ошибок допущенных на каждом из уровней реализации?
Вот вам "риаллайф" задача:
Предположим, что дядя Вася программист, и хочет чтоб "надсистема" пользуясь функциями WindowsAPI сгенерировала код для копирования из директории в директорию (считаем, что у нас нет простой функции для выполнения этой задачи).
Задача кажется тривиальной, но на ее примере будет любопытно посмотреть на реализацию таких вещей, как-
1. Дядя Вася захочет обрабатывать ошибки, предположим что у нас будут такие стратегии, как:
— игнорирование ошибок
— сообщение об ошибках через исключения
— -- через код возврата
2. Дядя Вася захочет изменить поведение при ошибке:
— копируем сразу в директорию назначения, ошиблись, ну и хрен с ним
— копируем во временную директорию, при ошибке — стираем ее содержимое (как ведут себя архиваторы, типа 7zip)
— копируем сразу в директорию назначения...
3. Дяде Васе взбрело в голову поддерживать протоколы, т.е. реализовать копирование из/в файловой системы по протоколу file://, из сети — http://, из зашифрованного источника бабымани — manya://
4. Нужно реализовать ту же операцию в асинхронном стиле, без использования сторонних библиотек для какой-нибудь платформы с MedvedOS
Думаю, что реализация всех этих вещей сама по себе может стать непростой задачей, а если еще учитывать, что программист должен будет выполнять работу по созданию "надсистемы" и отлаживать получившийся пирог...
