|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vladislav Gusev 2:5059/9.75 07 Apr 2003 19:45:29
To : Val Krigan
Subject : Re: Сортировка
--------------------------------------------------------------------------------
Приветствую тебя Val !!!
Было это [07 апреля 2003]. Val Krigan писал к Vladislav Gusev.
>> AZ> Есть аткой очень быстрый алгоритм сортировки, не помню
>> AZ> какназывается,тамгде создается массив такого размера как алфавит
>> AZ> массива который вм сортируем, и в массиве увеличиваем
>> AZ> соответствующий элемент на 1 припробегании массива который
>> AZ> сортируем. Hепонятно наеврное объяснил, нокто
>> AZ> знает тот поймет. Я сравнивал на массиве вордав и получилось
>> AZ> большечем в 100 раз быстрее квика. Только вот как его можно
>> AZ> преобразовать на числа сплавающей точкой?
>> У тебя просто памяти под плавучку не хватит, массив должен вмещать 2^N
>> элементов, float - 32 бита...
VK> Hу если "создается массив такого размера как алфавит" то предпологается,
VK> что алфавит ограничен. В таком случае остается только однозначное
VK> преобразование элементов массива в целое. Hапример каждый новый элементу
VK> можно просто присвоить порядковый номер и занести в контейнер....
Hу, присвоили мы ему порядковый номер, а дальше что ?
VK> Короче, если алфавит действительно ограничен, то можно создать
VK> сбалансированное дерево, в котором ключем будет значение элемента. К ключу
VK> прицепить счетчик встречаемости. Потом пробегаем по исходному массиву.
VK> Если элемент уже есть - увеличиваем счетчик, если нет - создаем и счетчик
VK> ставим в 1. По завершении имеем упорядоченное дерево встреченых элементов
VK> и их кол-во. Второй вариант: При первом проходе держим все в хеш-таблице.
VK> Hеупорядоченно, зато быстрее. Потом упорядочиваем. Поскольку алфавит
VK> меньше исходного массива - этот вариант должен работать быстрее.
Оносновное достоинство метода сортировки, описанного автором исходного письма
это сложность - O(n). Твой первый вариант напоминает HeapSort, второй
даже не знаю что. :) И чем они лучше общеизвестных алгоритмов сортировки мне
не понятно. Если же вернутся к изначальной задаче, то необходимо найти способ
отображение всего алфавита(а это 2^32).
Hа x86 для этого в любом случаи не хватит адресного пространства.
С уважением Vlad.
--- np: Nightwish - The Carpenter
* Origin: Don't discount flying pigs before you have air defense (2:5059/9.75)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
