Форум программистов, компьютерный форум CyberForum.ru

Функция сортировки - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.88
EnotikN
0 / 0 / 0
Регистрация: 11.07.2013
Сообщений: 14
14.07.2013, 20:02     Функция сортировки #1
Здравствуйте,коллеги! Подскажите какую-нибудь функцию сортировки с наименьшим количеством операций сравнения. В общем необходимо сравнить около тысячи элементов, sort занимает много времени. Просто каждая секунда играет роль. Заранее спасибо

Добавлено через 2 минуты
Может кому-то приходилось сталкиваться с такой проблемой. И у кого-то есть код
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.07.2013, 20:02     Функция сортировки
Посмотрите здесь:

C++ Функция сортировки и поиска
C++ Функция сортировки матрицы
Функция сортировки C++
C++ Функция сортировки
C++ не работает функция сортировки
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Jetu
касаткО
 Аватар для Jetu
51 / 51 / 1
Регистрация: 01.10.2011
Сообщений: 227
15.07.2013, 11:41     Функция сортировки #2
Здесь описаны все более менее известные сортировки. Посмотрите, поизучайте. И да, чуть не забыл:
а) что вы сортируете ?
б) что вы подразумеваете под "много времени" ?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
16.07.2013, 19:53     Функция сортировки #3
Цитата Сообщение от EnotikN Посмотреть сообщение
В общем необходимо сравнить около тысячи элементов
Так тут даже пузырьком можно засортить, раз ограничения настолько мелкие.
valik35
1 / 1 / 0
Регистрация: 17.07.2013
Сообщений: 29
17.07.2013, 01:39     Функция сортировки #4
опишите что сортируете
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
17.07.2013, 07:29     Функция сортировки #5
1 000 - это на столько мало, что даже по худшему алгоритму уйдут сотни микросекунд. Может проблема не в сравнениях, а в тёжлых перестановках?
EnotikN
0 / 0 / 0
Регистрация: 11.07.2013
Сообщений: 14
17.07.2013, 23:13  [ТС]     Функция сортировки #6
Просто это происходит в реальном времени и в течении минимум десяти минут. Например, зона обзора РЛС, представляет собой набор ячеек с информацией и все время необходимо их сравнивать.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
18.07.2013, 15:08     Функция сортировки #7
А машина какая? Тактовая частота, средняя такность операций с кешем, размер кеша, частота шины, тайминги оперативы, размер одного элемента. И ещё, какую долю процессорного времени, можно выделить на сортировку с учётом того, что паралельно надо делать ещё что то и по какому алгоритму выполняется отдельное сравнение. Доли миллисекунды и 10 минут на столько несопоставимы, что возникают сомнения в том, что проблема кроется именно в алгоритме верхнего уровня.
Dmitriy_M
1294 / 1175 / 104
Регистрация: 20.03.2009
Сообщений: 4,211
Записей в блоге: 11
18.07.2013, 18:11     Функция сортировки #8
EnotikN, а что показывает профилировщик?
Для сортировок основанных на сравнениях предел http://www.cyberforum.ru/cgi-bin/latex.cgi?O\left(n\log \left( {n} \right)\right) , у std::sort именно такая характеристика.
EnotikN
0 / 0 / 0
Регистрация: 11.07.2013
Сообщений: 14
18.07.2013, 20:49  [ТС]     Функция сортировки #9
taras atavin, к сожалению описать алгоритм верхнего уровня не могу, так как это секрет. Могу лишь только сказать, что при сравнении до 80 элементов, алгоритм работает нормально. При большей загруженности начинает затыкаться.

Dmitriy_M, вроде еще функция mergesort имеет такую характеристику

Добавлено через 11 минут
Jetu, Сортирую ячейки с информацией по степени важности
Dmitriy_M
1294 / 1175 / 104
Регистрация: 20.03.2009
Сообщений: 4,211
Записей в блоге: 11
18.07.2013, 21:05     Функция сортировки #10
EnotikN, merge sort, heap sort, quick sort, и т.д. Какая из них быстрее можно узнать только прогонкой тестов. Так же при анализе не учитывается стоимость сравнения ключей.
Погоняй в VTune, им можно бесплатно пользоваться 30 дней. Если Проект пишется под nix системой, то прогони под valgrind, и посмотри граф вызовов на повторное вычисление одних и тех же данных, и введи кеширование.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.07.2013, 21:14     Функция сортировки #11
Цитата Сообщение от EnotikN Посмотреть сообщение
при сравнении до 80 элементов
Значит тормозит либо свап, либо сравнение. На 80 элементах сортировка вообще не особо важна.
Лучше скажите, что именно сортируется. Вернее, какой размер у ваших ячеек, как они сравниваются и как свапаются.
EnotikN
0 / 0 / 0
Регистрация: 11.07.2013
Сообщений: 14
18.07.2013, 21:31  [ТС]     Функция сортировки #12
Dmitriy_M, спасибо вам большое



Добавлено через 3 минуты
diagon, жаль,что не могу привести управляющий алгоритм. Писала статьи по этому поводу, но что-то в интернете найти её не могу.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
18.07.2013, 21:38     Функция сортировки #13
Цитата Сообщение от EnotikN Посмотреть сообщение
taras atavin, к сожалению описать алгоритм верхнего уровня не могу, так как это секрет. Могу лишь только сказать, что при сравнении до 80 элементов, алгоритм работает нормально. При большей загруженности начинает затыкаться.
Проблема врядли в нём. А вот алгоритм сравнения не помешает.
EnotikN
0 / 0 / 0
Регистрация: 11.07.2013
Сообщений: 14
18.07.2013, 21:48  [ТС]     Функция сортировки #14
taras atavin, попробую сортировку mergesort. Спасибо вам
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.07.2013, 07:10     Функция сортировки
Еще ссылки по теме:

Функция сортировки массива в структуре C++
Функция сортировки массива C++
C++ Функция сортировки массива

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Зосима
23.07.2013, 07:10     Функция сортировки
  #15

Не по теме:

Спинным мозгом чувствую, что тут под элементом подразумевается не число, а матрица чисел типа double, размера эдак 100x100

Yandex
Объявления
23.07.2013, 07:10     Функция сортировки
Ответ Создать тему
Опции темы

Текущее время: 16:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru