Сортированные списки.

← →
liver (2005-05-25 09:34) [0]

Надо написать как можно более быстрый сортированный список.
У кого какие есть идеи ?
Может кто уже писал такое, вернее такое писал каждый. интересует оптимизированный код. Наиболее эыффективный.

← →
Ega23 © (2005-05-25 09:39) [1]

Может кто уже писал такое, вернее такое писал каждый.

Это ты, брат, прав. В универе такое каждый писал.

Наиболее эыффективный.

Зависит от списка, количества элементов и т.п. К примеру, больше 1000 элементов - бинарное дерево быстрее пузырька работать будет.

интересует оптимизированный код.

Не вопрос. Можешь ко мне на e-mail ткнуться. Беру недорого - $100 за килобайт кода.

← →
Digitman © (2005-05-25 09:41) [2]

> Надо написать как можно более быстрый сортированный список

списки не "пишут", списки формируют, заполняют, сортируют и т.д.

> У кого какие есть идеи ?

воспользоваться любым готовым подходящим классом вида TXXXList : TList, TStringList, TObjectList и т.д. и т.п.

каждый из них УЖЕ имеет встроенный метод, реализующий сортировку заполненного списка по алгоритму QuickSort

> интересует оптимизированный код

код вышеупомянутого алгоритма в вышеупомянутых классах вполне оптимален

> Наиболее эыффективный

об эффективности того или иного алгоритма сортировки нельзя рассуждать в отрыве от характера сортируемых данных

← →
liver (2005-05-25 09:43) [3]

интересуют очень большие списки.
ну например на 1 000 000 элементов.
Сортировку пузырьком я и использую.
Просто думал может кто кодом поделится...
а 100$ а килобайт...ты загнул да я и сам написать могу :)
просто сегда думал что на форумах люди делятся мыслями и идеяями...не за деньги :)

← →
Ega23 © (2005-05-25 09:47) [4]

просто сегда думал что на форумах люди делятся мыслями и идеяями...не за деньги :)

Заметь, в твоей фразе нету слова "код". :о)
Идея - пожалуйста: метод сортировки бинарным деревом. Алгоритм - Яндекс дофига выдаст. Реализация сложнее, чем пузырёк, но на больших списках работает "со свистом".

А насчёт кода... Видишь ли, я в своё время штук 10 алгоритмов сортировки реализовал (домашнее задание такое было). Писал и отлаживал код несколько дней. А теперь взять и просто так кому-то дать?

← →
liver (2005-05-25 09:48) [5]

Digitman ©
Данные в списке будут типа Double

← →
Digitman © (2005-05-25 09:49) [6]

> интересуют очень большие списки.
> ну например на 1 000 000 элементов

кроме размера список характеризуется еще и показателем повторяемости его элементов, и от этого показателя немало зависит выбор того или иного алгоритма сортировки

например, алгоритм QuikSort будет заметно более эффективен при уникальных (неповторяющихся) значениях элементов в сортируемом списке

← →
liver (2005-05-25 09:50) [7]

Ega23 ©
ээээ брат...как же ты тогда бесплатные компоненты юзаешь и вообще относишься к оупенсоурс ? У тебя выходит весь софт лицензионный....

← →
Anatoly Podgoretsky © (2005-05-25 09:51) [8]

Что значит быстрый, по мне любой список быстрый, он же памятник, кто же его посадит.

← →
liver (2005-05-25 09:52) [9]

Digitman ©
Элементы в списке преимущественно будут уникальными.

← →
Digitman © (2005-05-25 09:54) [10]

> liver (25.05.05 09:48) [5]
> Данные в списке будут типа Double

тип данных не столь важен в дан.случае

хотя один и тот же алгоритм сортировки даст различные показатели производительности для списка FP-чисел и чисел с огран.точностью

← →
liver (2005-05-25 09:54) [11]

Anatoly Podgoretsky ©
ну вот смотри.
напишу функцию которая делает бинарный поиск.
продцедуру которая вставляет элемент в список с учетом сортировки.
или стоит всавлять всавлять...а потом один раз сортировать.

← →
Ega23 © (2005-05-25 09:57) [12]

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

А я кроме FireBird ничего из ОО и не использую. Софт - да, весь лицензионный. Более того, я нигде не анонсировал, что я исповедую OO-религию.
Всё дело в том, что программирование - моя профессия (правда это ещё и хобби, редкий случай, когда за хобби - деньги платят). Я этим зарабатываю себе на жизнь, а не занимаюсь в свободное от работы время.
И ещё я не люблю халявщиков (их, вообще-то, никто не любит).

← →
liver (2005-05-25 09:59) [13]

Ega23 ©
никто не говорит что твой код будет браться таким какой он есть.
его посмотрят и возьмут из него лучшее и заточат под свои задачи...
ну да ладно...это уже флуд...
по делу

← →
Anatoly Podgoretsky © (2005-05-25 10:16) [14]

Так все таки вставка или сортировка, а вставляет кто?

← →
Anatoly Podgoretsky © (2005-05-25 10:17) [15]

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

← →
liver (2005-05-25 10:22) [16]

я так думаю что лучше сортировать на этапе вставки
много мелких...я так думаю

← →
Digitman © (2005-05-25 10:27) [17]

> я так думаю что лучше сортировать на этапе вставки
> много мелких...я так думаю

решение - от балды ?

наверно, да)

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

← →
Alex Konshin © (2005-05-25 13:02) [18]

Ты сначала определись, для чего тебе этот список. И список-ли тебе нужен.
Нужен ли тебе будет последовательный доступ к элементам?
Нужен ли доступ по номеру?
Будет ли он динамически изменяться или после построения он будет практически read-only?

Даже если последовательный доступ нужен, это не означает автоматически, что нельзя использовать те же бинарные деревья, наприр AVL-tree - их замечательно можно обходить влюбом порядке. А уж поиск/вставка/удаление там очень быстрые.

Смотри AVLtree и Arrays нв моем сайте из анкеты.

← →
Андрюха7 © (2005-05-25 16:42) [19]

http://algolist.manual.ru/ds/index.php
На этом сайте много полезной инфы на эту и не только темы.

← →
liver (2005-05-26 09:20) [20]

Digitman ©

нет, не от балды.
Сортировка бинарная быстрее чем пузырьком.
Если вставлять на этапе вставки то скорость будет больше чем все сразу сортировать.

← →
Anatoly Podgoretsky © (2005-05-26 09:48) [21]

liver (26.05.05 09:20) [20]
Кто тебе такое сказал.

← →
Digitman © (2005-05-26 10:05) [22]

> liver (26.05.05 09:20) [20]
> Если вставлять на этапе вставки то скорость будет больше
> чем все сразу сортировать

это ты загнул.

← →
liver (2005-05-26 10:50) [23]

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

> liver (26.05.05 10:50) [23]

ты не гадай на кофейной гуще, а возьми и поэкспериментируй с готовым демо-проектом (%DELPHI%\Demos\Threads\thrddemo.dpr), наглядно (визуально) показывающим преимущества и недостатки того или иного алгоритмов сортировки на том или ином ряду

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

liver (26.05.05 10:50) [23]
если массив упорядоченый то бинарная сортировка выигрывает у пузырька. во всяком случае я такое прочел.

На самом деле наоборот, ты больше такую траву не кури, то есть не читай такие испочники.

> liver (26.05.05 10:50) [23]

основное время при выполнении сортировки "на месте" любым алгоритмом, тратится на "обмен элементов местами".

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

в случае рекурс.алгоритмов, базирующихся на "половинном делении", сортировка того же ряда как правило приводит как минимум к одному "обмену".

← →
liver (2005-05-26 11:51) [28]

будем значит проводить тесты

← →
liver (2005-05-26 11:53) [29]

QuickSort побыстрее будет судя по %DELPHI%\Demos\Threads\thrddemo.dpr

> QuickSort побыстрее будет судя по

.. на конкретном ряду ..
а на твоем может и медленней быть

← →
liver (2005-05-26 13:29) [31]

у меня Double в массиве

← →
liver (2005-05-26 13:29) [32]

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

> у меня Double в массиве

да хоть Triple - неважно.

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

под "что чаще" из перечисленного как раз и выбирай алгоритм

Сортированные списки. Найти похожие ветки