Кто нибудь, объясните, почему:

Это что за нехороший класс такой. Его размер больше хранимой в нем строки!

Во втором случае у тебя массив из 4х экземпляров класса std::string.

А вообще здесь тоже народ возмущается: http://forums.msdn.microsoft.com/en-US/vcl...7-e482c4e461a7/

без нехорошего класса, ты бы хранил указатель на начало строки, а размер указателя на твоей платформе равен 32 бита  

Ужжас. Целых 32 байта. Как жить дальше?  
Неужели в системных требованиях придется писать "1 mb. ram"?      

Не, не. sizeof() возвращает размер в байтах. Посмотрите файлик basic_string.h, там действительно напихали всего.

упс, я думал он в биты перевел...

SABROG - Я всегда юзал сей класс даже не задумываясь об этом.
В данном случае мне нужно создать массив из 6 000 000 объектов, и памяти явно не хватает, ~1.3 Gb сжирает, поэтому я и решил проверить.
Проверил, расстроился... Лучше бы и не зал сего  

Ну пустые классы занимать будут тогда 183 мегабайта в твоем массиве.

Я не знаю какая у тебя задача, но можно попробывать использовать массив обычных char'ов, а строки разделять \0'ми. Но это конечно, если есть возможность последовательного заполнения массива и еще надо будет написать алгоритм поиска строки по индексу.

не многовато-ли будет для оперативной памяти?  
такой массив данных нужно хранить на в файле или в БД...

Неа, так не пойдет... Нужно изменять значение строк.

Добавлено через 2 минуты и 58 секунд

Массив-то и хранится в нескольких файлах.
Но для операций над ним, нужно загрузить в память.

Любопытный бенчмарк на сравнение Си и STL строк, не в пользу последних: http://deepencpp.blogspot.com/2007/08/stds...comparison.html

Lazin, а у меня тоже подобная ситуация возникала, из базы данных делается выборка окола 1.5 млна записей, по 20 колонок в каждой. Т.е. 30 млн. строк., которые распихваются по структурам и векторам. Сжирается вся оператива и вся виртуалка. Далее происходят операции типа парсинга этого всего дела. Объединения, конвертация из текста в числа и т.п. После того как алгоритм отработает результат пихается в Excel файл и после этого память освобождается. Теоретически можно как-то выгружать ненужные участки и подгружать новые по 10 раз, но это скажется на скорости работы программы. Т.е. либо скорость, либо память.

Добавлено через 4 минуты и 4 секунды


Тогда массив указателей на динамеческие строки типа char. Передал в какую-нибудь строковую функцию, она вернет новый указатель с изминенным текстом, старый удалиш и замениш новым. Правда все будет распихано по памяти неизвестно как.

Давно уже пора переходить на x64 и не мучиться с ограничением 2гб.

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

ничего любопытного, STL реализаций много, а значит этот бенчмарк идет лесом, и второе: по вашему за удобство ничем не надо расплачиваться?


+1

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

Хотябы light-weight классы строковые сделали бы, где можно реализовать хотябы простые операции без которых невозможна работа и с обычными char массивами.

Гм... Согласен! Не хотелось бы в С спускаться...но, похоже придется.


Непонял...  На х32 ограничение 4гб. Или я чего не понял?

Там если комменты почитать, то есть и обратные результаты. Пока сам не потестиш с разными реализациями не примешь правильное решение.

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

Это сообщение отредактировал(а) SABROG - 29.7.2008, 12:44

ОС тоже кушать хочет

К примеру...?

Думаю - ДА.
Это алгоритм унификации слов. Т.е. есть каталог  котором хранятся файлы словарей(простые .txt). Так вот при добавления нового файла, нужно проанализировать все словари на предмет повторения слов. Сами понимаете, итераций...ого-го  

Ты чего не понял  Фактически для пользовательской программы система предоставляет 2гб виртуального адресного пространства. Часть адресов уже занята системными модулями и их данными, часть является служебной, часть под стек и кучу. На практике ограничение составляет порядка 1.5 гб. 

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

Действительно ли у тебя присутствует наобходимость хранить все 6млн. объектов в памяти? 

для процесса - 2Гб

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

Вообще это дурной подход к делу, так как нужно заботиться о масштабировании, завтра тебе понадобится обработать не 6 000 000 объектов, на несколько порядков больше, и ни в какую память они не влезут, что будешь делать? 

Добавлено через 1 минуту и 38 секунд

ну так это просто индексация, все читать не обязательно...

Согласен. Нет, памяти хватает. Но как-то медлено это все происходит... Я просто кимарю на раб. месте, пока день не закончится. В данный момент в словарях 5 746 337 слов, операция над ними занимает ~13 часов на P4 Core 2 Duo 3.2Ghz? 2Gb ram DDR2-Dual.
Может есть какие-то иные методы...?

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

Да БД однозначно.

Добавлено через 1 минуту и 38 секунд
Надо сделать ещё одну оговорку. БД может не подойти в случае, если исходный формат, в котором будут поступать данные, всегда будет txt и от тебя это не зависит. И в случае, если данные словари достаточно часто меняются. 

а на что время в основном тратится?

Абсолютно согласен. Исправлю.

В случае, если структура файла меняется редко или она просто дополняется новыми словами с конца, можно хранить не слова, а хеши. Ессно проиндексировать, но здесь простое соответветствие -- хеш+позиция_в_файле

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

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

А вообще словари надо попросту специальным образом проиндексировать. Например создаешь файл индекса, где букве "А" соответствует стартовое смещение в файле каждого словаря и длинна участка. В итоге в память ты уже будешь загружать не все слова, а только на букву "А", далее сравниваешь сначала строки по размеру. Если длинна строк не идентична, то они уже не равны (правда не знаю, может функция сравнения строк уже так и делает.

Тогда ещё отсортировать надо 

Добавлено через 6 минут и 29 секунд


Всё-таки лучше действительно посчитать один раз хеши. Возьми какую-нибудь быструю хеш-функцию, например adler32, создай массив простых структур/классов, которые бы хранили хеш слова + позицию слова в файле, можно ещё длину слова. Если основная операция сравнение слов, то здесь ты многократно выигрываешь. 

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

Предварительно обработать данные - без сомнения. Создать какое-нибудь индексное B-дерево. А затем легко и приятно всё, что надо добавлять и пр. txt и прямой перебор - явно не удачное решение 

На std::sort(), std::unique() и далее на итерации по словам между словарями.

тогда логично для этого использовать структуры данных, на которых эти операции имели бы сложность О(1) или O(ln(N))

Всем Преогромное Спасибо   
Приступаю к реализации.

Решил тоже сравнить на своей тачке скорость:

gcc


msvc

А это сравнение идентичных строк удвоенной длинны (gcc):





Собирал проги без каких-либо ключей оптимизации, т.е. тупо:





Тесты проводились под Win2000SP4.


Это сообщение отредактировал(а) SABROG - 29.7.2008, 18:34

SABROG, в VS по умолчанию stl проверяет выход за границы контейнера, это отключается каким-то макросом... результат для msvc должен быть близок к результату gcc
кстати на очень длинных строках результат может каардинално измениться...  

Запущу тесты на ночь на длинных строках. Завтра запощу.

ну не на столько-же длинных  

Это сделано специально, чтобы когда ты увеличиваешь размер строки память не пришлось перевыделять (новую выделить, скопировать элементы, старую удалить).
Так делают все stl контейнеры.
Так же есть метод reserve, через который можно установить желаемый размер, но он будет установлен, только если текующий зарезирвированный размер меньше.

string хранит указатель на память, размер строки не влияет на размер string

зависит от реализации.

Сегодня не судьба. Ночью в офисе вырубило электричество все результаты пропали.

Размер самой строки через sizeof вообще не возможно получить  Мы получаем размер всех полей класса: указателя на строку (4 байта), её физический размер (4 байта), её логический размер (4 байта). Откуда взялось отсальное - фиг его знает, надо смотреть  Ну, плюс выравнивани не забываем!

Это понятно. Но откуда взялись 32 байта  
Это походу 8 указателей, или что-то еще...бред...
А в Лине кто-то проверял?
Щас в Mingw проверю.

Добавлено через 13 минут и 42 секунды
Проверил. Вот результаты.

Для MSVC-2008, компилил из командной строки, без каких либо опций.

И для Mingw:

Тоже без опций. Разница на лицо.

О, ещё аллокатор и итератор для начала. Может и для конца. А итератор - это уже не 4 байта...

в студии нужно компилить с таким дефайном

что-бы все было честно  

А студия 2005 все-равно выдает 28 байт против 4х в mingw (gcc).

ну еще-бы, он вроде-бы должен проверку итераторов отключать 
да, и

Блин, и в чём мораль? Смотрим заголовычные файлы МинГВ. Все данные строки хранятся через некий _M_dataplus, в котором есть:

И куча реинтерпрет-кастов затем. Чтобы получить, например, _Rep:

Зачем всё так сложно? Скорей всего виноват референс-каунтинг. Если хочется сравнить реально память, занимаемую строками - создаём огромное количество этих строк и смотрим, сколько памяти жрёт процесс.

А я и так и так пробывал, разницы нету 

Последовал совету Любителя, вот код:



Создается 6 млнов экземпляров пустых классов:



В итоге:
mingw (gcc) - 141 896 kb
msvc - 235 716 kb

Это сообщение отредактировал(а) SABROG - 30.7.2008, 15:39

SABROG - Мда... Я уже поднимал тему по замене std::string из-за малого функционала.
Похоже теперь появился еще один повод искать замену std::string  
С каждым днем все больше радости  

А если хотя бы 1 символ в строку записать? Может в случае mingw для пустых строк просто не хранится никакой служебной инфы. 

И ещё - везде надо включать оптимизацию. Иначе сравнение не объективно.

Ну для gcc -O3 я могу прописать, на другие ключи у меня знаний не хватит. А для cl я вообще не знаю ключей оптимизации.

С таким кодом я вообще получил неожиданные результаты:



gcc - 376 604kb
msvc - 235 716kb

Попробывал провести тест снова с пустыми классами и опять msvc продул, а с заполненными продувает gcc.

Скомпилил прогу с помощью gcc с максимальной оптимизацией -O3, результат никак не изменился.

Это сообщение отредактировал(а) SABROG - 30.7.2008, 16:27

немного потестировал пример из блога deepencpp для разных строк

для коротких строк
l1 и l2 - длины строк, конкретные значения не важны, важно отношение - больше, меньше...


для длинных


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

Добавлено через 44 секунды
зы
компилятор vs2005, ключи /O2, /Ot

/O1 - size
/O2 - speed
/Ox - full




то то  

1. cl /?
2. Скажем, cl /Ox.


Можно увидеть вариант со включенной отимизацией?

Добавил ключи /Ox и -O3 соотв, результаты не изменились никак вообще. Оптимизация вообще никак не повлияла на тесты с пустыми и заполненными классами. Т.е. осталось все прежним.

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

Это сообщение отредактировал(а) SABROG - 30.7.2008, 16:40

Гм... Я в ступоре  

Вот кстати еще один вариант:



Результат:

msvc - 235 716kb
gcc - 282 932kb

А тут я решил увеличить количество строк до 90 млн.ов c непустыми классами, результат мне не очень понравился:

gcc - 563 712kb
msvc - 352 452 kb

Это сообщение отредактировал(а) SABROG - 30.7.2008, 16:59

Boost::array
STL == как на ресурсы, работать быстро - гдк то слышал, хотя работать быстро не получается(во первых память не вовремя олсвобождается, а во вторых new,delete,malloc,realloc - медленнеы так как ищют дырки в памяти, то и есть свободные места)

Ой, а можно по-русски? 

Добавлено через 21 секунду
Да, и кстати boost::array - это для массивов постоянного размера.

А вот в подтверждение моих слов результаты метода max_size(), который возвращает максимальное количество символов, которое может содержать экземпляр класса std::string:

gcc - 1073741820
msvc - 4294967294

Т.е. все-таки msvc хоть и имеет размер класса 28 байт, но он резервирует много памяти для новой строки о чем говорит функция capacity(), которая возвращает 15 байт для msvc и 0 байт для gcc.

Это сообщение отредактировал(а) SABROG - 30.7.2008, 17:19

Еще ради интереса stlport бы сравнили на обоих компиляторах  А так же gcc 4.x 

мне вот интересно к чему эти тесты? если бы С строки оказались быстркее, вы бы отказались от string? иЛи из-за того, что msvc дает меньший размер все бросят gcc? по моему это пустая трата времени...

А к чему любые подобные тесты?  

Ага, а потом начнется, а вот еще и для watcom сравните и для icc и для bcc. А потом на разных платформах, операционных системах. А потом версии библиотек, стабильные/не стабильные. А потом еще и с разными ключами собранные библиотеки. А потом скажут, что сравниваете не верно, код должен быть другой.  

А у меня stlport не собирается для Студии. Вот что сообщает:

Какие мысли?

Вы на stlport тестируйте, там честнее будет для всех компиляторов, т.к. у студии собственная stl.

Вот я и попытался...

Народ, а че за фигня. Прописал пути:



Пытаюсь скомпилить так:



Получаю: 



Меняю на 



Получаю 



Меняю на:



Опять не компилится. Меняю на полный путь:



Компилиться. Почему линкер не видит ни переменную окружения LIB, ни косвенный путь через -L./LIB/ (даже -L../LIB пробывал с вариациями) ?
---

Ага, это спасает отца русской демократии:



Это сообщение отредактировал(а) SABROG - 30.7.2008, 23:51