История изменений

Исправление ~~tz4678~~, 25.12.20 21:39 (текущая версия) :

Мне интересны рассуждения такого эксперты как ты. Во т есть C++ код с твоими учебными алгоритмами (которые кроме как для зачетов нигде не нужны):

#include <iostream>
#include <stdlib.h>
#include <time.h>

template <typename T>
void swap(T &x, T &y)
{
  x = x ^ y;
  y = y ^ x;
  x = x ^ y;
}

template <typename T>
void sort(T *arr, int size)
{
  for (int i = 0; i < size; i++)
  {
    bool flag = true;
    for (int j = 0; j < size - (i + 1); j++)
    {
      if (arr[j] > arr[j + 1])
      {
        flag = false;
        swap(arr[j], arr[j + 1]);
      }
    }
    if (flag)
    {
      break;
    }
  }
}

int main()
{
  srand(time(NULL));
  int size = 1000;
  int arr[size];
  for (int i = 0; i < size; ++i)
  {
    arr[i] = rand() % 1000;
  }
  std::cout << "Before sorting:";
  for (int i = 0; i < size; ++i)
    std::cout << " " << arr[i];
  std::cout << std::endl;
  sort(arr, size);
  std::cout << "After:";
  for (int i = 0; i < size; ++i)
    std::cout << " " << arr[i];
  std::cout << std::endl;
}

Этот код написал я, человек, знания которого о C++ ограничиваются тем, что его синтаксис похож на JS либо PHP, ну и работой со ссылками и указателями в другмих языках.

Вот мы его скомпилировали и запустили:

❯ time ./bubble                                                                              
Before sorting: 274 ... 289 693 687
After: 0 1 1 ... 984 984 985 986 987 988 988 990 992 992 993 994 995 996 996 997 998 999
./bubble  0.01s user 0.00s system 96% cpu 0.012 total

А теперь запустили код на Python:

#!/usr/bin/env python
import random
from typing import Any, List


def bubble(arr: List[Any]) -> List[Any]:
    length = len(arr)
    changed = True
    while changed:
        changed = False
        for i in range(length - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                changed = True
    return arr


if __name__ == '__main__':
    nums = [random.randint(0, 1000) for _ in range(1000)]
    print('Before:', nums)
    bubble(nums)
    print('After:', nums)

Вышло в 32 раза медленее.

❯ time ./bubble.py                                                                             
Before: [...]
After: [...]
./bubble.py  0.39s user 0.06s system 116% cpu 0.395 total

А теперь с помощью встроенных функций отсортируем список ака массив:

❯ time python -c 'import random; print(sorted([random.randint(0, 1000) for _ in range(1000)]))'
[0, 2, 2, 3, 4, 6, 9, 10, ..., 936, 937, 938, 938, 939, 940, 940, 940, 941, 942, 942, 944, 944, 945, 946, 948, 948, 948, 948, 949, 952, 953, 954, 955, 955, 955, 956, 961, 962, 964, 964, 967, 968, 968, 970, 970, 970, 972, 972, 973, 973, 973, 973, 977, 977, 978, 979, 981, 982, 984, 984, 986, 986, 987, 987, 988, 989, 989, 989, 990, 994, 995, 998, 999, 1000]
python -c   0.19s user 0.08s system 129% cpu 0.206 total

Вышло всего 17 раз медленее… А вот теперь перепиши код на Питоне так чтобы он работал быстрее C++. Хотя я понимаю что это невозможно, но не представляюв какой ситуации Python может приблизиться по скорости даже к C++ (чистая сишка быстрее крестов). Ну хотя бы обгони по скорости встроенные функции. Отсюда вывод: на скриптовых языках нет смысла пытаться реализовать алгоритмы, нужно писать сишыне биндинги. Так же в Python не нужны почти все паттерны из GoF и т.д., так как это не кресты, не джава и даже не додиез.

Исходная версия ~~tz4678~~, 25.12.20 21:37:

#include <iostream>
#include <stdlib.h>
#include <time.h>

template <typename T>
void swap(T &x, T &y)
{
  x = x ^ y;
  y = y ^ x;
  x = x ^ y;
}

template <typename T>
void sort(T *arr, int size)
{
  for (int i = 0; i < size; i++)
  {
    bool flag = true;
    for (int j = 0; j < size - (i + 1); j++)
    {
      if (arr[j] > arr[j + 1])
      {
        flag = false;
        swap(arr[j], arr[j + 1]);
      }
    }
    if (flag)
    {
      break;
    }
  }
}

int main()
{
  srand(time(NULL));
  int size = 1000;
  int arr[size];
  for (int i = 0; i < size; ++i)
  {
    arr[i] = rand() % 1000;
  }
  std::cout << "Before sorting:";
  for (int i = 0; i < size; ++i)
    std::cout << " " << arr[i];
  std::cout << std::endl;
  sort(arr, size);
  std::cout << "After:";
  for (int i = 0; i < size; ++i)
    std::cout << " " << arr[i];
  std::cout << std::endl;
}

Вот мы его скомпилировали и запустили:

❯ time ./bubble                                                                              
Before sorting: 274 ... 289 693 687
After: 0 1 1 ... 984 984 985 986 987 988 988 990 992 992 993 994 995 996 996 997 998 999
./bubble  0.01s user 0.00s system 96% cpu 0.012 total

А теперь запустили код на Python:

#!/usr/bin/env python
import random
from typing import Any, List


def bubble(arr: List[Any]) -> List[Any]:
    length = len(arr)
    changed = True
    while changed:
        changed = False
        for i in range(length - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                changed = True
    return arr


if __name__ == '__main__':
    nums = [random.randint(0, 1000) for _ in range(1000)]
    print('Before:', nums)
    bubble(nums)
    print('After:', nums)

Вышло в 32 раза медленее.

❯ time ./bubble.py                                                                             
Before: [...]
After: [...]
./bubble.py  0.39s user 0.06s system 116% cpu 0.395 total

А теперь с помощью встроенных функций отсортируем список ака массив:

❯ time python -c 'import random; print(sorted([random.randint(0, 1000) for _ in range(1000)]))'
[0, 2, 2, 3, 4, 6, 9, 10, ..., 936, 937, 938, 938, 939, 940, 940, 940, 941, 942, 942, 944, 944, 945, 946, 948, 948, 948, 948, 949, 952, 953, 954, 955, 955, 955, 956, 961, 962, 964, 964, 967, 968, 968, 970, 970, 970, 972, 972, 973, 973, 973, 973, 977, 977, 978, 979, 981, 982, 984, 984, 986, 986, 987, 987, 988, 989, 989, 989, 990, 994, 995, 998, 999, 1000]
python -c   0.19s user 0.08s system 129% cpu 0.206 total