Форум: "Основная";
Текущий архив: 2005.06.14;
Скачать: [xml.tar.bz2];
ВнизСортированные списки. Найти похожие ветки
← →
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]если массив упорядоченый то бинарная сортировка выигрывает у пузырька. во всяком случае я такое прочел.
← →
Digitman © (2005-05-26 10:54) [24]
> liver (26.05.05 10:50) [23]
ты не гадай на кофейной гуще, а возьми и поэкспериментируй с готовым демо-проектом (%DELPHI%\Demos\Threads\thrddemo.dpr), наглядно (визуально) показывающим преимущества и недостатки того или иного алгоритмов сортировки на том или ином ряду
← →
Digitman © (2005-05-26 10:55) [25]там представлено всего 3 широкоизвестных алгоритма, но ничто не мешает добавить еще косой десяток интересующих, дабы иметь более полную картину
← →
Anatoly Podgoretsky © (2005-05-26 11:30) [26]liver (26.05.05 10:50) [23]
если массив упорядоченый то бинарная сортировка выигрывает у пузырька. во всяком случае я такое прочел.
На самом деле наоборот, ты больше такую траву не кури, то есть не читай такие испочники.
← →
Digitman © (2005-05-26 11:38) [27]
> 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
← →
Digitman © (2005-05-26 11:57) [30]
> QuickSort побыстрее будет судя по
.. на конкретном ряду ..
а на твоем может и медленней быть
← →
liver (2005-05-26 13:29) [31]у меня Double в массиве
← →
liver (2005-05-26 13:29) [32]значения могут быть любые, одинаковые, повторяющиеся, уникальные и т.д.
← →
Digitman © (2005-05-26 13:34) [33]
> у меня Double в массиве
да хоть Triple - неважно.
> значения могут быть любые, одинаковые, повторяющиеся, уникальные
под "что чаще" из перечисленного как раз и выбирай алгоритм
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2005.06.14;
Скачать: [xml.tar.bz2];
Память: 0.53 MB
Время: 0.04 c