| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Оптимальная сортировка [D6]
Mr.F © (2005-06-06 16:28:00)Есть такая задача: дан массив, в нем куча элементов в массиве... (> 10^9)
Надо их отсортировать. Элементы не повторяются. Одна операция сравнения = далеко не один цикл процессора, поскольку элементами массива являются указатели на строки с нулевым символом в конце.
Нужен реальный алгоритм (код), который сведет к минимуму операции сравнения элементов.
Digitman (2005-06-06 17:10:00) [1]
> какие все-таки алгоритмы уважают себя?
те самые, которые с учетом выбранной codepage и collation order спавнивают строки посимвольно
Digitman (2005-06-06 17:08:00) [2]
> Mr.F © (06.06.05 16:40) [8]
> ведь проверка в алгоритмах не на равенство, а < или >...
если 1-я строка короче 2-й, то в зависимости от КОНКРЕТНЫХ выбранных критериев "равенства" можно сразу утверждать, что 1-я > 2-й, или 2-я > 1-й
Хинт (2005-06-06 16:42:00) [3]QuickSort (сортировка Хоара)
Mr.F (2005-06-06 16:40:00) [4]> некоторые сравнивают сначала длину (если есть готовая)
Готовая - есть, но помочь она ничем не может... ведь проверка в алгоритмах не на равенство, а < или >...
Так какие все-таки алгоритмы уважают себя???
Digitman (2005-06-06 16:39:00) [5]
> Элементы не повторяются
сразу квиксорт напрашивается
Digitman (2005-06-06 16:37:00) [6]
> Бывают такие массивы
угу ... и ты, конечно же, готов дать голову на отсечение. что своими глазами видел length(такого_массива) >= 10^9 .. )
нельзя ли поскромней ?) ... не врать хотя бы ?)
> И как же они поступают
некоторые сравнивают сначала длину (если есть готовая)
далее посимвольно, в цикле, с учетом кодировки и case-условий..
Mr.F (2005-06-06 16:35:00) [7]сорри... 10^6 :)))
Mr.F (2005-06-06 16:34:00) [8]> Такого массива в Дельфи быть не может.
Бывают такие массивы... дело в том, что это всего лишь array of Char, в котором непрерывно записаны строки, разделенные нулевым символом
> уважающие себя алгоритмы поступают иначе ..
И как же они поступают???
Digitman (2005-06-06 16:32:00) [9]
> куча элементов в массиве... (> 10^9)
и точно) ... врешь и не моргаешь !)
Digitman (2005-06-06 16:31:00) [10]
> операция сравнения = далеко не один цикл процессора, поскольку
> элементами массива являются указатели на строки с нулевым
> символом в конце
целиком строки что ли сравниваешь ? или как ?
уважающие себя алгоритмы поступают иначе ..
Anatoly Podgoretsky (2005-06-06 16:30:00) [11]Такого массива в Дельфи быть не может.
| |
