Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Клуб программистов > Свободное общение
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 23.07.2018, 13:08   #1
eduard-fe
 
Аватар для eduard-fe
 
Регистрация: 23.07.2018
Сообщений: 8
По умолчанию Продам алгоритм сортировки (адаптирую под ваши нужды)

Когда-то сделал код для сортировки (C++11), так как не устраивала производительность std::sort(). Вот сравнение std::sort() для случайной последовательности c моим кодом в релизе. Сравнение сделано честно, без скрытых фокусов по отношению к std::sort.

Код:
n (int)                 std::sort [sec]   my::sort [sec]
---------------------------------------------------------
1000                   0.000034          0.000033
1000000               0.0576               0.0156
1000000000          36.94                 10.47

n (double)           std::sort [sec]   my::sort [sec]
---------------------------------------------------------
1000                   0.000036          0.000032
1000000               0.0402               0.0158
1000000000          42.70                 15.41
Чем больше упорядоченности в данных, тем быстрее мой код относительно std::sort(), например, до 7 раз для полностью упорядоченной последовательности.

Если я обратился не туда, посоветуйте куда нужно.
Sincerely yours,
I am utterly indifferent to you.
eduard-fe вне форума Ответить с цитированием
Старый 27.07.2018, 07:30   #2
eduard-fe
 
Аватар для eduard-fe
 
Регистрация: 23.07.2018
Сообщений: 8
По умолчанию

Вот более честное сравнение, которое учитывает тот факт, что мой алгоритм обеспечивает стабильную сортировку, и, значит, его нужно сравнивать с std::stable_sort, а не с std::sort

Код:
n (int)             std::stable_sort [sec]   my::sort [sec]    ratio
---------------------------------------------------------------------
1000                   0.000065          0.000034             1.91x
1000000               0.0624               0.0173             3.58x
1000000000          86.56                 18.95               4.56x   

n (double)           std::stable_sort [sec]   my::sort [sec]   ratio
---------------------------------------------------------------------
1000                   0.000089          0.000056             1.58x
1000000               0.115               0.0197              5.85x
1000000000          115.34                 22.63              5.09x
Sincerely yours,
I am utterly indifferent to you.
eduard-fe вне форума Ответить с цитированием
Старый 30.07.2018, 11:34   #3
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,618
По умолчанию

Если твой алгоритм работает настолько лучше std::sort - то ты легко можешь защитить на этом кандидатсую, а быть может и докуторскую, стать известным чуваком примерно как Кнут. А ты тут на форуме ерундой занимаешься.
rrrFer вне форума Ответить с цитированием
Старый 31.07.2018, 05:35   #4
eduard-fe
 
Аватар для eduard-fe
 
Регистрация: 23.07.2018
Сообщений: 8
По умолчанию

Вычислительная сложность алгоритма O(N log N), что является такой же как у qsort. В алгоритме нет никакой научной новизны, просто качественная реализация и настройка его параметров под конкретный процессор (i7), потому нет предмета для публикации.

Алгоритм разрабатывался для соревнований (как скрытое преимущество), но выше 11 места мне не удалось подняться (нужно быть лучше во всем, а не в части)
Sincerely yours,
I am utterly indifferent to you.
eduard-fe вне форума Ответить с цитированием
Старый 31.07.2018, 07:20   #5
kvitaliy
Участник клуба
 
Регистрация: 17.05.2011
Сообщений: 1,660
По умолчанию

eduard-fe, а можете выложить простенький exe для теста?
Пусть будет сортировка массива int в 4 байта и диапазон [-2 147 483 648, +2 147 483 647] размерностью в 10 миллионов(10 000 000) + замер времени чистой сортировки, без учета формирования начального массива.
Если возможно 2 варианта, x86 и x64.
kvitaliy вне форума Ответить с цитированием
Старый 31.07.2018, 10:53   #6
eduard-fe
 
Аватар для eduard-fe
 
Регистрация: 23.07.2018
Сообщений: 8
По умолчанию

To: kvitaliy

Подготовлю в следующем варианте.

1. Тестовый exe (x64, release, -o2) будет считывать бинарный файл с данными (неважно int, double), сортировать по возрастанию, создавать новый бинарный файл с сортированными данными. Это обеспечивает минимизацию времени загрузки данных и гарантирует наличие кода, а не муляжа.

2. С вас потребуется сделать такой же exe, но с std::sort (std::stable_sort), выполнить сравнительные замеры на данных разного характера (случайные, случайные с большим числом дубликатов, упорядоченные), и обязательно выложить результаты сравнения.

Файл вышлю только Вам с обязательством не выкладывать в сеть и никому не передавать. Файл будет настроен на 10^8 элементов. Время сортировки порядка 4 сек, что достаточно, чтобы уловить различия.

У Вас есть возможность прогнать тест в линуксе? Винда у меня есть только на маломощной машине со старым компилятором (WinXp).
Sincerely yours,
I am utterly indifferent to you.
eduard-fe вне форума Ответить с цитированием
Старый 31.07.2018, 14:11   #7
kvitaliy
Участник клуба
 
Регистрация: 17.05.2011
Сообщений: 1,660
По умолчанию

Цитата:
Сообщение от eduard-fe Посмотреть сообщение
У Вас есть возможность прогнать тест в линуксе?
Нет, я не имею такой возможности. Только Win7. Но думаю, что если скомпилируете под XP, то ни чего страшного, должно запустится и на 7-ке.


Цитата:
Сообщение от eduard-fe Посмотреть сообщение
будет считывать бинарный файл с данными
Ну пусть будет так, это уже не существенные детали.

Цитата:
Сообщение от eduard-fe Посмотреть сообщение
выполнить сравнительные замеры на данных разного характера (случайные, случайные с большим числом дубликатов, упорядоченные), и обязательно выложить результаты сравнения.
Если есть такие данные в виде файлов, то нет проблем. Я же и собирался сравнить.
kvitaliy вне форума Ответить с цитированием
Старый 31.07.2018, 20:46   #8
WorldMaster
Старожил
 
Аватар для WorldMaster
 
Регистрация: 25.08.2011
Сообщений: 2,841
По умолчанию

Интересно бы на код посмотреть. Конечно может быть там и правда что-то выдающееся но странно что за все время развития информационных технологий никто не придумал подобное. Вроде великие умы занимались этой задачей ..

Вы говорите что код не покажете. А каким образом вы предлагаете оценить его качественность так сказать. Все равно нужно когда то показать код. А то окажется что у вас там метод дихотомии просто распаралеленн на несколько потоков.
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два.
WorldMaster вне форума Ответить с цитированием
Старый 01.08.2018, 06:54   #9
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,618
По умолчанию

Цитата:
Сообщение от eduard-fe Посмотреть сообщение
У Вас есть возможность прогнать тест в линуксе?
У меня есть.
Цитата:
Сообщение от eduard-fe Посмотреть сообщение
считывать бинарный файл с данными (неважно int, double)
Если у вас не SSD диск - то значительную часть этих 4 секунд будет именно файл считываться и записываться. Операции с диском медленные же.

Цитата:
Сообщение от WorldMaster Посмотреть сообщение
А то окажется что у вас там метод дихотомии просто распаралеленн на несколько потоков.
Мало того, мы тут замечали, что вижуал студия распараллеливает автоматически (по крайней мере векторизует) и в документации нашли, что по умолчанию автоматический векторизатор включен )). Отсюда - код может начать работать в несколько раз быстрее если написан так, что компилятор обнаружит возможность распараллеливания. И это может случаться или не случаться внезапно )). В G++ вроде как распараллеливание включается на -O3.

Что касается стандартных алгоритмов - они работают по умолчанию последовательно, но в последнем стандарте есть параллельные расширения этих же алгоритмов: https://en.cppreference.com/w/cpp/ex...elism/existing

Цитата:
Сообщение от eduard-fe Посмотреть сообщение
просто качественная реализация и настройка его параметров под конкретный процессор (i7)
Ну а если у меня не i7? - в первых двух постах про i7 ни слова не было...
rrrFer вне форума Ответить с цитированием
Старый 01.08.2018, 08:03   #10
WorldMaster
Старожил
 
Аватар для WorldMaster
 
Регистрация: 25.08.2011
Сообщений: 2,841
По умолчанию

Цитата:
Сообщение от eduard-fe Посмотреть сообщение
просто качественная реализация и настройка его параметров под конкретный процессор (i7)
Тогда уж сразу указывайте всю конфигурацию машины которая требуется чтобы ваш алгоритм работал. Интересно какую сумму должен будет потратить конечный пользователь чтобы получить все плюшки от алгоритма.
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два.
WorldMaster вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как адаптировать вкладки под свои нужды !!! 333_org_ua JavaScript, Ajax 0 05.12.2010 16:04
Помогите выбрать лицензию для ХР под описанные нужды. bset111 Windows 8 15.12.2009 22:38