Forth http://fforum.winglion.ru/ |
|
*масштабируемый счетчик длины строки http://fforum.winglion.ru/viewtopic.php?f=19&t=1210 |
Страница 3 из 3 |
Автор: | Alexander [ Пт мар 28, 2008 08:46 ] |
Заголовок сообщения: | |
А идея тут простая: если вам часто приходится оперировать со строками, то операция вычисления байта-описателя будет камнем преткновения. А если не так часто приходится со строками работать предлагаю сделать так: Старший бит - признак того, что следующий байт снова описатель длины. Т.Е. старший бит=1, интерпретируем следующий байт как описатель длины строки, если старший бит=0, то это последний байт в описателе длины строки, а следующий за ним байт уже непосредственно сама строка. Конечно, если ипользовать различные длины символов, то в первом байте описателе строки можно бит стоящий перед старшим использовать под описание длины символа. Все зависит от того чего вы хотите. А как же вы собираетесь обращаться к каждому символу??? |
Автор: | Forthware [ Пт мар 28, 2008 13:14 ] |
Заголовок сообщения: | |
Alexander писал(а): А идея тут простая: если вам часто приходится оперировать со строками, то операция вычисления байта-описателя будет камнем преткновения. Ну, автору виднее. Лично я особых проблем не вижу, ни чем не хуже чем работа со счетными строками.Alexander писал(а): Старший бит - признак того, что следующий байт снова описатель длины. Т.Е. старший бит=1, интерпретируем следующий байт как описатель длины строки, если старший бит=0, то это последний байт в описателе длины строки, а следующий за ним байт уже непосредственно сама строка. А теперь почитайте внимательно первый пост. Alexander писал(а): Конечно, если ипользовать различные длины символов, то в первом байте описателе строки можно бит стоящий перед старшим использовать под описание длины символа. Задачей не предусмотрено, и автором уточнено что такая функциональность выходит за рамки задачи.Alexander писал(а): А как же вы собираетесь обращаться к каждому символу??? Тут речь идет о формате хранения строки. Как аргумент любая строка представляется двумя ячейками стека: ( c-addr u ). Поэтому, чтение n-ного символа при стеке ( c-addr u n ) будет выглядеть:
NIP CHARS + C@ |
Автор: | Alexander [ Пт мар 28, 2008 14:07 ] |
Заголовок сообщения: | |
Forthware писал(а): Тут речь идет о формате хранения строки. Как аргумент любая строка представляется двумя ячейками стека: ( c-addr u ). Поэтому, чтение n-ного символа при стеке ( c-addr u n ) будет выглядеть: NIP CHARS + C@ Не совсем то, кто мешает передать только адрес строки, а проводить интерпретацию хранимых данных определенной процедурой. Ну а что про другое Forthware писал(а): А теперь почитайте внимательно первый пост.
Предлагаю отказаться от двоичной системы счисления, взять например основание системы счисления 36, и в старшем бите первого и единственного байта хранить признак системы счисления. думаю что 36 в степени 7 степени всех удовлетворит, а это позволит хранить если я правильно посчитал 78364164095 байт. Конечно 36 грубая оценка, можно и поменьше взять чтобы не так много памяти расходовать в пустую, найти так сказать золотую середину |
Автор: | Forthware [ Пт мар 28, 2008 18:00 ] |
Заголовок сообщения: | |
Alexander писал(а): Не совсем то, кто мешает передать только адрес строки, а проводить интерпретацию хранимых данных определенной процедурой. Никто не мешает, только не надо после этого спрашивать:Alexander писал(а): А как же вы собираетесь обращаться к каждому символу??? ;)Alexander писал(а): Предлагаю отказаться от двоичной системы счисления, взять например основание системы счисления 36, и в старшем бите первого и единственного байта хранить признак системы счисления. Вот это уже интереснее. Конечно, при 36-ричной системе, средняя потеря составит около 18 байт (дополнительно к 1 байту самого счетчика) в то время как 4 байтный счетчик имеет потерю 3 байта, что в 6 раз меньше. Поэтому, все строки с длиной более 127 символов в предложенном вами варианте проиграют по компактности всем другим предложенным в этой ветке решениям, причем значительно.
Но идея оригинальна, такой еще не было. Да и реализовать не сложно. |
Автор: | mOleg [ Пт мар 28, 2008 19:26 ] |
Заголовок сообщения: | |
Alexander писал(а): А идея тут простая: если вам часто приходится оперировать со строками, то операция вычисления байта-описателя будет камнем преткновения. в любом случае быстрее чем с ASCIIZ строками Alexander писал(а): А если не так часто приходится со строками работать предлагаю сделать так: Старший бит - признак того, что следующий байт снова описатель длины. Т.Е. старший бит=1, интерпретируем следующий байт как описатель длины строки, вы написали то же, что есть в ТЗ к данной задачке. Alexander писал(а): Все зависит от того чего вы хотите. А как же вы собираетесь обращаться к каждому символу???
это другая проблема. |
Автор: | Alexander [ Пн мар 31, 2008 18:49 ] |
Заголовок сообщения: | |
Forthware писал(а): Конечно, при 36-ричной системе, средняя потеря составит около 18 байт (дополнительно к 1 байту самого счетчика) в то время как 4 байтный счетчик имеет потерю 3 байта, что в 6 раз меньше. Поэтому, все строки с длиной более 127 символов в предложенном вами варианте проиграют по компактности всем другим предложенным в этой ветке решениям, причем значительно.
Немного уточнения, 1 или 2 старших бита указывают на ту или иную систему счисления, а остальные биты указывает вес, например, для двух бит 00 - двоичная, 01 - третичная, 10 - пятиричная, 11 - семяричная, основание системы - простое число, тогда оставшиеся 6 бит можно использовать под кодирование длины строки, и тут может быть не помешает идея скрытой 1 для увеличения разрядности, как это в сопроцессоре сделано ( пока только озвучил). Опять же если системы счисления будут близки, то возникает неоднозначность представления данных. А это важно или нет??? И опять появился подводный камень интервал изменения длины строки - очень нелинейный, т.е. с каким шагом будет меняться длина строки. Но в два байта уложится всегда можно: 1) для строк длиной до 127 символов включительно описатель 1 байт, а для всех остальных два байта, но уже не в двоичной системе. 2) или первый байт система счисления, а второй как весовая функция. В этом случае накладные расходы прямопропорциональны системе счисления. И как же узнать точную длину строки, т.е. число использованных символов в такой строке, ведь не все же используются. |
Автор: | WingLion [ Пн мар 31, 2008 22:37 ] |
Заголовок сообщения: | |
Alexander писал(а): 1) для строк длиной до 127 символов включительно описатель 1 байт, а для всех остальных два байта, но уже не в двоичной системе.
Можно вопрос? Кто будет всю мировую электронику переделывать под "байты не в двоичной системе"? p.s. я - пас. Меня устраивают "байты в двоичной системе" |
Автор: | mrack_ [ Ср апр 02, 2008 09:09 ] |
Заголовок сообщения: | |
Цитата: Предлагаю отказаться от двоичной системы счисления, взять например основание системы счисления 36, и в старшем бите первого и единственного байта хранить признак системы счисления.
думаю что 36 в степени 7 степени всех удовлетворит, а это позволит хранить если я правильно посчитал 78364164095 байт. так, имеем байт, - 8 бит, - если первый бит 0 то семь битов за ним двоичные, - если первый бит 1 то семь битов за ним трицатишестиричные ? |
Автор: | Forthware [ Ср апр 02, 2008 12:46 ] |
Заголовок сообщения: | |
mrack_ писал(а): - если первый бит 1 то семь битов за ним трицатишестиричные Биты не могут быть 36-ричными, поскольку BIT это есть BInary digiT по определению.
|
Автор: | Уууууу.... [ Ср апр 02, 2008 13:06 ] |
Заголовок сообщения: | |
Сорри, что анонимно - задолбался свой пароль тут восстанавливать. Люди - что вы все такое курите, а?! Или это нюхать надо?!! Ну какой ПРАКТИЧЕСКИЙ смысл в строке, у которой непонятный счётчик? Вот сколько живу - ни разу не видел строки, длиннее нескольких десятков килобайт - да и то я сделал это тогда, практически, по малолетству. Пример - Delphi - сделали, помнится, int - и не парятся. Потому как 1) и так до кучи; 2) извлечь целое по адресу куда проще и быстрее, чем проводить кучу вычислений, только для того, чтобы узнать длину строки!!! |
Автор: | VoidVolker [ Ср апр 02, 2008 22:16 ] |
Заголовок сообщения: | |
Уууууу.... писал(а): Люди - что вы все такое курите, а?! Или это нюхать надо?!! Ну какой ПРАКТИЧЕСКИЙ смысл в строке, у которой непонятный счётчик? Вот сколько живу - ни разу не видел строки, длиннее нескольких десятков килобайт - да и то я сделал это тогда, практически, по малолетству.
Дык это же конкурс - задачи тут зачастую не более чем игра для интелекта, наличие практического смысла не обязательно, главное чтоб интересно было решать |
Автор: | WingLion [ Ср апр 02, 2008 23:55 ] |
Заголовок сообщения: | |
Уууууу.... писал(а): Сорри, что анонимно - задолбался свой пароль тут восстанавливать.
Да уж, с таким ником K`[f и пароль не долго позабыть... |
Автор: | K`[f [ Чт апр 03, 2008 06:02 ] |
Заголовок сообщения: | |
VoidVolker писал(а): Дык это же конкурс - задачи тут зачастую не более чем игра для интелекта, наличие практического смысла не обязательно, главное чтоб интересно было решать Smile Какой конкурс, если обсуждаете ЧТО надо сделать? Я понимаю если бы задача формулировать как "сделать то-то, как можно более элегантнее". Помню, давно уже, в ZX-ревю была интересная ПРАКТИЧЕСКАЯ задача - максимально короткая функция рассчёта адреса следующей скан-строки для заданного знакоместа. Я нашёл почти оптимальное решение. Рекорд был, помнится, 15 байт. WingLion писал(а): Да уж, с таким ником K`[f и пароль не долго позабыть...
Зависть - плохое чувство. |
Автор: | mOleg [ Чт апр 03, 2008 21:02 ] |
Заголовок сообщения: | |
Уууууу.... писал(а): Сорри, что анонимно - задолбался свой пароль тут восстанавливать. :)
Люди - что вы все такое курите, а?! Или это нюхать надо?!! Ну какой ПРАКТИЧЕСКИЙ смысл в строке, у которой непонятный счётчик? Вот сколько живу - ни разу не видел строки, длиннее нескольких десятков килобайт - да и то я сделал это тогда, практически, по малолетству. :) Пример - Delphi - сделали, помнится, int - и не парятся. Потому как 1) и так до кучи; 2) извлечь целое по адресу куда проще и быстрее, чем проводить кучу вычислений, только для того, чтобы узнать длину строки!!! во-первых, не обязательно в строках хранить текст, можно и бинарные данные, можно и картинки, иконки например. во-вторых, всеравно быстрее, чем подсчет длины asciiz строки. |
Страница 3 из 3 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |