Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 23:48

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 44 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: *масштабируемый счетчик длины строки
СообщениеДобавлено: Чт мар 20, 2008 12:04 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Надеюсь все знакомы с тем, как в СПФ хранятся строки и каких типов они бывают...
А так же знакомы с проблемами, которые возникают при попытке сохранить в памяти
строку со счетчиком, длиной более 255 байт.

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

Выходов видится из этой проблемы несколько, например, можно поступить со счетчиком
длины строки так, как поступают с кодированием utf8 символов, которые могут
кодироваться последовательностью от 1 до 6 байт. Как простейший вариант, можно
старший бит в байте отвести под префикс расширения, таким образом, строки длиной
менее 128 символов будут иметь счетчик длиной в один байт, более длинные строки
буду иметь два байта, еще более длинные 3 и так далее:
<pre>
127: 01111111
150: 10000000 00010111
561744: 10100010 10100100 01010000
</pre>
Необходимо найти быстрое и простое решение, позволяющее кодировать длину счетчика
строки наиболее оригиальным и практичным образом в памяти.
Как всегда задаются имена и стековые диаграммы необходимых слов, но в данном задании
стековые диаграммы могут быть изменены наиболее практичным на ваш взгляд образом.
Код:

\ сохранить счетчик длины строки u в памяти по адресу addr
\ вернуть длину # байт, занятых под счетчик строки
: SCNT! ( u addr --> # )
        ;

\ прочесть счетчик длины строки u из памяти по адресу addr,
\ длину счетчика строки в байтах.
: SCNT@ ( addr --> u # )
        ;

\ вернуть адрес начала строки addr и ее длину в байтах
: SCOUNT ( '#str --> addr u )
         ;

\ компилировать строку со счетчиком на вершину кодофайла
: s", ( asc u --> )
      ;

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Последний раз редактировалось mOleg Чт мар 20, 2008 15:56, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 12:21 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
может, имеет смысл сделать идентификатор количества байт в счетчике более прозрачным?

Например, в первом байте два старших бита под это задействовать
<pre>

00 -> остальные 6 бит байта - длина строки

01 -> длина строки 14 бит

10 -> длина строки 22 бита

11 -> длина строки 30 бит

</pre>

хотя, с 22-мя битами длины строки - оно как бы и не особо надо. Можно извернуться, и назначить тег 10, например, для строк со сжатием налету ;)

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 12:37 
расширяя идею WingLion
отдать целиком первый байт под описатель длины строки
компрамисный так сказать вариант и срок жизни его с учетом развития техники так сказать пригоден
(сколько лет пройдет когда нам перестанет хватать строк в 64К ? один? два? три? )
тратим минимум два байта в первом указываем количество байт на длинну строки и вперед :)


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 12:41 
* отдать целиком первый байт под описатель количества байт указателя длины строки


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 12:41 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
64К уже и сейчас не хватает, если под "строкой" подразумевать, например, редактируемый текстовый файл :) (Нe название, а содержимое)

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 12:46 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
mrack_ писал(а):
отдать целиком первый байт под описатель длины строки компрамисный так сказать вариант и срок жизни его с учетом развития техники так сказать пригоден (сколько лет пройдет когда нам перестанет хватать строк в 64К ? один? два? три? )

ну, могу просто сказать, увеличение счетчика строки в два раза на форке приводит к увеличению исполнимого файла на 717 байт, а при использовании 4 байтового - 2159байт. Не много, но и не так уж и мало. Но дело в том, что в строке может храниться не только имя слова 8)

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 12:51 
mOleg писал(а):
ну, могу просто сказать, увеличение счетчика строки в два раза на форке приводит к увеличению исполнимого файла на 717 байт, а при использовании 4 байтового - 2159байт. Не много, но и не так уж и мало. Но дело в том, что в строке может храниться не только имя слова 8)

С этим придется мириться. В условиях 32-бит архитектуры 4 байта на счетчик - оптимально имхо.


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 12:54 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Владимир писал(а):
С этим придется мириться.

Читаем ТЗ,

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

Посему следующее сообщение подобного рода будет удалено.

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 13:19 
Не в сети

Зарегистрирован: Вс дек 02, 2007 17:31
Сообщения: 442
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Поскольку длины строк 128<n<255 встречаются чаще чем n>255, да и счетчик занимает бОльшую часть от строки в коротких строках, то мне кажется имеет смысл использовать следующий принцип:
- если первый байт 0..254, то это длина строки, которая следует сразу за ним;
- если первый байт =255, то длина-255 в следующих 3-х байтах.

Код:
\ сохранить счетчик длины строки u в памяти по адресу addr
\ вернуть длину # байт, занятых под счетчик строки
: SCNT! ( u addr --> # ) OVER 255 < IF C! 1 ELSE SWAP 255 - 8 LSHIFT 255 OR SWAP ! 4 THEN ;

\ прочесть счетчик длины строки u из памяти по адресу addr,
\ длину счетчика строки в байтах.
: SCNT@ ( addr --> u # ) DUP C@ DUP 255 = IF DROP @ 8 RSHFIT 255 + 4 ELSE NIP 1 THEN ;

\ вернуть адрес начала строки addr и ее длину в байтах
: SCOUNT ( '#str --> addr u ) DUP SCNT@ ROT + SWAP ;

\ компилировать строку со счетчиком на вершину кодофайла
: s", ( asc u --> ) DUP HERE SCNT! ALLOT HERE SWAP DUP ALLOT MOVE ;

_________________
Am I evil? I'm man - yes I am! © James Hatefield


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 13:22 
Не в сети

Зарегистрирован: Вс дек 02, 2007 17:31
Сообщения: 442
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Хочу уточнить. В ТЗ не заметил максимального ограничения длины. Может 3 байта как у меня мало?

_________________
Am I evil? I'm man - yes I am! © James Hatefield


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 13:25 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Forthware писал(а):
Хочу уточнить. В ТЗ не заметил максимального ограничения длины. Может 3 байта как у меня мало?

лучше бы 4-ре, но три тоже прокатит.

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

Кстати, в приведенном вами варианте можно выделять всего лишь один бит на расширение разрядности числа, например нулевой,
тогда наличие нулевого бита сброшенного в ноль - признак строки длиной в 127 байт (то есть восьмибитового числа), а установленность в "1" - признак 31битного числа 8)
но, все-таки, более рациональным видися 1-2-4 байта, либо 1-2-3-4 байта под число.

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 14:18 
Не в сети

Зарегистрирован: Вс дек 02, 2007 17:31
Сообщения: 442
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Хорошо. Тогда второй вариант, малость переделаный, для простоты реализации, ваш.
- если младший бит ноль, то в старших семи длина строки;
- иначе читаем 2 байта. Если второй бит нуль, то длина строки в старших 14 иначе к ним добавляем еще 16 из следующих 2 байт.

Код:
: SCNT! ( u addr --> # )
SWAP DUP 128 U< IF 2* SWAP C! 1 EXIT THEN
CELLS DUP 0x10000 U< IF 1 OR SWAP W! 2 ELSE 3 OR SWAP ! 4 THEN
;

: SCNT@ ( addr --> u # )
DUP C@ DUP 1 AND
IF 2 AND IF @ 2 RSHIFT 4 ELSE W@ 2 RSHIFT 2 THEN
ELSE 2/ NIP 1 THEN
;

: SCOUNT ( '#str --> addr u ) DUP SCNT@ ROT + SWAP ;

: s", ( asc u --> ) DUP HERE SCNT! ALLOT HERE SWAP DUP ALLOT MOVE ;

_________________
Am I evil? I'm man - yes I am! © James Hatefield


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 14:20 
Не в сети

Зарегистрирован: Вс дек 02, 2007 17:31
Сообщения: 442
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
mOleg писал(а):
Кстати, в приведенном вами варианте можно выделять всего лишь один бит на расширение разрядности числа, например нулевой,
Ну, там идея как раз таки была в том, чтобы оптимизировать строки длинной от 128 до 254 байт. В моем первом варианте их счетчик был 1 байтным, а в вашем уже 2 байта.

_________________
Am I evil? I'm man - yes I am! © James Hatefield


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 15:21 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
У меня вопрос:
Cлова в словаре и строки в памяти всегда будут представлены одинаково(например оба ascii или оба utf8) или могут быть разными?

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт мар 20, 2008 15:25 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
chess писал(а):
Cлова в словаре и строки в памяти всегда будут представлены одинаково(например оба ascii или оба utf8) или могут быть разными?

к чему конкретно этот вопрос?
в задаче не определено, какого типа будет строка, могут вообще быть бинарные данные...

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 44 ]  На страницу 1, 2, 3  След.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 13


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB