Посмотрел эту статью, сделал для себя вывод: чтобы использовать хэш для сортировки, и при этом исключить коллизии, хэш-функция должна быть достаточно сложной, и потребует определенных затрат времени. Неизвестно, окупятся ли эти затраты. А для разового поиска в массиве определенной строки (если поиск осуществляется регулярно и достаточно часто) вполне годится. Даже при наличии коллизий, т.к. просмотр будет всего лишь раз от начала к концу массива.
хэш-функция должна быть достаточно сложной Таких функций масса. Возми уже хоть CRC32 - уже вероятность коллизии достаточно мала. Возьми MD2/MD4 - она вообще смехотворна.
Не стоит путать задачу поиска строки и задачу сортировки строк по возрастанию или убыванию ("аб" < "ба"). По моим наивным представлениям хэш используется в основном для поиска строк в таблице. В этом случае сортировку мы имеем по значениям хэш-функции, а не по содержимому строк . Такой подход дает больше возможностей в выборе хэш-функции, т.к. не нужно обеспечивать отображение порядка: h1 < h2 если S1 < S2. Есть ли "хорошие" хэш-функции строк с сохранением порядка (кроме тривиальных) мне не известно. А посему выскажу несколько замечаний не в пользу хэширования. 1. Не стоит мешать в одну кучу первичную сортировку, вторичную сортировку и добавление новой строки в уже отсортированный список. Если список один раз отсортирован, то можно к каждой строке прицепить ярлык - целочисленный индекс = ее порядку в отсортированном списке и вторичную сортировку производить по этому индексу (тоже своего рода хэш . При вставке новой строки в отсортированный список число необходимых сравнений гораздо меньше чем при первичной сортировке, особенно при использовании известных методов быстрого поиска. Если используются индексы для вторичной сортировки, то для вставки строк можно предусмотреть резервирование младших разрядов индекса для новых вставленных строк (чтобы при вставке перенумеровывать не все индексы списка, а часть). Короче говоря, произведя один раз первичную сортировку с обычным сравнением строк, поддерживать затем сортированное состояние при вставке новых строк гораздо проще. 2. Почему по жизни для сортировки строк рулит qsort с обычным сравнением строк без всяких хэшей ? Потому что по жизни сортируются "нормальные" человеческие строки, которые с большой вероятностью различаются в первых 4-8 символах. Кстати и пример с "mama","papa","rama" тоже показателен - на фига тут какой-то хэш ? Трудно представить себе задачу в которой встретятся две строки длиной в 1Кб различающиеся в последних символах. Это конечно не означает, что можно использовать какую попало функцию сравнения строк. Например, известно, что апишная CompareString довольно тормозная и лучше использовать другие оптимизированные варианты сравнения. Однако естественное желание перейти от посимвольного сравнения к "продвинутому" всегда упирается в вопрос: а не проиграем ли мы в целом, если будем оптимизировать сравнения например 4 байтов, когда бОльшая часть строк различается в первых двух. Например, даже учет длины паскалевских строк требует определенного времени и не дает практического выигрыша. Другой пример: если длина строк выравнена на 4 с заполнением нулями, то можно сравнивать строки с учетом регистра по 4 байта с использованием BSWAP. Если на PII,PIII это еще может пройти, то на P4 эта инструкция довольно тормозная и игра уже может не стоить свечь. 3. Если "часто" встречаются совпадающие строки или строки, различающиеся в последних символах (например, фамилии мужского и женского рода или фамилии с инициалами), то не плохо бы учесть статистику совпадений. Например есть список из N фамилий из которых каждая встречается 2 раза. Для сортировки нужно произвести N(N-1)/2 сравнений, из которых только N/2 будут совпадать, т.е. относительная доля полных совпадений = 1/(N-1), при N > 100 доля совпадений будет меньше 1%. Стоит тут что-то оптимизировать, если остальные строки различаются в первых символах ? Другой случай - это большой процент повторений (например, название города в адресных данных, должность сотрудника и т.п.). В реляционных БД этот вопрос решается путем выделения повторяющихся данных в отдельные справочные таблицы. Если очень хочется сотворить собственный вариант хранения данных в текстовом виде, то можно использовать тот же принцип - выделять часто повторяющиеся данные в отдельный столбец или таблицу и для дубликатов хранить только один вариант строки и обращаться к нему по ссылке. Нечто подобное мне приходилось "изобретать" на дельфях - благо там строки динамические и оператор S1:=S2 просто присваивает S1 указатель на ту же строку, что и S2, просто увеличивая счетчик ссылок. Тогда при сравнениях строк можно действительно сравнивать равенство указателей (насколько это эффективно, сказать не могу, нет статистики - просто так казалось логичнее, как многим кажется логичным использовать хэш, хотя толку от него может и не быть). {Кстати прозвучавшие "откровения" с сортировкой (перестановкой) массива указателей на строки вместо самих строк переменной длины меня несколько удивили - для дельфей это дело очевидное и обыденное (см. реализацию TStringList).} 4. Часто увлекаются оптимизацией ради оптимизации, хотя во многих случаях просто достаточно обеспечить разумное время выполнения задачи. Например, в интерактивном режиме с выводом результата сортировки на экран нет никакой разницы отсортируем мы список за 20 мс или за 20 мкс.
leo > Хи-хи, если сначала сравнивать длину, а только потом сам текст, то может ты и прав (поскольку тут 2 операции А нужно сравнивать эти строки простым посимвольным сравнением, начиная с 0-го (длины) - при разной длине сразу же будет выход из цикла
2 leo К кому направлено ваше пламенное обращение, я не очень понял , но подозреваю, что ко мне... (нумерация моя, и к вашей никак не привязана! :о)) 1. Я не за коммунистов и не за интернационал! Просто в сложившихся условиях мне проще реализовать эту муть через хэш (нужно влезать в существующий лихозакрученный приклад), потому и возник вопрос. Обратите внимание, там не спрашивается "как сортировать большие массивы данных", там спрашивается "имеет ли смысл преобразовывать строку в хэш". 2. Если убрать эмоции, то ваш пост сводится к тому, что вы считаете нецелесообразным использовать хэш и предлагаете оптимизировать за счет "знания" структуры строки (записи) и статистики. Так? Принимается, но "не в этой жизни" - структура записи неизвестна, распределение по частоте элементов тоже неопределено, только диапазон от 0x00 до 0xFF. 3. По поводу БД... Немного не из той оперы, это во-первых, а во-вторых, уверен, что все присутствующие здесь знакомы с трудами г. Кодда (либо с их интертрепацией :о)) 4. Мне бы не хотелось ограничивать задачу знанием особенностей процессора, языка реализации и т.д. Лучше в более общем виде. 5. Я тоже против "оптимизации ради оптимизации". Но если это не интерактив, а фон? А количество записей не сотни, а миллионы (при мне было 18млн, а ожидаемое макс. кол-во ~28млн, при 1К длины)? Есть резон пооптимизировать? Надеюсь, не задел, ОК?
leo Перестановка указателей не является моим "откровением" или изобретением. Ты знаешь это, я знаю, а вот человек не знал. Почему бы не сказать ему об этом? Да и проще понять один единственный пост, чем установить борланда и ковыряться в его исходниках. const Если тебе нужна именно сортировка, то хэши тебе никак не помогут.
Нет, нет, нет... leo прав... Это меня унесло и развезло... Простите, пожалуйста... Кстати и пример с "mama","papa","rama" тоже показателен - на фига тут какой-то хэш ? Пардон, leo - мы обговаривали сортировку поинтеров - я его не совсем понял. А потом вообще ушел в сторону - башка чумовая - поэтому еще раз прошу прощения.
2 cresta Ну, что это не знал! "Чай, не из дяревни!" :о) Просто сама процедура сортировки (довольно навороченная, не мною написанная (причем едва ли она перелопачивает млны записей, наверняка указатели) - вопчем лезть туда нет никакого желания!) уже существует и давно активно используется. Моя цель - уменьшить время обработки данных. Дольше всего идут сортровки (их там несколько). В принципе, задачу решил (правда мне не очень нравится каким образом), заказчик доволен. Просто счас интерено, было ли более более элегантное решение. Перебираем многие варианты, хэш - один из них. Почему не помогут? Идея-то благая - уменьшить объем инфы. Ведь при прочих одинаковых условиях 2Г отсортируются всегда медленее 2К (это я для примера)
2 all Похоже, хэширование не проходит? (после слов Volodya) Жаль... Но я попробую в праздники еще поковырять. Мне все же кажется, что что-то в этом есть. Большое спасибо за участие.
При хешировании ты не можешь утверждать, что хеш произвольно выбранной строки обязательно будет численно меньше или больше хеша какой-либо другой строки.
2 volodya Я так и предполагал, потому и задал вопрос про сортировку и хэш, т.е. возможен ли хэш, пригодный для сортировки. Совершенно не считаю это обсуждение - потерей времени. Спасибо за приведенные ссылки, они мне уже помогли. :о) Не в тему... Получается ли пару раз в неделю по мешку постучать, или все больше в мечтах?
S_T_A_S_ > "Хи-хи, ... начиная с 0-го (длины) - при разной длине сразу же будет выход из цикла" Ха-ха-ха, выход с каким результатом ? Речь идет не о поиске строки (равно\не равно), а о сравнении строк (меньше, равно, больше) и длина тут вообще ни причем. В нашем случае: "Ха-ха-ха" < "Хи-хи", хотя ее длина больше. А вот слова, начинающиеся на "Ху", будут больше "Хи-хи" при любой длине Я же имел ввиду вот что: можно ли зная длину ускорить сравнение достаточно длинных строк, совпадающих или различающихся в "последних" символах, например, за счет перехода к сравнению по 4 байта (с BSWAP или еще как). Если сразу браться за анализ длины, то потеряем на строках, различающихся в первых символах, поэтому нужен какой-то компромисс. В итоге все опять же зависит от статистики и получается довольно сомнительно, поэтому я эту идею в свое время и забросил. const > "Если убрать эмоции, то ваш пост сводится к тому, что ..." Если убрать эмоции, то мой пост сводится просто к "мыслям вслух". Что касается стиля изложения, то как показывает опыт - так лучше доходит до тех, кто "спит или болтает на лекции" (как видим и на этот раз сработало А по сути, я сразу сказал, что просто не знаю ничего о хэшах сохраняющих отношение порядка строк. Если чего разузнаешь или придумаешь - поделись мыслями.
Может я чего не понял, но вроде как надо поиметь массив строк просто сказочного объема и при этом не тратить на поиск строки годы? Есть такая вещь, как хеш-таблица. Она используется для хранения словарей данных. Общая идея следующая: Есть хеш-функция, которая обеспечивает низкую вероятность коллизий (хотя, подойдет любая, но об этом ниже). Прикидываем максимальный размер массива и создаем массив указателей на наши данные нужного размера. Как известно, хеш-функция рожает некое число. Это число будет индексом данных в нашем массиве. Т.е., если отс строки "фыва" функция даст число 3, то mas[3] = "фыва". Таким образом, для поиска данных нужно всего лишь взять хеш от искомых данных и все. Недостатки: необходимо резервировать огромный объем памяти и при маленьком коэффициенте заполнения поимеем просто неприличный расход памяти впустую. Преимущества: стандартные операции (вставка, удаление и поиск) имеют трудоемкость О(1). Если функция допускает коллизии, то используются модификации таблиц, например хеш-таблица с цепочками коллизий или хеш-таблица с открытой адресацией. Если интересно, могу рассказать. Такая структура данных идеальна для всякого рода словарей, баз данных и т.д.. В общем, если интересно - могу рассказать более детально.
cresta А, то есть боевая задача была именно отсортировать? Но ведь сортируют обычно с какой-то определенной целью, вот я и подумал, что этой целью является быстрый поиск..
