Есть набор строк (количество строк не определено), длина строки ~1K, элементы строки могут принимать значение от 00 до FF. Вопрос, имеет ли смысл преобразовывать строку в хэш и сотрировать набор хэш-строк? И вообще, существуют ли алгоритмы хэширования, результат которых пригоден для сортировки? Или лучше не заморачиваться? <тема для меня новая, советы и ссылки приветствуются!>
Не имеет. На вычисление хэша потратишь дополнительное время, а потом все равно будешь сортировать (хэши). Более того, для совпадающих хэшей придется сортировать именно строки. Конечно существуют. Например, хэш-функция, возвращающая первый символ строки. Короче говоря, алфавит
IMHO для ускорения сортировки лучше 1м символом строки хранить длину строки / 4 (а может лучше длина_строки & 0xFF, зависит от самих строк). Это если ascii. Если символы 2х байтные, то просто длину строки. Тоже хеш, вроде алфавита
Хеши вроде бы и придумали для того, чтобы длинные ключи превращать в короткие... Хотя если строки сильно отличаются друг от друга первыми символами можно и просто сравнивать.
Чем тратить время на хэши, лучше составить таблицу указателей на строки и сортировать указатели, а не сами строки.
Положим, у тебя есть три строки. "mama" "papa" "rama" теперь покажи мне, как ты будешь сортировать указатели.
volodya Мне кажется у тебя недавно была такая же задача Просто Массив указателей [1] -> b [2] -> a [3] -> c после сортировки [2] [1] [3] например Я верно написал?
const Вычислять кешь для такой строки - занятие скорее всего неблагодарное. Хотя наверно комбинированный вариант (вычисление хеша для части строки) возможно рулит. Мне кажется тут нужно что-то типа индексной сортировки. То есть берётся буква с строке, и она сразу "относится" с некоторым местом. И так по первой букве других строк. Но этот вариант по обращениям к памяти - проиграет - поэтому лучше придумать хитроумный хеш, который сделает подобную работу. То есть, о чём я говорю Есть N связанных списков, сгрупированные в массив по 256 элементов. то есть МАССИВ: Код (Text): [1] -> [указатель элемент] -> [2] [3] Мы берём букву, и помещаем указатель на строку в список, который относится к индексу массива, то есть если буква равна 1, то помещаем указатель в 1 элемент массива, вот так например Код (Text): [1] -> [указатель на строку, которая начинается с 1] -> [2] [3] Потом тоже самое производится для второго символа всех строк, и так далее Прикол в том, что массив - всегда 1 %) Конечно описанный алгоритм - негодится, но сама идея может использоваться и развиваться. Дерзайте.
volodya Допустим есть .data s1 db "mama",0 s2 db "papa",0 s3 db "rama",0 1. Получаем кол-во строк (допустим 3) 2. Выделяем (получаем) кусок памяти под таблицу размером 3 дворда 3. В первые 4 байта по адресу таблицы записываем eax от lea eax,str1 (начало первой строки) 4. Следующие 4 байта - начало второй строки 5. Последние 4 байта - адрес последней строки Есть три дворда, они выстроены по возрастанию адресов строк. Т.е. Указатель_1...Указатель_3. Сами строки в беспорядке. 6. Теперь берем любой алгоритм сортировки и переставляем указатели по такому принципу: 7. mov esi, Указатель_1 (например, offset Table) mov edi, Указатель_2 (например, offset Table+4) lstrcmpi, esi,edi если eax > 0 то меняем в таблице первый и второй дворд местами. Строки 1 и 2 уже упорядочены между собой. При этом пересылается только два дворда. Сами строки где были в памяти, там и остались 8. Продолжаем выбранный алгоритм, сравнивая строки, находящиеся по адресам, которые забиты в таблице, и продолжаем (при необходимости) менять местами эти адреса в таблице Для коротких строк, которые ты привел, сортировать указатели не имеет смысла. Смысл появляется для строк достаточно большой длины, например, как у автора 1кб. Т.к. переставлять две строки по 1 кб значительно дольше, чем переставить два дворда. После сортировки сам набор строк остался в неизменном виде, его никто не тасовал. А таблица приведена в состояние, при котором строка_по_offset+0 < строка_по_offset+4 < строка_по_offset+8..... и т.д. Теперь надо единственный раз пройти через набор строк, выбирая их по адресам от offset+0 до offset+8 и складывая в новую кучу, которая будет уже набором сортированных строк. Повторяюсь, на массиве из трех трехбуквенных строк этот метод лишён смысла. Он помогает при больших массивах и длинных строках
Я понял тебя. Меня смутила первоначальная постановка вопроса и некорректно сформулированная фраза. Надо было говорить "сортировка поинтеров согласно значениям строк" или как-нибудь еще. Идея ничего. А вообще - мне больше всего нравится хеш-таблица. Так что идея с хеш-функцией без коллизий смотрится вполне неплохо. Просто const не сказал важной вещи - что будет происходить чаще - вставка или выборка. Есть и еще один интересный вариант, предложенный captain cobalt - ищите по форуму - где-то недалеко было...
2 all прошу пардону, что не принял участия в обсуждении (Инет обрубили). Спасибо за советы... 2 volodya 1. А вообще - мне больше всего нравится хеш-таблица. Так что идея с хеш-функцией без коллизий смотрится вполне неплохо на данный момент мне тоже ближе хэширование (по крайней мере пока от такого подхода не отказался). Но из-за отсутствия подобающего опыта (и, если уж совсем честно - знаний) не могу подобрать "подходящую" функцию (без коллизий). С наскоку "закидать шапками" не получилось => надо врубать поосновательней. Гугл дает _огромное_ количество ссылок откровенно дилетантского содержания. Потому и решил поспрошать в форуме. 2. Просто const не сказал важной вещи - что будет происходить чаще - вставка или выборка Выборка чаще... Есть желание разнести хэширование и сортировку по времени, т.е. получать хэш на втавке, и использовать уже готовый хэш при сортировке. Но пока это не принципиально... 3. Есть и еще один интересный вариант, предложенный captain cobalt - ищите по форуму - где-то недалеко было... Перед созданием темы попробовал поискать по форуму, но, видать, руки кривоваты... Попробовал и счас поискать - тоже что-то не нашел. >:о( 2 cresta Я правильно понял - предлагается перемещать не сами строки, как это делается в обычной сортировке, а указатели на строки, предварительно сравнивая эти строки? Интересный подход, но настораживает следующее. Сравнить 2 строки - несложно, переместить указатели - тоже понятно. Но ведь нужно еще и сравнить полученный результат с результатами предыдущих итераций. Т.е. мало знать, что строка_1000 > строка_1001, нужно еще (чтобы корректно разместить указатель) знать, что строка_1000 больше строк 5,15,98,586, но меньше строка_503. не будет ли потери эффективности из-за таких сравнений? Или такой подход уже вами используется, и я зря опасаюсь?
const Совершенно верно. И опасения совершенно напрасны То что я привел, всего лишь сравнение двух строк. Фрагмент из общего процесса. Но ведь сортировка не ограничивается перестановкой двух строк. Как в любом алгоритме сортировки, ты будешь продолжать сравнения (и перестановки при необходимости) всей кучи строк, пока строки (или указатели) не будут упорядочены. Я привел только как упорядочить две строки между собой. Чтобы был понятен принцип работы. Количество сравнений\перестановок одинаково, с указателями или без. Упрощается(ускоряется) перестановки, т.к. два дворда переставить значительно быстрее, чем две строки. P.S. Это не есть алгоритм сортировки. Алгоритм может быть любым, его выбирай исходя из своих условий. Я применял такой принцип (сортировка указателей) на практике, ничего страшного нет в этом.
не могу подобрать "подходящую" функцию (без коллизий) дык, есть специальные функции, называемые криптографическими, вот они без коллизий работают. только очень медленно. а целый ряд обычных, вполне нормальных хаш-функций я приводил тут: http://www.wasm.ru/forum/index.php?action=vthread&forum=17&topic=5348
volodya Порылся в msdn, но не нашёл ответ на такой вопрос: если строка1 меньше чем строка2, то всегда ли хэш от строки1 будет также меньше хэша от строки2? И ещё: о длине хэш-данных нашёл только это: HASH - это длинная строка из набора символов '0123456789ABCDEF'. Всего таких символов в HASH'е - ровно 32 штуки. Значит получается сравнивать придется все равно строки. длиной 32 байта?
стоп-стоп-стоп... не путай грешное с праведным. еще раз если строка1 меньше чем строка2, то всегда ли хэш от строки1 будет также меньше хэша от строки2? 1. "строка1 меньше чем строка2" - видимо, надо понимать фразу как "длина строки1 меньше, чем длина строки2" 2. "хэш от строки1 будет также меньше хэша от строки2" - хеш - это число и сравниваем мы два числа. И вопрос бессмысленнен без хеш-функции - каждая хеш-функция вычисляет хеш по-разному и вовсе не факт, что хеш меньшей по длине строки будет численно меньше. Он может быть и больше!
Ну а если нет такой однозначной зависимости, то как можно сортировать по хэш-строкам? Если отсортированы хэш-строки, то исходные строки могут ведь оказаться (и исходя из сказанного тобой, наверняка окажутся) несортированными. Или я че-то недопонял Получается как сказал RobinFood в первом ответе, что вычислять хэши, чтобы сортировать строки - бессмысленно? Вот две строки, сортированые по возрастанию: "аааббб" "ааабббввв" Всегда ли хэш первой строки будет меньше хэша второй строки? Если нет, какой смысл применения хэша для сортировки строк? По-моему смысла нет. Или вот такие строки: "абвгде" "абвгдя" Опять же, будет ли хэш1 всегда меньше хэша2
Если нет, какой смысл применения хэша для сортировки строк? По-моему смысла нет. Нет, если использовать напрямую - в лоб, как думаешь ты. Хеш можно использовать как вспомогательную величину, т.к. удобнее сравнивать два int, чем два char *. А вообще, я изначально думал о http://rsdn.ru/article/alg/bintree/hash.xml
