Ученые-информатики используют нотацию Большой О для определения эффективных алгоритмов. В этой статье меня больше интересует, как языки компьютерного программирования работают с простым алгоритмом сортировки. Я проведу это сравнение, используя системные часы для измерения количества времени (в миллисекундах), которое требуется для использования сортировки по выбору для сортировки одного миллиона случайно сгенерированных чисел, хранящихся в массиве.
Языки, которые я буду использовать в своем сравнении, - это C ++, Java, JavaScript и Python. Без лишних слов, приступим.
Компьютер, использованный в тесте
Вот характеристики моего ноутбука Dell, который я использовал в этом тесте производительности:
Процессор: Intel Core i5–8250U CPU @ 1,60 ГГц 1,80 ГГц
Установленная оперативная память: 8,00 ГБ (можно использовать 7,90 ГБ)
Тип системы: 64-битная операционная система, процессор на базе x64
Алгоритм сортировки выбора
Выборочная сортировка - один из самых простых в реализации алгоритмов сортировки. Конечно, это не самый эффективный алгоритм, но моя цель - измерить эффективность языка программирования, а не эффективность алгоритма. Работа с неоптимальным алгоритмом подчеркнет эффективность или неэффективность языка программирования больше, чем если бы мы использовали более эффективный алгоритм сортировки, такой как QuickSort.
Вот псевдокодовая реализация алгоритма сортировки выбора:
Установить n равным размеру массива.
Для i от 1 до n - 1:
Установить минимальное значение i
Для j = i + 1 to n:
Если массив [j] ‹array [minimum]:
Установить минимум на j
Конец, если
Конец для
Swap (array [i], array [minimum]
Конец для
Теперь давайте обсудим, как измерять время в целом, а затем, когда я продемонстрирую, как реализовать сортировку по выбору на каждом языке, я продемонстрирую, как измерять время работы алгоритма.
Измерение системного времени
В большинстве языков программирования есть функции для записи системной даты и времени. Для многих языков одна и та же функция захватывает оба. Я приведу здесь два примера: один для языка, в котором есть специализированная библиотека для отслеживания времени (C ++), и один, в котором есть класс, который предоставляет методы для отслеживания времени (JavaScript).
В JavaScript есть класс для работы со временем - Date class. Этот класс хранит данные как о дате, так и о времени. Я буду использовать в своей программе только один метод из этого класса, getMilliseconds method. Вот небольшая программа, демонстрирующая, как я измеряю системное время в JavaScript:
let numbers = [];
const NUM_ELEMENTS = 1000;
let start = new Date();
for (let i = 1; i <= NUM_ELEMENTS; i++) {
numbers.push(i);
}
let stop = new Date();
let duration = stop.getMilliseconds() - start.getMilliseconds();
print("Time in milliseconds for loop to run:",duration);
Результат этой программы:
Time in milliseconds for loop to run: 13
В C ++ библиотека chrono содержит функции, которые мне нужны для измерения системного времени. Вот программа, демонстрирующая, как использовать эту библиотеку:
#include <iostream>
#include <chrono>
using namespace std;
int main()
{
const int NUM_ELEMENTS = 1000;
int numbers[NUM_ELEMENTS];
auto start = chrono::system_clock::now();
for (int i = 1; i <= NUM_ELEMENTS; i++) {
numbers[i-1] = i;
}
auto stop = chrono::system_clock::now();
auto lapsed_time =
chrono::duration_cast<chrono::milliseconds>
(stop - start).count();
cout << "It took " << lapsed_time
<< " milliseconds to populate the array." << endl;
return 0;
}
Результат этой программы:
It took 0 milliseconds to populate the array.
У каждого языка есть свой способ захвата системного времени, поэтому в этой статье мы увидим пять различных методов. Я представил здесь два, чтобы вы почувствовали, как улавливать системное время в программе.
Разобравшись с этими предварительными инструкциями, давайте начнем синхронизировать языки программирования при выполнении сортировки по выбору, чтобы увидеть, какие из них наиболее эффективны.
Сортировка выделения в C ++
Вот программа, которую я написал для измерения производительности сортировки выбора в C ++:
#include <iostream>
#include <chrono>
#include <cstdlib>
#include <ctime>
using namespace std;
void selectionSort(int arr[], int numElements) {
int minimum;
for (int i = 0; i < numElements-1; i++) {
minimum = i;
for (int j = i+1; j < numElements; j++) {
if (arr[j] < arr[minimum]) {
minimum = j;
}
}
int temp = arr[i];
arr[i] = arr[minimum];
arr[minimum] = temp;
}
}
void setArray(int arr[], int numElements) {
int randNum;
for (int i = 0; i < numElements; i++) {
randNum = rand() % 1000000 + 1;
arr[i] = randNum;
}
}
int main()
{
srand(time(0));
const int NUMELEMENTS = 10000;
const int MID = NUMELEMENTS / 2;
const int END = NUMELEMENTS - 1;
int numbers[NUMELEMENTS];
setArray(numbers, NUMELEMENTS);
auto start = chrono::system_clock::now();
selectionSort(numbers, NUMELEMENTS);
auto stop = chrono::system_clock::now();
cout << numbers[0] << ", " << numbers[MID]
<< ", " << numbers[END] << endl;
auto lapsed_time =
chrono::duration_cast<chrono::milliseconds>
(stop – start).count();
cout << "It took " << lapsed_time
<< " milliseconds to sort the array." << endl;
return 0;
}
Чтобы убедиться, что массив отсортирован, я отображаю первый элемент, элемент в средней точке массива и элемент в конце массива.
Результат этой программы:
1, 16568, 32765 It took 122 milliseconds to sort the array.
Теперь давайте посмотрим на версию для Java.
Производительность сортировки выбора в Java
Даже если вы никогда раньше не программировали на Java, у вас не должно возникнуть проблем с использованием моей программы на Java, чтобы проверить производительность алгоритма сортировки по выбору. Вот программа:
import java.util.Random;
public class SSort {
static void selectionSort(int[] arr) {
int minimum;
for (int i = 0; i < arr.length-1; i++) {
minimum = i;
for (int j = i+1; j < arr.length; j++) {
if (arr[j] < arr[minimum]) {
minimum = j;
}
}
int temp = arr[i];
arr[i] = arr[minimum];
arr[minimum] = temp;
}
}
static void buildArray(int[] arr) {
Random rand = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = rand.nextInt(1000000);
}
}
public static void main(String args[]) {
final int NUM_ELEMENTS = 10000;
final int MID = NUM_ELEMENTS/2;
final int END = NUM_ELEMENTS-1;
Random rand = new Random();
int [] numbers = new int[NUM_ELEMENTS];
buildArray(numbers);
long start = System.currentTimeMillis();
selectionSort(numbers);
long stop = System.currentTimeMillis();
System.out.println(numbers[0] + "," +
numbers[MID] + "," + numbers[END]);
System.out.println("It took " + (stop - start) +
" milliseconds to sort the array.");
}
}
Вот результат одного запуска этой программы:
99,500997,999990 It took 50 milliseconds to sort the array.
Версия C ++ заняла 122 миллисекунды, поэтому Java не так неэффективна по сравнению с C ++, как некоторые говорят.
Теперь перейдем к версии этого сравнения производительности для JavaScript.
Производительность сортировки выделения в JavaScript
JavaScript - наш первый интерпретируемый язык для тестирования. Опять же, вам не нужно знать JavaScript, чтобы понять этот код, поскольку JavaScript использует много синтаксиса в стиле C. В JavaScript массивы отличаются, поскольку JavaScript не компилируется, и я буду использовать метод push для добавления данных в массив, а не для индексации. В остальном мой код JavaScript очень похож на первые две программы.
Вот код JavaScript:
function buildArray(arr) {
for (let i = 1; i <= 10000; i++) {
arr.push(Math.floor(Math.random() * Math.floor(1000000)));
}
}
function selectionSort(arr) {
let minimum = 0;
for (let i = 0; i < arr.length-1; i++) {
minimum = i;
for (let j = i+1; j < arr.length; j++) {
if (arr[j] < arr[minimum]) {
minimum = j;
}
}
let temp = arr[i];
arr[i] = arr[minimum];
arr[minimum] = temp;
}
}
let numbers = [];
const NUM_ELEMENTS = 10000;
const MID = NUM_ELEMENTS/2;
const END = NUM_ELEMENTS-1;
buildArray(numbers);
let start = new Date();
selectionSort(numbers);
let stop = new Date();
let duration = stop.getMilliseconds() - start.getMilliseconds();
print(numbers[0], numbers[MID], numbers[END]);
print("It took",duration,"milliseconds to sort the array.");
Вот результат одного запуска этой программы:
179 508179 999945 It took 83 milliseconds to sort the array.
Эта программа занимала больше времени, чем моя программа на Java, чтобы отсортировать массив, но это время было все же меньше (на 40 миллисекунд), чем моя версия на C ++.
А теперь перейдем к версии Python.
Производительность сортировки выбора в Python
Как и в случае с JavaScript, основное отличие Python от других языков заключается в структуре данных, используемой для хранения чисел. В Python нет массивов, но есть списки, которые можно использовать таким же образом. Способ генерации случайных чисел Python также отличается, но не настолько, чтобы код мог вас запутать.
Вот код моей программы сортировки выбора Python:
from random import seed
from random import randint
from time import time
def selectionSort(nums):
for i in range(0, len(nums)-1):
minimum = i
for j in range(i+1, len(nums)):
if (nums[j] < nums[minimum]):
minimum = j
temp = nums[i]
nums[i] = nums[minimum]
nums[minimum] = temp
def buildList(nums):
seed(1)
for i in range(1,10000):
nums.append(randint(1,1000000))
numbers = []
mid = 5000
end = 9999
buildList(numbers)
start = int(time() * 1000)
selectionSort(numbers)
stop = int(time() * 1000)
duration = stop-start
print(numbers[0], numbers[mid], numbers[len(numbers)-1])
print("It took", duration, "milliseconds to sort the list.")
Результат одного запуска этой программы:
233 498036 999720 It took 2755 milliseconds to sort the list.
Заключение по производительности
Вот время, которое потребовалось каждому языку для сортировки 10000 случайно сгенерированных чисел с использованием алгоритма сортировки по выбору, отсортированного от самого быстрого к самому медленному:
Java: 50 миллисекунд
JavaScript: 83 миллисекунды
C ++: 122 миллисекунды
Python: 2755 миллисекунд
Обсуждение
Меня несколько удивило то, что Java была быстрее, чем C ++, но еще больше меня удивило то, что JavaScript был быстрее, чем C ++. Увидев этот вывод, я решил выяснить, связана ли низкая производительность C ++ с используемым мною компилятором (Code :: Blocks).
Чтобы проверить это, я переместил программу в имеющуюся у меня систему Linux и запустил ее с помощью компилятора gcc, который является частью моего дистрибутива Linux. Я получил следующий результат:
114, 490695, 999987 It took 118 milliseconds to sort the array.
Очевидно, что изменение среды программирования не улучшает производительность C ++ сортировки выбора.
Я планирую продолжить исследование различий в производительности между этими разными языками и напишу, что я нашел. Следующее мое расследование будет с обработкой строк.
Благодарим за прочтение и, пожалуйста, ответьте на эту статью или напишите мне по электронной почте с вашими комментариями и предложениями.
