Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > sizeof(std::string) == 32, Почему ???

Автор: andrew_121 29.7.2008, 10:53

Кто нибудь, объясните, почему: Код     std::string str;     std::string stra[4];          int sz = sizeof(str); // 32     sz = sizeof(stra); // 128 Это что за нехороший класс такой. Его размер больше хранимой в нем строки!

Автор: SABROG 29.7.2008, 11:13

Во втором случае у тебя массив из 4х экземпляров класса std::string. А вообще здесь тоже народ возмущается: http://forums.msdn.microsoft.com/en-US/vclanguage/thread/9a59970d-c7bf-4ed5-8267-e482c4e461a7/

Автор: Lazin 29.7.2008, 11:17

Цитата(andrew_121 @  29.7.2008,  10:53 ) Это что за нехороший класс такой. Его размер больше хранимой в нем строки!  без нехорошего класса, ты бы хранил указатель на начало строки, а размер указателя на твоей платформе равен 32 бита

Автор: Mayk 29.7.2008, 11:22

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

Автор: SABROG 29.7.2008, 11:23

Цитата(Lazin @ 29.7.2008,  11:17) Цитата(andrew_121 @  29.7.2008,  10:53 ) Это что за нехороший класс такой. Его размер больше хранимой в нем строки!  без нехорошего класса, ты бы хранил указатель на начало строки, а размер указателя на твоей платформе равен 32 бита  Не, не. sizeof() возвращает размер в байтах. Посмотрите файлик basic_string.h, там действительно напихали всего.

Автор: Lazin 29.7.2008, 11:35

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

Автор: andrew_121 29.7.2008, 12:08

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

Автор: SABROG 29.7.2008, 12:15

Цитата(andrew_121 @ 29.7.2008,  12:08) SABROG - Я всегда юзал сей класс даже не задумываясь об этом. В данном случае мне нужно создать массив из 6 000 000 объектов, и памяти явно не хватает, ~1.3 Gb сжирает, поэтому я и решил проверить. Проверил, расстроился... Лучше бы и не зал сего  Ну пустые классы занимать будут тогда 183 мегабайта в твоем массиве. Я не знаю какая у тебя задача, но можно попробывать использовать массив обычных char'ов, а строки разделять \0'ми. Но это конечно, если есть возможность последовательного заполнения массива и еще надо будет написать алгоритм поиска строки по индексу.

Автор: Lazin 29.7.2008, 12:16

Цитата(andrew_121 @  29.7.2008,  12:08 ) массив из 6 000 000 объектов не многовато-ли будет для оперативной памяти?   такой массив данных нужно хранить на в файле или в БД...

Автор: andrew_121 29.7.2008, 12:19

Цитата(SABROG @  29.7.2008,  12:15 ) можно попробывать использовать массив обычных char'ов, а строки разделять \0'ми. Неа, так не пойдет... Нужно изменять значение строк. Добавлено через 2 минуты и 58 секунд Цитата(Lazin @  29.7.2008,  12:16 ) такой массив данных нужно хранить на в файле или в БД...  Массив-то и хранится в нескольких файлах. Но для операций над ним, нужно загрузить в память.

Автор: SABROG 29.7.2008, 12:24

Любопытный бенчмарк на сравнение Си и STL строк, не в пользу последних: http://deepencpp.blogspot.com/2007/08/stdstring-vs-const-char-comparison.html Lazin, а у меня тоже подобная ситуация возникала, из базы данных делается выборка окола 1.5 млна записей, по 20 колонок в каждой. Т.е. 30 млн. строк., которые распихваются по структурам и векторам. Сжирается вся оператива и вся виртуалка. Далее происходят операции типа парсинга этого всего дела. Объединения, конвертация из текста в числа и т.п. После того как алгоритм отработает результат пихается в Excel файл и после этого память освобождается. Теоретически можно как-то выгружать ненужные участки и подгружать новые по 10 раз, но это скажется на скорости работы программы. Т.е. либо скорость, либо память. Добавлено через 4 минуты и 4 секунды Цитата(andrew_121 @  29.7.2008,  12:19 ) Неа, так не пойдет... Нужно изменять значение строк. Тогда массив указателей на динамеческие строки типа char. Передал в какую-нибудь строковую функцию, она вернет новый указатель с изминенным текстом, старый удалиш и замениш новым. Правда все будет распихано по памяти неизвестно как.

Автор: W4FhLF 29.7.2008, 12:30

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

Автор: vinter 29.7.2008, 12:33

Цитата(SABROG @  29.7.2008,  13:24 ) Lazin, а у меня тоже подобная ситуация возникала, из базы данных Цитата(andrew_121 @  29.7.2008,  13:08 ) В данном случае мне нужно создать массив из 6 000 000 объектов, и памяти явно не хватает, ~1.3 Gb сжирает если это не расчитано на машины с большим кол-вом оперативы, аля серверы. Тогда надо подумать, не ошиблись ли вы случаем с выбором алгоритма? Цитата(SABROG @  29.7.2008,  13:24 ) Любопытный бенчмарк на сравнение Си и STL строк, не в пользу последних: http://deepencpp.blogspot.com/2007/08/stds...comparison.html ничего любопытного, STL реализаций много, а значит этот бенчмарк идет лесом, и второе: по вашему за удобство ничем не надо расплачиваться? Цитата(Mayk @  29.7.2008,  12:22 ) Ужжас. Целых 32 байта. Как жить дальше?   Неужели в системных требованиях придется писать "1 mb. ram"?  +1

Автор: Lazin 29.7.2008, 12:34

Цитата(andrew_121 @  29.7.2008,  12:19 ) Но для операций над ним, нужно загрузить в память.  неужели для обработки одной строки нужно знать все остальные, может как-нибудь, в несколько проходов можно все обработать?

Автор: SABROG 29.7.2008, 12:38

Цитата(vinter @  29.7.2008,  12:33 ) ничего любопытного, STL реализаций много, а значит этот бенчмарк идет лесом, и второе: по вашему за удобство ничем не надо расплачиваться? Хотябы light-weight классы строковые сделали бы, где можно реализовать хотябы простые операции без которых невозможна работа и с обычными char массивами.

Автор: andrew_121 29.7.2008, 12:39

Цитата(SABROG @  29.7.2008,  12:24 ) Любопытный бенчмарк на сравнение Си и STL строк, не в пользу последних Гм... Согласен! Не хотелось бы в С спускаться...но, похоже придется. Цитата(W4FhLF @  29.7.2008,  12:30 ) Давно уже пора переходить на x64 и не мучиться с ограничением 2гб.  Непонял...  На х32 ограничение 4гб. Или я чего не понял?

Автор: SABROG 29.7.2008, 12:44

Цитата(andrew_121 @ 29.7.2008,  12:39) Цитата(SABROG @  29.7.2008,  12:24 ) Любопытный бенчмарк на сравнение Си и STL строк, не в пользу последних Гм... Согласен! Не хотелось бы в С спускаться...но, похоже придется. Цитата(W4FhLF @  29.7.2008,  12:30 ) Давно уже пора переходить на x64 и не мучиться с ограничением 2гб.  Непонял...  На х32 ограничение 4гб. Или я чего не понял? Там если комменты почитать, то есть и обратные результаты. Пока сам не потестиш с разными реализациями не примешь правильное решение. Надо что-то с алгоритмом думать. Если программа начинает работать со свопом, то смысла тогда уже нет все держать в памяти, т.к. это равнозначно обычному чтению байтов из файла.

Автор: vinter 29.7.2008, 12:44

Цитата(andrew_121 @  29.7.2008,  13:39 ) Непонял... smile На х32 ограничение 4гб. Или я чего не понял?  ОС тоже кушать хочет

Автор: andrew_121 29.7.2008, 12:45

Цитата(vinter @  29.7.2008,  12:33 ) STL реализаций много К примеру...? Цитата(Lazin @  29.7.2008,  12:34 ) неужели для обработки одной строки нужно знать все остальные, может как-нибудь, в несколько проходов можно все обработать? Думаю - ДА. Это алгоритм унификации слов. Т.е. есть каталог  котором хранятся файлы словарей(простые .txt). Так вот при добавления нового файла, нужно проанализировать все словари на предмет повторения слов. Сами понимаете, итераций...ого-го

Автор: W4FhLF 29.7.2008, 12:47

Цитата(andrew_121 @  29.7.2008,  12:39 ) На х32 ограничение 4гб. Или я чего не понял? Ты чего не понял  Фактически для пользовательской программы система предоставляет 2гб виртуального адресного пространства. Часть адресов уже занята системными модулями и их данными, часть является служебной, часть под стек и кучу. На практике ограничение составляет порядка 1.5 гб.  Всегда есть два направления: память и быстродействие. В любом случае работа с данными находящимися в физической памяти(файл подкачки к которой не относится) будет всегда быстрее. Нужно найти золотую середину.  Действительно ли у тебя присутствует наобходимость хранить все 6млн. объектов в памяти?

Автор: Lazin 29.7.2008, 12:49

Цитата(andrew_121 @  29.7.2008,  12:39 ) На х32 ограничение 4гб. для процесса - 2Гб кстати можно использовать паттерн light weight хранить не массив строк, а массив объектов каждый объект хранит номер строки (или смещение) в файле если объект не используется, то он хранит необходимый минимум данных, для того что-бы он мог считать себя из файла если к объекту происходит обращение, то он считывает свои данные из памяти(так как знает откуда читать) прозрачно для клиента Вообще это дурной подход к делу, так как нужно заботиться о масштабировании, завтра тебе понадобится обработать не 6 000 000 объектов, на несколько порядков больше, и ни в какую память они не влезут, что будешь делать?  Добавлено через 1 минуту и 38 секунд Цитата(andrew_121 @  29.7.2008,  12:45 ) Это алгоритм унификации слов. Т.е. есть каталог  котором хранятся файлы словарей(простые .txt). Так вот при добавления нового файла, нужно проанализировать все словари на предмет повторения слов. Сами понимаете, итераций...ого-го ну так это просто индексация, все читать не обязательно...

Автор: andrew_121 29.7.2008, 12:52

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

Автор: vinter 29.7.2008, 12:53

Цитата(Lazin @  29.7.2008,  13:49 ) для процесса - 2Гб винду можно с ключиком запустить и будет 3

Автор: W4FhLF 29.7.2008, 12:55

Цитата(andrew_121 @  29.7.2008,  12:52 ) Может есть какие-то иные методы...? Да БД однозначно. Добавлено через 1 минуту и 38 секунд Надо сделать ещё одну оговорку. БД может не подойти в случае, если исходный формат, в котором будут поступать данные, всегда будет txt и от тебя это не зависит. И в случае, если данные словари достаточно часто меняются.

Автор: Lazin 29.7.2008, 12:57

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

Автор: andrew_121 29.7.2008, 12:59

Цитата(Lazin @  29.7.2008,  12:49 ) Вообще это дурной подход к делу, так как нужно заботиться о масштабировании, завтра тебе понадобится обработать не 6 000 000 объектов, на несколько порядков больше, и ни в какую память они не влезут, что будешь делать? Абсолютно согласен. Исправлю.

Автор: W4FhLF 29.7.2008, 13:00

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

Автор: Lazin 29.7.2008, 13:00

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

Автор: SABROG 29.7.2008, 13:00

Цитата(andrew_121 @ 29.7.2008,  12:52) Цитата(SABROG @  29.7.2008,  12:44 ) Если программа начинает работать со свопом, то смысла тогда уже нет все держать в памяти Согласен. Нет, памяти хватает. Но как-то медлено это все происходит... Я просто кимарю на раб. месте, пока день не закончится. В данный момент в словарях 5 746 337 слов, операция над ними занимает ~13 часов на P4 Core 2 Duo 3.2Ghz? 2Gb ram DDR2-Dual. Может есть какие-то иные методы...? Может есть смысл воспользоваться одной из баз данных ? В них уже реализованы алгоритмы поиска, сравнения, индексации, экономии памяти и т.д. А вообще словари надо попросту специальным образом проиндексировать. Например создаешь файл индекса, где букве "А" соответствует стартовое смещение в файле каждого словаря и длинна участка. В итоге в память ты уже будешь загружать не все слова, а только на букву "А", далее сравниваешь сначала строки по размеру. Если длинна строк не идентична, то они уже не равны (правда не знаю, может функция сравнения строк уже так и делает.

Автор: W4FhLF 29.7.2008, 13:04

Цитата(SABROG @  29.7.2008,  13:00 ) Например создаешь файл индекса, где букве "А" соответствует стартовое смещение в файле каждого словаря и длинна участка. Тогда ещё отсортировать надо  Добавлено через 6 минут и 29 секунд Цитата(andrew_121 @  29.7.2008,  12:45 ) Это алгоритм унификации слов. Т.е. есть каталог  котором хранятся файлы словарей(простые .txt). Так вот при добавления нового файла, нужно проанализировать все словари на предмет повторения слов. Сами понимаете, итераций...ого-го Всё-таки лучше действительно посчитать один раз хеши. Возьми какую-нибудь быструю хеш-функцию, например adler32, создай массив простых структур/классов, которые бы хранили хеш слова + позицию слова в файле, можно ещё длину слова. Если основная операция сравнение слов, то здесь ты многократно выигрываешь.  Мало памяти, высокая производительность как раз в случае проверки дубликатов.

Автор: Любитель 29.7.2008, 13:11

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

Автор: andrew_121 29.7.2008, 13:22

Цитата(Lazin @  29.7.2008,  12:57 ) а на что время в основном тратится?  На std::sort(), std::unique() и далее на итерации по словам между словарями.

Автор: Lazin 29.7.2008, 13:35

Цитата(andrew_121 @  29.7.2008,  13:22 ) std::sort(), std::unique() тогда логично для этого использовать структуры данных, на которых эти операции имели бы сложность О(1) или O(ln(N))

Автор: andrew_121 29.7.2008, 15:00

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

Автор: SABROG 29.7.2008, 18:33

Цитата(andrew_121 @ 29.7.2008,  15:00) Всем Преогромное Спасибо    Приступаю к реализации. Решил тоже сравнить на своей тачке скорость: gcc Цитата "running test batch for STL strings........." +0.000056: string string -0.000059: string1 string2 -0.000049: 1string 2string -0.000055: string string1 -0.000059: string1 string "running test batch for C strings........." +0.000022: string string -0.000022: string1 string2 -0.000013: 1string 2string -0.000022: string string1 -0.000022: string1 string msvc Цитата "running test batch for STL strings........." +0.000102 -0.000104 -0.000102 -0.000100 -0.000104 "running test batch for C strings........." +0.000029 -0.000029 -0.000018 -0.000029 -0.000029 А это сравнение идентичных строк удвоенной длинны (gcc): Цитата "running test batch for STL strings........." +0.000066: stringstring stringstring +0.000069: string1string2 string1string2 +0.000069: 1string2string 1string2string +0.000068: stringstring1 stringstring1 +0.000068: string1string string1string "running test batch for C strings........." +0.000034: stringstring stringstring +0.000039: string1string2 string1string2 +0.000038: 1string2string 1string2string +0.000031: stringstring1 stringstring1 +0.000031: string1string string1string Цитата >g++ -v Reading specs from C:/MinGW/bin/../lib/gcc/mingw32/3.4.2/specs Configured with: ../gcc/configure --with-gcc --with-gnu-ld --with-gnu-as --host= mingw32 --target=mingw32 --prefix=/mingw --enable-threads --disable-nls --enable -languages=c,c++,f77,ada,objc,java --disable-win32-registry --disable-shared --e nable-sjlj-exceptions --enable-libgcj --disable-java-awt --without-x --enable-ja va-gc=boehm --disable-libgcj-debug --enable-interpreter --enable-hash-synchroniz ation --enable-libstdcxx-debug Thread model: win32 gcc version 3.4.2 (mingw-special) Собирал проги без каких-либо ключей оптимизации, т.е. тупо: Код g++ -o stl stl.cpp g++ -o c c.cpp Код cl c.cpp cl stl.cpp Тесты проводились под Win2000SP4.

Автор: Lazin 29.7.2008, 18:55

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

Автор: SABROG 29.7.2008, 18:58

Цитата(Lazin @ 29.7.2008,  18:55) SABROG, в VS по умолчанию stl проверяет выход за границы контейнера, это отключается каким-то макросом... результат для msvc должен быть близок к результату gcc кстати на очень длинных строках результат может каардинално измениться...  Запущу тесты на ночь на длинных строках. Завтра запощу.

Автор: Lazin 29.7.2008, 20:18

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

Автор: Torsten 30.7.2008, 08:36

Цитата(andrew_121 @  29.7.2008,  10:53 ) Это что за нехороший класс такой. Его размер больше хранимой в нем строки! Это сделано специально, чтобы когда ты увеличиваешь размер строки память не пришлось перевыделять (новую выделить, скопировать элементы, старую удалить). Так делают все stl контейнеры. Так же есть метод reserve, через который можно установить желаемый размер, но он будет установлен, только если текующий зарезирвированный размер меньше.

Автор: vinter 30.7.2008, 09:38

Цитата(Torsten @  30.7.2008,  09:36 ) Это сделано специально, чтобы когда ты увеличиваешь размер строки память не пришлось перевыделять (новую выделить, скопировать элементы, старую удалить). string хранит указатель на память, размер строки не влияет на размер string Цитата(Torsten @  30.7.2008,  09:36 ) Так делают все stl контейнеры. зависит от реализации.

Автор: SABROG 30.7.2008, 10:31

Цитата(Lazin @ 29.7.2008,  20:18) ну не на столько-же длинных  Сегодня не судьба. Ночью в офисе вырубило электричество все результаты пропали.

Автор: Любитель 30.7.2008, 13:25

Цитата(Torsten @  30.7.2008,  08:36 ) Это сделано специально, чтобы когда ты увеличиваешь размер строки память не пришлось перевыделять (новую выделить, скопировать элементы, старую удалить). Так делают все stl контейнеры. Так же есть метод reserve, через который можно установить желаемый размер, но он будет установлен, только если текующий зарезирвированный размер меньше. Размер самой строки через sizeof вообще не возможно получить  Мы получаем размер всех полей класса: указателя на строку (4 байта), её физический размер (4 байта), её логический размер (4 байта). Откуда взялось отсальное - фиг его знает, надо смотреть  Ну, плюс выравнивани не забываем!

Автор: andrew_121 30.7.2008, 13:59

Цитата(Любитель @  30.7.2008,  13:25 ) Размер самой строки через sizeof вообще не возможно получить smile Мы получаем размер всех полей класса: указателя на строку (4 байта), её физический размер (4 байта), её логический размер (4 байта). Откуда взялось отсальное - фиг его знает, надо смотреть smile Ну, плюс выравнивани не забываем! Это понятно. Но откуда взялись 32 байта   Это походу 8 указателей, или что-то еще...бред... А в Лине кто-то проверял? Щас в Mingw проверю. Добавлено через 13 минут и 42 секунды Проверил. Вот результаты. Код #include <string> #include <vector> #include <iostream> int main() {     std::string str;     std::vector<char> cv;     std::vector<int> iv;     int sz1 = sizeof(str);     int sz2 = sizeof(cv);     int sz3 = sizeof(iv);          std::cout<< "sizeof(std::string)       = " << sz1 << std::endl                 << "sizeof(std::vector<char>) = " << sz2 << std::endl                 << "sizeof(std::vector<int>)  = " << sz3 << std::endl;          return 0; } Для MSVC-2008, компилил из командной строки, без каких либо опций. Код sizeof(std::string)       = 28 sizeof(std::vector<char>) = 24 sizeof(std::vector<int>)  = 24 И для Mingw: Код sizeof(std::string)       = 4 sizeof(std::vector<char>) = 12 sizeof(std::vector<int>)  = 12 Тоже без опций. Разница на лицо.

Автор: Любитель 30.7.2008, 14:23

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

Автор: Lazin 30.7.2008, 14:25

в студии нужно компилить с таким дефайном Код #define _SECURE_SCL 0 что-бы все было честно

Автор: SABROG 30.7.2008, 14:58

Цитата(Lazin @ 30.7.2008,  14:25) в студии нужно компилить с таким дефайном Код #define _SECURE_SCL 0 что-бы все было честно  А студия 2005 все-равно выдает 28 байт против 4х в mingw (gcc). Код #include <iostream> #define _SECURE_SCL 0 int main(int argc, char *argv[]) {     std::cout << sizeof(std::string) << std::endl;     return 0; }

Автор: Lazin 30.7.2008, 15:19

Цитата(SABROG @  30.7.2008,  14:58 ) А студия 2005 все-равно выдает 28 байт против 4х в mingw (gcc). ну еще-бы, он вроде-бы должен проверку итераторов отключать  да, и Код #define _SECURE_SCL 0 #include <iostream>

Автор: Любитель 30.7.2008, 15:23

Блин, и в чём мораль? Смотрим заголовычные файлы МинГВ. Все данные строки хранятся через некий _M_dataplus, в котором есть: Код _CharT* _M_p; // The actual data. И куча реинтерпрет-кастов затем. Чтобы получить, например, _Rep: Код       struct _Rep_base       {     size_type        _M_length;     size_type        _M_capacity;     _Atomic_word        _M_refcount;       }; Зачем всё так сложно? Скорей всего виноват референс-каунтинг. Если хочется сравнить реально память, занимаемую строками - создаём огромное количество этих строк и смотрим, сколько памяти жрёт процесс.

Автор: SABROG 30.7.2008, 15:24

Цитата(Lazin @ 30.7.2008,  15:19) Цитата(SABROG @  30.7.2008,  14:58 ) А студия 2005 все-равно выдает 28 байт против 4х в mingw (gcc). ну еще-бы, он вроде-бы должен проверку итераторов отключать  да, и Код #define _SECURE_SCL 0 #include <iostream> А я и так и так пробывал, разницы нету  Последовал совету Любителя, вот код: Код #include <iostream> int main(int argc, char *argv[]) {     std::cout << sizeof(std::string) << std::endl;     for (int i=0; i < 6000000; i++)     {         new std::string;     }     std::cin.get();     return 0; } Создается 6 млнов экземпляров пустых классов: В итоге: mingw (gcc) - 141 896 kb msvc - 235 716 kb

Автор: andrew_121 30.7.2008, 15:50

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

Автор: W4FhLF 30.7.2008, 15:55

Цитата(SABROG @  30.7.2008,  15:24 ) mingw (gcc) - 141 896 kb msvc - 235 716 kb А если хотя бы 1 символ в строку записать? Может в случае mingw для пустых строк просто не хранится никакой служебной инфы.

Автор: Любитель 30.7.2008, 15:58

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

Автор: SABROG 30.7.2008, 16:19

Цитата(Любитель @ 30.7.2008,  15:58) И ещё - везде надо включать оптимизацию. Иначе сравнение не объективно. Ну для gcc -O3 я могу прописать, на другие ключи у меня знаний не хватит. А для cl я вообще не знаю ключей оптимизации. С таким кодом я вообще получил неожиданные результаты: Код #include <iostream> #define _SECURE_SCL 0 int main(int argc, char *argv[]) {     std::cout << sizeof(std::string) << std::endl;     for (int i=0; i < 6000000; i++)     {         new std::string("Hello, World!");     }     std::cin.get();     return 0; } gcc - 376 604kb msvc - 235 716kb Попробывал провести тест снова с пустыми классами и опять msvc продул, а с заполненными продувает gcc. Скомпилил прогу с помощью gcc с максимальной оптимизацией -O3, результат никак не изменился.

Автор: Lazin 30.7.2008, 16:20

немного потестировал пример из блога deepencpp для разных строк для коротких строк l1 и l2 - длины строк, конкретные значения не важны, важно отношение - больше, меньше... Код С     | stl | ------+-----+----------+ 1.0   | 3.0 | l1 == l2 | 1.2   | 2.6 | l1 != l2 | ------+-----+----------+ для длинных Код С     | stl | ------+-----+----------+ 1.0   | 3.0 | l1 == l2 | 88.   | 25. | l1 != l2 | ------+-----+----------+ честно говоря я думал что на длинных строках результаты будут равны, но все оказалось еще интереснее... Добавлено через 44 секунды зы компилятор vs2005, ключи /O2, /Ot

Автор: W4FhLF 30.7.2008, 16:22

Цитата(SABROG @  30.7.2008,  16:19 ) А для cl я вообще не знаю ключей оптимизации. /O1 - size /O2 - speed /Ox - full Цитата(SABROG @  30.7.2008,  16:19 ) gcc - 376 604kb msvc - 235 716kb то то

Автор: Любитель 30.7.2008, 16:24

Цитата(SABROG @  30.7.2008,  16:19 ) А для cl я вообще не знаю ключей оптимизации. 1. cl /? 2. Скажем, cl /Ox. Цитата(SABROG @  30.7.2008,  16:19 ) Попробывал провести тест снова с пустыми классами и опять msvc продул, а с заполненными продувает gcc. Можно увидеть вариант со включенной отимизацией?

Автор: SABROG 30.7.2008, 16:32

Цитата(Любитель @  30.7.2008,  16:24 ) Можно увидеть вариант со включенной отимизацией?  Добавил ключи /Ox и -O3 соотв, результаты не изменились никак вообще. Оптимизация вообще никак не повлияла на тесты с пустыми и заполненными классами. Т.е. осталось все прежним. Если сравнивать два теста с пустыми классами и заполненными, то можно увидеть, что размер занимаемой памяти для msvc не меняется вообще. Видимо msvc проигрывает в первом тесте из-за того, что резервирует память изначально, чего не делает gcc.

Автор: andrew_121 30.7.2008, 16:39

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

Автор: SABROG 30.7.2008, 16:54

Вот кстати еще один вариант: Код #define _SECURE_SCL 0 #include <iostream> int main(int argc, char *argv[]) {     std::cout << sizeof(std::string) << std::endl;             for (int i=0; i < 6000000; i++)     {         new std::string("", 1);     }     std::cin.get();     return 0; } Результат: msvc - 235 716kb gcc - 282 932kb А тут я решил увеличить количество строк до 90 млн.ов c непустыми классами, результат мне не очень понравился: gcc - 563 712kb msvc - 352 452 kb

Автор: Lycifer 30.7.2008, 16:58

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

Автор: Любитель 30.7.2008, 17:00

Цитата(Lycifer @  30.7.2008,  16:58 ) STL == как на ресурсы, работать быстро - гдк то слышал, хотя работать быстро не получается(во первых память не вовремя олсвобождается, а во вторых new,delete,malloc,realloc - медленнеы так как ищют дырки в памяти, то и есть свободные места)  Ой, а можно по-русски?  Добавлено через 21 секунду Да, и кстати boost::array - это для массивов постоянного размера.

Автор: SABROG 30.7.2008, 17:11

А вот в подтверждение моих слов результаты метода max_size(), который возвращает максимальное количество символов, которое может содержать экземпляр класса std::string: gcc - 1073741820 msvc - 4294967294 Т.е. все-таки msvc хоть и имеет размер класса 28 байт, но он резервирует много памяти для новой строки о чем говорит функция capacity(), которая возвращает 15 байт для msvc и 0 байт для gcc.

Автор: just_geek 30.7.2008, 18:25

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

Автор: vinter 30.7.2008, 18:46

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

Автор: Любитель 30.7.2008, 18:48

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

Автор: SABROG 30.7.2008, 19:25

Цитата(just_geek @ 30.7.2008,  18:25) Еще ради интереса stlport бы сравнили на обоих компиляторах  А так же gcc 4.x Ага, а потом начнется, а вот еще и для watcom сравните и для icc и для bcc. А потом на разных платформах, операционных системах. А потом версии библиотек, стабильные/не стабильные. А потом еще и с разными ключами собранные библиотеки. А потом скажут, что сравниваете не верно, код должен быть другой.

Автор: andrew_121 30.7.2008, 19:30

А у меня stlport не собирается для Студии. Вот что сообщает: Код C:\projects\stlport\build\lib>nmake -fmsvc.mak Microsoft (R) Program Maintenance Utility Version 9.00.21022.08 Copyright (C) Microsoft Corporation.  All rights reserved.         cl /nologo /W4 /Wp64 /GR /EHsc /Zm800  /GL /MD /Zi /O2  /DWIN32 /D_WINDO WS /DNDEBUG  /I../../stlport  /c /Foobj\vc8\shared\dll_main.o /Fdobj\vc8\shared\ stlport.5.1.pdb ../../src\dll_main.cpp cl : Command line warning D9035 : option 'Wp64' has been deprecated and will be removed in a future release dll_main.cpp C:\projects\stlport\stlport\stl/_locale.h(108) : error C2487: 'collate' : member  of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_locale.h(109) : error C2487: 'ctype' : member o f dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_locale.h(110) : error C2487: 'monetary' : membe r of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_locale.h(111) : error C2487: 'numeric' : member  of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_locale.h(112) : error C2487: 'time' : member of  dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_locale.h(113) : error C2487: 'messages' : membe r of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_locale.h(118) : error C2487: 'all' : member of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(74) : error C2487: 'right' : member of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(75) : error C2487: 'internal' : memb er of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(76) : error C2487: 'dec' : member of  dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(77) : error C2487: 'hex' : member of  dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(78) : error C2487: 'oct' : member of  dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(79) : error C2487: 'fixed' : member of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(80) : error C2487: 'scientific' : me mber of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(81) : error C2487: 'boolalpha' : mem ber of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(82) : error C2487: 'showbase' : memb er of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(83) : error C2487: 'showpoint' : mem ber of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(84) : error C2487: 'showpos' : membe r of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(85) : error C2487: 'skipws' : member  of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(86) : error C2487: 'unitbuf' : membe r of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(87) : error C2487: 'uppercase' : mem ber of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(88) : error C2487: 'adjustfield' : m ember of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(89) : error C2487: 'basefield' : mem ber of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(90) : error C2487: 'floatfield' : me mber of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(93) : error C2487: 'goodbit' : membe r of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(94) : error C2487: 'badbit' : member  of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(95) : error C2487: 'eofbit' : member  of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(96) : error C2487: 'failbit' : membe r of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(99) : error C2487: '__default_mode' : member of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(100) : error C2487: 'app' : member o f dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(101) : error C2487: 'ate' : member o f dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(102) : error C2487: 'binary' : membe r of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(103) : error C2487: 'in' : member of  dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(104) : error C2487: 'out' : member o f dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(105) : error C2487: 'trunc' : member  of dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(109) : error C2487: 'beg' : member o f dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(110) : error C2487: 'cur' : member o f dll interface class may not be declared with dll interface C:\projects\stlport\stlport\stl/_ios_base.h(115) : error C2487: 'end' : member o f dll interface class may not be declared with dll interface NMAKE : fatal error U1077: '"C:\Program Files\Microsoft Visual Studio 9.0\VC\BIN \cl.EXE"' : return code '0x2' Stop. Какие мысли?

Автор: Torsten 30.7.2008, 20:24

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

Автор: andrew_121 30.7.2008, 22:18

Цитата(Torsten @  30.7.2008,  20:24 ) Вы на stlport тестируйте, там честнее будет для всех компиляторов, т.к. у студии собственная stl.  Вот я и попытался...

Автор: SABROG 30.7.2008, 23:36

Народ, а че за фигня. Прописал пути: Код @echo off set MINGW=C:/MinGW set QMAKESPEC=win32-g++ set PATH=%QTDIR%/bin;%MINGW%/bin;c:/gdb/bin;%PATH% set LIB=c:/stl/lib;%MINGW%/lib set INCLUDE=c:/stl/stlport;%MINGW%/include; cmd Пытаюсь скомпилить так: Код g++ -O3 -o strstrings stlstrings.cpp -lstlport Получаю:  Код C:\MinGW\bin\..\lib\gcc\mingw32\3.4.5\..\..\..\..\mingw32\bin\ld.exe: cannot fin d -lstlport Меняю на  Код g++ -O3 -o strstrings stlstrings.cpp -lstlport.5.1 Получаю  Код C:\MinGW\bin\..\lib\gcc\mingw32\3.4.5\..\..\..\..\mingw32\bin\ld.exe: cannot fin d -lstlport.5.1 Меняю на: Код g++ -O3 -o strstrings stlstrings.cpp -L./LIB/ -lstlport.5.1 Опять не компилится. Меняю на полный путь: Код D:\Work\STLportStringTest>g++ -O3 -o strstrings stlstrings.cpp -Lc:/stl/lib -lst lport.5.1 Компилиться. Почему линкер не видит ни переменную окружения LIB, ни косвенный путь через -L./LIB/ (даже -L../LIB пробывал с вариациями) ? --- Ага, это спасает отца русской демократии: Код set LPATH=c:/stl/lib

Автор: SABROG 31.7.2008, 01:25

Вроде бы собрал STLPort для обоих компиляторов, а размеры классов почему-то не изменились также как и количество занимаемой памяти. Даже как в мануале прописал инклюд первым, видимо компилеры все-таки родной STL включают. Пол третьего ночи, сил уже нету...

Автор: Mayk 31.7.2008, 05:24

Цитата(SABROG @  31.7.2008,  05:25 ) видимо компилеры все-таки родной STL включают Попробуй в STLPort'овском string'е прописать #error hello world. если сообщение ошибке не вылетит - значит stl port не подключен. если вылетит - подключен

Автор: SABROG 31.7.2008, 08:21

Цитата(Mayk @ 31.7.2008,  05:24) Цитата(SABROG @  31.7.2008,  05:25 ) видимо компилеры все-таки родной STL включают Попробуй в STLPort'овском string'е прописать #error hello world. если сообщение ошибке не вылетит - значит stl port не подключен. если вылетит - подключен Прописал этот error в файле "string.h" STLPort'a, снес переменную окружения INCLUDE, прописал в переменной окружения PATH путь с инклюдами STLPort'a в самом начале. Не помогает, все-равно mingw берет старый и все нормально компилит. --- Похоже при компиляции каждый раз нужно задавать непосредственные пути. Так error выдает, что говорит о том, что все-таки STLPort увиделся: Код g++ -mthreads -Ic:/stl/stlport -O3 -o stlpmingw stlstrings.cpp -Lc:/stl/stlport/lib -lstlport.5.1 --- Фух, собрал таки наконец. Итак 6 млн.ов классов std::string (STLPort) занимают в памяти: msvc - 189 132kb (Родной STL - 235 716kb) mingw -  188 912 kb (Родной STL - 141 896kb) Пустой класс имеет размер 24 байта для обоих компиляторов. 6 млн.ов строк "hello, worldhello, worldhello, worldhello, worldhello, worldhello, worldhello, worldhello, worldhello, worldhello, worldhello, worldhello, worldhello, world" отнимают приблизительно 1 гиг и 200 мегов памяти и при этом разница между компиляторами не была больше 400кб.

Автор: andrew_121 31.7.2008, 12:17

SABROG - Вот ты упертый   Спасибо от всех читающих сею тему   Я вот поразмыслил. В моем представлении строковый класс должен содержать что-то вроде: Код struct storage {    char* str;    int len;    int reserved; }; или Код struct storage {    char* begin;    char* end;    char* endofstorage; }; И это 12 байт. А на* еще 12 байт, и для чего их использовать...хз...

Автор: SABROG 31.7.2008, 13:18

Цитата(andrew_121 @  31.7.2008,  12:17 ) А на* еще 12 байт Дык я же писал, что у msvc 15 байт в резерве на строку. Т.е. по сути пустой экземпляр класса std::string это готовая строка размером в 15 байт, поэтому нет никакой разницы между пустым классом и заполненным, если строка меньше 15 символов. Делалось это, по видимому, для ускорения работы программы, чтобы не приходилось дополнительно выделять память под каждую строку в зависимости от длинны строки.

Автор: Любитель 31.7.2008, 13:35

SABROG, строка хранится в памяти непрерывно. Это вообщем-то факт (чтобы нормально рабоали c_str и data). Поэтому в классе должен быть только указатель на строку. Никак не сама строка.

Автор: SABROG 31.7.2008, 13:43

Цитата(Любитель @ 31.7.2008,  13:35) SABROG, строка хранится в памяти непрерывно. Это вообщем-то факт (чтобы нормально рабоали c_str и data). Поэтому в классе должен быть только указатель на строку. Никак не сама строка. Я писал раньше, что метод capacity() возвращет количество символов, которое может содержать строка изначально. Эксперимент показал, что размеры занимаемой памяти никак не менялся, если я создавал 6 млн.ов пустых строк, или 6 млн.ов строк длинной меньше 15 символов (hello, world).

Автор: Mayk 31.7.2008, 13:45

Цитата(Любитель @  31.7.2008,  17:35 ) Поэтому в классе должен быть только указатель на строку. Никак не сама строка.  Скажи это разработчикам STLport и STL в MS. А то они совсем идиоты. Ещё расскажи им что хранить в классе длину строки не надо. Ибо "только указатель" это наше всё.

Автор: Любитель 31.7.2008, 13:46

И? То, что во многих реализациях стл память резервируется заранее - это очевидно. Только к sizeof-у сабжевому это не имеет никакого отношения

Автор: Mayk 31.7.2008, 13:46

плин не получилось впереёд SABROG'а ответить      тьфу блин не склеилось Цитата(Любитель @  31.7.2008,  17:46 ) И? То, что во многих реализациях стл память резервируется заранее - это очевидно. Только к sizeof-у сабжевому это не имеет никакого отношения smile  И где же она резервируется как не внутри класса?  Берется из эфира?

Автор: vinter 31.7.2008, 13:50

Цитата(Mayk @  31.7.2008,  14:46 ) И где же она резервируется как не внутри класса?  Берется из эфира? в классе хранится указатель на выделенную в куче память. Причем тут объект класса? Цитата(SABROG @  31.7.2008,  14:43 ) Я писал раньше, что метод capacity() возвращет количество символов, которое может содержать строка изначально. и что? это размер выделенной памяти, каким образом это должно показать, что память выделена внутри объекта?

Автор: Любитель 31.7.2008, 13:53

Mayk!   Цитата(Mayk @  31.7.2008,  13:46 ) И где же она резервируется как не внутри класса?  Берется из эфира? Код int* a = new int [1000]; assert(sizeof(a) != 1000); // !!! Добавлено через 1 минуту и 42 секунды Резервируется, короче, она никак не внутри класса. Ибо размер класса статичен, строки - нет. А очень желательно хранить строку непрерывно (иначе - проблем больше будет). Что касается размера буфера, размера строки, аллокаторов, итераторов и пр. - да, это хранится в самом классе. Не только указатель, но никак ни сама строка. Добавлено через 2 минуты и 36 секунд Цитата(Mayk @  31.7.2008,  13:45 ) STL в MS К слову - Dinkumware STL. Платно доступна, кстати, для гцц

Автор: Lazin 31.7.2008, 14:04

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

Автор: SABROG 31.7.2008, 14:46

Цитата(Lazin @  31.7.2008,  14:04 ) достаточно хранить в памяти хэш Какие алгоритмы могут дать хэш размером в 32 бита ? Я правильно понимаю "хэш" в данном контексте это уникальное значение, которое берется путем математических манипуляций с уникальной строкой. Т.е. если была строка "Hello, World" и я поменяю W на прописную w, то хэш уже будет другой. И хэш будет мне гарантировать, что в базе не появится строка с подобных хешем. Когда я подобное искал, то не нашел алгоритмов с хэшами меньше 128 бит и то они не гарантировали уникальности. В итоге пришел к выводу, что экономнее хранить строки как есть, т.к. хэши даже для однобайтовых строк слишком длинные.

Автор: Любитель 31.7.2008, 15:02

Хеш - не может быть абсолютно уникальным  Иначе это не хеш - а просто сжатая строка

Автор: W4FhLF 31.7.2008, 15:05

Цитата(SABROG @  31.7.2008,  14:46 ) Какие алгоритмы могут дать хэш размером в 32 бита ? http://en.wikipedia.org/wiki/Adler-32 Для нескольких миллионов слов пойдёт. Цитата(SABROG @  31.7.2008,  14:46 ) Когда я подобное искал, то не нашел алгоритмов с хэшами меньше 128 бит и то они не гарантировали уникальности. Как они могут гарантировать уникальность? Сколько всего состояний может принять последовательность 128 бит? 2^128. А сколько всего состояний может принять последовательность, например, из 256 бит? Ясно, что 2^256  >> 2^128 и что меньшая последовательность в прицнипе не сможет хранить все состояния первой. Тут вопрос вероятности, а в нормальных хеш-функциях они очень малы, поэтому ими пренебрегают.

Автор: Любитель 31.7.2008, 15:10

Цитата(W4FhLF @  31.7.2008,  15:05 ) и что меньшая последовательность в прицнипе не сможет хранить все состояния первой Ну, если быть точным - для строки это в некоторой мере возможно, учитывая, что символом с кодом ниже 32 у нас нет.

Автор: Lazin 31.7.2008, 15:21

Цитата(SABROG @  31.7.2008,  14:46 ) Когда я подобное искал, то не нашел алгоритмов с хэшами меньше 128 бит и то они не гарантировали уникальности. В итоге пришел к выводу, что экономнее хранить строки как есть, т.к. хэши даже для однобайтовых строк слишком длинные.  boost::hash пишет хэш в size_t,  2^32 = 4 294 967 296 количество слов = 6 000 000 так что коллизии маловероятны...

Автор: andrew_121 31.7.2008, 15:45

Цитата(Mayk @  31.7.2008,  13:45 ) Ещё расскажи им что хранить в классе длину строки не надо. Не согласен. Если в цикле нужно проверять размер одной и той же строки, то это расходы на strlen(). Плюс, необходимо знать размер вместимости строки, и предварительно выделять с запасом, чтоб избежать постоянного перевыделения памяти. имхо.

Автор: UnrealMan 1.8.2008, 02:18

Цитата(andrew_121 @  31.7.2008,  12:17 ) А на* еще 12 байт, и для чего их использовать...хз...  Сделано специально для малых строк. Таким образом малые строки могут храниться в стеке, что может повысить быстродействие. Если длина строки больше некоторого порогового значения, то для хранения символов используется динамическая память. Цитата(Любитель @  31.7.2008,  13:35 ) SABROG, строка хранится в памяти непрерывно. Это вообщем-то факт Для обсуждаемых здесь реализаций факт, стандарт же не гарантирует непрерывность.

Автор: Mayk 1.8.2008, 05:36

Цитата(Любитель @  31.7.2008,  17:53 ) Резервируется, короче, она никак не внутри класса. Ибо размер класса статичен, строки - нет Если размер строки <константы то его не статичность идёт побоку. Ссылка  на Short String Optimisation уже была.

Автор: andrew_121 1.8.2008, 12:01

Цитата(UnrealMan @  1.8.2008,  02:18 ) Сделано специально для малых строк. Таким образом малые строки могут храниться в стеке, что может повысить быстродействие. Если длина строки больше некоторого порогового значения, то для хранения символов используется динамическая память. Глупость   А если длина строки меньше 12, то что, где рассудок?

Автор: Lazin 1.8.2008, 12:17

Цитата(andrew_121 @  1.8.2008,  12:01 ) Глупость smile  А если длина строки меньше 12, то что, где рассудок? ты учти что менеджер памяти выделяет память под маленькие объекты блоками фиксированного размера, кратными степеням двойки, под строку размером 12 байт может быть выделено 16 байт, а может и 32... плюс обращение к строке в куче дороже чем обращение к строке в стеке, плюс создание и освобождение строки в куче не дешевая операция, в отличии от создания объекта в стеке... блин, так и не понял, нафига тебе хранить кучу строк в памяти?

Автор: Vyacheslav 1.8.2008, 17:12

Цитата(Любитель @  31.7.2008,  13:35 ) SABROG, строка хранится в памяти непрерывно. Это вообщем-то факт (чтобы нормально рабоали c_str и data). Поэтому в классе должен быть только указатель на строку. Никак не сама строка. Стандарт это не регламентирует в отличие от непрерывной памяти для vector. И  c_str и data  как раз могут не отражать как на самом деле хранится строка.

Автор: Любитель 1.8.2008, 17:21

Цитата(Vyacheslav @  1.8.2008,  17:12 ) Стандарт это не регламентирует в отличие от непрерывной памяти для vector. И  c_str и data  как раз могут не отражать как на самом деле хранится строка.  Согласен. Но, с точки зрения реализации - зачем нам неконстантная сложность для c_str и data?

Автор: vinter 1.8.2008, 17:24

Цитата(Vyacheslav @  1.8.2008,  18:12 ) Стандарт это не регламентирует в отличие от непрерывной памяти для vector. И  c_str и data  как раз могут не отражать как на самом деле хранится строка. стандарт может и  не регламентирует, но врядли вы найдете реализацию string где итераторы не являются обычными указателями.

Автор: phprus 2.8.2008, 18:44

Цитата(andrew_121 @ 29.7.2008,  12:45) Цитата(Lazin @  29.7.2008,  12:34 ) неужели для обработки одной строки нужно знать все остальные, может как-нибудь, в несколько проходов можно все обработать? Думаю - ДА. Это алгоритм унификации слов. Т.е. есть каталог  котором хранятся файлы словарей(простые .txt). Так вот при добавления нового файла, нужно проанализировать все словари на предмет повторения слов. Сами понимаете, итераций...ого-го  Задача не очень понятна. Исходные данные: 1) много файлов содержащих слова 2) новый файл со словами Возникают вопросы: Что нужно получить в результате? В случае если нужно получить один результирующий файл в котором будут все уникальные слова, то имеем элементарную задачу. Сливаем все слова в один файл, сортируем его сортировкой слиянием ( О(n*log(n)) ) и за О(н) удаляем дублирующиеся слова. Это наиболее быстрое из всех возможных решений, кроме того оно не требовательно к оперативной памяти. В некоторых случаях для решения этой задачи достаточно стандартной *nix'овой утилиты sort аналоги которой есть и под винду. Если нужно новый файл очистить от тех слов, которые есть в старых файлах, то можно слить все старые файлы в один, отсортировать его, после чего задачу поиска дублей можно решить за один проход по обоим файлам. Если что-то еще, то уточни задачу, но очень похоже, что ты что-то не то делаешь. Не похоже что-бы подобная задача требовала загрузки всех данных в память. Хэш-таблицы тут не подойдут, так как потребуется дополнительное время на из создание, а во вторых в связи с возможностью коллизий при каждом поиске нужно будет сравнивать не только вычислять и сравнивать хэш-коды, но и сравнивать сами строки, что приведет фактически к 2-х кратному росту числа проходов по данным.

Автор: W4FhLF 2.8.2008, 18:55

Цитата(phprus @  2.8.2008,  18:44 ) Сливаем все слова в один файл, сортируем его сортировкой слиянием ( О(n*log(n)) ) Ну это в теории конечно так красиво. Попробуй отсортировать файл с 10 млн. слов, это займёт никак не меньше времени, чем просчёт и построение хеш-таблиц. Цитата(phprus @  2.8.2008,  18:44 ) а во вторых в связи с возможностью коллизий Приведи такую коллизию для двух реально существующих слов в нашем или английском языке хотя бы для функции adler32.

Автор: Mayk 2.8.2008, 19:13

Цитата(phprus @  2.8.2008,  22:44 ) В случае если нужно получить один результирующий файл в котором будут все уникальные слова, то имеем элементарную задачу. Сливаем все слова в один файл, сортируем его сортировкой слиянием ( О(n*log(n)) ) и за О(н) удаляем дублирующиеся слова. а вообще можно и не руками писать. а юзать готовое  Цитата(Lazin @  29.7.2008,  16:16 ) такой массив данных нужно хранить на в файле или в БД...  Цитата(SABROG @  29.7.2008,  17:00 ) Может есть смысл воспользоваться одной из баз данных ? В них уже реализованы алгоритмы поиска, сравнения, индексации, экономии памяти и т.д. говорят, что современные базы данных умееют импортировать тектсовые файлы.

Автор: phprus 2.8.2008, 21:53

Цитата(W4FhLF @  2.8.2008,  18:55 ) Ну это в теории конечно так красиво. Попробуй отсортировать файл с 10 млн. слов, это займёт никак не меньше времени, чем просчёт и построение хеш-таблиц. Проверял. Файл из 10 млн. строк длинной от 5 до 25 символов ( 152 Мб ) сотритуется на моем ноутбуке утилитой sort за 2 минуты 13 секунд. Хэш-таблица может быть более ресурсоемкой, так как требует дополнительных сравнений строк, что-бы разрешать возможные коллизии. Кроме того если сами сравниваемые строки хранить на диске, то в результате будет много чтений из различных участков файла, а это гораздо медленнее непрерывного чтения в случае сортированных файлов. Цитата(W4FhLF @  2.8.2008,  18:55 ) Приведи такую коллизию для двух реально существующих слов в нашем или английском языке хотя бы для функции adler32.  В английском языке потенциально бесконечное количество слов. 2^32 меньше бесконечности, по этому коллизии будут. Кстати я совсем забыл о существовании утилиты comm, которая умеет вот что: Цитата comm — утилита unix, читает файл1 и файл2, которые должны быть предварительно лексически отсортированы, и генерирует вывод, состоящий из трёх колонок текста: строки, найденные только в файле файл1; строки, найденные только в файле файл2; и строки, общие для обоих файлов. Имя файла «-» означает стандартный ввод. Перед каждой колонкой будет напечатано столько символов табуляции, сколько печатается колонок с меньшими номерами. Например, если вывод второй колонки подавляется, то перед строками, печатаемыми в первой колонке, символов табуляции не будет совсем, а перед строками в третьей колонке будет напечатан один символ табуляции. Утилита comm предполагает, что файлы были предварительно лексически отсортированы; все символы участвуют в сравнении строк. Параметры запуска -1  Подавить вывод первой колонки. -2 Подавить вывод второй колонки. -3 Подавить вывод третьей колонки. -i Нечувствительное к регистру сравнение строк.  Следовательно задача автора темы в случае файлов может решиться вообще без программирования.

Автор: W4FhLF 3.8.2008, 06:51

Цитата(phprus @  2.8.2008,  21:53 ) Проверял. Файл из 10 млн. строк длинной от 5 до 25 символов ( 152 Мб ) сотритуется на моем ноутбуке утилитой sort за 2 минуты 13 секунд. Ну так сложно оценить. Может этот файл уже был близок к отсортированному состоянию? Однако просчёт 10 миллинов хешей на процессоре 3гц займёт ~1 сек.   Цитата(phprus @  2.8.2008,  21:53 ) Хэш-таблица может быть более ресурсоемкой, так как требует дополнительных сравнений строк, что-бы разрешать возможные коллизии. Цитата(phprus @  2.8.2008,  21:53 ) В английском языке потенциально бесконечное количество слов. 2^32 меньше бесконечности, по этому коллизии будут. Да коллизии здесь не аргумент. Число существующих слов не бесконечно. Вероятность сущестсования коллизии не нулевая, но она слишком мала. В крайнем случае можно взять 64 битную хеш-функцию. Тогда на 32х битных системах сравнение будет выполняться за 2 такта в худшем случае, а на 64 битных за 1.  Допустим для подчёта контрольной суммы файлов любых размеров в интернете используется md5. Почему-то ещё никто не наткнулся на коллизию, но её вероятность тоже не нулевая.

Автор: phprus 3.8.2008, 09:17

Цитата(W4FhLF @  3.8.2008,  06:51 ) Ну так сложно оценить. Может этот файл уже был близок к отсортированному состоянию? Маловероятно. Но что-бы нормально оценить нужно взять данные автора и сравнить время работы. Цитата(W4FhLF @  3.8.2008,  06:51 ) Однако просчёт 10 миллинов хешей на процессоре 3гц займёт ~1 сек. smile  Процессора... А сколько памяти займет такая табличка? Она во первых потребует загрузить все слова в память, а ва вторых еще место под саму хэш-таблицу. Кроме того хэш-таблицу в памяти нужно будет каждый раз перестраивать, а вот один раз отсортированные файлы повторной сортировки не требуют. Цитата(W4FhLF @  3.8.2008,  06:51 ) Да коллизии здесь не аргумент. Число существующих слов не бесконечно. Вероятность сущестсования коллизии ненулевая, но она слишком мала. В крайнем случае можно взять 64 битную хеш-функцию. Тогда на 32х битных системах сравнение будет выполняться за 2 такта в худшем случае, а на 64 битных за 1. Возьмем 64 битную хэшфункцию. Она даст нам 2^64 степени комбинаций. Предположим, что у нас такая мегафункция, что она все слова отобразила в разные значения. НО тут возникает проблема, что мы физически не можем создать хэш-таблицу с 2^64 ячеек. По этому придется этот хэш усекать и вот тут уже вероятность появления коллизий значительно возрастает, по этому приходится применять меры по разрешению коллизий и как следствие либо все данные в память, либо большое количество дорогих дисковых операций. Цитата(W4FhLF @  3.8.2008,  06:51 ) Допустим для подчёта контрольной суммы файлов любых размеров в интернете используется md5. Почему-то ещё никто не наткнулся на коллизию, но её вероятность тоже ненулевая. Для md5 можно подобрать второй файл с таким-же хэш-кодом. Кроме того задача контрольных сумм не требует 100% отсутствия коллизий.

Автор: SABROG 3.8.2008, 09:21

Для контрольной суммы пойдет и простой CRC32. Контрольная сумма и хэш разные вещи. Я не думаю что в DirectConnect просто так юзают TTH, а не Adler32.

Автор: W4FhLF 3.8.2008, 10:26

Цитата(phprus @  3.8.2008,  09:17 ) А сколько памяти займет такая табличка? Смотря что в ней хранить помимо самого хеша, если упор на скорость то ещё позицию слова и длину хранить надо. Ну для 10 млн. слов метров 100 отожрёт.  Цитата(phprus @  3.8.2008,  09:17 ) Она во первых потребует загрузить все слова в память Слова в памяти хранить как раз нет никакой необходимости. Можно читать файл порциями по 10-20 мегабайт и строить таблицу.  А для сортировки что меньше памяти надо? Там-то как раз весь файл в памяти иметь нужно.  Цитата(phprus @  3.8.2008,  09:17 )  НО тут возникает проблема, что мы физически не можем создать хэш-таблицу с 2^64 ячеек. Зачем нам такая таблица? Кол-во записей == кол-ву слов.  Цитата(phprus @  3.8.2008,  09:17 ) Для md5 можно подобрать второй файл с таким-же хэш-кодом. Можно? Ну попробуй подобрать или хотя бы в сети найти примеры таких файлов   Нет, я понимаю теория великая вещь. В ней столько всего возможно, но вот практика штука более ограниченная и в ней приходится делать некоторые допущения и это будет всё прекрасно работать и решать поставленную задачу. В данной теме интерес именно прикладной, т.е. теория меня здесь не особо интересует. Добавлено через 12 минут и 54 секунды Цитата(SABROG @  3.8.2008,  09:21 ) Я не думаю что в DirectConnect просто так юзают TTH, а не Adler32. Ты прав. Я собственно adler32 предложил просто как пример очень быстрой функции и с учётом экономии памяти. Это даже не хеш-функция как таковая  Ну все же понимают, что чудес не бывает. Надо исходить из поставленной задачи.  Вот было бы интересно взять какой-нибудь более или менее полный словарь русского/английского и посмотреть будут ли там коллизии. Вопрос где взять такой словарь?

Автор: phprus 3.8.2008, 11:33

Цитата(W4FhLF @  3.8.2008,  10:26 ) Слова в памяти хранить как раз нет никакой необходимости. Можно читать файл порциями по 10-20 мегабайт и строить таблицу.  Это потребуется для разрешения коллизий. Либо все слова держать в памяти, либо в хэш-таблице придется хранить смещения в файлах данных, но это приведет к огромным дисковым тормозам. Цитата(W4FhLF @  3.8.2008,  10:26 ) А для сортировки что меньше памяти надо? Там-то как раз весь файл в памяти иметь нужно.  А про алгоритмы внешней сортировки вы не слышали? Расход оперативной памяти можно сделать очень маленьким. Цитата(W4FhLF @  3.8.2008,  10:26 ) Зачем нам такая таблица? Кол-во записей == кол-ву слов.  Поиск по переполненной хэш-таблице вещь чрезвычайно медленная. Количество ячеек в таблице должно быть как минимум на треть больше чем количество записей в ней и и то при таком количестве пустых ячеек коллизии будут. Кстати а можно поинтересоваться вы вообще хоть какие-либо алгоритмы сортировки знаете? А хэш-таблицы реализовывали? Судя по тому, что вы не знаете основ говорит о том, что все-же нет. Цитата(W4FhLF @  3.8.2008,  10:26 ) Нет, я понимаю теория великая вещь. В ней столько всего возможно, но вот практика штука более ограниченная и в ней приходится делать некоторые допущения и это будет всё прекрасно работать и решать поставленную задачу. В данной теме интерес именно прикладной, т.е. теория меня здесь не особо интересует. Я то как раз и говорю про практику, а вот вы рисуете какую-то идеальную картину при том на столько идеальную, что ее даже в теории быть не может, а не то что на практике. Цитата(W4FhLF @  3.8.2008,  10:26 ) Вот было бы интересно взять какой-нибудь более или менее полный словарь русского/английского и посмотреть будут ли там коллизии. Алгоритм хэширования коллизий может и не дать, НО в хэш-таблице коллизии будут. Если конечно размер таблицы будет адекватный, а не такой, что количество ячеек будет равно количеству возможных значений хэш-кодов.

Автор: W4FhLF 3.8.2008, 13:11

phprus, в общем видимо я где-то протормозил, но под хеш-таблицей я не имел ввиду структуру данных "hash table". Всё что я говорил про время и память касалось только лишь расчёта хешей для слов, а не их отображения в какую-либо структуру. И когда ты говорил коллизия я это понимал как hash(s1) == hash(s2). Теперь всё ясно. Цитата(phprus @  3.8.2008,  11:33 ) Либо все слова держать в памяти, либо в хэш-таблице придется хранить смещения в файлах данных, но это приведет к огромным дисковым тормозам. Да какие дисковые тормоза? В качестве value харнить позиции слов в файле. Файл читать целиком придётся в любом случае(кусками или ещё как-нибудь). А про запись автор ничего не говорил. Он сказал, что надо проанализировать на предмет наличия дубликатов. Цитата(phprus @  3.8.2008,  11:33 ) А про алгоритмы внешней сортировки вы не слышали? А это не дисковые тормоза?

Автор: phprus 3.8.2008, 14:50

Цитата(W4FhLF @  3.8.2008,  13:11 ) Да какие дисковые тормоза? В качестве value харнить позиции слов в файле.  Вот здесь и всплывут тормоза. Даже для фрагментированного файла последовательное чтение будет быстрее, чем чтение маленьких кусочков из разных участков файла. (Тут так-же не надо забывать про то, что ОС кеширует данные с диска в оперативке, и этот кэш будет эффективнее при последовательном чтении, чем при постоянных перескоках в разные концы файла). В случае сортировки количество чтений из произвольных участков файла будет минимальным, а в случае работы с отсортированными последовательностями будет вообще только последовательное чтение.

Автор: W4FhLF 3.8.2008, 15:11

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

Автор: phprus 3.8.2008, 16:24

Цитата(W4FhLF @  3.8.2008,  15:11 ) Я не понимаю зачем нам читать из разных концов файла? Вспомни как происходит поиск в хэш-таблице. Вначале по хэшу ищется нужная запись, а потом для того что-бы гарантировать, что это не коллизия сравниваются сами значения. То значение, которое мы ищем у нас в памяти, а вот то значение которое в хэш-таблице у нас на диске и что-бы его получить нужно считать данные с диска. При поиске следующего слова оно у нас будет в памяти, а вот ссылка из хэш-таблицы снова будет вести на диск и при том в совершенно случайную область файла исходных данных.

Автор: W4FhLF 3.8.2008, 16:43

phprus, всё понял, я действительно гоню  Спасибо, что проявил терпение. Добавлено через 6 минут и 44 секунды А что если в качестве значения использовать pair<hash, position>? Hash в любом случае вычисляется один раз, позиция известна при первом проходе. Тогда для разрешения коллизий не придётся читать с диска.

Автор: phprus 3.8.2008, 19:09

Цитата(W4FhLF @  3.8.2008,  16:43 ) А что если в качестве значения использовать pair<hash, position>? Hash в любом случае вычисляется один раз, позиция известна при первом проходе. Тогда для разрешения коллизий не придётся читать с диска.  Не получится. На входе функции поиска у нас строка, а в хэш-таблице смещение в файле. И эти 2 сущности надо как-то сравнивать. Как следствие надо читать строку из файла.

Автор: Mayk 4.8.2008, 07:34

Вопрос,задаваемый (n+1)-ый раз: А кто нибудь может доступным языком объяснить почему БД нельзя использовать?

Автор: Lazin 4.8.2008, 09:14

Цитата(Mayk @  4.8.2008,  07:34 ) А кто нибудь может доступным языком объяснить почему БД нельзя использовать? топикстартер желает написать свою БД, имхо.

Автор: andrew_121 4.8.2008, 09:33

Цитата(Lazin @  1.8.2008,  12:17 ) блин, так и не понял, нафига тебе хранить кучу строк в памяти?  Уже не надо в памяти хранить. Это так для развития, понимания...

Автор: W4FhLF 6.8.2008, 15:46

В общем выдался свободный часок и я таки реализовал то, что предлагал. Т.е. считать хеши и позиции слов. Потом сортировка этого вектора и вывод дубликатов.  Перестраховался и в качестве хеша вычисляется md5 и берутся его 1 и 4 блоки. Хеш хранится в __int64. Для вычисления хеша подключил свою когда-то написанную на ассемблере оптимизированную либу для вычисления md5. Поэтому процедура string_hash слегка уродлива  Для сортировки массива используется алгоритм HeapSort.  В конце программы в консоль выводятся слова, которые имеют дубликаты в словаре.  Словари для тестов брал отсюда: http://www.insidepro.com/eng/download.shtml На моём процессоре AMD 2.2 гц на построение таблицы и её сортировку для словаря 2.5 млн. слов уходит ~5 секунд. Меня такой результат вполне удовлетворил так, что решил оставить реализацию как есть. Проект для VS 2008 в аттаче.  Код // words_unify.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <vector> #include <iostream> #include <fstream> #include <string> #include <cstdlib> #pragma comment (lib, "md5.lib")  extern "C" {      void _stdcall procMD5hash(char* in_buffer,          unsigned int size,          void* out_buffer);  }  unsigned __int64 string_hash(const char* str, unsigned len) {     unsigned int md5[4];     char tmp_str[256] = {0};     strcpy((char*)&tmp_str, str);     procMD5hash((char*)&tmp_str, len, &md5);     md5[1] = md5[3];     return *((unsigned __int64*)(&md5[0])); } typedef std::pair<unsigned __int64, unsigned> PairItem; typedef std::vector< PairItem > HashTable; void compute_hash_array(const std::string& filepath, HashTable& hash_table ) {     #define CRLF_LEN 2        // для файлов, где перенос строки == \r\n     std::ifstream ifs(filepath.c_str());     if(ifs.fail())         throw std::ios::failure("File not found.");     std::string word;     unsigned current_pos = 0;     while(!ifs.eof())     {         ifs >> word;         hash_table.push_back(std::make_pair(string_hash(word.c_str(), word.length()), current_pos));         current_pos += word.length() + CRLF_LEN;         word.clear();     } } void print_duplicates(const std::string& filepath, const HashTable& hash_table) {     std::ifstream ifs(filepath.c_str());     if(ifs.fail())         throw std::ios::failure("Cannot open the file.");     size_t size = hash_table.size();     std::string word;     for(size_t i = 0; i < (size - 1); ++i)     {         if(hash_table[i].first == hash_table[i+1].first)         {             ifs.seekg(hash_table[i].second);             ifs >> word;             std::cout << word << std::endl;             while(hash_table[i].first == hash_table[i+1].first)                 ++i;         }     } } void downHeap(HashTable& a, long k, long n)  {     PairItem new_elem = a[k];     long child;     while(k <= n/2)      {         child = 2*k;                  if( child < n && (a[child].first < a[child+1].first) )             child++;         if( new_elem.first >= a[child].first )              break;          a[k] = a[child];         k = child;     }     a[k] = new_elem; } void heapSort(HashTable& a) {     long i, size = a.size();     PairItem temp;     for(i = size / 2 - 1; i >= 0; --i)          downHeap(a, i, size - 1);     for(i = size - 1; i > 0; --i)      {         temp = a[i];          a[i] = a[0];          a[0] = temp;         downHeap(a, 0, i - 1);      } } int main(int argc, char* argv[]) {     HashTable hash_table;     std::string s = "E:\\dictionary_huge_c.txt";          try      {         compute_hash_array(s, hash_table);          heapSort(hash_table);         print_duplicates(s, hash_table);     } catch(...) {}     return 0; }

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)