Внутреннее представление кортежа
Запись от CoderHuligan размещена 07.02.2022 в 18:08
Показов 2014
Комментарии 6
|
Внешнее представление языка программирования (далее ЯП) очень важная вещь, но еще более важно как он устроен на внутреннем уровне. То есть каким образом реализованы те или иные структуры данных и пр. и с какой эффективностью они работают во время исполнения ( в ран-тайме). Самой важной структурой данных в нашем языке будет кортеж - коллекция данных разных типов, доступ к которым должен обеспечиваться по индексам. Этими типами могут быть обычные массивы, целые и дробные числа, кортежи, множества и функции. Каким образом это делается в других языках, например в lua, euphoria, pithon и пр.? По разному. В основном используются либо динамические списки, либо гетерогенные массивы указателей на аллоцируемые динамически данные. Но такая организация данных имеет свои недостатки. Постоянно аллоцируемые маленькие участки памяти сильно фрагментируют память, что при длительной работе кода может привести к её деградации - исчерпании участков необходимой длины. malloc увы не дефрагментирует память, да это и невозможно. Эту проблему ЯП решают создавая свои аллокаторы. Например выделяют блоки определенной величины и избегая излишних обращений к malloc просто выделяют участки из уже выделенных блоков. Но это не решает проблему кардинально. Слишком все сложно получается на внутреннем уровне, да и скорость падает. Чтобы память не деградировала в ней всегда должны быть участки достаточной длины. Этого можно достичь только выделяя участки вдвое большей величины, чем действительно необходимая память. А еще лучше выделять участки в прогрессии 2 4 8 16 и т.д. Этого можно достичь только используя базовую структуру типа массив. И массив этот должен естественно быть динамическим. Обычно такие массивы создают выделяя отдельно память под структуру, в которой содержится указатель на блок данных + длина массива и длина выделенной памяти. Однако, в таком случае приходится принимать меры для поддерживания двух указателей вместо одного. Строковая библиотека sds, которая входит в базу данных redis, вообще отказалась от отдельной структуры и создала ячейки для хранения длины массива и длины памяти позади адреса с первой ячейкой массива. При этом требуется всего лишь один указатель. Так поступим и мы. Но как это сделать если массив гетерогенный, да еще нужно реализовать динамическую структуру типа последовательность, в которой можно добавлять элементы в начало и конец с одной и той же скоростью? Долго я ломал голову над этим.. Каких только вариантов не передумал! Однако в конце концов остановился на такой схеме. Итак, выделяем блок памяти под наш массив. При помощи того же malloc. В первом элементе будут два поля - 1 - длина выделенного блока (long lm[2]; - смотри ниже в структуре ); 2 - размер элемента. Во втором элементе содержаться также два поля: 1 - начало "головы" массива; 2 - фактическая длина. В остальных элементах, начиная с третьего, начинается сама область последовательности. Формат самого элемента последовательности выполнен примерно так:
Удаление элементов из такой структуры данных может быть двух типов. Если данные упорядочены в массиве и нужно сохранить их порядок, то удаляем элемент сдвигом части массива на освободившееся место. Такая операция конечно затратна, но не сильно при нынешних скоростях. Если же упорядоченность не нужна, то удаляем элемент копированием на его место последнего элемента с последующим уменьшением длины массива на 1. Модуль с конкретной реализацией еще не создан. Интересно кто либо реализовывал кортежи подобным образом? Думаю, что работа с кортежем по такой схеме будет гораздо быстрее и эффективнее. | |||||
Размещено в Без категории
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 6
Комментарии
-
Элемент очень похож на VARIANT из Microsoft Visual Basic.Запись от politoto размещена 07.02.2022 в 20:05 
-
Вроде похож, но как там он у майкров реализован на внутреннем уровне - неясно.Запись от CoderHuligan размещена 08.02.2022 в 11:42
-
>В первом элементе будут два поля - 1 - длина выделенного блока (long lm[2]; - смотри ниже в структуре ); 2 - размер >элемента. Во втором элементе содержаться также два поля: 1 - начало "головы" массива; 2 - фактическая длина.
А почему бы их просто не втащить под своими именами в структуру? И с индексацией не придется куролесить.
>char a;//для идентификации типа в ран-тайм
Что в рантайм, что не в рантайм, тип однозначно определен в идентификаторах юниона.
ПС: я услышал слово Рапира. Насколько я понимаю, слово кортеж выплыло из нее. В нынешних языках это слово (кортеж) трактуют совершенно иначе.
ППС: интересную тему подняли, готов пообсуждать, если что.Запись от vantfiles размещена 08.02.2022 в 12:26
-
Тогда надо будет иметь отдельный указатель на структуру и выделять эту структуру динамически, а это чревато возможной деградацией памяти из-за того, что структура мала к тому же будут и другие структуры других размеров.. Неоправданное усложнение. Гораздо удобнее иметь один единственный указатель на блок памяти, который можно освобождать в одном месте. гораздо меньшая вероятность ошибок. Также не вводить счетчик ссылок или сборщик мусора.
А как тогда определить тип элемента, например во время операции сложения разных типов, когда нужно будет приводить один тип к другому?
Верно. Это из Рапиры. В питоне это совершенно иная концепция. Надо ввести другое обозначение, например - ряд.
Ок.
Впереди представления динамических строк и массивов однотипных элементов. Считаю, что универсализм вреден - надо иметь и обычные массивы , но с возможностью контроля индексов в ран-тайм. Но сначала нужно с нашим кортежем разобраться.Запись от CoderHuligan размещена 08.02.2022 в 13:26
-
Указатель на указатель естественно.Запись от CoderHuligan размещена 09.02.2022 в 19:22
-
Сорян, я вообще не о том. Удалил.
Запись от Hrethgir размещена 17.02.2022 в 23:28
