C: Анализ методов сортировки
Некоторые терминалы отправляют <NL>, когда <C-Enter> нажимается. Это эквивалентно отправке <C-J>.
Для обнаружения, что терминал делает с <Shift-Enter>, <Ctrl-Enter> и <Enter>, переходят к терминалу, тип <Ctrl-V> (подобный предложению sykora для энергии), и вводят в последовательности, которой Вы интересуетесь.
Используя терминал гнома, я получаю следующее:
<Enter> : ^M
<S-Enter> : ^M
<C-Enter> : <NL>
Рассмотрение man ascii указывает, что ^M дает эти <CR> последовательность.
ответ - то, что это зависит от терминала, и существует простой способ проверить.
4 ответа
sortperf.py имеет хорошо подобранный набор тестовых примеров и использовался для поддержки эссе, найденного здесь , и выполнения сортировки по времени THE в Python lo много лет назад. Обратите внимание, что, наконец, Java может перейти на timsort благодаря Джошу Блоку (см. здесь ), поэтому я полагаю, что они написали свою собственную версию тестовых примеров - однако я могу Трудно найти ссылку на это. (timsort, стабильный, адаптивный, итеративный вариант естественной сортировки слиянием, особенно подходит для языков с семантикой ссылок на объект, таких как Python и Java, где «перемещение данных» относительно дешево [[поскольку все, что когда-либо перемещается, это ссылки, также известные как указатели , а не капли неограниченного размера ;-)]],
Окончательное исследование сортировки - это докторская диссертация Боба Седжвика . Но в его учебниках по алгоритмам есть много полезной информации, и это первые два места, где я бы искал набор тестов и методологию. Если вы недавно прошли курс, вы будете знать больше, чем я; В прошлый раз, когда у меня был курс, лучшим методом было использование быстрой сортировки до разделов размером 12, а затем выполнение сортировки вставкой для всего массива. Но ответы меняются так же быстро, как и оборудование.
В книгах Джона Бентли по программированию Perls есть и другая информация о сортировке.
Вы можете быстро создать набор тестов, содержащий
Случайные целые числа
Сортированные целые числа
Обратно отсортированные целые числа
Отсортированные целые числа, слегка нарушенные
Если память не изменяет, это наиболее важные случаи для алгоритма сортировки.
Если вы хотите отсортировать массивы, которые не помещаются в кэш, вам необходимо измерить эффекты кеширования. valgrind эффективен, если он медленный.
Это подробное обсуждение , а также ссылки на большое количество связанных веб-страниц, которые могут оказаться полезными, также описывает полезный набор входных данных для тестирования алгоритмов сортировки (причины см. на связанной странице). Резюмируя:
- Полностью случайно перетасованный массив
- Уже отсортированный массив
- Уже отсортированный в обратном порядке массив
- Массив бензопилы
- Массив идентичных элементов
- Уже отсортированный массив с N перестановками (с N от 0 . От 1 до 10% от размера)
- Уже отсортированный массив в обратном порядке массив с N перестановками
- Данные, которые имеют нормальное распределение с повторяющимися (или близкими) ключами (только для стабильной сортировки)
- Псевдослучайные данные (ежедневные значения S & P500 или другой индекс на десятилетие может быть здесь хорошим набором тестов; они доступны на Yahoo.com)
На этом сайте показаны различные алгоритмы сортировки с использованием четырех групп: http://www.sorting-algorithms.com/
В дополнение к четырем группам в ответе Нормана вы хотите проверить алгоритмы сортировки с помощью набора чисел, которые имеют некоторое сходство в числах:
- Все целые числа уникальны
- Одно и то же целое число во всей коллекции
- Несколько уникальных ключей
Изменение количества элементов в коллекции также является хорошей практикой: проверьте каждый алгоритм с 1K, 1M, 1G и т. Д., Чтобы узнать, что - это влияние этого алгоритма на память.