Если размер строки <константы то его не статичность идёт побоку. Ссылка  на Short String Optimisation уже была.


Это сообщение отредактировал(а) Mayk - 1.8.2008, 05:36

Глупость   А если длина строки меньше 12, то что, где рассудок?    

ты учти что менеджер памяти выделяет память под маленькие объекты блоками фиксированного размера, кратными степеням двойки, под строку размером 12 байт может быть выделено 16 байт, а может и 32... плюс обращение к строке в куче дороже чем обращение к строке в стеке, плюс создание и освобождение строки в куче не дешевая операция, в отличии от создания объекта в стеке...

блин, так и не понял, нафига тебе хранить кучу строк в памяти?

Стандарт это не регламентирует в отличие от непрерывной памяти для vector. И  c_str и data  как раз могут не отражать как на самом деле хранится строка. 

Согласен. Но, с точки зрения реализации - зачем нам неконстантная сложность для c_str и data?

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

Задача не очень понятна.
Исходные данные:
1) много файлов содержащих слова
2) новый файл со словами

Возникают вопросы:
Что нужно получить в результате?

В случае если нужно получить один результирующий файл в котором будут все уникальные слова, то имеем элементарную задачу. Сливаем все слова в один файл, сортируем его сортировкой слиянием ( О(n*log(n)) ) и за О(н) удаляем дублирующиеся слова.
Это наиболее быстрое из всех возможных решений, кроме того оно не требовательно к оперативной памяти. В некоторых случаях для решения этой задачи достаточно стандартной *nix'овой утилиты sort аналоги которой есть и под винду.

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

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

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

Ну это в теории конечно так красиво. Попробуй отсортировать файл с 10 млн. слов, это займёт никак не меньше времени, чем просчёт и построение хеш-таблиц.



Приведи такую коллизию для двух реально существующих слов в нашем или английском языке хотя бы для функции adler32. 


Это сообщение отредактировал(а) W4FhLF - 2.8.2008, 18:59

а вообще можно и не руками писать. а юзать готовое 




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



Это сообщение отредактировал(а) Mayk - 2.8.2008, 19:15

Проверял. Файл из 10 млн. строк длинной от 5 до 25 символов ( 152 Мб ) сотритуется на моем ноутбуке утилитой sort за 2 минуты 13 секунд.

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



В английском языке потенциально бесконечное количество слов. 2^32 меньше бесконечности, по этому коллизии будут.

Кстати я совсем забыл о существовании утилиты comm, которая умеет вот что:

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

Ну так сложно оценить. Может этот файл уже был близок к отсортированному состоянию?

Однако просчёт 10 миллинов хешей на процессоре 3гц займёт ~1 сек.  





Да коллизии здесь не аргумент. Число существующих слов не бесконечно. Вероятность сущестсования коллизии не нулевая, но она слишком мала. В крайнем случае можно взять 64 битную хеш-функцию. Тогда на 32х битных системах сравнение будет выполняться за 2 такта в худшем случае, а на 64 битных за 1. 
Допустим для подчёта контрольной суммы файлов любых размеров в интернете используется md5. Почему-то ещё никто не наткнулся на коллизию, но её вероятность тоже не нулевая.


Это сообщение отредактировал(а) W4FhLF - 3.8.2008, 10:33

Маловероятно. Но что-бы нормально оценить нужно взять данные автора и сравнить время работы.


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



Возьмем 64 битную хэшфункцию. Она даст нам 2^64 степени комбинаций. Предположим, что у нас такая мегафункция, что она все слова отобразила в разные значения. НО тут возникает проблема, что мы физически не можем создать хэш-таблицу с 2^64 ячеек. По этому придется этот хэш усекать и вот тут уже вероятность появления коллизий значительно возрастает, по этому приходится применять меры по разрешению коллизий и как следствие либо все данные в память, либо большое количество дорогих дисковых операций.



Для md5 можно подобрать второй файл с таким-же хэш-кодом. Кроме того задача контрольных сумм не требует 100% отсутствия коллизий.

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

Смотря что в ней хранить помимо самого хеша, если упор на скорость то ещё позицию слова и длину хранить надо. Ну для 10 млн. слов метров 100 отожрёт. 




Слова в памяти хранить как раз нет никакой необходимости. Можно читать файл порциями по 10-20 мегабайт и строить таблицу. 

А для сортировки что меньше памяти надо? Там-то как раз весь файл в памяти иметь нужно. 



Зачем нам такая таблица? Кол-во записей == кол-ву слов. 



Можно? Ну попробуй подобрать или хотя бы в сети найти примеры таких файлов  

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

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


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

Вот было бы интересно взять какой-нибудь более или менее полный словарь русского/английского и посмотреть будут ли там коллизии. Вопрос где взять такой словарь?

Это сообщение отредактировал(а) W4FhLF - 3.8.2008, 10:33

Это потребуется для разрешения коллизий. Либо все слова держать в памяти, либо в хэш-таблице придется хранить смещения в файлах данных, но это приведет к огромным дисковым тормозам.


А про алгоритмы внешней сортировки вы не слышали? Расход оперативной памяти можно сделать очень маленьким.


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

Кстати а можно поинтересоваться вы вообще хоть какие-либо алгоритмы сортировки знаете? А хэш-таблицы реализовывали? Судя по тому, что вы не знаете основ говорит о том, что все-же нет.


Я то как раз и говорю про практику, а вот вы рисуете какую-то идеальную картину при том на столько идеальную, что ее даже в теории быть не может, а не то что на практике.


Алгоритм хэширования коллизий может и не дать, НО в хэш-таблице коллизии будут. Если конечно размер таблицы будет адекватный, а не такой, что количество ячеек будет равно количеству возможных значений хэш-кодов.