Сколько байт достаточно для хранения длины строки?

← →
AlexanderMS © (2007-11-05 06:49) [0]

В моём случае длина каждой строки редко переваливает даже за 255. В файл записываю по привычке (плохая привычка, ИМХО), её длину в 4 байта (integer). Тут пришла мысль, что нерационально использую дисковое пространство, и подумал ограничиться двумя байтами (word). Но вспомнил, что компьютер работает с регистрами в 4 байта, и возник вопрос: как это скажется на времени выполнения всей процедуры чтения? Строк в файле может быть достаточно много.

Попутный вопрос: почему свойста Count у везде Integer (а не cardinal/dword), хотя количество элементов не может быть отрицательным?

← →
homm © (2007-11-05 06:54) [1]

> [0] AlexanderMS © (05.11.07 06:49)
> как это скажется на времени выполнения всей процедуры чтения?

Никак не скажется. Дисковая система работает в тысячи раз медленнее, нежели регистры процессора.

← →
Джо © (2007-11-05 07:04) [2]

> и возник вопрос: как это скажется на времени выполнения
> всей процедуры чтения?

Практика — критерий истины. То есть, я хочу сказать, что, потратив от силы 20 минут на написание тестового кода, вы получите *практический* ответ на ваш вопрос.

> Попутный вопрос: почему свойста Count у везде Integer (а
> не cardinal/dword), хотя количество элементов не может быть
> отрицательным?

В стандарте языка Делфи максимальная длина строки — 2 Гб, а не 4, поэтому Cardinal здесь никак не подходит.
И, второе, «свойства Count» вовсем не «везде» типа Integer. Ничто не мешает им быть хоть Int64. Как например, свойство Size у TStream.

← →
Юрий Зотов © (2007-11-05 07:15) [3]

> почему свойста Count у везде Integer

Потому что мудр и дальновиден дядька Борланд. Integer - это generic тип, так что код останется рабочим и при переходе на другую разрядность. С другой стороны, даже если каждый элемент списка имеет минимально возможный размер (1 байт), то их количество все равно не может превысить Max(Integer) (разве что изменится механизм адресации, но это вряд ли).

← →
Однокамушкин (2007-11-05 08:04) [4]

> почему свойста Count у везде Integer

Потому что с беззнаковым Count можно огрести кучу проблем вот в таком часто встречающемся цикле:
var I: Cardinal; for I := 0 to Count - 1 do ...

Если вдруг окажется, что Count = 0, то выражение Count - 1 даст в зависимости от настроек компилятора либо ошибку времени выполнения Range check error, либо 4294967295, и цикл пойдёт молотить 4294967296 итераций, гуляя по несуществующим элементам

> как это скажется на времени выполнения всей процедуры чтения?

По сравнению с временем чтения с диска время любой операции с регистрами - исчезающе малая величина... Но экономить два байта на диске при нынешних их объёмах - это уже из области извращений

← →
Однокамушкин (2007-11-05 08:23) [5]

> Юрий Зотов © (05.11.07 07:15) [3]
> Потому что мудр и дальновиден дядька Борланд. Integer -
> это generic тип, так что код останется рабочим и при переходе
> на другую разрядность.

Cardinal, в отличие от DWORD, такойже generic-тип, как и Integer

Тут дело в другом... В ранних версиях Delphi Cardinal был недоделанным, его диапазон был от 0 до 2147483647 (т.е. совпадал с беззнаковой половиной диапазона Integer), а старший бит не использовался... Уж не знаю, почему так было сделано, но исправлено это было, кажется, только в Delphi 4, а до этого никто Cardinal-ом не пользовался, потому что смысла не было, вот и сложилось исторически, что во всех библиотеках везде Integer

← →
Anatoly Podgoretsky © (2007-11-05 08:51) [6]

> Cardinal, в отличие от DWORD, такойже generic-тип, как и
> Integer

Так и DWORD тоже.
Неисповедимы пути Борланда с Cardinal

← →
Anatoly Podgoretsky © (2007-11-05 08:55) [7]

> (разве что изменится механизм адресации, но это вряд ли).

Так он давно изменен, пользовательским программам в ОС можно выделять не 2 гб, а 3 - но Борланд на это не отрегировал.

← →
AlexanderMS © (2007-11-05 08:59) [8]

Большое всем спасибо. Всё понял.
Но если использовать Integer и файл "битый", то SetLength(S, Очень большое число) даст большое зависание, которое я не знаю, как ловить.

← →
Однокамушкин (2007-11-05 13:05) [9]

> Anatoly Podgoretsky © (05.11.07 08:51) [6]
>
> Так и DWORD тоже.
> Неисповедимы пути Борланда с Cardinal

DWORD вообще не является встроенным в язык типом, поэтому не является ни generic, ни fundamental... А ещё DWORD определён как синонми встроенного типа LongWord, который относится как раз к фундаментальным (проверено в Delphi 7)

← →
Однокамушкин (2007-11-05 13:16) [10]

> AlexanderMS © (05.11.07 08:59) [8]
> Но если использовать Integer и файл "битый", то SetLength(S,
> Очень большое число) даст большое зависание,

А какая версия Delphi? У меня в семёрке нет никакого зависания: либо всё работает, либо строка становится пустой (если число больше MaxInt), либо возникает исключение AV (если число меньше или равно MaxInt, но больше некоторой максимально возможной границы), а AV очень легко ловится

← →
Anatoly Podgoretsky © (2007-11-05 13:28) [11]

> Однокамушкин (05.11.2007 13:05:09) [9]

Не совсем так, кто жаловался на Cardinal, вот теже самые пертрубации происходили и с DWORD
После 16 бит у Борланда серьезные проблемы с беззнаковыми числами.

← →
ProgRAMmer Dimonych © (2007-11-05 13:55) [12]

> Однокамушкин (05.11.07 08:04) [4]
> Но экономить два байта на диске при нынешних их объёмах - это уже из
> области извращений

Йа извращенец. :) Загоняю в программу кучу строк, состоящих из одного символа (условию не противоречит).

> Строк в файле может быть достаточно много.

Тогда Ваши 2 лишних байта составят 2/5 лишнего объёма файла. Т.е. 700 МБайтный файл будет содержать 280 МБ нулей. Я лучше в эти 280 МБ книжек полезных накачаю из интернета.

В контексте данной задачи извращением можно считать, пожалуй, только подход, который используется в MIDI-файлах (см. описание), и то необязательно.

← →
homm © (2007-11-05 13:59) [13]

> [12] ProgRAMmer Dimonych © (05.11.07 13:55)
> Т.е. 700 МБайтный файл будет содержать 280 МБ нулей.

700 мегабайтный файл строк из одного символа? 140 из оставшихся мегабайт будут содержать нули, а еше 140 единицы. Да лучше на оставшиеся 280Мб тоже книжек накачаю и сделаю нормальный файл 140Мб.

← →
ProgRAMmer Dimonych © (2007-11-05 14:04) [14]

> homm © (05.11.07 13:59) [13]
> 700 мегабайтный файл строк из одного символа? 140 из оставшихся
> мегабайт будут содержать нули, а еше 140 единицы.

Да нет, вроде 280 МБ лишних нулей по сравнению с 2-байтной длиной строки. Т.к. для каждой строки что-то типа:

00 00 00 01 <1 Символ>

А вариант с Word"ом:

00 01 <1 Символ>

Так что, AlexanderMS ©, на Word переходить стоит (раз есть такая возможность), а насчёт быстродействия:

> homm © (05.11.07 06:54) [1]

← →
TUser © (2007-11-05 14:09) [15]

А что чтение/запись таких строк есть единственная задача вашей программы, или она все-таки должна в режиме реального времени как можно быстрее реагировать на запуск межконтинентальной ракеты вероятным противником и кидать смс Балуевскому через веб-форму Билайна? Это я к тому, что скорее всего, реальная задача - не только работа с диском, но и какие-нибудь расчеты, траекторий, допустим, и, скажем, отображение ракеты с помощью ДиректХ, и так чтобы земной шарик вертеть при этом было можно мышкой. И все это выполняется намного чаще и требует оптимизации, потому что от этого зависит скорость работы пользователя. А чтение данных с диска в большинстве случаев оптимизации вообще не требует. Ну выполняется эта операция один раз в сутки в течении пяти секунд, а вы сделаете не пять, а 4,8. Кто это заметит?

← →
homm © (2007-11-05 14:13) [16]

> [14] ProgRAMmer Dimonych © (05.11.07 14:04)
> А вариант с Word"ом:
>
> 00 01 <1 Символ>

Ты явно что-то не понял, сравни с моим вариантом:

<1 Символ>

← →
ProgRAMmer Dimonych © (2007-11-05 14:19) [17]

> homm © (05.11.07 14:13) [16]
> Ты явно что-то не понял, сравни с моим вариантом:
> <1 Символ>

Перечитал, понял, оценил. Только такой вариант уже не будет соответствовать условию задачи, где длины строк переваливают за 255 символов, хотя и редко. :)

← →
Anatoly Podgoretsky © (2007-11-05 14:20) [18]

> ProgRAMmer Dimonych (05.11.2007 13:55:12) [12]

> Я лучше в эти 280 МБ книжек полезных накачаю из интернета.

И каждую размером в 1 байт.
Кроме того, ты явно не знаешь, что такое строка и нужен ли ей счетчик.

← →
Anatoly Podgoretsky © (2007-11-05 14:22) [19]

> homm (05.11.2007 14:13:16) [16]

У тебя тоже не корректно, одна строка это

<1 Символ> + CRLF

← →
ProgRAMmer Dimonych © (2007-11-05 14:29) [20]

> Anatoly Podgoretsky © (05.11.07 14:20) [18]
> И каждую размером в 1 байт.

Невыгодно: трафик до килобайтов округляется :)

> Кроме того, ты явно не знаешь, что такое строка и нужен
> ли ей счетчик.

Так ведь задача-то не моя.

> Anatoly Podgoretsky © (05.11.07 14:22) [19]
> У тебя тоже не корректно, одна строка это
> <1 Символ> + CRLF

Тогда зачем длину строки указывать в файле? Читаем до CRLF - и усё.

← →
homm © (2007-11-05 14:31) [21]

> [19] Anatoly Podgoretsky © (05.11.07 14:22)
> У тебя тоже не корректно

Для матиматики, приведенной в [12] вполне корректно :) Просто символы вместо строк, зачем что-то еще.

← →
Riply © (2007-11-05 14:58) [22]

Можно содрать способ хранения с MFT:
Первые два поля по пол байта.
// 0.5 Byte 0.5 Byte //---|----------------|----------------|----------------|----------------|-------- //.. | Length of | Length of | | | ..... // | var DataOffset | var DataLength | DataLength | DataOffset | //---|----------------|----------------|----------------|----------------|-------- // DataOffset ---------->| // | // ----------------|--------------------------------|---------------- // .... | Data described | ........ // | by Element | // ----------------|--------------------------------|---------------- // | | // |<----- DataLength-------------->|

Мне кажется, что компактнее сложно придумать :)

← →
homm © (2007-11-05 15:07) [23]

> [22] Riply © (05.11.07 14:58)

Что в данном случае будет DataOffset ?

← →
Riply © (2007-11-05 15:13) [24]

> [23] homm © (05.11.07 15:07)
> Что в данном случае будет DataOffset ?

Ну это надо подогнать под свои нужды.
В некоторых структурах MFT сначала подряд "заголовки" (первая конструкция),
а потом сами данные, слитые в одно целое. В этом случае DataOffset - оффсет до
наших данных с размером DataLength.

Можно попробовать располагать данные сразу после заголовка.
Тогда необходимость в DataOffset пропадает.

← →
Riply © (2007-11-05 15:15) [25]

> [24] Riply © (05.11.07 15:13)
И DataLength и DataOffset могут иметь нулевую длинну.

← →
KilkennyCat (2007-11-05 15:23) [26]

Я могу и компактнее придумать, но это уже кодирование начнется...

← →
sniknik © (2007-11-05 15:28) [27]

> Мне кажется, что компактнее сложно придумать :)
легко!
простой текстовый файл будет компактнее

в "твоей" (MFT) будет больше на больших файлах где на смещение 1 байта будет явно не хватать (считаю что DataOffset это смещение данных от начала файла), а минимально возможной описательной частью будет 3 байта.

линуксовый с одним завершающим строку #10 будет еще компактнее.

← →
Riply © (2007-11-05 15:29) [28]

> [26] KilkennyCat (05.11.07 15:23)
> Я могу и компактнее придумать, но это уже кодирование начнется...
Не сомневаюсь.
Но они (Microsoft), остановились именно на этом способе.
Из каких соображений, нам не доложили :)
Знаю одно: шла драка за совмещение компактности и скорости.

> Я могу и компактнее придумать, но это уже кодирование начнется...
архивы думаю не рассматриваются... это естественно уже потом сархивировать полученную "компактную" структуру.

← →
KilkennyCat (2007-11-05 15:30) [30]

> sniknik © (05.11.07 15:28) [27]
> простой текстовый файл будет компактнее

Неа. Он не совсем простой. А вот идеально простому текстовому файлу одного байта на символ слишком много.

> [27] sniknik © (05.11.07 15:28)
>в "твоей" (MFT) будет больше на больших файлах где на смещение 1 байта будет явно не хватать
>(считаю что DataOffset это смещение данных от начала файла)

Ты невнимательно посмотрел структуру. DataOffset может содержать и Int64

>а минимально возможной описательной частью будет 3 байта.

Минимальная структура - 1 байт :)

> [29] sniknik © (05.11.07 15:30)
> это естественно уже потом сархивировать полученную "компактную" структуру.

Так они и поступают.

> [31] Riply © (05.11.07 15:32)
> Ты невнимательно посмотрел структуру. DataOffset может содержать
> и Int64

А не int128 ? :)

> Минимальная структура - 1 байт :)
ага, 1 раз, в начале структуры с нулевой длинной.
и чем дальше тем больше будет размер заголовка. на второй строке первая 256 байт это уже 1+2+1(/0)
и т.д.
1 и даже 3 байта в заголовке = исчезающе малая величина.

← →
KilkennyCat (2007-11-05 15:39) [35]

> sniknik © (05.11.07 15:30) [29]
> архивы думаю не рассматриваются...

Нет, не архивы... что-то близко к кодированию передачи данных. То есть, раскладываем весь файл побитно, и кодируем, например, каждые 16 бит. Хоть это близко к архивам но не совсем..., и скорость кодирования и декодирования очень высокая.

> [33] homm © (05.11.07 15:37)
> А не int128 ? :)

И его тоже :)
Но есть различные "выкрутасы" с этими полями.
В них (выкрутасах) игра может строиться и на том,
что первые два поля рассматриваются, как знаковые.
В этом случае int128 не поместиться :)

> [34] sniknik © (05.11.07 15:38)
> ага, 1 раз, в начале структуры с нулевой длинной.

И в середине может быть нулевой элемент.
Соответственно и
> и чем дальше тем больше будет размер заголовка. на второй строке первая 256 байт это уже 1+2+1(/0)
не совсем верно :)

> ProgRAMmer Dimonych (05.11.2007 14:29:20) [20]

Зачем говорить о строках, когда речь идет об двоичных файлах.

> Riply (05.11.2007 14:58:22) [22]

Ты куда их гонишь, они же свихнутся.

> не совсем верно :)
я в основном про смещение, оно как видно уже на втором шаге может перевалить байт и стать 2 мя (или не на втором но очень очень быстро), что в сумме с описательным байтом самих смещения и длинны будет 3 байта, и хоть удавись, а дальше в меньше не уложишься.
если же первая строка не 256, а поменьше, например 1 байт, то 1+1+1 - описатель + смешение + длинна, и тоже очень быстро сумма переваливает 256 и на смешение нужно уже 2 байта. (3 прям магическое число)
не говоря уж о том когда размер действительно "подрастет" до использования int128 в смещении...

1 байт вначале, и редкие 2 случайных в том же начале (до 256) это не "не совсем верно" это "в основном верно. но есть не играющие роли исключения".

а тот же линуксовый текст всегда на одну строку 1 байт. читать правдя всегда придется только сначала, не адресно, но по задаче вроде произвольная адресация и не стоит.

Сколько байт достаточно для хранения длины строки? Найти похожие ветки