Давно завидовал #истам и их String...
Dec. 20th, 2007 09:55 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
pigmeich... а тут меня еще и на раздумья о диапозонах потянуло.
Какая операция над C-строками одновременно частая и O(N) дорогая?
Вычисление длины строки. Особенно некрасиво получается если вы хотите перебрать строку с конца - приходится сначало до этого конца O(N) ехать.
И давно витала идея "а почему бы не хранить длину строки в специальной переменной". Действительно, почему бы и нет? Строки, обычно, занимают заметно больше 4-х байтового int, зато выростет производительность и по функции не надо будет таскать временную переменную с длиной строки.
Был и недостаток: принцип инкаспуляции не позволяет нам "выдавать" во вне класса хранилище строки. Вроде бы ничего страшного - можно наплодить друзей и методов.
Еще один недостаток: мы ограничиваем размер строки. Правда, ограничиваем где-то числом в 4Гб, что имеет смысл лишь на 64-битных системах. А на них и
Тем более, что позже придумали итераторы. А также в STL вошли алгоритмы.
И обнаружились два недостатка:
1. В алгоритмах диапозон указывается двумя итераторами на начало и конец, но проверка корректности, то есть принадлежности итераторов одному контейнеру и правильной последовательности, не производится.
Кроме того, такая передача неудобна с точки зрения наглядности кода:
Запись
код не украшает.
2. В реализации алгоритмов почти повсеместно используется идиома просмотра последовательности
Такая запись удобна и с точки зрения производительности: операция итерации заменяется на разыменование. Но тут совсем не используется длина! Зачем же мы ее хранили.
Самое смешное, что длина нужна чтобы
1. организовать цикл с итерацией
2. получить доступ с конца строки
3. Определить размер буфера.
И только для 3-го пункта нужна именно длина. Для первых двух лучше подойдет указатель на конец буфера.
Итак, вместо указателя на начало сопряженного с длиной, мы храним два указателя - на начало и конец.
А поддиапозон, можно получить просто поставив указатели на родительский диапозон. Только для этого требуется константность хранилищ объектов. Проще говоря, семантика copy on write, либо неизменность контейнеров.
В .NET используется именно второй вариант. Кроме того, из-за отсутсвия проблем с управлением памятью неизменяемые строки почти автоматически становытся безопасны для передачи между потоками. А класс StringBuilder, служащий для изготовления новых строк, в спецификации нагло объявляется себя небезопасным с точки зрения потоков.
Тут у меня все не получается подойти к логическому концу, кроме того, время прижимает. Потому просто дам ссылки на свой код где сделанны #-подобные строки (это не рабочий прототип, просто мазки, вопросами правильного размещения счетчика ссылок я не задавался):
http://www.everfall.com/paste/id.php?4euuxsz84lsi
http://www.everfall.com/paste/id.php?5d42z63wnzdu
http://www.everfall.com/paste/id.php?t9562ixjkdmm
Какая операция над C-строками одновременно частая и O(N) дорогая?
Вычисление длины строки. Особенно некрасиво получается если вы хотите перебрать строку с конца - приходится сначало до этого конца O(N) ехать.
И давно витала идея "а почему бы не хранить длину строки в специальной переменной". Действительно, почему бы и нет? Строки, обычно, занимают заметно больше 4-х байтового int, зато выростет производительность и по функции не надо будет таскать временную переменную с длиной строки.
Был и недостаток: принцип инкаспуляции не позволяет нам "выдавать" во вне класса хранилище строки. Вроде бы ничего страшного - можно наплодить друзей и методов.
Еще один недостаток: мы ограничиваем размер строки. Правда, ограничиваем где-то числом в 4Гб, что имеет смысл лишь на 64-битных системах. А на них и
Тем более, что позже придумали итераторы. А также в STL вошли алгоритмы.
И обнаружились два недостатка:
1. В алгоритмах диапозон указывается двумя итераторами на начало и конец, но проверка корректности, то есть принадлежности итераторов одному контейнеру и правильной последовательности, не производится.
Кроме того, такая передача неудобна с точки зрения наглядности кода:
Запись
copy(it1, it2, it3);
код не украшает.
2. В реализации алгоритмов почти повсеместно используется идиома просмотра последовательности
for(iterator = begin; iterator != end; ++iterator)(кстати, если вычислять end() как begin + length и не поставить const получиться небольшое падение в скорости)
Такая запись удобна и с точки зрения производительности: операция итерации заменяется на разыменование. Но тут совсем не используется длина! Зачем же мы ее хранили.
Самое смешное, что длина нужна чтобы
1. организовать цикл с итерацией
2. получить доступ с конца строки
3. Определить размер буфера.
И только для 3-го пункта нужна именно длина. Для первых двух лучше подойдет указатель на конец буфера.
Итак, вместо указателя на начало сопряженного с длиной, мы храним два указателя - на начало и конец.
А поддиапозон, можно получить просто поставив указатели на родительский диапозон. Только для этого требуется константность хранилищ объектов. Проще говоря, семантика copy on write, либо неизменность контейнеров.
В .NET используется именно второй вариант. Кроме того, из-за отсутсвия проблем с управлением памятью неизменяемые строки почти автоматически становытся безопасны для передачи между потоками. А класс StringBuilder, служащий для изготовления новых строк, в спецификации нагло объявляется себя небезопасным с точки зрения потоков.
Тут у меня все не получается подойти к логическому концу, кроме того, время прижимает. Потому просто дам ссылки на свой код где сделанны #-подобные строки (это не рабочий прототип, просто мазки, вопросами правильного размещения счетчика ссылок я не задавался):
http://www.everfall.com/paste/id.php?4euuxsz84lsi
http://www.everfall.com/paste/id.php?5d42z63wnzdu
http://www.everfall.com/paste/id.php?t9562ixjkdmm
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2007-12-20 12:35 pm (UTC)no subject
Date: 2007-12-20 02:03 pm (UTC)no subject
Date: 2007-12-20 03:30 pm (UTC)no subject
Date: 2007-12-21 03:15 am (UTC)no subject
Date: 2007-12-20 01:05 pm (UTC)BSTR в COM хранит длину перед строкой.
ИМХО, лучше всего хранить отдельно, как раз ради фокуса о котором пишет
no subject
Date: 2007-12-20 02:31 pm (UTC)no subject
Date: 2007-12-20 01:33 pm (UTC)Надо было мне залочить комменты пока я дописываю статью.
А ведь совсем к другому хотел подойти... =)
no subject
Date: 2007-12-20 02:34 pm (UTC)no subject
Date: 2007-12-20 03:30 pm (UTC)Оно как минимум проблема с подстроками позволяет обойти
no subject
Date: 2007-12-20 03:33 pm (UTC)end = begin + длина
длина = end - begin
no subject
Date: 2007-12-20 03:37 pm (UTC)Просто потому что ты "длину" хранишь "отдельно" - передавая end
no subject
Date: 2007-12-21 03:14 am (UTC)Кроме того, с деревьями очень круто работает: сделав правильный итератор можно легко и просто брать поддеревья.