Несколько вопросов сортировки

Я нашел способ, который улучшает (насколько я проверял) алгоритм быстрой сортировки выше того, что уже сделано. Я работаю над его тестированием, а затем хочу рассказать об этом. Тем не менее, я был бы признателен за помощь в некоторых вещах. Итак, вот мои вопросы. Весь мой код находится в С++, кстати.

• Один из видов, которые я сравнивал с моей quicksort, - это std:: sort из стандартной библиотеки С++. Однако, похоже, он очень медленный. Я только сортирую массивы ints и longs, но, похоже, он примерно в 8-10 раз медленнее, чем мой быстроходный и стандартный quicksort Bentley и McIlroy (и, возможно, Sedgewick). У кого-нибудь есть идеи относительно того, почему это так медленно? Код, который я использую для сортировки, просто станд:: сортировать (а, а + numelem); где a - массив longs или ints, а numelem - количество элементов в массиве. Числа очень случайны, и я пробовал разные размеры, а также различные количества повторяющихся элементов. Я также пробовал qsort, но это еще хуже, как я ожидал. Изменить: игнорировать этот первый вопрос - он был разрешен.

• Я хотел бы найти более хорошие реализации быстрой сортировки, чтобы сравнить с моей быстрой сортировкой. Пока у меня есть Bentley-McIlroy, и я также сравнил с первой опубликованной версией быстрорежущей машины с двойным стержнем Владимира Ярославского. Кроме того, я планирую портировать timsort (который представляет собой сортировку слияния, я считаю) и оптимизированную двоякую быструю сортировку из источника jdk 7. О каких других хороших реализациях быстрой сортировки вы знаете? Если они не на C или С++, это может быть хорошо, потому что я хорошо переношу, но я бы предпочел C или С++, если вы знаете о них.

• Как бы вы порекомендовали выпустить слово о моих добавлениях в quicksort? До сих пор мой quicksort, по-видимому, был значительно быстрее, чем все другие операторы, которые я тестировал. Основным источником его скорости является то, что он обрабатывает повторяющиеся элементы намного эффективнее других методов, которые я нашел. Он почти полностью уничтожает поведение худшего случая, не добавляя много времени на проверку повторяющихся элементов. Я опубликовал об этом на форумах Java, но не получил ответа. Я также пробовал писать в Jon Bentley, потому что он работал с Владимиром на его двухповоротной быстродействующей машине и не получил ответа (хотя меня это не удивило). Должен ли я написать статью об этом и поместить ее на arxiv.org? Должен ли я размещать сообщения на некоторых форумах? Есть ли списки рассылки, на которые я должен писать? Я работаю над этим в течение некоторого времени, и мой метод является законным. У меня есть некоторый опыт публикации публикаций, потому что я кандидат в области вычислительной физики. Должен ли я попытаться приблизиться к кому-то в отделе компьютерных наук моего университета? Кстати, я также разработал другую быстродействующую быстродействующую двойную точку, но это не лучше, чем моя однопользовательская быстродействующая сортировка (хотя она лучше, чем двойная смены с двумя наборами данных с несколькими наборами данных).

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

Ответы

Ответ 1

Если у вас есть уверенность в вашей работе, обязательно попробуйте как можно скорее обсудить ее с кем-то, знающим в вашем университете. Этого недостаточно, чтобы показать, что ваш код работает быстрее, чем другая процедура на вашем компьютере. Вы должны математически доказать, какую производительность вы утверждаете, достигнув посредством анализа вашего алгоритма. Я бы сказал, что первое, что нужно сделать, это убедиться, что оба алгоритма, которые вы сравниваете, реализованы и скомпилированы оптимально - вы можете просто обманывать себя здесь. Вероятность индивидуума, добившегося столь заметного улучшения такого важного метода сортировки, не имея уже глубокого знания своих приемлемых вариантов, кажется незначительной. Однако не позволяйте мне отговаривать вас. В любом случае, это должно быть интересно. Вы хотите разместить здесь код? ... Кроме того, поскольку quicksort особенно уязвим для наихудших сценариев, тесты, которые вы выбрали для запуска, могут иметь огромный эффект, а также выбор опорных точек. В общем, я бы сказал, что любой набор данных с большим количеством эквивалентных элементов или тот, который уже сильно отсортирован, никогда не является хорошим выбором для быстрой сортировки - и есть уже известные способы борьбы с этой ситуацией и лучшие альтернативные методы сортировки.

Ответ 2

Если вы действительно сделали прорыв и попросите математику доказать это, вы должны попытаться опубликовать его в Journal of ACM. Это определенно один из самых престижных журналов для компьютерной науки.

Второй лучшим будет один из журналов IEEE, например Транзакции по разработке программного обеспечения.