родилась такая идея сделать хранилище для строк,

интерфейс примерно такой

unsigned int addString( const char * str, size_t len ); //ID одинаковый для одинаковых str
void removeString( unsigned int id );
const char * toString( unsigned int id );

важно что бы имело минимальный размер в памяти, ну и добавлять/удалять строки можно рантайм

я думаю уже кто-то решал и думал над этим, есть идеи?

З.Ы. была идея хранить на HDD

Здравствуйте, IROV.., Вы писали:

IRO>родилась такая идея сделать хранилище для строк,

IRO>интерфейс примерно такой

На каком курсе учитесь?

Здравствуйте, smeeld, Вы писали:

S>Здравствуйте, IROV.., Вы писали:

IRO>>родилась такая идея сделать хранилище для строк,

IRO>>интерфейс примерно такой

S>На каком курсе учитесь?

	отучился
	10 лет опыта работы, куча выпущенных проектов, начиная от казуальных, заканчивая серверами для ММО, а чё?

а по сути?

Здравствуйте, IROV.., Вы писали:

IRO>родилась такая идея сделать хранилище для строк
IRO>я думаю уже кто-то решал и думал над этим, есть идеи?

Даже решения есть, не то что идеи:
http://www.boost.org/libs/flyweight/

You will always get what you always got
  If you always do  what you always did

Здравствуйте, IROV.., Вы писали:


IRO>а по сути?

Тут думают над распределёнными хранилищами данных для хранения петабайт инфы,
чтоб породить что-то конкурентноспособное и денег срубить, а Вы про какие-то
строчки вспомнили, как первокурсник.

Здравствуйте, IROV.., Вы писали:

IRO>родилась такая идея сделать хранилище для строк,

IRO>интерфейс примерно такой

IRO>unsigned int addString( const char * str, size_t len ); //ID одинаковый для одинаковых str
IRO>void removeString( unsigned int id );
IRO>const char * toString( unsigned int id );

IRO>важно что бы имело минимальный размер в памяти, ну и добавлять/удалять строки можно рантайм

IRO>я думаю уже кто-то решал и думал над этим, есть идеи?

IRO>З.Ы. была идея хранить на HDD

а зачем?

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

MyString s;
s += "a";
s += "b";
//...
MyString s2 = s;//(1)

после (1) эти два объекта s и s2 содержали указатель на одну и ту же
область памяти.

Здравствуйте, smeeld, Вы писали:

S>Здравствуйте, IROV.., Вы писали:


IRO>>а по сути?

S>Тут думают над распределёнными хранилищами данных для хранения петабайт инфы,
S>чтоб породить что-то конкурентноспособное и денег срубить, а Вы про какие-то
S>строчки вспомнили, как первокурсник.
А у меня всего на всего нужно влезть в 70мг памяти, и как мне кажется мои строки жрут много.
и все же

Здравствуйте, jazzer, Вы писали:

J>Здравствуйте, IROV.., Вы писали:

IRO>>родилась такая идея сделать хранилище для строк
IRO>>я думаю уже кто-то решал и думал над этим, есть идеи?

J>Даже решения есть, не то что идеи:
J>http://www.boost.org/libs/flyweight/

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

Здравствуйте, Zhendos, Вы писали:

Z>Здравствуйте, IROV.., Вы писали:

IRO>>родилась такая идея сделать хранилище для строк,

IRO>>интерфейс примерно такой

IRO>>unsigned int addString( const char * str, size_t len ); //ID одинаковый для одинаковых str
IRO>>void removeString( unsigned int id );
IRO>>const char * toString( unsigned int id );
...
Z>а зачем?

...
Человеку скорее всего нужно, что бы после

 
int a = addString("a",1);
int b = addString("b",1);

переменные a и b содержали значения, не зависимые от запуска к запуску.

Здравствуйте, IROV.., Вы писали:

IRO>родилась такая идея сделать хранилище для строк,

IRO>интерфейс примерно такой

IRO>unsigned int addString( const char * str, size_t len ); //ID одинаковый для одинаковых str
IRO>void removeString( unsigned int id );
IRO>const char * toString( unsigned int id );

IRO>важно что бы имело минимальный размер в памяти, ну и добавлять/удалять строки можно рантайм

IRO>я думаю уже кто-то решал и думал над этим, есть идеи?

Решал.
Собственно хранение строк и доступ по индексу реализуются элементарно.
Берем два массива. В одном хранятся строки подряд, в другом — индексы "голов".

std::vector<int> Head;   // индекс первого символа строки
std::vector<char> Chars; // строки

Можно хранить с завершающим нулем (удобно для передачи в сишные функции), либо вычислять длину строки налету (а можно совместить):

length = Head(i+1) - Head(i); // Длина i-й строки

В последнем случае в массиве Head можно хранить дополнительный замыкающий элемент "сторож", чтобы не плодить if'ы в вычислениях.

Доступ к i-й строке выглядит так:

const char * toString( unsigned int id ) const
{
   return &Chars[Head[id]];
}

При вставке в середину или при изменении длины строки придется подвинуть все символы, расположенные правее и поправить индексы в Head. На первый взгляд кажется накладным, но на моих задачах это получается намного быстрее, чем использование традиционного vector<string> или каких-либо сложных страничных контейнеров.
Cache-friendly и всё такое..

IRO>"ID одинаковый для одинаковых str"
нужен хеш.

Считаем хеш, получаем индекс строки в массиве.
Хеш реализуется на двух массивах — в одном, собственно, хеш таблица — хранится индекс первого элемента в списке коллизии.
Во втором массиве (размер которого равен размеру массива Head) индекс следующего в списке коллизий, либо -1, если конец списка.

IRO>З.Ы. была идея хранить на HDD

Приведенная структура сериализуется очень задешево. Для каждого массива внутри контейнера записываются число элементов и собственно содержимое.
Т.е. получается всего 4 вызова write/read (для хеша — 8, добавляются еще два массива — хеш-таблица + список коллизий).


Да, если размер памяти критичен и число строк может уложиться в 32К, то "vector<int> Head" меняется на "vector<short> Head" и затраты по памяти уменьшаются вдвое

Добавлю...
У меня индекс в массиве — именованная сущность, поэтому отрицательные индексы нужны для обозначения невалидных объектов, либо для спец. значений.
Если можешь воспользоваться беззнаковыми типами, то "vector<unsigned short> Head" дает пространство для маневра.

Здравствуйте, Zhendos, Вы писали:

Z>Здравствуйте, IROV.., Вы писали:

IRO>>родилась такая идея сделать хранилище для строк,

IRO>>интерфейс примерно такой

IRO>>unsigned int addString( const char * str, size_t len ); //ID одинаковый для одинаковых str
IRO>>void removeString( unsigned int id );
IRO>>const char * toString( unsigned int id );

IRO>>важно что бы имело минимальный размер в памяти, ну и добавлять/удалять строки можно рантайм

IRO>>я думаю уже кто-то решал и думал над этим, есть идеи?

IRO>>З.Ы. была идея хранить на HDD

Z>а зачем?

Z>строковые константы и так будут иметь одинаковый
Z>адрес в случае использования связки современный компилятор/линковщик.
Z>Значит остается только случай генерируемых на лету строк,
Z>но для них можно взять класс строк, такой чтобы
Z>

Z>MyString s;
Z>s += "a";
Z>s += "b";
Z>//...
Z>MyString s2 = s;//(1)
Z>

Z>после (1) эти два объекта s и s2 содержали указатель на одну и ту же
Z>область памяти.
это уже реализовано,
http://rsdn.ru/forum/cpp/3853558.1

Автор: IROV..
Дата: 23.06.10

да и это не решает проблему сжать данные

Здравствуйте, IROV.., Вы писали:


Z>>после (1) эти два объекта s и s2 содержали указатель на одну и ту же
Z>>область памяти.
IRO>это уже реализовано,
IRO>http://rsdn.ru/forum/cpp/3853558.1

Автор: IROV..
Дата: 23.06.10

Это уже реализовано в Qt (QString),
и в std::string, который идет в составе gcc.

Скорее всего если покопаться, то для любой
современной платформы можно найти уже существующее.

Зачем еще один?

IRO>да и это не решает проблему сжать данные

ИМХО конечно, но если вам нужно еще и сжимать,
то это слишком специфичная задача,
и стоит описать ее в посте.

PS
Если речь идет о парсере какого-то языка,
то может стоит хранить смещение в файле и размер строки
и отображать файл в память.

Здравствуйте, IROV.., Вы писали:

IRO>Здравствуйте, jazzer, Вы писали:

J>>Здравствуйте, IROV.., Вы писали:

IRO>>>родилась такая идея сделать хранилище для строк
IRO>>>я думаю уже кто-то решал и думал над этим, есть идеи?

J>>Даже решения есть, не то что идеи:
J>>http://www.boost.org/libs/flyweight/

IRO>а разве это не просто намаханый контейнер для хранению данных с хешированием?
IRO>Памяти то меньше не станет?

В смысле? У тебя в самой программе будет использоваться хэндл на строку, а не строка целиком.
Т.е. каждая уникальная строка будет храниться в единственном экземпляре.
Соответственно выигрыш появляется, если очень много одинаковых строк (авторы приводят в качестве примера всякие HTML, где одни и те же теги повторяются из раза в раз).
http://www.boost.org/doc/libs/1_56_0/libs/flyweight/doc/examples.html#example4

В общем, прочитай доки, они коротки и есть замеры производительности, в смысле памяти в том числе.
http://www.boost.org/doc/libs/1_56_0/libs/flyweight/doc/performance.html

IRO>Мне кажется строки особенно FilePath можно было бы не плохо с архивировать,
IRO>тут мне видится некое дерево, или архивация, или что-то еще.

В каком смысле архивировать? lza? Или prefix tree (для FilePath должно хорошо работать, по идее)?

You will always get what you always got
  If you always do  what you always did

Здравствуйте, Zhendos, Вы писали:

Z>PS
Z>Если речь идет о парсере какого-то языка,
Z>то может стоит хранить смещение в файле и размер строки
Z>и отображать файл в память.

Имеется ввиду что-нибудь типа:

struct MyString {
   static char *file_map_addr;
   off_t offset;
   size_t length;
};

Здравствуйте, IROV.., Вы писали:

IRO>Мне кажется строки особенно FilePath можно было бы не плохо с архивировать,
IRO>тут мне видится некое дерево, или архивация, или что-то еще.

Что известно о данных? Какая евристика? Много совпадающих префиксов?
Можно использовать что-то типа Trie, где доступ к конкретной строке осуществляется через лист дерева.

Здравствуйте, Zhendos, Вы писали:

Z>Здравствуйте, Zhendos, Вы писали:

Z>>PS
Z>>Если речь идет о парсере какого-то языка,
Z>>то может стоит хранить смещение в файле и размер строки
Z>>и отображать файл в память.

Z>Имеется ввиду что-нибудь типа:
Z>

Z>struct MyString {
Z>   static char *file_map_addr;
Z>   off_t offset;
Z>   size_t length;
Z>};
Z>

Это самое простое что приходит в голову, но боюсь с "отображать в файл" может быть проблемы с "кросс-платформ"

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Здравствуйте, IROV.., Вы писали:

IRO>>Мне кажется строки особенно FilePath можно было бы не плохо с архивировать,
IRO>>тут мне видится некое дерево, или архивация, или что-то еще.

EP>Что известно о данных? Какая евристика? Много совпадающих префиксов?
EP>Можно использовать что-то типа Trie, где доступ к конкретной строке осуществляется через лист дерева.
EP>Image: 480px-Patricia_trie.svg.png
Все динамическое, за ранние ничего не известно — чаще всего это пути к файлам

Здравствуйте, IROV.., Вы писали:

Z>>Имеется ввиду что-нибудь типа:
Z>>

Z>>struct MyString {
Z>>   static char *file_map_addr;
Z>>   off_t offset;
Z>>   size_t length;
Z>>};
Z>>

IRO>Это самое простое что приходит в голову, но боюсь с "отображать в файл" может быть проблемы с "кросс-платформ"

Какие проблемы, в POSIX и win32 есть отображение файла,
какие еще ОС вы хотите поддерживать?

Здравствуйте, Zhendos, Вы писали:

Z>Здравствуйте, IROV.., Вы писали:

Z>>>Имеется ввиду что-нибудь типа:
Z>>>

Z>>>struct MyString {
Z>>>   static char *file_map_addr;
Z>>>   off_t offset;
Z>>>   size_t length;
Z>>>};
Z>>>

IRO>>Это самое простое что приходит в голову, но боюсь с "отображать в файл" может быть проблемы с "кросс-платформ"

Z>Какие проблемы, в POSIX и win32 есть отображение файла,
Z>какие еще ОС вы хотите поддерживать?
https://www.madewithmarmalade.com/
например

Здравствуйте, IROV.., Вы писали:

IRO>важно что бы имело минимальный размер в памяти, ну и добавлять/удалять строки можно рантайм

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

В общем, формулируй техзадание. А заодно, расскажи о предметной области.


Про время жизни. Например.

Строки хранятся в жутко запакованном виде. И есть сравнительно небольшой кэш распакованных строк.
По запросу getString(i) — если нет в кэше, распаковываем, кэшируем. Выдаём указатель на элемент кэша.
Периодически чистим кэш, вызывая специальную функцию. (Чистить кэш в произвольный момент нельзя, т.к. строки у нас запоминаются как голые указатели, абсолютно неподконтрольные).
Если заменить голые указатели на умные, например, на shared_ptr, то можно сбрасывать элементы или страницы кэша по мере того, как нужда в них пропадает.