Русский
Русский
English
Статистика
Реклама

Сортировка

Нестабильная сортировка в JavaScript

29.09.2020 12:13:11 | Автор: admin

Когда я вижу пост на подобную тему в любой социальной сети, под ним почти всегда оказывается множество комментов вот такого типа:

  • Зачем это нужно знать, если есть встроенные методы сортировки?

  • Зачем изобретать велосипед заново?

  • Это нужно, чтобы пройти собеседование, объективно больше незачем это знать

  • В "любой движок javascript" работают не дураки, и уже сделали все как нужно

И сам я раньше считал так же, пока не пришел в одну из команд Ростелеком ИТ frontend-разработчиком. Вместе мы набрели на очень интересный кейс: нужно было создать виджет, который мог бы встраиваться в информационные системы всех наших макрорегиональных филиалов и упрощать работу операторов по подбору оптимального тарифа.

Сразу к делу

Как думаете, что произойдет после выполнения данного кода?

Кажется, что ничего странного, но есть нюансы.

Случай номер раз

Сделали задачу, техническое решение, код, unit-тесты. По бизнес-процессу тоже все хорошо. При поверхностном тестировании проблем не нашли. Но когда дело дошло до авто-тестов, начались странности. Конфигурация, которую просчитывал Node.js 10, в основном отдавала корректный результат, но иногда конфигурация отличалась. Что усложняло процесс поиска проблемы, учитывая, что в режиме отладки конфигурация отдавалась всегда корректной. А еще у одних членов команды некорректная конфигурация воспроизводилась, а у других нет. И мы сделали вывод, что в старой версии, наверное, баг, и решили обновить версию на более новую.

После длительного поиска проблемы в коде ошибка не была найдена. Тестирование проекта на разных Node показало, что при запуске проекта на Node, начиная с версии 11, ответ был всегда стабильным. Что и послужило решением этой проблемы. Версия Node была обновлена до 12, и проблема исчезла.

Случай номер два

На этот раз конфигурации отличались уже в разных версиях браузера: в Google Chrome 80 был корректный результат, а в его 69 версии нет. И тут нам стало интересно, почему же конфигурация отличается.

  • Увидел, что версии отличаются

  • Открыл Release notes Google Chrome

  • Обнаружил, что Google Chrome 69 это последняя сборка, где используется 6-я версия V8

  • Открыл Release notes V8

  • И начал просматривать все статьи между 6 и 7 версией V8

Спустя некоторое время я наткнулся на статью Getting things sorted in V8, в которой говорится, что с 7-й версии V8 переходит на стабильный алгоритм сортировки TimSort, вместо предыдущего нестабильного QuickSort. И тут сразу стало понятно, что никакой магии нет, и все эти баги из-за нестабильной сортировки.

Нюансы сортировки

Сортировка в Node.js 10.22 (движок V8 v6.8) QuickSort.

Как видите, массив из первого скриншота изменил порядок, хотя функция сравнения всегда возвращала 0.

Сортировка в Node.js 14.5 (движок V8 v7.0) TimSort.

На этот раз сортировка уже не изменила данные.

Как дальше жить

И что же в итоге получается? То, что у клиентов могут быть разные результаты работы нашего кода в зависимости от типа сортировки используемого движка JavaScript. И если с Node.js переход на новую версию решит проблему, то заставить всех пользователей сделать то же самое со своими браузерами не получится.

Есть несколько разных решений, которые подойдут для конкретных кейсов. В нашем случае мы решили использовать реализацию алгоритма BlockSort (wikisort). Да, реализация работает медленнее, чем нативная сортировка браузера, но зато теперь я уверен в стабильности результата сортировки там, где это необходимо.

Сравнение разных вариантов решения с нативной реализацией

Мы решили сравнить:

  • lodash.sortby

  • WikiSort javascript адаптация (WikiSort)

  • QuickSort нативная реализация V8 (node.js 10.22.0)

  • TimSort нативная реализация V8 (node.js 14.5.0)

В ходе теста было создано 10 массивов со случайным сортируемым значением, в каждом из которых было по 100 тысяч объектов.

Из этого графика можно сделать вывод: после оптимизаций, которые провел движок V8, сортировка WikiSort не уступает нативной реализации TimSort, хотя при первых сортировках разница довольно заметная. А вот lodash я бы не стал советовать.

Посмотреть результаты теста подробнее можно тут sort-test-js, а исходный код тут Tihon-Ustinov/sort-test-js

Где стабильно?

версия

дата релиза

движок JavaScript

стабильность

Node.js

11.0.0

2018-10-23

V8 7.0.276.28

+

Node.js

10.22.0

2020-07-21

V8 6.8.275.32

-

Google Chrome

70.0.3538

2018-10-16

V8 7.0.276

+

Google Chrome

69.0.3497

2018-09-04

V8 6.9.427

-

Выводы

  • Не верьте в магию JavaScript, у всех странных кейсов в этом языке есть объяснение

  • Изучайте технологии, которые вы используете

  • Читайте официальную документацию

  • Следите за тем, что появляется в новых версиях

  • Не думайте, что уже все сделано и придумано, и вам нужно только использовать готовые решения

Подробнее..

Решаем вопрос сортировки в JavaScript раз и навсегда

30.05.2021 14:10:27 | Автор: admin

Вступление

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

С чего все началось

В один прекрасный летний день, на проекте с AngularJS мне поручили добавить функцию сортировки в таблицу. При этом критериев для сортировки может быть сразу несколько, и направление по каждому критерию может быть независимым.

Список требований:

  • использовать несколько выражений как ключ для сортировки

  • возможность указать направление сортировки независимо по каждому из ключей

  • возможность сортировать строки без учета регистра, и с учетом локали

  • устойчивость сортировки

Что нам предлагает AngularJS для сортировки? документация по filter:orderBy

{{ orderBy_expression | orderBy : expression : reverse : comparator }}$filter('orderBy')(collection, expression, reverse, comparator)Example:<tr ng-repeat="friend in friends | orderBy:'-age'">...</tr>

У меня возникло несколько замечаний по поводу этого фильтра. Для начала, знак - в этом примере не может быть математической операцией, потому что есть значения для которых это бессмысленная операция, например строки. В документации говорится что это префикс, который указывает направление сортировки. Если продолжить разбор, что это вообще за выражение? Это, вроде как, похоже на JS, но в то же время не очень. Это синтаксис выражений для AngularJS, который так же опасен как eval, но при этом имеет свои ограничения. То что этот синтаксис исключителен для AngularJS значит что эти знания невозможно перенести на другие проекты на JS. Кроме того, нельзя использовать TypeScript для проверки этих выражений. expression кроме того может принимать не только строку, но и функцию, которая возвращает ключ для сортировки. Но если указывать функцию, то направление сортировки указать нельзя и теряется гибкость. Так же можно указать несколько критериев сортировки, если задать массив из строк или функций.

Идем дальше, направление сортировки так же можно поменять вторым параметром reverse. Но возникает проблема! Если указывать несколько критериев сортировки с помощью функций, то нельзя указать направление индивидуально для каждого критерия. Если же указывать направиление сортировки в каждом критерии индивидуально, то этот параметр лишний.

Теперь посмотрим на третий параметр comparator, который позволяет задать особый способ сравнения элементов. Но при этом если было указано несколько критериев сортировки, то один и тот же comparator будет использоваться для каждого критерия. В результате localeSensitiveComparator будет использоваться для сортировки чисел.

И спрашивается, какая мне польза использовать интерфейс который сам с собой не дружит в трех местах, несовместим с TypeScript и его можно использовать исключительно в богом позабытом фреймворке? В мире JavaScript таких примеров, к сожалению, полным полно.

lodash

Посмотрим на библиотеку lodash, В ней есть функция _.sortBy, которая позволяет сортировать массив по ключу.

var users = [    { 'user': 'fred',   'age': 48 },    { 'user': 'barney', 'age': 36 },    { 'user': 'fred',   'age': 40 },    { 'user': 'barney', 'age': 34 }]; _.sortBy(users, [(o) => o.user]);// => objects for [['barney', 36], ['barney', 34], ['fred', 48], ['fred', 40]] _.sortBy(users, ['user', 'age']);// => objects for [['barney', 34], ['barney', 36], ['fred', 40], ['fred', 48]]

Хм, эта функция не позволяет указывать направление сортировки, почему так? Из-за этого я хотел сразу отбросить lodash, но потом увидел _.orderBy.

This method is like _.sortBy except that it allows specifying the sort orders of the iteratees to sort by.

Добавление опционального параметра не должно ломать обратную совместимость, поэтому мне совсем непонятно почему это сделали отдельной функцией. Посмотрим на его использование:

// Sort by `user` in ascending order and by `age` in descending order._.orderBy(users, ['user', 'age'], ['asc', 'desc']);// => objects for [['barney', 36], ['barney', 34], ['fred', 48], ['fred', 40]]

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

В целом, _.orderBy это терпимый метод сортировки.

Array#sort

Если же мы хотим использовать только стандартную библиотеку JavaScript, у Array нам доступен метод sort. В этом методе можно указать функцию для сравнения элементов. Сам по себе этот интерфейс для сортировки позволяет указать любой возможный критерий для сортировки. Правда он не так удобен для использования как сортировка по ключу, и есть довольно много подводных камней. Самый большой подводный камень, с моей точки зрения, к этой функции есть очень строгое требование линейно упорядоченного множества. Это требование очень просто нарушить. В прошлом, несоблюдение этих требований в некоторых браузерах приводило к бесконечным циклам и крахам.

items.sort(function(a, b) {    if (b.salary < a.salary) {      return -1;    }    if (b.salary > a.salary) {      return 1;    }    if (a.id < b.id) {      return -1;    }    if (a.id > b.id) {      return 1;    }    return 0;});// Для сравнения, эквивалентный код с использованием `lodash`// намного короче и его проще читать:lodash.orderBy(items, ['salary', 'id'], ['desc', 'asc']);

Когда критериев для сортировки будет больше, то разница в удобстве будет еще больше, что приведет повторению кода. Отсутствие удобства и громоздкость обычно приводит к тому, что в код закрадываются трудно уловимые ошибки.

Если же мы хотим примеры адекватных интерфейсов, нужно смотреть в сторону других языков.

SQL / SEQUEL

Стоит начать с того что данные лучше всего нужно сортировать на стороне сервера, и отображать на клиенте как есть, без перестановок. Если можно убрать сортировку на клиенте, поздравляю, проблема решена! Но этот пост не о таких ситуациях, поэтому попробуем позаимствовать опыт SQL.

Как ни как, сортировка это часть языка SQL с 1976 года, и с его помощью люди давно сортируют данные налево и направо. Кому, как не пользователям реляционных баз данных, приходится больше всего сортировать данные по сложным критериям?

SELECT EMPNO,NAME,SALFROM EMPWHERE DNO 50ORDER BY EMPNO

SQL позволяет указывать несколько критериев сортировки, а так же независимо указывать направление сортировки по разным критериям:

SELECT EMPNO,NAME,SALFROM EMPORDER BY SAL DESC, EMPNO ASC

Вот к такому нужно стремиться. К сожалению, SQL это отдельный язык и без специального синтаксиса нет возможности внедрить это напрямую.

Haskell и Rust

Haskell и Rust предоставляют довольно элегантные методы для сортировки по ключу:

Haskell sortOn:

import Data.Ord (Down)import Data.Sort (sortOn)sortOn (\employee -> (Down (salary employee), employee_id employee)) employees

Rust slice::sort_by_key:

use std::cmp::{Reverse};slice.sort_by_key(|employee| (Reverse(employee.salary), employee.id))

Здесь сортировка по нескольким критериям достигается за счет лексикографического порядка кортежей, а сортировка по убыванию за счет оберточных типов (newtype) Down и Reverse, которые инвертирует порядок сортировки своего содержания. Это очень простой для использовани интерфейс, и он полностью совместим со всеми требованиями.

Python

В Python у списков есть встроенный метод list.sort и гобальный метод sorted, в котором можно указать критерий сортировки через именованный аргумент key.

Ранее эти методы так же принимали аргумент cmp, но его убрали потому что он не нужен.

sorted(employees, key=lambda employee: (employee.salary, employee.id))

Python, как Haskell и Rust, здесь использует кортеж для сортировки по нескольким критериям, но нельзя указывать направление сортировки отдельно для каждого критерия. К счастью, это легко исправить, создав клас-обертку для обратной сортировки. Это упростит метод сортировки, убрав один аргумент, и одновременно расширит возможности сортировки.

from ord_reverse import Reversesorted(employees, key=lambda employee: (Reverse(employee.salary), employee.id))

Java и C#

В Java метод Arrays.sort принимает Comparator (который почти состоит одной функции сравнения двух элементов). Но Comparator так же позволяет строить компараторы, добавляя новые критерии сравнения, используя метод thenComparing. Можно обратить направление сортировки используя метод reversed.

Comparator<Employee> comparator =  Comparator.comparing(Employee.getSalary).reversed()    .thenComparing(Employee.getId);Arrays.sort(array, comparator);

Здесь есть небольшой недостаток нет простого способа указать обратное направление сортировки для отдельного критерия. Давайте попробуем написать компаратор вида ORDER BY SALARY ASC, ID DESC:

// Вариант 1, создавать два компаратора, и складывать ихComparator<Employee> comparator =  Comparator.comparing(Employee.getSalary)    .thenComparing(Comparator.comparing(Employee.getId).reversed());// Вариант 2, инвертирует компаратор дважды. Таким образом первый компаратор// будет использовать прямое направиление сортировки.Comparator<Employee> comparator =  Comparator.comparing(Employee.getSalary).reversed()    .thenComparing(Employee.getId).reversed();

Если не учитывать LINQ Query, который есть прямым наследником SQL, в C# для сортировки используется Enumerable.OrderBy и Enumerable.OrderByDescending, а так же Enumerable.ThenBy и Enumerable.ThenByDescending для добавления новых критериев сортировки.

IEnumerable<Employee> query =    employees    .OrderByDescending(employee => employee.Salary)    .ThenBy(employee => employee.Id);

По сравнению с Java здесь легче указать обратною сортировку для индивидуальных ключей. Но есть и недостатки не очевидно когда именно будет происходить сортировка, и слишком множатся методы: IEnumerable 4 метода, по сравнению с 1 в Haskell/Rust/Python. Количество методов в C# можно было бы свести к двум, используя простой класс для инверсии сравнения.

В целом, как Java, так и C# удовлетворяют требования сортировки. К сожалению, оба языка используюь более громоздкий подход с использованием ООП.

C и C++

C qsort:

#include <stdlib.h>int cmp_employee(const void *p1, const void *p2){      const employee *a = (employee*)p1;      const employee *b = (employee*)p2;      if (b->salary < a->salary) {        return -1;      }      if (b->salary > a->salary) {        return 1;      }      if (a->id < b->id) {        return -1;      }      if (a->id > b->id) {        return 1;      }    return 0;  }  /* ... */  qsort(employees, count, sizeof(employee), cmp_employee);

C++ std::sort:

#include <algorithm>/* ... */std::sort(employees.begin(), employees.end(), [](const employee &a, const employee &b) {  return (b->salary < a->salary) || (a->id < b->id);});

Как в C, так и в C++ сортировать можно только предоставляя функцию сравнения элементов. Только в C сравнение элементов требует возвращать не -1, 0, 1, а в C++ проверять что первый элемент меньше второго. В каком-то смысле, так теряется часть информации о сравнении. Скорее всего, это приводит к тому что функция сравнения в C++ вызывается больше чем необходимо.

В C и в C++ нет встроенных способов сортировки по ключу и отсутствуют воспомагательные классы для сборки компараторов из нескольких частей. Array#sort, который мы рассматривали ранее имеет те же недостатки как и эти две функции.

Выбираем то что лучше подходит

Из всех перечисленных интерфейсов, наиболее компактная и выразительная сортировка в Haskell и Rust. Можем ли мы перенести ее в JavaScript?

Кортежей в JS нет, но для этих целей можно использовать массивы, так как JS позволяет хранить разные типы в массивах. Оберточных типов нет, но мы можем выбрать нужные типы и определить их форму в функции сравнения. Как это будет выглядеть?

sortBy(array, (employee) => [{ reverse: employee.salary }, employee.id]);

Определяем линейный порядок в JavaScript

Для того чтобы использовать сортировку по ключу, нужно для начала определиться как сравнивать ключи. Так как в JavaScript нет приемлимого встроенного порядка, нет интерфейсов, Trait-ов и typeclass-ов, то необходимо выбрать достаточное подмножество сравнений для которых будет определен полный порядок, или сравнение будет неуспешным.

Определяем с нуля:

  1. null меньше всех значений. Это альтернативно использованию типа Maybe или Option.

  2. Если типы разные, сравнение бросает ошибку.

  3. Особое значение NaN меньше всех других чисел.

  4. Остальные числа, строки, були и BigInt сравниваются между собой как определено в JavaScript.

  5. Массивы сравниваются используя лексикографический порядок, рекурсивно сравнивая элементы.

  6. Если оба значения имеют форму { reverse: xxx }, то значение xxx будет рекурсивно сравниваться в обратном порядке. Это равносильно использованию Down / Reverse

  7. Если оба значения имеют форму { localeCompare: sss, collator: ccc }, строки sss сравниваются используя коллатор ccc. Коллаторы в обоих значений должны быть равны.

  8. Все остальное бросает ошибку.

Из-за строгости определения, здесь должно быть достаточно ограничений чтобы сравнение удовлетворяло линейному порядку или было неуспешным. Этого подмножества должно хватить для того чтобы решать все возможные задачи сортировки.

Как только мы выбрали интерфейс для сортировки и определили линейный порядок, осталось дело за малым воплотить это в виде библиотеки: better-cmp

Бонус: почему я не использовал библиотеку X?

  • orderBy: не смотря на "Inspired by Angular's orderBy filter", эта библиотека довольно хороша. Но я предпочел пойти дальше.

  • thenby: довольно хорошая библиотека, копирует интерфейс Java для комбинации компараторов, но я решил копировать другой язык из-за эргономики.

  • multisort: _

    if (/[^\(\r\n]*\([^\(\r\n]*\)$/.test(nextKey)) {    var indexOfOpenParenthesis = nextKey.indexOf("(");    var args = JSON.parse("[" + nextKey.slice(indexOfOpenParenthesis+1, -1) + "]");    nextKey = nextKey.slice(0, indexOfOpenParenthesis);}
    

Заключение

  • Надеюсь что этот обзор интерфейсов сортировок в разных языках был вам полезен, и что в будущем вам легче будет разобраться как сортировать данные по многим критериям.

  • Довольно странно что для такой распространенной операции как сортировка разные языки используют разные интерфейсы.

  • Ещё более странно странно что в "текущем году" в JavaScript нет широко известной и адекватной сортировки по ключу.

  • Лучшее решение для JavaScript что смог сделать теперь воплощено в виде библиотеки better-cmp, доступной на npm.

Подробнее..

Как разложить фото, видео по папкам, исходя из их дат, используя python

01.10.2020 10:13:11 | Автор: admin

Всем знакомы завалы из фото и видео, кои покоятся годами после копирования с устройств. Особенно это характерно для iphone,ipad, которые при прямом копировании (без itunes) создают
залежи медиаконтента. Как это все разложить по годам-месяцам?
Да, есть синхронизация, да, можно сразу все сортировать. Но
Кто-то предпочитает ничего не трогать, так как соблюдается единство свалки, кто-то делает робкие попытки разложить все накопленное хотя бы по годам.

Бесспорно, через проводник, используя табличный вид, вручную не составит труда все это это раскидать, но начинаешь смотреть старые фото, и процесс затягивается.
Поэтому напишем простую программу, которая разложит файлы в папке по годам с месяцами в них:



Программа сама будет определять дату, заглядывая в дату изменения файла:



Почему используем дату изменения, а не дату создания файла?
Как правило, она более корректно указывает на дату файла, чем ее тезка.

Импорт модулей на старте:
import os,timeimport datetimeimport shutil


Предложим пользователю скопировать путь (windows) к папке с файлами:
p=input('Скопируйте сюда путь к фото. Например: E:/\1')os.chdir(p)


Введем функцию создания папок с месяцами от 01 до 12 (да простят мне отсутствие f' строк):
#создаем папки месяцев от 01 до 12def d():    for x in range (1,13):        if x>9:            if not os.path.exists(str(x)):                os.makedirs(str(x))        else:            if not os.path.exists('0'+str(x)):                os.makedirs('0'+str(x))


Следующая функция обработает дату, полученную с фото/видео файла:
def mod_date(file):    t = os.path.getmtime(file)    return datetime.datetime.fromtimestamp(t)


Теперь, пройдясь по папке, программа соберет все расширения файлов, а заодно,
определит какой год у файла. Для каждого года будет создана своя папка, а в ней,
в свою очередь, будут созданы папки с месяцами:
a=[] #['AAE', 'MOV', 'JPG', 'PNG']for root, dirs, files in os.walk(p):        for file in files:        if file[-3:] not in a:            a.append(file[-3:])        if file[-3:] in a:            year=str(mod_date(file))[:10][:4]                        if not os.path.exists(year):                os.makedirs(year)            os.chdir(p+'/'+year)                        d()            os.chdir(p)

*Таким образом можно раскидать по папкам файлы с совершенно разными (любыми) расширениями, а не только jpeg,mov,mkv.

Еще раз пройдемся по папке со свалкой фото, теперь уже перенося фото в соответствующие, вновь созданные папки:
try:    for root, dirs, files in os.walk(p):            for file in files:                if file[-3:] in a:                    year=str(mod_date(file))[:10][:4]                                        month=str(mod_date(file))[:10][5:7] #месяц создания фото                    shutil.move(file, year+'/'+month+'/'+file) #перенос файла в папкуexcept EnvironmentError:    ('Вроде готово')


Так как программа завершается с ошибкой, в цикле не найдя последнего файла, что не влияет на ее корректное выполнение, используется костыль из try,except, который притупляет бдительность впечатлительных особ, получающих красноту в консоль.

ps. Пост не претендует на научность, но, возможно, кому-то поможет победить свалки фото/видео.

Программа скачать.
Подробнее..

Золушка от LEGO машина на основе ИИ и Raspberry Pi рассортирует детальки за вас

22.01.2021 16:14:24 | Автор: admin

Конструктор LEGO нередко используют для создания корпуса какого-нибудь механизма с движком на малинках. Чаще всего этот тандем используется в различных роботах, дронах, вездеходах. Энтузиаст Дэниел Уэст (Daniel West) пошел другим путем и создал машину с участием Raspberry Pi и LEGO для автоматической сортировки деталей этого конструктора. Естественно, на основе искусственного интеллекта. Без ИИ, наверное, и утюги скоро работать не смогут.

Под катом описание механизма работы сортировщика, а также еще несколько любопытных проектов на базе малинок.

Интересно, что сама машина для сортировки создана из 10 000 блоков LEGO! На ее создание ушло два года.


Эта машина настоящая Золушка от LEGO. Она в состоянии отсортировать любую деталь конструктора в один из 18 контейнеров со скоростью один кубик за две секунды. Более того, сортировщик в состоянии распознать каждый из когда-либо созданных блоков LEGO, включая те, которые ему еще не попадались. Эта универсальность отличает систему от ранее созданных машин похожего назначения.

Что под капотом



Машина работает на следующем железе:

  • Raspberry Pi 3, модель B+;
  • Модуль камеры Raspberry Pi V2;
  • 9 движков (управляемых через мультиплексор сервопривода, взаимодействующего с Raspberry Pi по I2C);
  • 6 двигателей LEGO (управляемые контроллерами электромоторы L298N с использованием цифровых I/O-портов на Raspberry Pi).

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

Обучение нейросети


Свою нейросеть Дэниел Уэст обучил, используя изображения 3D-моделей кубиков LEGO. При этом разработчик столкнулся с проблемой нехватки данных для обучения нейросети. Реальных качественных изображений было недостаточно, а синтетические изображения не давали корректных результатов. В итоге только комбинация синтетических и реальных изображений помогла добиться успеха. Нейросеть смогла с высокой точностью распознавать кубики LEGO, даже если ранее не взаимодействовала с ними.

К слову, для сбора данных энтузиаст оставил машину прогонять детальки через сканер на несколько дней. В итоге собрал датасет из приблизительно 300 000 изображений элементов LEGO без маркировки для обработки ИИ. Подробнее о работе ИИ и его обучении Дениэл рассказал в отдельном очень наглядном видео и описал процесс в тексте.

Лишь часть из 300 000 изображений, которые получил разработчик.

В качестве софта энтузиаст использовал Blender открытое ПО для создания трехмерной компьютерной графики и Tensor Flow, открытую программную библиотеку для машинного обучения от Google. Также в работе ему помогло сообщество мейкеров из конструктора LEGO Rebrickable.

Run, деталька, run


Разработка настоящая конвейерная машина в миниатюре. Масса деталек по гусеничному конвейеру поступает в так называемое входное ведро. Здесь детальки идут одна за другой, чтобы на опознание поступал строго один блок LEGO.


Порядок достигается за счет вибрирующей платформы, которая работает на моторчике LEGO. Вибрируя, платформа распределяет детальки, добиваясь, чтобы они не лежали друг на друге и поступали на сканирование по одной.

Модуль камеры Raspberry Pi захватывает видео каждого блока, которое обрабатывает Raspberry Pi 3 Model B+ и отправляет по беспроводной сети на более мощный компьютер, где оперирует нейронная сеть, классифицируя детальки. Обработанные нейросетью данные отправляются обратно в сортировочную машину, чтобы она могла вытолкнуть деталь в один из 18 контейнеров, используя ряд самоуправляемых шлюзов.

Пока проект больше подходит под рубрику Не пытайтесь повторить это дома, поскольку автор проделал огромную работу по обучению ИИ. Но, согласитесь, штука интересная.

Raspberry Pi в деле


А вот еще несколько последних интересных проектов с участием малинки.

Сканер пленки RoboScan



Работать с пленкой все сложнее сказывается все увеличивающаяся временная пропасть между технологиями. В проекте под названием RocoScan используется Raspberry Pi с цифровой зеркальной камерой. Устройство не только сканирует изображение со старой пленки, но и автоматизирует процесс записи изображений в отдельную папку.

Корпус для сервера в стиле Minecraft



Этот светящийся знакомый всем блок руды из игры Minecraft на самом деле является сервером Minecraft! Внутри Raspberry Pi 4 вместе с SSD на 128 ГБ, на котором работает Paper MC SMP. Красота!

Отрезатель корочек



Устройство, которое мы заслужили! Если вы любитель идеальных сэндвичей, вы знаете, что в них нет места поджаренным и твердым корочкам. Эта машина на малинке исключит из вашей жизни рутинное избавление от бутербродных несовершенств.

Автоматизированный курятник



Очевидно, что это можно использовать не только для курятников. Но один энтузиаст автоматизировал открытие и закрытие дверей курятника, чтобы защитить свое хозяйство ночью. В основе Raspberry Pi и несколько таймеров, которые инициируют открытие и закрытие дверей утром и вечером. А ваш курятник работает на питоне?

Есть ли у вас любимый проект на малинке? Делитесь в комментариях!

Подробнее..

Вот это скорость! Как мы подружили наш UBA-модуль с ClickHouse и что из этого вышло

02.02.2021 10:16:21 | Автор: admin
В прошлом году мы выпустили мажорную версию своего продукта Solar Dozor 7. В новую версию нашей DLP-системы вошел модуль продвинутого анализа поведения пользователей UBA. При его создании мы попробовали разные базы данных, но по совокупности критериев (о них скажем ниже) в итоге остановились на ClickHouse.

Освоить ClickHouse местами было непросто, многое стало для нас откровением, но главное преимущество этой СУБД затмевает все её недостатки. Как вы поняли из заголовка, речь о скорости. По этому параметру ClickHouse оставляет далеко позади традиционные коммерческие базы данных, которые мы в своих продуктах, в том числе в Solar Dozor, тоже используем.

В общем, если вы давно хотели, но никак не решались попробовать, изучите наш опыт, он может вам пригодиться.


Кадры из мультфильма Турбо (2013 год)

О модуле UBA и его архитектуре


Принцип работы модуля UBA в том, что он анализирует активность сотрудников в реальном времени, проверяя корпоративную почту, и формирует личный профиль устойчивого поведения пользователя. В случае отклонений Solar Dozor сообщает о них, чтобы можно было вовремя заметить нехарактерные действия сотрудников.

Все данные, которые нужны UBA-модулю, лежат в ClickHouse. Его мы ставим заказчику на ту же машину, куда инсталлируем и сам Solar Dozor. В базе храним не письма, а метаданные сообщений, то есть кто, когда, с кем переписывался, какова тема письма, какие вложения оно содержит и т. д. Время хранения можно настраивать, нам для расчетов нужен 90-дневный период. Поддержкой UBA-модуля занимаемся мы, частично это могут делать и админы клиента. В любом случае задача разработчиков максимально автоматизировать администрирование БД.

Идем дальше. Основную работу делает UBA-сервер, который мы писали на Clojure. Он обрабатывает данные, лежащие в ClickHouse, и производит расчеты. UBA-сервер запоминает последнюю дату для обработанных данных и периодически проверяет, есть ли в ClickHouse более свежие данные, чем в расчете. Если есть, то старые результаты удаляются и производится перерасчет.

Еще один компонент системы модуль Indexer, написанный на Scala. Он умеет работать с разными источниками данных. В случае с UBA у Indexer две задачи. Первая вытаскивать метаданные писем пользователей из основной БД и отправлять их в ClickHouse. Вторая выступать механизмом буферизации и грузить данные пачками. Когда перейдем к подробностям работы с ClickHouse, я расскажу об этом подробнее.

Для визуализации информации мы активно используем Grafana как при разработке, так и при добавлении новых фич в готовый продукт. Конечно, мы хотим перетащить все в свой интерфейс, но пока от этой палочки-выручалочки отказаться сложно. На некоторые графики в Grafana мы потратим пару часов, а разработчику понадобилась бы неделя, чтобы сделать то же самое стандартными средствами. Обычно это непозволительная роскошь. Поэтому, если дизайнеры не очень сильно придираются к цвету графика или ширине надписи, Grafana это спасение, ведь время у разработчиков расписано по минутам. Хотя это дополнительный софт, и в случае с некоторыми нашими клиентами иногда все упирается в сертификацию.

Сейчас вокруг ClickHouse появляются дополнительные средства разработки. В частности, мы используем Metabase это удобное средство прототипирования и быстрого моделирования расчетов.

Скорость. Я скорость!


Сначала несколько слов о том, какими критериями мы руководствовались, выбирая СУБД для UBA-модуля. Нас интересовали:

  • стоимость лицензии;
  • скорость обработки;
  • минимальный объем хранения;
  • скорость разработки;
  • минимальное администрирование;
  • минимальные требования к железу.


По первым четырем пунктам ClickHouse уверенно обошел конкурентов, и мы остановились на нем. Поговорим о главном преимуществе ClickHouse, ну, кроме того, что он бесплатный :-)

Скорость, скорость и еще раз скорость. Это главное, почему мы взяли его на борт. С ClickHouse вы сможете обрабатывать миллион записей в секунду на относительно скромных мощностях. Традиционные базы для такого требуют куда более серьезного железа. Скорость работы объясняется несколькими причинами:

  • Принципиально иной метод хранения данных ClickHouse делает их компрессию, архивирует и хранит по колонкам. Соответственно, нагрузка на диск снижается.
  • В ClickHouse распараллеливание задач на несколько потоков не требует дополнительных усилий. СУБД использует все доступные процессоры сервера без вмешательства админа. Если в случае с традиционной базой для этого придется серьезно заморочиться, то ClickHouse делает это по умолчанию. Нам, наоборот, приходится его ограничивать, чтобы остальным сервисам что-то осталось.
  • ClickHouse использует специальные инструкции процессора SSE, AVX, благодаря чему быстро перелопачивает большие объемы данных в оперативке. Тут логика простая: будучи созданным недавно, ClickHouse рассчитан на новое железо и его новые возможности.


Благодаря этому UBA-модуль может быстро строить аналитику по сообщениям пользователя и искать отклонения. В традиционных базах данных несколько миллионов записей будут обрабатываться достаточно долго, в ClickHouse при правильно написанном запросе это можно сделать за секунды.

ClickHouse дает преимущества и на этапе разработки благодаря его быстроте мы можем постоянно проводить эксперименты по обработке данных и проверять гипотезы. И не тратим на это кучу времени.

Какую сборку выбрать


ClickHouse разработали в Яндексе изначально для своих нужд. Но тогда собственные сборки они не выпускали. Это делала сторонняя иностранная компания Altinity.

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

Обновления выходят довольно часто, но с ними нужно быть осторожными. В каждой новой версии ClickHouse есть новые фишки, исправления, но, как следствие, и новые баги. Разработчики Яндекса не очень переживают, если новая версия может привести к проблемам с совместимостью. Да, для нас это проблема, а они могут не заморачиваться и добавлять новые функции, исходя из своих потребностей и не тестируя все возможные сочетания функций. Но по мере внедрения ClickHouse в большем количестве крупных компаний отношение разработчиков Яндекса к клиентам постепенно смягчается.

Изначально ClickHouse был NoSQL-СУБД, но теперь он понимает SQL. Это тоже добавило нам немного проблем. Мы использовали прежний вариант, а потом некоторые старые команды поменяли свой смысл. (Оффтоп: лучше не забывать выносить код SQL-запросов из основного кода приложения. Иначе потребуется доработка исходника при самых тривиальных изменениях. Если этого не сделать на этапе разработки, то в нашем случае при необходимости исправить тот или иной запрос у клиента придется ждать выхода новой версии продукта).

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



Эгоист и альтруист одновременно


С традиционными базами данных история простая: настроили использовать 20 Гб памяти они будут их использовать и никому не отдадут. С ClickHouse все иначе. Резервировать память под него не получится. Он будет использовать все, что найдет. Но и умеет делиться ClickHouse отдает память, если в данный момент она ему не нужна. С одной стороны, эта особенность позволяет нам развернуть на одной машине несколько сервисов. А с другой стороны, нам приходится ограничивать ClickHouse, так как другие модули Solar Dozor тоже хотят кушать, а он делится памятью только тогда, когда самому не надо. Поэтому прописываем такие параметры:

<max_memory_usage>
<max_memory_usage_for_user>
<max_memory_usage_for_all_queries>

<max_bytes_before_external_sort>
<max_bytes_before_external_group_by>

Число потоков max_threads также влияет на потребление. Поэтому можно поколдовать и с этим параметром. Он определяет параллельность работы ClickHouse. Если уменьшим ее в два раза, то и потребление памяти при параллельных операциях тоже снизится в два раза.

Как я уже сказал, обычно клиент выделяет нам под Solar Dozor одну машину, на ней, кроме UBA, установлены и все остальные модули. Поэтому у истории с бескорыстным ClickHouse есть и обратная сторона. Другой софт может сожрать всю отданную память, и тому уже ничего не достанется, придет OOM Killer. Конечно, было бы хорошо резервировать под ClickHouse определенный объем памяти, но пока такой функции нет.

О правильном секционировании и удачной сортировке


Мы секционировали табличку с метаданными сообщений (кто, кому, когда, с какой темой, какие вложения, размер) по дням. Вообще, для ClickHouse это очень мелкое дробление, но у нас большой объем данных. Поэтому в наших условиях день это оптимальная единица и с точки зрения структуры данных, и с точки зрения администрирования системы.



Таблицу расчетов мы секционировали по месяцам. Понятно, что их объем меньше, чем объем самих данных, поэтому тут агрегация по месяцам удобнее.

Общее правило простое: не нужно делать слишком много секций, даже если кажется, что ваш случай точно требует мелкого дробления данных. Больше секций больше файлов на диске, а значит, операционная система будет тупить. Если нам нужно что-то быстро отобразить в интерфейсе, вытаскивать большой объем данных из одного файла быстрее, чем из множества.

С сортировкой своя история. Данные столбца физически хранятся в отдельном файле в сжатом виде в порядке, указанном в параметре сортировки. При хорошем сжатии файл получается небольшим, и чтение с диска занимает минимальное время. Если данные отсортировать правильно, то одинаковые значения будут храниться рядом, а алгоритмы компрессии ClickHouse хорошо сожмут их. Данные всех столбцов должны быть физически отсортированы в одном и том же порядке. Поэтому, если в таблице много столбцов, надо выбирать, по какому набору столбцов нужно сделать сортировку. Если скомпоновать и сжать эти данные неправильно, интерфейс или пакетная обработка будут тормозить.

И несколько слов о запросах. Их условия должны содержать поле секционирования. Оптимизатор запросов в ClickHouse пока далек от того, что есть в других базах (например, PostgreSQL и Oraсle). Он не понимает зависимости данных между столбцами. Чтобы минимизировать объемы данных, считываемых с диска, нужно явно указывать, какие диапазоны данных нужны для запроса. Условие запроса для этого должно содержать границы данных по условию секционирования. В идеале чтобы каждый запрос доставал данные из одной секции, то есть указываем: сходи в конкретный день и ищи только там.

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

Любитель есть большими порциями


Если до этого вы работали только с традиционными базами данных, придется перестраиваться. С ClickHouse не прокатит каждый раз вставлять по строчке: он не любит частых вставок. Если у нас много источников данных и каждый вставляет по одной строчке, то ClickHouse становится плохо. То есть, например, он выдерживает 100 вставок в секунду. Вы спросите: Как же так? 100 вставок и все?.. А где же миллион в секунду, о котором говорили? Оказывается, ClickHouse сделан так, что он может пережить 100 вставок в секунду, а в каждой вставке при этом 10 000 строк. Вот вам и тот самый миллион.

Вообще, для себя мы выработали правило: данные нужно вставлять не чаще чем раз в 10 секунд. Так мы получаем необходимую скорость и стабильную работу.

Но нужна промежуточная буферизация, которая накопит этот миллион. Этим у нас как раз занимается Indexer, который я уже упоминал.



В Clickhouse есть такая фишка, как буферные таблицы, но это полумера. С одной стороны, они позволяют волшебным образом исправить ситуацию с частыми вставками без переделки серверного кода. На нашем железе в буферную таблицу можно вставлять в 10 раз чаще, чем в обычную. Но при этом память приходится распределять вручную. Для каждой буферной таблицы нужно назначить заранее определенное число и размер буферов. И использовать эту память под что-то другое будет нельзя. Хорошо бы угадать с этими параметрами сразу, иначе эти таблицы придется пересоздавать.

Поэтому самый правильный вариант буферизация в приложении, что мы и сделали на этапе разработки. Несмотря на эти танцы с бубном, оно того стоит: в традиционной базе данных вставить даже 1000 строк в секунду, скорее всего, не получится даже на очень хорошем железе.

Про мутации


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

В традиционных базах данных вставил строчку, удалил строчку сразу видишь результат. Тут все иначе. В ClickHouse пишешь команду удаления, она ставится в очередь мутаций, и через некоторое время будет выполнена. То есть по факту это выглядит так: вот данные есть, и сейчас они еще есть, до сих пор есть, а теперь раз и исчезли. Данные могут измениться в любой момент и по другой причине: например, в результате оптимизации или дедупликации число строк может уменьшиться. В ClickHouse нет физических первичных и уникальных ключей. Поэтому в таблицах всегда есть дубли (а если нет, то будут). Данные могут никогда не схлопнуться и/или никогда не дедуплицироваться. Кстати, опция FINAL не работает, если есть незаконченные мутации.

За скорость приходится платить дополнительными телодвижениями разработчиков в коде надо предусмотреть обработку задержек на выполнение мутации, чтобы пользователя это никак не коснулось. В частности, нужно писать код (запросы, логику обработки данных) так, чтобы не падать, если данные не соответствуют идеальному представлению о них.



У нас исходные данные, которые хранятся в ClickHouse, не удаляются и не меняются (за исключением добавления новых данных и удаления старых по партициям). Меняются только расчеты. Мы пересчитываем результаты при появлении новых данных, и у нас могут измениться алгоритмы расчетов при установке новой версии. Все это не требует построчных изменений в данных (операции update и delete). Поэтому в нашем случае очень длинных очередей мутаций не бывает.

Не злоупотребляйте словарями


В ClickHouse есть такой интерфейс словари, куда можно положить любую команду, которая вытащит список из какого-то источника. Например, если нужно залезть во внешний файл со списком сотрудников организации или в Active Directory.

Словари нужны для таких меняющихся данных, как должность, телефон, семейное положение сотрудника и т. п. Если их корректное отображение критично, то словарь необходим. Все, что не меняется, нужно класть в обычные таблицы ClickHouse. Наиболее удобным для нас оказался словарь в JSON, получаемый через http-запрос, самый естественный и самый надежный. Пишем команду сходить на такой-то сервер и взять то, что нам нужно.

В других БД все это сделать сложнее, надо писать специальную программу, которая будет доставать списки из внешних источников. В ClickHouse никаких дополнительных действий не нужно. Он достанет данные из внешнего источника и будет работать с ними как с таблицей.

Словари нужно создавать, поддерживать, дебажить. Но надо помнить, что каждый словарь дополнительная зависимость от внешнего источника и потенциальное место возникновения проблемы, если при запросе окажется, что с источником что-то не так.

Как повысить надежность?


В отличие от традиционных баз данных ClickHouse не гарантирует сохранность всех данных на все 100%. Вообще, для решения этой задачи существуют специальные механизмы транзакций, откатов изменений и восстановления после сбоев. В ClickHouse все это либо не реализовано, либо сделано в минимальном объеме. Это тоже своего рода плата за скорость. Впрочем, если сильно заморочиться, то можно повысить надежность. Но придется строить кластер систему из нескольких серверов, на которые мы установим ClickHouse и сервис для распределенных систем ZooKeeper. Будем делать бэкапы, репликацию данных. Очевидно, что это потребляет дополнительные ресурсы, место на дисках, производительность и т. д.

Тут надо обратить внимание на три момента.
  1. Проектирование
    Если спроектировать кластер неправильно, отказ любого компонента может привести к отказу всего кластера. В каждом конкретном случае выбор схемы будет разным. И нужно понимать, от каких аварий конкретная схема защищает, а от каких нет. Но это тема для отдельной статьи.
  2. Обслуживание
    Все процедуры надо четко описать и протестировать. Ну и вообще, не забывать про золотое правило: работает не трогай!
  3. Тестирование изменений на идентичном стенде
    Любые изменения и обновления надо проверять не на уже работающей системе, а на тестовой. Потому что, если что, смотри пункт 2.

В общем, средства повышения надежности совершенно точно понижают производительность, а если накосячить, то и саму надежность.

Нам пока не приходилось сталкиваться с таким запросом от заказчика. Но когда-то это наверняка произойдет, и мы готовимся к такому варианту.

В любом случае тут все упирается в ваши возможности: стоимость железа, сетевой инфраструктуры, обучения персонала и т. д. нужно соизмерять с реальными потребностями в высокой доступности. Если таких ресурсов нет, может быть, повышенная надежность не так уж и нужна? Понятно, что ClickHouse история не про банковские или другие критичные данные.

И напоследок: проверьте железо заранее


Казалось бы, железо без SSE 4.2 сейчас почти не встретить. Но однажды нам достался мощнейший сервер с процессором, который эти инструкции не поддерживает. А для ClickHouse поддержка SSE 4.2 одно из системных требований. Оказалось, что закончился старый проект, железо хорошее, не выбрасывать же.

Яндекс рекомендует выделять под ClickHouse отдельный сервер как минимум с 30 Гб оперативки. В наших условиях никто не даст под БД отдельное железо. Как я уже говорил, на одном сервере у заказчиков крутится весь Solar Dozor со всеми его модулями и их компонентами. Но, если все настроить правильно, полет пройдет нормально.

В общем, в нашем случае ClickHouse оказался хорошей альтернативой традиционным СУБД. Ему не нужны серьезные мощности, чтобы показывать впечатляющие результаты. ClickHouse делает более удобным процесс разработки, но к нему нужно привыкнуть, подружиться с его особенностями и реально оценивать уровень его возможностей.

Автор: Леонид Михайлов, ведущий инженер отдела проектирования Solar Dozor
Подробнее..

Сортировка выбором

06.07.2020 02:17:13 | Автор: admin
Всем привет. Эту статью я написал специально к запуску курса Алгоритмы и структуры данных от OTUS.



Введение


Сортировка массива является одной из первых серьезных задач, изучаемых в классическом курсе Алгоритмы и структуры данных дисциплины computer science. В связи с этим задачи на написание сортировок и соответствующие вопросы часто встречаются на собеседованиях на позиции стажера или junior разработчика.

Постановка задачи


Традиционно стоит начать изложение решений задачи с ее постановки. Обычно задача сортировки предполагает упорядочивание некоторого массива целых чисел по возрастанию. Но на самом деле, это является некоторым упрощением. Излагаемые в этом разделе алгоритмы можно применять для упорядочивания массива любых объектов, между которыми установлено отношение порядка (то есть про любые два элемента можно сказать: первый больше второго, второй больше первого или они равны). Упорядочивать можно как по возрастанию, так и по убыванию. Мы же воспользуемся стандартным упрощением.

Сортировка выбором


Одной из простейших сортировок является сортировка выбором.

Описание алгоритма


Сортировка массива выбором осуществляется так: массив делится на две части. Одна из частей называется отсортированной, а другая неотсортированной. Алгоритм предполагает проход по всему массиву с тем, чтобы длина отсортированной части стала равна длине всего массива. В рамках каждой итерации мы находим минимум в неотсортированной части массива и меняем местами этот минимум с первым элементом неотсортированной части массива. После чего мы увеличиваем длину отсортированной части массива на единицу. Пример осуществления одной итерации представлен ниже:
1 3 5 | 8 9 6 -> 1 3 5 6 | 9 8

Реализация


Предлагаю посмотреть на реализацию данного алгоритма на языке C:
void choiseSortFunction(double A[], size_t N){    for(size_t tmp_min_index = 0; tmp_min_index < N;                                  tmp_min_index++) {        //ищем минимум        for(size_t k = tmp_min_index + 1; k < N; k++) {            if (A[k] < A[tmp_min_index]) {                double min_value = A[k];                A[k] = A[tmp_min_index];                A[tmp_min_index] = min_value;            }        }    }}


Анализ


Предлагаю проанализировать данный алгоритм. Тело внутреннего цикла само по себе выполняется за O(1), то есть не зависит от размера сортируемого массива. Это означает, что для понимания асимптотики алгоритма необходимо посчитать сколько раз выполняется это тело. На первой итерации внешнего цикла имеют место (n 1) итераций внутреннего цикла. На второй итерации внешнего цикла (n 2) итерации внутреннего цикла. Продолжая это рассуждение и далее, мы приходим к следующему:

$T(n) = (n - 1) * O(1) + (n - 2) * O(1) + ... + O(1) = O((n - 1) + (n - 2) + ... + 1) = O((n - 1) * n / 2) = O(n ^ 2)$



В процессе вычислений, мы воспользовались сначала свойствами О нотации, а затем формулой для вычисления суммы арифметической прогрессии.

Для порядка необходимо оценить еще и дополнительную память, которая требуется для выполнения алгоритма. Здесь все гораздо проще: мы выделяли память только для счетчиков цикла и переменной буфера, позволяющей обменивать 2 элемента массива местами. Поэтому:

$M(n) = O(1)$



В результате анализа мы пришли к тому, что временная сложность алгоритма зависит от размера входного массива квадратично. Поэтому данную сортировку относят к классу квадратичных сортировок. Результат анализа не зависит от содержания массива: он верен в лучшем, в худшем и в среднем случае.

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

Двусторонняя сортировка выбором


Некоторый интерес может представлять оптимизация алгоритма, реализованного выше: во время прохода по неотсортированной части массива можно параллельно с минимальным элементом искать максимальный. Таким образом после итерации можно уменьшать неотсортированную часть массива не на единицу, а на двойку. Асимптотического улучшения алгоритма не происходит, но тем не менее скорость его выполнения может незначительно увеличиться, число сравнений ведь также увеличивается в два раза.

Рекурсивная сортировка выбором


В качестве упражнения можно попробовать написать алгоритм не с использованием цикла, а с использованием рекурсии. На java это может выглядеть следующим образом:
public static int findMin(int[] array, int index){    int min = index - 1;    if(index < array.length - 1) min = findMin(array, index + 1);    if(array[index] < array[min]) min = index;    return min;}  public static void selectionSort(int[] array){    selectionSort(array, 0);}  public static void selectionSort(int[] array, int left){    if (left < array.length - 1) {        swap(array, left, findMin(array, left));        selectionSort(array, left+1);    }}  public static void swap(int[] array, int index1, int index2) {    int temp = array[index1];    array[index1] = array[index2];    array[index2] = temp;}


Итоги


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



Если вы хотите подробнее узнать о курсе, приглашаю всех на бесплатный вебинар, который пройдет уже 10 июля.


Подробнее..

Сортировка вставками

09.07.2020 12:23:49 | Автор: admin
Всем привет. Сегодня продолжаем серию статей, которые я написал специально к запуску курса Алгоритмы и структуры данных от OTUS.



Введение


Сортировка массива является одной из первых серьезных задач, изучаемых в классическом курсе Алгоритмы и структуры данных дисциплины computer science. В связи с этим задачи на написание сортировок и соответствующие вопросы часто встречаются на собеседованиях на позиции стажера или junior разработчика.

Постановка задачи


Традиционно стоит начать изложение решений задачи с ее постановки. Обычно задача сортировки предполагает упорядочивание некоторого массива целых чисел по возрастанию. Но на самом деле, это является некоторым упрощением. Излагаемые в этом разделе алгоритмы можно применять для упорядочивания массива любых объектов, между которыми установлено отношение порядка (то есть про любые два элемента можно сказать: первый больше второго, второй больше первого или они равны). Упорядочивать можно как по возрастанию, так и по убыванию. Мы же воспользуемся стандартным упрощением.

Сортировка вставками


В прошлый раз мы поговорили об одной из простейших сортировок сортировке выбором. Сегодня речь пойдет о несколько более сложном алгоритме сортировке вставками.

Описание алгоритма


Сортировка массива вставками осуществляется так: также как и в случае сортировки выбором массив делится на две части. Одна из частей называется отсортированной, а другая неотсортированной. Алгоритм предполагает проход по всему массиву с тем, чтобы длина отсортированной части стала равна длине всего массива. В рамках каждой итерации мы берем первый элемент неотсортированной части массива и осуществляем с ним следующую операцию: пока наш элемент строго меньше чем предыдущий меняем их местами. После чего увеличиваем длину отсортированной части массива на единицу. Таким образом путем последовательного перемещения изучаемого элемента мы добиваемся того, чтобы он встал на свое место. Пример осуществления одной итерации представлен ниже:
1 3 5 | 2 9 6 -> 1 3 2 5 9 6 -> 1 2 3 5 9 6 -> 1 2 3 5 | 9 6

Реализация


Предлагаю посмотреть на реализацию данного алгоритма на языке C:

void insertionSortFunction(double array[], int size) {    int i, j, temp;    // i представляет длину отсортированной части массива, начинаем с 1, потому что один элемент сам по себе считается упорядоченным    for (i = 1; i < size; i++) {        temp = array[i];        for (j = i - 1; j >= 0; j--) {            if (array[j] < temp) {                break;            }              array[j + 1] = array[j];            array[j] = temp;        }    }}


Анализ


Предлагаю проанализировать данный алгоритм.

Начать анализ проще всего будет с получения асимптотики памяти. Независимо от длины и структуры предлагаемого для сортировки массива выделяется память только для двух счетчиков цикла и одной вспомогательной переменной, служащей для осуществления обмена двух переменных значениями. Таким образом всегда верно:

$M(n) = O(1)$

.

Со временем все несколько интереснее. Тело внутреннего цикла само по себе выполняется за O(1), то есть не зависит от размера сортируемого массива. Это означает, что для понимания асимптотики алгоритма необходимо посчитать сколько раз выполняется это тело. Но количество итераций внутреннего цикла зависит от того, насколько хорошо упорядочены (или не упорядочены) элементы сортируемого массива. Для осуществления анализа необходимо посмотреть несколько случаев.

Минимальное количество итераций достигается в том случае, если сортируемый массив уже отсортирован. Действительно, для каждой итерации внешнего цикла for происходит ровно одна итерация внутреннего цикла. Это так называемый лучший случай.

$T(n) = (n - 1) * O(1) = O(n)$

Таким образом, сортировка осуществляется за линейное время.

В худшем случае число итераций предполагается наибольшим, то есть break никогда не срабатывает. На первой итерации внешнего цикла осуществляется одна итерация внутреннего цикла. На второй итерации внешнего цикла осуществляется 2 итерации внутреннего цикла. Продолжая рассуждение дальше, можно прийти к тому, что на последней ((n 1) ой) итерации внешнего цикла выполниться (n 1) итерация внутреннего цикла. Получаем:

$T(n) = O(1) + 2 * O(1) + 3 * O(1) + ... + (n - 1) * O(1) = O(1 + 2 + 3 + ... + (n - 1)) = O(n * (n - 1) / 2) = O(n ^ 2)$

Для осуществления вычислений мы воспользовались свойствами О нотации и формулой суммы арифметической прогрессии.

В среднем случае предполагается, что число итераций внутреннего цикла для какой-то конкретной итерации внешнего цикла равно его среднему значению, то есть математическому ожиданию. Предположим, что все допустимые числа срабатываний внутреннего цикла равновероятны. В таком случае, среднее число итераций внутреннего цикла равно image. Предполагается, что i это номер итерации внешнего цикла. Теперь для подсчета асимптотики необходимо вычислить image. То есть мы просто подсчитываем сколько раз выполняется тело внутреннего цикла. Таким образом, получаем image.

Если подводить итоги, то асимптотика алгоритма по памяти

$O(1)$

по времени в лучшем случае

$O(n)$

и в среднем и в худшем случаях

$O(n^2)$

Поэтому данную сортировку относят к классу квадратичных сортировок.

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

Итоги


Мы рассмотрели еще одну квадратичную сортировку: сортировку вставками, посмотрели на ее устойчивую реализацию. Сортировка является преимущественно учебной, хотя на практике она может применяться благодаря неплохой асимптотике в лучшем случае: если к достаточно большому упорядоченному объему данных понадобится добавить новые данные так, чтобы все данные были опять упорядочены, может пригодится внутренний цикл for. Таким образом, можно поддерживать за

$O(n)$

упорядоченность объема данных.



Узнать о курсе подробнее.


Подробнее..

Быстрая сортировка

25.10.2020 18:16:57 | Автор: admin
Всем привет. Сегодня продолжаем серию статей, которые я написал специально к запуску курса Алгоритмы и структуры данных от OTUS. По ссылке вы сможете подробно узнать о курсе, а также бесплатно посмотреть запись Demo-урока по теме: Три алгоритма поиска шаблона в тексте.



Введение


Сортировка массива является одной из первых серьезных задач, изучаемых в классическом курсе Алгоритмы и структуры данных дисциплины computer science. В связи с этим задачи на написание сортировок и соответствующие вопросы часто встречаются на собеседованиях на позиции стажера или junior разработчика.

Постановка задачи


Традиционно стоит начать изложение решений задачи с ее постановки. Обычно задача сортировки предполагает упорядочивание некоторого массива целых чисел по возрастанию. Но на самом деле, это является некоторым упрощением. Излагаемые в этом разделе алгоритмы можно применять для упорядочивания массива любых объектов, между которыми установлено отношение порядка (то есть про любые два элемента можно сказать: первый больше второго, второй больше первого или они равны). Упорядочивать можно как по возрастанию, так и по убыванию. Мы же воспользуемся стандартным упрощением.

Быстрая сортировка


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

Описание алгоритма


Алгоритм быстрой сортировки является рекурсивным, поэтому для простоты процедура на вход будет принимать границы участка массива от l включительно и до r не включительно. Понятно, что для того, чтобы отсортировать весь массив, в качестве параметра l надо передать 0, а в качестве r n, где по традиции n обозначает длину массива.

В основе алгоритма быстрой сортировке лежит процедура partition. Partition выбирает некоторый элемент массива и переставляет элементы участка массива таким образом, чтобы массив разбился на 2 части: левая часть содержит элементы, которые меньше этого элемента, а правая часть содержит элементы, которые больше или равны этого элемента. Такой разделяющий элемент называется пивотом.

Реализация partiion'а:
partition(l, r):
pivot = a[random(l ... r - 1)]
m = l
for i = l ... r - 1:
if a[i] < pivot:
swap(a[i], a[m])
m++
return m


Пивот в нашем случае выбирается случайным образом. Такой алгоритм называется рандомизированным. На самом деле пивот можно выбирать самым разным образом: либо брать случайный элемент, либо брать первый / последний элемент учатка, либо выбирать его каким-то умным образом. Выбор пивота является очень важным для итоговой сложности алгоритма сортировки, но об этом несколько позже. Сложность же процедуры partition O(n), где n = r l длина участка.

Теперь используем partition для реализации сортировки:

Реализация partiion'а:
sort(l, r):
if r - l = 1:
return
m = partition(l, r)
sort(l, m)
sort(m, r)


Крайний случай массив из одного элемента обладает свойством упорядоченности. Если массив длинный, то применяем partition и вызываем процедуру рекурсивно для двух половин массива.

Если прогнать написанную сортировку на примере массива 1 2 2, то можно заметить, что она никогда не закончится. Почему так получилось?

При написании partition мы сделали допущение все элементы массива должны быть уникальны. В противном случае возвращаемое значение m будет равно l и рекурсия никогда не закончится, потому как sort(l, m) будет вызывать sort(l, l) и sort(l, m). Для решения данной проблемы надо массив разделять не на 2 части (< pivot и >= pivot), а на 3 части (< pivot, = pivot, > pivot) и вызывать рекурсивно сортировку для 1-ой и 3-ей частей.

Анализ


Предлагаю проанализировать данный алгоритм.

Временная сложность алгоритма выражается через нее же по формуле: T(n) = n + T(a * n) + T((1 a) * n). Таким образом, когда мы вызываем сортировку массива из n элементов, тратится порядка n операций на выполнение partition'а и на выполнения себя же 2 раза с параметрами a * n и (1 a) * n, потому что пивот разделил элемент на доли.

В лучшем случае a = 1 / 2, то есть пивот каждый раз делит участок на две равные части. В таком случае: T(n) = n + 2 * T(n / 2) = n + 2 * (n / 2 + 2 * T(n / 4)) = n + n + 4 * T(n / 4) = n + n + 4 * (n / 4 + 2 * T(n / 8)) = n + n + n + 8 * T(n / 8) =. Итого будет log(n) слагаемых, потому как слагаемые появляются до тех пор, пока аргумент не уменьшится до 1. В результате T(n) = O(n * log(n)).

В худшем случае a = 1 / n, то есть пивот отсекает ровно один элемент. В первой части массива находится 1 элемент, а во второй n 1. То есть: T(n) =n + T(1) + T(n 1) = n + O(1) + T(n 1) = n + O(1) + (n 1 + O(1) + T(n 2)) = O(n^2). Квадрат возникает из-за того, что он фигурирует в формуле суммы арифметической прогрессии, которая появляется в процессе расписывания формулы.

В среднем в идеале надо считать математическое ожидание различных вариантов. Можно показать, что если пивот делит массив в отношении 1:9, то итоговая асимптотика будет все равно O(n * log(n)).

Сортировка называется быстрой, потому что константа, которая скрывается под знаком O на практике оказывается достаточно небольшой, что привело к широкому распространению алгоритма на практике.

Читать ещё:




Подробнее..

Из песочницы Функциональное программирование на Python для самых маленьких Часть 1 Lambda Функция

22.06.2020 10:10:48 | Автор: admin
image

Я решил написать эту серию статей ибо считаю что никто не должен сталкиваться с той стеной непонимания с которой столкнулся я где для того чтобы понять что то в Функциональном Программировании (Далее ФП) тебе надо уже знать многое в ФП. Эту статью я старался написать максимально просто настолько понятно чтобы ее суть мог уловить мой племянник школьник который сейчас делает свои первые шаги в Python

Небольшое введение


Для начала давайте разберемся что такое функциональное программирование, в чем его особенности, зачем оно было придумано и где и как его использовать. Стоп А зачем? Об этом написаны тонны материалов да и в этой статье судя по всему эта информация не особо нужна. Эта статья написана для того чтобы научились разбираться в коде который написан в функциональном стиле. Но если вы все таки хотите разобраться в истории Функционального Программирования и разобраться в том как оно работает под капотом то советую вам почитать о таких вещах как

  • Чистая Функция
  • Функции высшего порядка

Но для понимания того что сказано в этой статье знать это не обязательно.

Итак, начнем


Для начала надо понять следующее что такое Функциональное Программирование вообще. Лично я знаю две самые часто упоминаемые парадигмы в повседневном программировании это ООП и ФП.

Если упрощать совсем и объяснять на пальцах то описать эти две парадигмы можно следующим образом:

  • ООП это Объектно Ориентированное Программирование парадигма в которой пишут функции и методы аргументами которых являются Объекты каких то классов
  • По такой логике можно установить что ФП это парадигма в которой пишут функции и методы аргументами которых являются другие Функции все понятно. Ответ скрыт в самом названии

Как говорил мой любимый учитель zverok Виктор Шепелев вся работа в программировании это работа с данными взял какие то данные, поигрался с ними и вернул обратно.

Это относится и к ФП взял какие то данные, взял какую то функцию, поигрался с ними и выдал что то на выходе.

Не стану расписывать все ибо это будет оооочень долго цель данной статьи это помочь разобраться а не объяснить все и как что работает поэтому тут мы рассмотрим основные функции из ФП.

В большинстве своем ФП (как я его воспринимаю) это просто упрощенное написание кода. Любой код написанный в функциональном стиле может быть довольно легко переписан в обычном без потери качества но более примитивно. Цель ФП заключается в том чтобы писать код более простой, понятный и который легче поддерживать а также который занимает меньше памяти ну и куда же без этого разумеется главная новая мораль программирования DRY (Dont Repeat Yourself Не повторяйся).

Сейчас мы с вами разберем одну из основных функций которые применяются в ФП Lambda функцию.

В следующих статьях мы разберем такие функции как Map, Zip, Filter и Reduce.

Lambda функция


Lambda это инструмент в python и других языках программирования для вызова анонимных функций. Многим это скорее всего ничего не скажет и никак не прояснит того как она работает поэтому я расскажу вам просто механизм работы lambda выражений.

Все очень просто.

Рассмотрим пример. Например нам надо написать функцию которая бы считала площадь круга при известном радиусе.

Формула площади круга это

S = pi*(r**2)

где
S это площадь круга
pi математическая константа равная 3.14 которую мы получим из стандартной библиотеки Math
r радиус круга единственная переменная которую мы будем передавать нашей функции

Круг с радиусом

Теперь оформим это все в python

import math #Подключаем библиотеку mathpi_const = round(math.pi, 2) #округляем pi до второго знака после запятой иначе она будет выглядеть как 3.141592653589793 а нам это будет неудобно# Пишем функцию которая будет вычислять площадь круга по заданному радиусу в обычном варианте записиdef area_of_circle_simple(radius):  return pi_const*(radius**2)print(area_of_circle_simple(5))print(area_of_circle_simple(12))print(area_of_circle_simple(26))>>>78.5>>>452.16>>>2122.64

Вроде бы неплохо но это все может выглядеть куда круче если записывать это через lambda

import math #Подключаем библиотеку mathpi_const = round(math.pi, 2) #округляем pi до второго знака после запятой иначе она будет выглядеть как 3.141592653589793 а нам это будет неудобно# Пишем функцию которая будет вычислять площадь круга по заданному радиусу в функциональном стилеarea_of_circle_by_lambda = lambda radius: pi_const*(radius**2) print(area_of_circle_by_lambda(5))print(area_of_circle_by_lambda(12))print(area_of_circle_by_lambda(26))>>>78.5>>>452.16>>>2122.64

Для полноты картины покажем как вызывать lambda функцию анонимно

import math #Подключаем библиотеку mathpi_const = round(math.pi, 2) #округляем pi до второго знака # после запятой иначе она будет выглядеть # как 3.141592653589793 а нам это будет неудобноprint((lambda radius: pi_const*(radius**2))(5))print((lambda radius: pi_const*(radius**2))(12))print((lambda radius: pi_const*(radius**2))(26))>>>78.5>>>452.16>>>2122.64

Что бы вы понимали анонимный вызов функции подразумевает то что вы используете её нигде не объявляя как в примере выше.

Лямбда функция работает по следующему принципу

func = lambda перечисляются аргументы через запятую : что то с ними делаетсяprint(func(передаем аргументы))>>>получаем результат того что находится после двоеточия двумя строками выше

Рассмотрим пример с двумя входными аргументами. Например нам надо посчитать объем конуса по следующей формуле:

V = (height*pi_const*(radius**2))/3

Конус с габаритами

Запишем это все в python:

import math #Подключаем библиотеку mathpi_const = round(math.pi, 2) #округляем pi до второго знака после запятой иначе она будет выглядеть как 3.141592653589793 а нам это будет неудобно#Формула объема конуса в классической форме записиdef cone_volume(height, radius):  volume = (height*pi_const*(radius**2))/3  return volumeprint(cone_volume(3, 10))>>>314.0

А теперь как это будет выглядеть в lambda форме:

import math #Подключаем библиотеку mathpi_const = round(math.pi, 2) #округляем pi до второго знака после запятой иначе она будет выглядеть как 3.141592653589793 а нам это будет неудобно#Формула объема конуса в лямбда записиcone_volume = lambda height, radius : (height*pi_const*(radius**2))/3print(cone_volume(3, 10))>>>314.0

Вообще количество переменных никак не ограничено. Для примера посчитаем объем усеченного конуса где у нас учитываются 3 разные переменные.

Объем усеченного конуса считается по формуле:

V = (pi_const*height*(r1**2 + r1*r2 + r2**2))/3

Усеченный конус с габаритами

И вот как это будет выглядеть в python классически

import math #Подключаем библиотеку mathpi_const = round(math.pi, 2) #округляем pi до второго знака после запятой иначе она будет выглядеть как 3.141592653589793 а нам это будет неудобно#Формула объема усеченного конуса в классической записиdef cone_volume(h,r1,r2):  return (pi_const * h * (r1 ** 2 + r1 * r2 + r2 ** 2))/3print(cone_volume(12, 8, 5))print(cone_volume(15, 10, 6))print(cone_volume(20, 12, 9))>>>1620.24>>>3077.20>>>6970.8

А теперь покажем как это будет выглядеть в lambda но при этом не будем объявлять функцию заранее а опишем ее в момент вывода:

import math #Подключаем библиотеку mathpi_const = round(math.pi, 2) #округляем pi до второго знака после запятой иначе она будет выглядеть как 3.141592653589793 а нам это будет неудобноprint((lambda height, radius1, radius2 : (height*pi_const*(radius1**2 + radius1*radius2 + radius2**2))/3)(12, 8, 5))print((lambda height, radius1, radius2 : (height*pi_const*(radius1**2 + radius1*radius2 + radius2**2))/3)(15, 10, 6))print((lambda height, radius1, radius2 : (height*pi_const*(radius1**2 + radius1*radius2 + radius2**2))/3)(20, 12, 9))>>>1620.24>>>3077.20>>>6970.8

После того как мы разобрались как работает lambda функция давайте разберем еще кое что интересное что можно делать с помощью lambda функции что может оказаться для вас весьма неожиданным Сортировку

Сортировать одномерные списки в python с помощью lambda довольно глупо это будет выглядеть как бряцание мускулами там где оно совсем не нужно
Ну серьезно допустим у нас есть обычный список (не важно состоящий из строк или чисел) и нам надо его отсортировать тут же проще всего использовать встроенную функцию sorted()
И в правду, давайте посмотрим на это

new_int_list = [43,23,56,75,12,32] # Создаем список чиселprint(sorted(new_int_list)) # Сортируем список чиселnew_string_list = ['zum6z', 'yybt0', 'h1uwq', '2k9f9', 'hin9h', 'b0p0m'] # Создаем список строкprint(sorted(new_string_list)) # Сортируем список строк>>>[12, 23, 32, 43, 56, 75]>>>['2k9f9', 'b0p0m', 'h1uwq', 'hin9h', 'yybt0', 'zum6z']

В таких ситуациях действительно хватает обычного sorted() (ну или sort() если вам нужно изменить текущий список на месте без создания нового изменив исходный)

Но что если нужно отсортировать список словарей по разным ключам? Тут может быть запись как в классическом стиле так и в функциональном. Допустим у нас есть список книг вселенной Песни Льда и Пламени с датами их публикаций и количеством страниц в них.
Как всегда начнем с классической записи.

# Создали список из словарей книгasoiaf_books = [  {'title' : 'Game of Thrones', 'published' : '1996-08-01', 'pages': 694},  {'title' : 'Clash of Kings', 'published' : '1998-11-16', 'pages': 761},  {'title' : 'Storm of Swords', 'published' : '2000-08-08', 'pages': 973},  {'title' : 'Feast for Crows', 'published' : '2005-10-17', 'pages': 753},  {'title' : 'Dance with Dragons', 'published' : '2011-07-12', 'pages': 1016}]# Функция по получению названия книгиdef get_title(book):    return book.get('title')# Функция по получению даты публикации книгиdef get_publish_date(book):    return book.get('published')# Функция по получению количества страниц в книгеdef get_pages(book):    return book.get('pages')# Сортируем по названиюasoiaf_books.sort(key=get_title)for book in asoiaf_books:  print(book)print('-------------')# Сортируем по датамasoiaf_books.sort(key=get_publish_date)for book in asoiaf_books:  print(book)print('-------------')# Сортируем по количеству страницasoiaf_books.sort(key=get_pages)for book in asoiaf_books:  print(book)>>>{'title': 'Clash of Kings', 'published': '1998-11-16', 'pages': 761}>>>{'title': 'Dance with Dragons', 'published': '2011-07-12', 'pages': 1016}>>>{'title': 'Feast for Crows', 'published': '2005-10-17', 'pages': 753}>>>{'title': 'Game of Thrones', 'published': '1996-08-01', 'pages': 694}>>>{'title': 'Storm of Swords', 'published': '2000-08-08', 'pages': 973}>>>------------->>>{'title': 'Game of Thrones', 'published': '1996-08-01', 'pages': 694}>>>{'title': 'Clash of Kings', 'published': '1998-11-16', 'pages': 761}>>>{'title': 'Storm of Swords', 'published': '2000-08-08', 'pages': 973}>>>{'title': 'Feast for Crows', 'published': '2005-10-17', 'pages': 753}>>>{'title': 'Dance with Dragons', 'published': '2011-07-12', 'pages': 1016}>>>------------->>>{'title': 'Game of Thrones', 'published': '1996-08-01', 'pages': 694}>>>{'title': 'Feast for Crows', 'published': '2005-10-17', 'pages': 753}>>>{'title': 'Clash of Kings', 'published': '1998-11-16', 'pages': 761}>>>{'title': 'Storm of Swords', 'published': '2000-08-08', 'pages': 973}>>>{'title': 'Dance with Dragons', 'published': '2011-07-12', 'pages': 1016}

А теперь перепишем это все через lambda функцию

# Создали список из словарей книгasoiaf_books = [  {'title' : 'Game of Thrones', 'published' : '1996-08-01', 'pages': 694},  {'title' : 'Clash of Kings', 'published' : '1998-11-16', 'pages': 761},  {'title' : 'Storm of Swords', 'published' : '2000-08-08', 'pages': 973},  {'title' : 'Feast for Crows', 'published' : '2005-10-17', 'pages': 753},  {'title' : 'Dance with Dragons', 'published' : '2011-07-12', 'pages': 1016}]# Сортируем по названиюasoiaf_books.sort(key=lambda book: book.get('title'))for book in asoiaf_books:  print(book)print('-------------')# Сортируем по датамasoiaf_books.sort(key=lambda book: book.get('published'))for book in asoiaf_books:  print(book)print('-------------')# Сортируем по количеству страницasoiaf_books.sort(key=lambda book: book.get('pages'))for book in asoiaf_books:  print(book)>>>{'title': 'Clash of Kings', 'published': '1998-11-16', 'pages': 761}>>>{'title': 'Dance with Dragons', 'published': '2011-07-12', 'pages': 1016}>>>{'title': 'Feast for Crows', 'published': '2005-10-17', 'pages': 753}>>>{'title': 'Game of Thrones', 'published': '1996-08-01', 'pages': 694}>>>{'title': 'Storm of Swords', 'published': '2000-08-08', 'pages': 973}>>>------------->>>{'title': 'Game of Thrones', 'published': '1996-08-01', 'pages': 694}>>>{'title': 'Clash of Kings', 'published': '1998-11-16', 'pages': 761}>>>{'title': 'Storm of Swords', 'published': '2000-08-08', 'pages': 973}>>>{'title': 'Feast for Crows', 'published': '2005-10-17', 'pages': 753}>>>{'title': 'Dance with Dragons', 'published': '2011-07-12', 'pages': 1016}>>>------------->>>{'title': 'Game of Thrones', 'published': '1996-08-01', 'pages': 694}>>>{'title': 'Feast for Crows', 'published': '2005-10-17', 'pages': 753}>>>{'title': 'Clash of Kings', 'published': '1998-11-16', 'pages': 761}>>>{'title': 'Storm of Swords', 'published': '2000-08-08', 'pages': 973}>>>{'title': 'Dance with Dragons', 'published': '2011-07-12', 'pages': 1016}

Таким образом lambda функция хорошо подходит для сортировки многомерных списков по разным параметрам.

Если вы повторите весь этот код самостоятельно написав его сами то я уверен что с этого момента вы сможете сказать что отныне вы понимаете как работают lambda выражения и сможете применять их в работе.

Но где же тут та самая экономия места, времени и памяти? Экономится максимум пара строк.

И вот тут мы подходим к реально интересным вещам.

Которые разберем в следующей статье где мы обсудим map функцию.
Подробнее..

Перевод Алгоритм сортировки quadsort

27.07.2020 20:17:32 | Автор: admin

Вступление


Эта статья описывает стабильный нерекурсивный адаптивный алгоритм сортировки слиянием под названием quadsort.

Четверной обмен


В основе quadsort лежит четверной обмен. Традиционно большинство алгоритмов сортировки разработаны на основе бинарного обмена, где две переменные сортируются с помощью третьей временной переменной. Обычно это выглядит следующим образом:

    if (val[0] > val[1])    {        tmp[0] = val[0];        val[0] = val[1];        val[1] = tmp[0];    }

В четверном обмене происходит сортировка с помощью четырёх подменных переменных (своп). На первом этапе четыре переменные частично сортируются в четыре своп-переменные, на втором этапе они полностью сортируются обратно в четыре исходные переменные.

                                         A         S?    F                                   ?                     ?                                  A         S         F                                                                                ?F   ?F                                                                  A         S         F                                    ?                        ?                               A         S?    F                                         

Этот процесс показан на диаграмме выше.

После первого раунда сортировки одна проверка if определяет, отсортированы ли четыре своп-переменные по порядку. Если это так, то обмен завершается немедленно. Затем проверяется, отсортированы ли своп-переменные в обратном порядке. Если это так, то сортировка завершается немедленно. Если обе проверки дают отрицательный результат, то окончательное расположение известно и остаются две проверки для определения окончательного порядка.

Это исключает одно лишнее сравнение для последовательностей, который располагаются по порядку. В то же время создаётся одно дополнительное сравнение для случайных последовательностей. Однако в реальном мире мы редко сравниваем действительно случайные данные. Поэтому когда данные скорее упорядочены, чем беспорядочны, этот сдвиг в вероятности даёт преимущество.

Существует также общее повышение производительности за счёт исключения расточительного свопа. На языке C базовый четверной своп выглядит следующим образом:

    if (val[0] > val[1])    {        tmp[0] = val[1];        tmp[1] = val[0];    }    else    {        tmp[0] = val[0];        tmp[1] = val[1];    }    if (val[2] > val[3])    {        tmp[2] = val[3];        tmp[3] = val[2];    }    else    {        tmp[2] = val[2];        tmp[3] = val[3];    }    if (tmp[1] <= tmp[2])    {        val[0] = tmp[0];        val[1] = tmp[1];        val[2] = tmp[2];        val[3] = tmp[3];    }    else if (tmp[0] > tmp[3])    {        val[0] = tmp[2];        val[1] = tmp[3];        val[2] = tmp[0];        val[3] = tmp[1];    }    else    {       if (tmp[0] <= tmp[2])       {           val[0] = tmp[0];           val[1] = tmp[2];       }       else       {           val[0] = tmp[2];           val[1] = tmp[0];       }       if (tmp[1] <= tmp[3])       {           val[2] = tmp[1];           val[3] = tmp[3];       }       else       {           val[2] = tmp[3];           val[3] = tmp[1];       }    }

В случае, если массив не может быть идеально разделён на четыре части, хвост из 1-3 элементов сортируется с помощью традиционного бинарного обмена.

Описанный выше четверной обмен реализован в quadsort.

Четверное слияние


На первом этапе четверной обмен предварительно сортирует массив на четырёхэлементные блоки, как описано выше.

На втором этапе используется похожий подход для обнаружения упорядоченных и обратных порядков, но в блоках по 4, 16, 64 или более элементов этот этап обрабатывается как традиционная сортировка слиянием.

Это можно представить следующим образом:

main memory: AAAA BBBB CCCC DDDDswap memory: ABABABAB  CDCDCDCDmain memory: ABCDABCDABCDABCD

В первой строке четверной обмен используется для создания четырёх блоков по четыре отсортированных элемента в каждом. Во второй строке используется четверное слияние для объединения в два блока по восемь отсортированных элементов каждый в своп-памяти. В последней строке блоки объединяются обратно в основную память, и мы остаемся с одни блоком из 16 отсортированных элементов. Ниже приводится визуализация.



Эти операции действительно требуют удвоения памяти для свопа. Подробнее об этом позже.

Пропуск


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

В случае, если четыре блока упорядочены, операция слияния пропускается, так как является бессмысленной. Однако это требует дополнительной проверки if, и для случайно отсортированных данных эта проверка if становится всё более маловероятной по мере увеличения размера блока. К счастью, частота этой проверки if уменьшается вчетверо каждый цикл, в то время как потенциальная выгода каждый цикл увеличивается вчетверо.

В случае, если четыре блока находятся в обратном порядке, выполняется стабильный своп на месте.

В том случае, если только два из четырёх блоков упорядочены или находятся в обратном порядке, сравнения в самом слиянии излишни и впоследствии опускаются. Данные всё ещё нужно скопировать в своп-память, но это менее вычислительная процедура.

Это позволяет алгоритму quadsort сортировать последовательности в прямом и обратном порядке, используя n сравнений вместо n * log n сравнений.

Проверки границ


Ещё одна проблема с традиционной сортировкой слиянием заключается в том, что она тратит ресурсы на лишние проверки границ. Это выглядит следующим образом:

    while (a <= a_max && b <= b_max)        if (a <= b)            [insert a++]        else            [insert b++]

Для оптимизации наш алгоритм сравнивает последний элемент последовательности A с последним элементом последовательности B. Если последний элемент последовательности A меньше последнего элемента последовательности B, то мы знаем, что проверка b < b_max всегда будет ложной, потому что последовательность A первой полностью сливается.

Аналогично, если последний элемент последовательности A больше последнего элемента последовательности B, мы знаем, что проверка a < a_max всегда будет ложной. Это выглядит следующим образом:

    if (val[a_max] <= val[b_max])        while (a <= a_max)        {            while (a > b)                [insert b++]            [insert a++]        }    else        while (b <= b_max)        {            while (a <= b)                [insert a++]            [insert b++]        }

Слияние хвоста


При сортировке массива из 65 элементов вы в конечном итоге получаете сортированный массив из 64 элементов и сортированный массив из одного элемента в конце. Это не приведёт к дополнительной операции свопа (обмена), если вся последовательность в порядке. В любом случае, для этого программа должна выбрать оптимальный размер массива (64, 256 или 1024).

Другая проблема заключается в том, что неоптимальный размер массив приводит к лишним операциям обмена. Чтобы обойти эти две проблемы, процедура четверного слияния прерывается, когда размер блока достигает 1/8 размера массива, а остальная часть массива сортируется с помощью слияния хвоста. Основное преимущество слияния хвоста заключается в том, что оно позволяет сократить объём свопа quadsort до n/2 без существенного влияния на производительность.

Big O


Название Лучший Средний Худший Стабильный Память
quadsort n n log n n log n да n

Когда данные уже отсортированы или отсортированных в обратном порядке, quadsort совершает n сравнений.

Кэш


Поскольку quadsort использует n/2 объёма своп-памяти, использование кэша не так идеально, как сортировка на месте. Однако сортировка случайных данных на месте приводит к неоптимальному обмену. Основываясь на моих бенчмарках, quadsort всегда быстрее, чем сортировка на месте, если массив не переполняет кэш L1, который на современных процессорах может достигать 64КБ.

Wolfsort


Wolfsort это гибридный алгоритм сортировки radixsort/quadsort, который улучшает производительность при работе со случайными данными. Это в основном доказательство концепции, которое работает только с беззнаковыми 32-и 64-битными целыми числами.

Визуализация


В приведённой ниже визуализации выполняются четыре теста. Первый тест основан на случайном распределении, второй на распределении по возрастанию, третий на распределении по убыванию, четвёртый на распределении по возрастанию со случайным хвостом.

Верхняя половина показывает своп, а нижняя основную память. Цвета различаются для операций пропуска, свопа, слияния и копирования.



Бенчмарк: quadsort, std::stable_sort, timsort, pdqsort и wolfsort


Следующий бенчмарк был запущен на конфигурации WSL gcc версии 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1). Исходный код скомпилирован командой g++ -O3 quadsort.cpp. Каждый тест выполнен сто раз, и сообщается только о лучшем запуске.

По оси абсцисс время выполнения.



Таблица данных quadsort, std::stable_sort, timsort, pdqsort и wolfsort
Название Элементов Тип Лучший Средний Сравнений Порядок
quadsort 1000000 i32 0.070469 0.070635 случайный порядок
stablesort 1000000 i32 0.073865 0.074078 случайный порядок
timsort 1000000 i32 0.089192 0.089301 случайный порядок
pdqsort 1000000 i32 0.029911 0.029948 случайный порядок
wolfsort 1000000 i32 0.017359 0.017744 случайный порядок
quadsort 1000000 i32 0.000485 0.000511 возрастание
stablesort 1000000 i32 0.010188 0.010261 возрастание
timsort 1000000 i32 0.000331 0.000342 возрастание
pdqsort 1000000 i32 0.000863 0.000875 возрастание
wolfsort 1000000 i32 0.000539 0.000579 возрастание
quadsort 1000000 i32 0.008901 0.008934 возрастание ступеньками (пилой)
stablesort 1000000 i32 0.017093 0.017275 возрастание ступеньками (пилой)
timsort 1000000 i32 0.008615 0.008674 возрастание ступеньками (пилой)
pdqsort 1000000 i32 0.047785 0.047921 возрастание ступеньками (пилой)
wolfsort 1000000 i32 0.012490 0.012554 возрастание ступеньками (пилой)
quadsort 1000000 i32 0.038260 0.038343 нормальный порядок
stablesort 1000000 i32 0.042292 0.042388 нормальный порядок
timsort 1000000 i32 0.055855 0.055967 нормальный порядок
pdqsort 1000000 i32 0.008093 0.008168 нормальный порядок
wolfsort 1000000 i32 0.038320 0.038417 нормальный порядок
quadsort 1000000 i32 0.000559 0.000576 убывание
stablesort 1000000 i32 0.010343 0.010438 убывание
timsort 1000000 i32 0.000891 0.000900 убывание
pdqsort 1000000 i32 0.001882 0.001897 убывание
wolfsort 1000000 i32 0.000604 0.000625 убывание
quadsort 1000000 i32 0.006174 0.006245 убывание ступеньками
stablesort 1000000 i32 0.014679 0.014767 убывание ступеньками
timsort 1000000 i32 0.006419 0.006468 убывание ступеньками
pdqsort 1000000 i32 0.016603 0.016629 убывание ступеньками
wolfsort 1000000 i32 0.006264 0.006329 убывание ступеньками
quadsort 1000000 i32 0.018675 0.018729 случайный хвост
stablesort 1000000 i32 0.026384 0.026508 случайный хвост
timsort 1000000 i32 0.023226 0.023395 случайный хвост
pdqsort 1000000 i32 0.028599 0.028674 случайный хвост
wolfsort 1000000 i32 0.009517 0.009631 случайный хвост
quadsort 1000000 i32 0.037593 0.037679 случайная половина
stablesort 1000000 i32 0.043755 0.043899 случайная половина
timsort 1000000 i32 0.047008 0.047112 случайная половина
pdqsort 1000000 i32 0.029800 0.029847 случайная половина
wolfsort 1000000 i32 0.013238 0.013355 случайная половина
quadsort 1000000 i32 0.009605 0.009673 распределение волнами
stablesort 1000000 i32 0.013667 0.013785 распределение волнами
timsort 1000000 i32 0.007994 0.008138 распределение волнами
pdqsort 1000000 i32 0.024683 0.024727 распределение волнами
wolfsort 1000000 i32 0.009642 0.009709 распределение волнами

Следует отметить, что pdqsort не является стабильной сортировкой, поэтому он быстрее работает с данными в обычном порядке (общий порядок).

Следующий бенчмарк запускался на WSL gcc версии 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1). Исходный код скомпилирован командой g++ -O3 quadsort.cpp. Каждый тест выполнен сто раз, и сообщается только о лучшем запуске. Он измеряет производительность на массивах размером от 675 до 100000 элементов.

Ось X приведённого ниже графика это количество элементов, ось Y время выполнения.



Таблица данных quadsort, std::stable_sort, timsort, pdqsort и wolfsort
Название Элементов Тип Лучший Средний Сравнений Порядок
quadsort 100000 i32 0.005800 0.005835 случайный порядок
stablesort 100000 i32 0.006092 0.006122 случайный порядок
timsort 100000 i32 0.007605 0.007656 случайный порядок
pdqsort 100000 i32 0.002648 0.002670 случайный порядок
wolfsort 100000 i32 0.001148 0.001168 случайный порядок
quadsort 10000 i32 0.004568 0.004593 случайный порядок
stablesort 10000 i32 0.004813 0.004923 случайный порядок
timsort 10000 i32 0.006326 0.006376 случайный порядок
pdqsort 10000 i32 0.002345 0.002373 случайный порядок
wolfsort 10000 i32 0.001256 0.001274 случайный порядок
quadsort 5000 i32 0.004076 0.004086 случайный порядок
stablesort 5000 i32 0.004394 0.004420 случайный порядок
timsort 5000 i32 0.005901 0.005938 случайный порядок
pdqsort 5000 i32 0.002093 0.002107 случайный порядок
wolfsort 5000 i32 0.000968 0.001086 случайный порядок
quadsort 2500 i32 0.003196 0.003303 случайный порядок
stablesort 2500 i32 0.003801 0.003942 случайный порядок
timsort 2500 i32 0.005296 0.005322 случайный порядок
pdqsort 2500 i32 0.001606 0.001661 случайный порядок
wolfsort 2500 i32 0.000509 0.000520 случайный порядок
quadsort 1250 i32 0.001767 0.001823 случайный порядок
stablesort 1250 i32 0.002812 0.002887 случайный порядок
timsort 1250 i32 0.003789 0.003865 случайный порядок
pdqsort 1250 i32 0.001036 0.001325 случайный порядок
wolfsort 1250 i32 0.000534 0.000655 случайный порядок
quadsort 675 i32 0.000368 0.000592 случайный порядок
stablesort 675 i32 0.000974 0.001160 случайный порядок
timsort 675 i32 0.000896 0.000948 случайный порядок
pdqsort 675 i32 0.000489 0.000531 случайный порядок
wolfsort 675 i32 0.000283 0.000308 случайный порядок

Бенчмарк: quadsort и qsort (mergesort)


Следующий бенчмарк запускался на WSL gcc версии 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1). Исходный код скомпилирован командой g++ -O3 quadsort.cpp. Каждый тест выполнен сто раз, и сообщается только о лучшем запуске.

         quadsort: sorted 1000000 i32s in 0.119437 seconds. MO:   19308657 (случайный порядок)            qsort: sorted 1000000 i32s in 0.133077 seconds. MO:   21083741 (случайный порядок)         quadsort: sorted 1000000 i32s in 0.002071 seconds. MO:     999999 (возрастание)            qsort: sorted 1000000 i32s in 0.007265 seconds. MO:    3000004 (возрастание)         quadsort: sorted 1000000 i32s in 0.019239 seconds. MO:    4007580 (возрастание ступенями)            qsort: sorted 1000000 i32s in 0.071322 seconds. MO:   20665677 (возрастание ступенями)         quadsort: sorted 1000000 i32s in 0.076605 seconds. MO:   19242642 (общий порядок)            qsort: sorted 1000000 i32s in 0.038389 seconds. MO:    6221917 (общий порядок)         quadsort: sorted 1000000 i32s in 0.002305 seconds. MO:     999999 (убывание)            qsort: sorted 1000000 i32s in 0.009659 seconds. MO:    4000015 (убывание)         quadsort: sorted 1000000 i32s in 0.022940 seconds. MO:    9519209 (убывание ступенями)            qsort: sorted 1000000 i32s in 0.042135 seconds. MO:   13152042 (убывание ступенями)         quadsort: sorted 1000000 i32s in 0.034456 seconds. MO:    6787656 (случайный хвост)            qsort: sorted 1000000 i32s in 0.098691 seconds. MO:   20584424 (случайный хвост)         quadsort: sorted 1000000 i32s in 0.066240 seconds. MO:   11383441 (случайная половина)            qsort: sorted 1000000 i32s in 0.118086 seconds. MO:   20572142 (случайная половина)         quadsort: sorted 1000000 i32s in 0.038116 seconds. MO:   15328606 (распределение волнами)            qsort: sorted 1000000 i32s in 4.471858 seconds. MO: 1974047339 (распределение волнами)         quadsort: sorted 1000000 i32s in 0.060989 seconds. MO:   15328606 (стабильный)            qsort: sorted 1000000 i32s in 0.043175 seconds. MO:   10333679 (нестабильный)         quadsort: sorted    1023 i32s in 0.016126 seconds.       (random 1-1023)            qsort: sorted    1023 i32s in 0.033132 seconds.       (random 1-1023)

Показатель MO указывает количество сравнений, выполненных для 1 миллиона элементов.

В приведённом выше бенчмарке quadsort сравнивается с glibc qsort() через тот же интерфейс общего назначения и без каких-либо известных несправедливых преимуществ, таких как инлайнинг.

     random order: 635, 202,  47, 229, etc  ascending order: 1, 2, 3, 4, etc    uniform order: 1, 1, 1, 1, etc descending order: 999, 998, 997, 996, etc       wave order: 100, 1, 102, 2, 103, 3, etc  stable/unstable: 100, 1, 102, 1, 103, 1, etc     random range: time to sort 1000 arrays ranging from size 0 to 999 containing random data

Бенчмарк: quadsort и qsort (quicksort)


Этот конкретный тест выполнен с использованием реализации qsort() от Cygwin, которая под капотом использует quicksort. Исходный код скомпилирован командой gcc -O3 quadsort.c. Каждый тест выполнен сто раз, сообщается только о лучшем запуске.

         quadsort: sorted 1000000 i32s in 0.119437 seconds. MO:   19308657 (случайный порядок)            qsort: sorted 1000000 i32s in 0.133077 seconds. MO:   21083741 (случайный порядок)         quadsort: sorted 1000000 i32s in 0.002071 seconds. MO:     999999 (возрастание)            qsort: sorted 1000000 i32s in 0.007265 seconds. MO:    3000004 (возрастание)         quadsort: sorted 1000000 i32s in 0.019239 seconds. MO:    4007580 (возрастание ступенями)            qsort: sorted 1000000 i32s in 0.071322 seconds. MO:   20665677 (возрастание ступенями)         quadsort: sorted 1000000 i32s in 0.076605 seconds. MO:   19242642 (общий порядок)            qsort: sorted 1000000 i32s in 0.038389 seconds. MO:    6221917 (общий порядок)         quadsort: sorted 1000000 i32s in 0.002305 seconds. MO:     999999 (убывание)            qsort: sorted 1000000 i32s in 0.009659 seconds. MO:    4000015 (убывание)         quadsort: sorted 1000000 i32s in 0.022940 seconds. MO:    9519209 (убывание ступенями)            qsort: sorted 1000000 i32s in 0.042135 seconds. MO:   13152042 (убывание ступенями)         quadsort: sorted 1000000 i32s in 0.034456 seconds. MO:    6787656 (случайный хвост)            qsort: sorted 1000000 i32s in 0.098691 seconds. MO:   20584424 (случайный хвост)         quadsort: sorted 1000000 i32s in 0.066240 seconds. MO:   11383441 (случайная половина)            qsort: sorted 1000000 i32s in 0.118086 seconds. MO:   20572142 (случайная половина)         quadsort: sorted 1000000 i32s in 0.038116 seconds. MO:   15328606 (распределение волнами)            qsort: sorted 1000000 i32s in 4.471858 seconds. MO: 1974047339 (распределение волнами)         quadsort: sorted 1000000 i32s in 0.060989 seconds. MO:   15328606 (стабильный)            qsort: sorted 1000000 i32s in 0.043175 seconds. MO:   10333679 (нестабильный)         quadsort: sorted    1023 i32s in 0.016126 seconds.       (random 1-1023)            qsort: sorted    1023 i32s in 0.033132 seconds.       (random 1-1023)

В этом бенчмарке становится ясно, почему quicksort часто предпочтительнее традиционного слияния, он делает меньше сравнений для данных в возрастающем порядке, равномерно распределённых и для данных в убывающем порядке. Однако в большинстве тестов он показал себя хуже, чем quadsort. Quicksort также демонстрирует чрезвычайно низкую скорость сортировки данных, упорядоченных волнами. Тест с данными в случайном порядке показывает, что quadsort более чем в два раза быстрее при сортировке небольших массивов.

Quicksort быстрее в универсальных и стабильных тестах, но только потому, что это нестабильный алгоритм.
Подробнее..

Ищем максимальную разницу между соседями. User-friendly-разбор задачи по алгоритмам

08.12.2020 12:05:45 | Автор: admin
Привет, Хабр!

Давайте поговорим про алгоритмы. Новички часто воспринимают их как что-то тяжёлое, сложное и непонятное, и отчасти это правда, но алгоритмы это базис. А чем лучше вы знаете базис своей специальности, тем с большей вероятностью преуспеете в ней.



Сегодня мы посмотрим на одну красивую задачу по алгоритмам. Не будем отпугивать людей от работы с алгоритмами на самом старте, поэтому в нашем разборе не будет ни развесистых деревьев отрезков, ни разномастных оптимизаций задачи о рюкзаке, ни вероятностных тестов на простоту. User-friendly algos.

Вот задача: найти максимальную разницу между соседями.

Дан массив из N целых чисел. Он никак не упорядочен, а числа могут повторяться. Предположим, что мы отсортировали его и вычислили разницу между каждой парой последовательных элементов. Необходимо найти максимальную такую разницу и сделать это наиболее оптимальным способом.

Сложно? Можете попробовать сделать это до того, как нажмёте Читать дальше, а потом проверим решение.

Итак, поехали. Максимальная разница между соседями.

Рассмотрим пример:
Пусть дан массив из N=11 элементов.
A = [-1, -3, 10, 20, 21, 4, 3, 22, 10, -2, 15]

Cначала решим задачу наивно, это часто помогает. Мы можем сделать именно то, что от нас требует условие задачи отсортировать числа и найти разницу между соседними элементами. В зависимости от того, какую сортировку мы будем использовать, сложность решения будет варьироваться.

Если используем qsort или mergesort, то временная сложность составит O(N log N). Если нам известно, что числа распределены достаточно плотно на множестве целых чисел, то можно использовать сортировку подсчётом. Тогда мы получим O(U + N), где U разность между максимальным и минимальным элементом. Случай относительно редкий, но стоит помнить про такую возможность.

После сортировки получим массив:
As = [-3, -2, -1, 3, 4, 10, 10, 15, 20, 21, 22]
Выпишем массив разностей: D = [1, 1, 4, 1, 6, 0, 5, 5, 1, 1]
Получаем, что максимальная разница составляет 6.

Теперь подумаем, можно ли решить задачу быстрее? При переборе пар соседних элементов мы будем рассматривать много пар с маленькой разностью. Такие пары, возможно, и не смогут никогда дать наибольшую разность. И действительно, в отсортированном массиве у нас есть N-1 пара соседних чисел, разность между максимумом и минимумом пусть равна U. Тогда у наибольшей разности значение должно быть хотя бы U / (N 1). Эта оценка верна по принципу Дирихле.

Если голуби рассажены в клетки, причём число голубей больше числа клеток, то хотя бы в одной из клеток находится более одного голубя.


9 клеток содержат 10 голубей, по принципу Дирихле, хотя бы в одной клетке находятся более одного голубя (Википедия)

Пусть D[1] = As[2] As[1], D[n 1] = As[n] As[n 1], As[i] i-й элемент отсортированного массива. Тогда D[i] >= 0, D[1] + + D[N-1] = U.

Если предположить, что максимум из всех D[i] меньше U/(N-1), то вся сумма D[1] + + D[N-1] будет строго меньше U противоречие.

Отлично, мы получили нижнюю оценку на максимальную разность! Теперь попробуем как-то локализовать слишком близкие друг к другу элементы разобьём отрезок от минимального до максимального элемента на полуинтервалы длиной L=U/(N-1). Каждый элемент попадёт ровно в один полуинтервал. Получим разбиение всех элементов на непересекающиеся группы, их ещё называют батчами.

Определить, в какой именно из них попал элемент x, очень просто надо вычислить 1 + int((x a_min) / L) (нумеруем с единицы), где a_min минимальный элемент в массиве A, его можно найти за один проход по исходному массиву. Исключение составит только максимальный элемент элементы с таким значением лучше сделать отдельным батчом.

На рисунке представлено распределение из описанного выше примера. Для ясности проделаем эту процедуру руками:

U = 22 (-3) = 25, N = 11 => L = 25/(11-1) = 2.5
A = [-1, -3, 10, 20, 21, 4, 3, 22, 10, -2, 15]
(-1 (-3)) / 2.5 = 0.8 => batch = 1
(-3 (-3)) / 2.5 = 0 => batch = 1
(10 (-3)) / 2.5 = 13/2.5 = 5.2 =>batch = 6
(20 (-3)) / 2.5 = 23/2.5 = 9.2 => batch = 10
(21 (-3)) / 2.5 = 24/2.5 = 9.6 => batch = 10
(4 (-3)) / 2.5 = 7/2.5 = 2.8 => batch = 3
(3 (-3)) / 2.5 = 6/2.5 = 2.4 => batch = 3
(22 (-3)) / 2.5 = 10 => batch = 11
(10 (-3)) / 2.5 = 5.2 => batch = 6
(-2 (-3)) / 2.5 = 0.4 => batch = 1
(15 (-3)) / 2.5 = 7.2 => batch = 8



Распределение по батчам выполняется за линейное время и требует O(n) дополнительной памяти. Обратите внимание, что элементы из одного батча не могут дать максимальную разницу между двумя элементами. Мы специально подобрали его размер таким образом.

Где могут находиться два соседних по значениям элемента? Конечно же, в соседних непустых батчах! Например, на рисунке элементы из третьего и шестого батча могут идти подряд в отсортированном массиве, так как батчи между ними пустые. Понятно, что соседними будут только два элемента максимум из 3-го батча и минимум из 6-го. Аналогично, кандидатами на пару с максимальной разностью будут максимальный элемент первого батча и минимальный элемент третьего.

Выпишем все возможные пары элементов, которые могут дать наибольшую разность. Обозначим как min(i) минимальный элемент в i-й группе, как max(i) максимальный элемент.

max(1) = -1 min(3) = 3
max(3) = 4 min(6) = 10
max(6) = 10 min(8) = 15
max(8) = 15 min(10) = 20
max(10) = 21 min(11) = 22

Мы определили пары, которые стоит рассматривать. На практике необходимо сделать один проход по всем батчам, поддерживать последний непустой батч и максимальное значение в нём. Когда мы наткнёмся на следующий непустой батч, то найдём в нём минимум и попробуем обновить ответ.

Порадуемся мы решили задачу за время O(N).

На самом деле, мы использовали достаточно известную идею и по сути проделали первые шаги карманной сортировки, в оригинале её называют bucket-sort.


Элементы раскладываются по корзинам, а потом элементы в каждой корзине сортируются


В худшем случае она работает за O(n^2), но среднее время работы при достаточном количестве батчей и равномерном распределении элементов составляет O(n).

Но постойте, а как же случай, когда U=0, почему вы не рассмотрели его?, спросит внимательный читатель. Этот случай вырожденный, вот мы его и не рассмотрели, но давайте сделаем это сейчас для полноты вариантов.

Если разница между минимумом и максимумом равно нулю, то максимальная разница тоже равна нулю. Собственно, это всё.
Подробнее..

Задача о m максимумах

02.01.2021 20:04:09 | Автор: admin

Старая-старая школьно-студенческая задача... Дан массив целых чисел. Требуется найти m его максимальных (или минимальных) элементов. Когда я задаю эту задачу учащимся, то почти в каждой группе находятся "умельцы", решающие ее с помощью сортировки. В самом деле, это ведь так просто: сортируем массив по убыванию (вручную или подходящей библиотечной функцией) и просто берем m первых элементов. Такое решение всегда казалось мне алгоритмическим варварством - найти m максимумов достаточно просто за один проход массива; сортировка существенно сложнее. И однажды я решил исследовать сей вопрос вычислительными экспериментами. Результаты этих экспериментов я и предлагаю вашему вниманию. Не исключено, что кому-то результаты помогут и в практической работе. Намекну - интуиция меня в целом не подвела.

Spoiler

Без сортировки задача может быть решена, например, так. Создаем рабочий массив длины m и заполняем его начальными значениями. В общем случае можно в качестве такого значения выбрать минимальное значение int/integer для соответствующей среды программирования. А если известна нижняя граница значений исходного массива, то можно взять любое число, меньшее этой границы.

Итак рабочий массив заполнен одинаковыми значениями. Теперь берем элемент за элементом исходного массива и вставляем его в нужное место рабочего массива. При этом длину рабочего массива сохраняем равной m (после вставки последний элемент пропадает). Если очередной элемент меньше последнего значения рабочего массива, то он просто пропускается. Этот процесс имеет вычислительную сложность O(nm). Тогда как сортировка в лучшем случае описывается асимптотикой O(n*og(n)). Асимптотики показывают, как ведет себя функция (в данном случае - время сортировки) при стремлении параметров к бесконечности. Можно сказать, что время описанного алгоритма при стремлении n к бесконечности задается формулой t1=k1*O(n), а время сортировки t2=k2*O(n*log(n)). Здесь k1 и k2 - некие константы, зависящие от процессора, языка программирования, операционной системы и других факторов.

Я построил три системы тестов (для Питона, Java и VBA). Все тесты устроены по сути одинаково: строились массивы возрастающих размеров, заполнялись случайными числами задаваемого диапазона, сортировались с фиксацией времени и прогонялись через описанный выше алгоритм тоже с фиксацией времени. Каждый тест повторялся 10 раз и время усреднялось. В Питоне и Java использовалась встроенная сортировка, в VBA - реализация QuickSort.

Питон

Ниже показан код питоновских тестов.

import timefrom random import randint    def max_n_1(arr,n):    return sorted(arr,reverse=True)[0:n]    def max_n_2(arr,n):    res=[-1 for _ in range(n)]    for x in arr:        if x > res[n-1]:            i=n-1            j=i-1            while(j>=0 and res[j]<x):                res[i]=res[j]                i=i-1                j=j-1            res[i]=x    return res      def start():    k=10    n=10000    print("k=",k)    while(n<=500000):        print("n=",n,end=' ')        t1=0.0        for i in range(10):            arr=[randint(1,2000) for _ in range(n)]            start_time = time.time()            z1=max_n_1(arr,k)            fin_time = time.time()            t1=t1+(fin_time-start_time)        print(t1/10.0,end=' ')            t2=0.0        for i in range(10):             arr=[randint(1,2000) for _ in range(n)]            start_time = time.time()            z2=max_n_2(arr,k)            fin_time = time.time()            t2=t2+(fin_time-start_time)        print(t2/10.0)            n+=10000        start()

Размеры массива менялись от 10 до 500 тыс. элементов с шагом 10 тыс. Было выполнено два прогона: определение пяти и десяти максимумов. Результат для 10 максимумов показан ниже.

Время здесь приведено в миллисекундах. Что видим? Сортировка отстает (на краю интервала - вдвое). Для пяти максимумов картина аналогична. И надо заметить, что хотя питоновская сортировка очень эффективна, простой алгоритм оказывается быстрее. Заметны резкие провалы в производительности (зубцы на графиках). Они, вероятно, объясняются влиянием внутренних процессов (типа сборки мусора). Это же замечание относится и к другим графикам.

Java

Код тестов выглядел так:

import java.util.*;class Start{   public static void main(String [] args)   {       Random random = new Random();    Scanner inp = new Scanner(System.in);    long startTime,endTime,tot1,tot2;    int i,a,b,n,m,x,ii,jj,u;    a=1;    b=3000; // диапазон случайных чисел [a,b]    m=10;        System.out.println(a+" "+b+" "+m);    for (n=50000; n<=5000000; n+=50000)    {    int arr[] = new int[n];      int ma[]  = new int[m];      tot1=0;      for (u=0; u<10; u++)      {              for (i=0; i<n; i++)      {     arr[i]=a+random.nextInt(b-a+1);      }        startTime = System.currentTimeMillis();        Arrays.sort(arr);        endTime = System.currentTimeMillis();        tot1=tot1+(endTime-startTime);      }      tot2=0;      for (u=0; u<10; u++)      {              for (i=0; i<n; i++)      {      arr[i]=a+random.nextInt(b-a+1);      }           startTime = System.currentTimeMillis();      for (i=0; i<m; i++) ma[i]=-999999;      for (i=0; i<n; i++)      {            x=arr[i];                    if (x >= ma[m-1])            {              ii=m-1;              jj=ii-1;              while(jj>=0 && ma[jj]<x)              {                ma[ii]=ma[jj];                ii--;                jj--;              }                ma[ii]=x;            }          }          endTime = System.currentTimeMillis();          tot2=tot2+(endTime-startTime);        }      System.out.println(n+" "+tot1+" "+tot2);   }  } }

Здесь размер массива тоже менялся от 10 тыс. до 500 тыс. элементов. Время - в миллисекундах. Результат оказался весьма похожим на питоновский (только сортировка Javа, увы, медленнее).

VBA

В этом языке нет универсальной встроенной сортировки (можно, правда, сортировать ячейки листа, но в этом случае будут велики накладные расходы, связанные с загрузкой и выгрузкой данных). Поэтому пришлось реализовать QuickSort вручную. Все это выглядит так:

Private Declare Function GetTickCount Lib "kernel32" () As Long'::: Собственно сортировкаSub QSort(A() As Long, Optional b As Long = 1, Optional e As Long = 0)    If b > e Then Exit Sub    i& = b    j& = e    w& = A((i& + j&) / 2)    Do While (True)      Do While (A(i&) < w&)         i& = i& + 1      Loop      Do While (A(j&) > w&)         j& = j& - 1      Loop      If i& <= j& Then         Tmp& = A(i&)         A(i&) = A(j&)         A(j&) = Tmp&         i& = i& + 1         j& = j& - 1      End If      If i& > j& Then Exit Do    Loop        If j& > b Then QSort A, b, j&    If i& < e Then QSort A, i&, eEnd Sub'::: Проверка успешности сортировки Function check(X() As Long) As Boolean     n& = UBound(X)     For i& = 1 To n& - 1         If X(i& + 1) < X(i&) Then            Debug.Print "Err! i=" + CStr(i&)            check = False            Exit Function         End If     Next i&     check = TrueEnd Function'::: Вставка в упорядоченный массивSub ins_in_arr(X As Long, A() As Long, n As Integer)    If X < A(n) Then Exit Sub    For i% = 1 To n        If X > A(i%) Then           For j% = n To i% + 1 Step -1               A(j%) = A(j% - 1)           Next j%           A(i%) = X           Exit Sub        End If    Next i%End Sub'::: Собственно тестSub test()Const sz = 500Dim X() As LongDim Ma(1 To sz) As Long    Randomize    ooo& = 1    For n& = 10000 To 500000 Step 10000                t1# = 0        For nc% = 1 To 10                                ReDim X(1 To n&) As Long            For i& = 1 To n&                X(i&) = Rnd() * 5000            Next i&            s1& = GetTickCount            For i& = 1 To sz                Ma(i&) = -2147483647            Next i&            For i& = 1 To n&                ins_in_arr X(i&), Ma, 10            Next i&            s2& = GetTickCount            t1# = t1# + s2& - s1&                Next nc%                        Cells(ooo&, 1).Value = n&        Cells(ooo&, 2).Value = t1# / 10                        t2# = 0                For nc% = 1 To 10                    ReDim X(1 To n&) As Long            For i& = 1 To n&                X(i&) = Rnd() * 5000            Next i&            s1& = GetTickCount            QSort X, 1, n&            s2& = GetTickCount            If Not check(X) Then               MsgBox "Ошибка при сортировке!"               Exit Sub            End If            t2# = t2# + s2& - s1&        Next nc%        Cells(ooo&, 3).Value = t2# / 10        ooo& = ooo& + 1            Next n&End Sub

На каждом витке цикла корректность сортировки проверяется. Время проверки, естественно, не включается в общий хронометраж. Набор исходных данных тот же - от 10 до 500 тыс. целых чисел. Получает, в общем, похожая картина:

Представляет некоторый интерес изучить зависимость времени от количества искомых максимумов (при фиксированном размере массива). Здесь, очевидно, сортировка будет тем выгоднее, чем больше максимумов требуется найти. А вставка в упорядоченный массив будет тем медленнее, чем массив больше.

Самым невыгодным случаем будет являться, как ни странно, входной массив, уже упорядоченный по возрастанию. В этом случае количество сравнений при вставке достигнет максимума и будет равно n*m. Массив, упорядоченный по убыванию, напротив, весьма выгоден. Число сравнений здесь будет ~ m+n.

Описанный в самом начале статьи алгоритм, можно ускорить, если вместо простого упорядоченного массива использовать древовидную или пирамидальную структуру. Именно так и реализована в Питоне в модуле heapq функция nsmallest.

Для небольших массивов (несколько тысяч элементов и менее) разница в подходах представляется несущественной. И если нужно быстро написать код, то сортировка - вполне приемлемое решение. Для больших массивов выгоднее от сортировки отказаться.

Вот и все, что я хотел рассказать об этой задаче. Спасибо, что дочитали до конца. С наступившим 2021-м годом!

Подробнее..

PostgreSQL Antipatterns убираем медленные и ненужные сортировки

07.10.2020 20:16:52 | Автор: admin
Просто так результат SQL-запроса возвращает записи в том порядке, который наиболее удобен серверу СУБД. Но человек гораздо лучше воспринимает хоть как-то упорядоченные данные это помогает быстро сравнивать соответствие различных датасетов.

Поэтому со временем у разработчика может выработаться рефлекс Дай-ка я на всякий случай это вот отсортирую! Конечно, иногда подобная сортировка бывает оправдана прикладными задачами, но обычно такой случай выглядит как в старом анекдоте:
Программист ставит себе на тумбочку перед сном два стакана. Один с водой на случай, если захочет ночью пить. А второй пустой на случай, если не захочет.
Давайте разбираться когда сортировка в запросе точно не нужна и несет с собой потерю производительности, когда от нее можно относительно дешево избавиться, а когда сделать из нескольких одну.


#1: Нехватка work_mem


Обычно мы просто не обращаем внимания на наличие лишнего Sort-узла в плане он отрабатывает очень быстро по сравнению с самим извлечением данных. Но стоит чему-то пойти не так и перестать сортируемой выборке умещаться в памяти

SELECT generate_series(1, 1e6) i ORDER BY i;



Из-за сортировки мы начали свапаться на диск (buffers temp written), и потратили на это порядка 70% времени!

Давайте как-то ускорять. И самый простой способ, который рекомендует нам подсказка под иконкой восклицательного знака просто увеличить параметр work_mem так, чтобы памяти на сортировку все-таки хватало:

ALTER SYSTEM SET work_mem = '128MB';



На четверть быстрее, хотя мы не трогали ни текст запроса, ни структуру базы! К сожалению, такой способ не всегда допустим например, наш СБИС обслуживает одновременно тысячи клиентов в рамках одного узла PostgreSQL, и просто так раздавать память направо-налево мы не можем себе позволить. Может, есть способ вообще избавиться от сортировки?..

#2: Сортировка уже отсортированного


Начнем с самого простого варианта чтения данных из вложенного запроса:

SELECT  *FROM  (    SELECT generate_series(1, 1e6) i  ) TORDER BY  i;

Почти 2/3 всего времени выполнения заняла сортировка, хоть и происходила вся в памяти:


Но был ли в ней вообще смысл? Нет, потому что чтение из вложенного запроса сохраняет порядок записей и так. Поправим:

SELECT  *FROM  (    SELECT generate_series(1, 1e6) i  ) T;



Вроде мы ничего особенного не сделали, а запрос уже ускорился более чем в 2 раза.
Этим же свойством сохранения порядка записей обладают чтение из CTE (Common Table Expression, узел CTE Scan в плане), SRF (Set-Returning Function, Function Scan) или VALUES (Values Scan).

#3: Вложенная отладочная сортировка


Следующий пример обычно возникает в результате отладки, когда разработчик сначала проверял внутренний запрос, а потом вставил его в обвязку внешнего:

SELECT  i, 1e6 - iFROM  (    SELECT      *    FROM      generate_series(1, 1e6) i    WHERE      (i % 2, i % 3, i % 5, i % 7) = (1, 2, 4, 6)    ORDER BY -- осталось от отладки      i DESC  ) TORDER BY  i;



Мы-то понимаем, что внутренняя сортировка ни на что не влияет (в большинстве случаев), но СУБД нет. Поправим:

SELECT  i, 1e6 - iFROM  (    SELECT      *    FROM      generate_series(1, 1e6) i    WHERE      (i % 2, i % 3, i % 5, i % 7) = (1, 2, 4, 6)  ) TORDER BY  i;



Минус одна сортировка. Но вспомним предыдущий пункт насчет упорядоченности SRF, и исправим до конца:

SELECT  i, 1e6 - iFROM  generate_series(1, 1e6) iWHERE  (i % 2, i % 3, i % 5, i % 7) = (1, 2, 4, 6);



Вот и минус вторая сортировка. На данном конкретном запросе мы выиграли порядка 5%, всего лишь убрав лишнее.

#4: Index Scan вместо сортировки


Одна из классических причин неэффективности SQL-запросов, о которых я рассказывал в статье Рецепты для хворающих SQL-запросов:

CREATE TABLE tbl ASSELECT  (random() * 1e4)::integer fk -- 10K разных внешних ключей, now() - ((random() * 1e8) || ' sec')::interval tsFROM  generate_series(1, 1e6) pk;  -- 1M "фактов"CREATE INDEX ON tbl(fk); -- индекс для foreign key

То есть при разработке структуры базы мы описали FOREIGN KEY, повесили индекс на это поле, чтобы он отрабатывал быстро А потом пошли прикладные задачи.

Например, мы хотим узнать, когда был выставлен последний счет по конкретному клиенту:

SELECT  tsFROM  tblWHERE  fk = 1 -- отбор по конкретной связиORDER BY  ts DESC -- хотим всего одну "последнюю" записьLIMIT 1;



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

DROP INDEX tbl_fk_idx;CREATE INDEX ON tbl(fk, ts DESC);



Ух! Теперь весь наш запрос выполнился быстрее, чем одна только сортировка в предыдущем варианте.

#5: UNION ALL вместо сортировки


Но что делать, если от нас хотят такую сортировку, которая ну никак нормально на индекс не укладывается, хотя вроде и должна?

TRUNCATE TABLE tbl;INSERT INTO tblSELECT  CASE    WHEN random() >= 1e-5      THEN (random() * 1e4)::integer  END fk -- 10K разных внешних ключей, из них 0.0001 - NULL'ы, now() - ((random() * 1e8) || ' sec')::interval tsFROM  generate_series(1, 1e6) pk;  -- 1M "фактов"

Допустим, что нам надо показать оператору топовые 10 заявок сначала все неназначенные заявки (fk IS NULL), начиная от самых старых, а затем все его (fk = 1):

SELECT  *FROM  tblWHERE  fk IS NULL OR  fk = 1ORDER BY  fk NULLS FIRST, ts DESCLIMIT 10;



Вроде и индекс у нас есть, вроде и сортировка по нужным ключам, но как-то все некрасиво в плане Но давайте воспользуемся знанием, что чтение из вложенного запроса сохраняет порядок разделим нашу выборку на две заведомо непересекающиеся и снова склеим с помощью UNION ALL, примерно как делали это в статье PostgreSQL Antipatterns: сказ об итеративной доработке поиска по названию, или Оптимизация туда и обратно:

(  SELECT    *  FROM    tbl  WHERE    fk IS NULL  ORDER BY    fk, ts DESC  LIMIT 10)UNION ALL(  SELECT    *  FROM    tbl  WHERE    fk = 1  ORDER BY    fk, ts DESC  LIMIT 10)LIMIT 10;



И снова ни одной сортировки в плане, а запрос стал почти в 5 раз быстрее.

#6: Сортировки для оконных функций


Давайте теперь попробуем посчитать сразу по первым 10 клиентам одновременно количество заявок и время последней с помощью оконных функций:

SELECT DISTINCT ON(fk)  *, count(*) OVER(PARTITION BY fk ORDER BY ts) -- без DESC!FROM  tblWHERE  fk < 10ORDER BY  fk, ts DESC; -- хотим "последнее" значение ts



Сначала мы сортируем по (fk, ts) для вычисления оконного count(*), а потом еще раз по (fk, ts DESC) для вычисления DISTINCT.

Замечу, что если просто написать сортировку как в самом запросе count(*) OVER(PARTITION BY fk ORDER BY ts DESC), то будет, конечно, быстрее. Только вот результат неправильный везде будут одни единички.

Но ведь count, в отличие от разных first_value/lead/lag/..., вообще не зависит от порядка записей давайте просто уберем сортировку для него:

SELECT DISTINCT ON(fk)  *, count(*) OVER(PARTITION BY fk)FROM  tblWHERE  fk < 10ORDER BY  fk, ts DESC;



Так, от одной сортировки избавились. Правда, из-за этого теперь стали читать чуть больше buffers, обменяв Bitmap Heap Scan на Index Only Scan по нашему индексу, с которым совпадает целевая сортировка зато быстрее!

Хм Но ведь и оставшаяся сортировка с ним тоже совпадает. Можно ли и от нее избавиться, не нарушив корректность результата? Вполне! Для этого всего лишь укажем нужную рамку окна по всем записям (ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING):

SELECT DISTINCT ON(fk)  *, count(*) OVER(PARTITION BY fk ORDER BY ts DESC ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING)FROM  tblWHERE  fk < 10ORDER BY  fk, ts DESC;



Итого тот же результат в 2.5 раза быстрее, и без единой лишней сортировки.

Bonus: Полезные сортировки, которые не происходят


Давайте продолжим экспериментировать, и попробуем получить полный список клиентов со временем последней заявки для каждого, раз у нас есть подходящий индекс:

SELECT DISTINCT ON(fk)  *FROM  tblORDER BY  fk, ts DESC;



Прочитать почти 8GB данных ради 10K записей как-то многовато Давайте воспользуемся методикой рекурсивного DISTINCT:

WITH RECURSIVE T AS (  (    SELECT      fk    , ts    FROM      tbl    ORDER BY      fk, ts DESC    LIMIT 1 -- первая запись с минимальным ключом  )UNION ALL  SELECT    X.*  FROM    T  , LATERAL(      SELECT        fk      , ts      FROM        tbl      WHERE        fk > T.fk      ORDER BY        fk, ts DESC      LIMIT 1 -- следующая по индексу запись    ) X  WHERE    T.fk IS NOT NULL)TABLE T;



Получилось в 12 раз быстрее, потому что мы не читали ничего лишнего, в отличие от Index Only Scan. Хоть мы и использовали дважды в запросе ORDER BY, ни одной сортировки в плане так и не появилось.
Вероятно, в будущих версиях PostgreSQL для таких точечных чтений появится соответствующий тип узла Index Skip Scan. Но скоро его ждать не стоит.
Замечу, что результат этих запросов все-таки немного отличается второй не обрабатывает записи с fk IS NULL. Но кому надо извлечет их отдельно.

Знаете другие способы устранения лишних сортировок? Напишите в комментариях!
Подробнее..

Группировки и оконные функции в Oracle

24.07.2020 14:12:14 | Автор: admin
Привет, хабр! В компании, где я работаю, часто проходят (за мат извините) митапы. На одном из них выступал мой коллега с докладом об оконных функциях и группировках Oracle. Эта тема показалась мне стоящей того, чтобы сделать о ней пост.



С самого начала хотелось бы уточнить, что в данном случае Oracle представлен как собирательный язык SQL. Группировки и методы их применения подходят ко всему семейству SQL (который понимается здесь как структурированный язык запросов) и применимы ко всем запросам с поправками на синтаксис каждого языка.

Всю необходимую информацию я постараюсь кратко и доступно объяснить в двух частях. Пост скорее будет полезен начинающим разработчикам. Кому интересно добро пожаловать под кат.

Часть 1: предложения Order by, Group by, Having


Здесь мы поговорим о сортировке Order by, группировке Group by, фильтрации Having и о плане запроса. Но обо всем по-порядку.

Order by


Оператор Order by выполняет сортировку выходных значений, т.е. сортирует извлекаемое значение по определенному столбцу. Сортировку также можно применять по псевдониму столбца, который определяется с помощью оператора.

Преимущество Order by в том, что его можно применять и к числовым, и к строковым столбцам. Строковые столбцы обычно сортируются по алфавиту.

Сортировка по возрастанию применяется по умолчанию. Если хотите отсортировать столбцы по убыванию используйте дополнительный оператор DESC.

Синтаксис:

SELECT column1, column2, (указывает на название)
FROM table_name
ORDER BY column1, column2 ASC|DESC;

Давайте все рассмотрим на примерах:


В первой таблице мы получаем все данные и сортируем их по возрастанию по столбцу ID.

Во второй мы также получаем все данные. Сортируем по столбцу ID по убыванию, используя ключевое слово DESC.

В третьей таблице используется несколько полей для сортировки. Сначала идет сортировка по отделу. При равенстве первого оператора для полей с одинаковым отделом применяется второе условие сортировки; в нашем случае это зарплата.

Все довольно просто. Мы можем задать более одного условия сортировки, что позволяет более грамотно сортировать выходные списки.

Group by


В SQL оператор Group by собирает данные, полученные из базы данных в определенных группах. Группировка разделяет все данные на логические наборы, что дает возможность выполнять статистические вычисления отдельно в каждой группе.

Этот оператор используется для объединения результатов выборки по одному или нескольким столбцам. После группировки будет только одна запись для каждого значения, использованного в столбце.

С использованием оператора SQL Group by тесно связано использование агрегатных функций и оператор SQL Having. Агрегатная функция в SQL это функция, возвращающая какое-либо одно значение по набору значений столбца. Например: COUNT(), MIN(), MAX(), AVG(), SUM()

Синтаксис:

SELECT column_name(s)
FROM table_name
WHERE condition
GROUP BY column_name(s)
ORDER BY column_name(s);

Group by стоит после условного оператора WHERE в запросе SELECT. По желанию можно использовать ORDER BY, чтобы отсортировать выходные значения.

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

Решение 1 (без использования группировки):

SELECT DISTINCT    ie.department    ie.slary    FROM itx_employee ie    WHERE ie.salary = (             SELECT             max(ie1.salary)             FROM itx_employee ie1             WHERE ie.department = ie1.department             )

Решение 2 (с использованием группировки):

SELECTdepartment,max(salary)FROM itx_employeeGROUP BY department

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

Второй пример вышел короче и читабельнее, хотя выполняет такие же функции, что и первый.

Как у нас работает Group by: сначала разбивает два отдела на группы qa и dev. Потом для каждого из них ищет максимальную зарплату.

Having


Having это инструмент фильтрации. Он указывает на результат выполнения агрегатных функций. Предложение Having используется в SQL там, где нельзя применить WHERE.

Если предложение WHERE определяет предикат для фильтрации строк, то Having используется после группировки для определения логичного предиката, фильтрующего группу по значениям агрегатных функций. Предложение необходимо для проверки значений, полученных при помощи агрегатных функций из групп строк.

Синтаксис:

SELECT column_name(s)
FROM table_name
WHERE condition
GROUP BY column_name(s)
HAVING condition

Сначала мы выводим отделы со средней зарплатой больше 4000. Затем выводим максимальную зарплату с применением фильтрации.

Решение 1 (без использования GROUP BY и HAVING):

SELECT DISTINCTie.department AS "DEPARTMENT",(     (SELECT     AVG(ie1.salary)     FROM itx_employee ie1     WHERE ie1.department = ie.department)) AS "AVG SALARY"FROM itx_employee iewhere (SELECT     AVG(ie1.salary)     FROM itx_employee ie1     WHERE ie1.department = ie.department) > 4000


Решение 2 (с использованием GROUP BY и HAVING):

SELECTdepartment, AVG(salary)FROM itx_employee GROUP BY departmentHAVING AVG(salary) > 4000


В первом примере используется два подселекта: один для нахождения максимальной зарплаты, другой для фильтрации средней зарплаты. Второй пример, опять же, вышел намного проще и лаконичнее.

План запроса


Нередко бывают ситуации, когда запрос работает долго, потребляя значительные ресурсы памяти и дисков. Чтобы понять, почему запрос работает долго и неэффективно, мы можем посмотреть план запроса.

План запроса это предполагаемый план выполнения запроса, т.е. как СУБД будет его выполнять. СУБД распишет все операции, которые будут выполняться в рамках подзапроса. Проанализировав все, мы сможем понять, где в запросе слабые места и с помощью плана запроса сможем оптимизировать их.

Исполнение любого SQL предложения в Oracle извлекает так называемый план исполнения. Этот план исполнения запроса является описанием того, как Oracle будет осуществлять выборку данных, согласно исполняемому SQL предложению. План представляет собой дерево, которое содержит порядок шагов и связь между ними.

К средствам, позволяющим получить предполагаемый план выполнения запроса, относятся Toad, SQL Navigator, PL/SQL Developer и др. Они выдают ряд показателей ресурсоемкости запроса, среди которых основными являются: cost стоимость выполнения и cardinality (или rows) кардинальность (или количество строк).

Чем больше значение этих показателей, тем менее эффективен запрос.

Ниже можно увидеть анализ плана запроса. В первом решении используется подселект, во втором группировка. Обратите внимание, что в первом решении обработано 22 строки, во втором 15.

Анализ плана запроса:



Ещё один анализ плана запроса, в котором применяется два подселекта:


Этот пример приведен как вариант нерационального использования средств SQL и я не рекомендую вам его использовать в своих запросах.

Все перечисленные выше функции упростят вам жизнь при написании запросов и повысят качество и читабельность вашего кода.

Часть 2: Оконные функции


Оконные функции появились ещё в Microsoft SQL Server 2005. Они осуществляют вычисления в заданном диапазоне строк внутри предложения Select. Если говорить кратко, то окно это набор строк, в рамках которого происходит вычисление. Окно позволяет уменьшить данные и более качественно их обработать. Такая функция позволяет разбивать весь набор данных на окна.

Оконные функции обладают огромным преимуществом. Нет необходимости формировать набор данных для расчетов, что позволяет сохранить все строки набора с их уникальными ID. Результат работы оконных функций добавляется к результатирующей выборке в еще одно поле.

Синтаксис:

SELECT column_name(s)
Агрегирующая функция (столбец для вычислений)
OVER ([PARTITION BY столбец для группировки]
FROM table_name
[ORDER BY столбец для сортировки]
[ROWS или RANGE выражение для ограничения строк в пределах группы])

OVER PARTITION BY это свойство для задания размеров окна. Здесь можно указывать дополнительную информацию, давать служебные команды, например добавить номер строки. Синтаксис оконной функции вписывается прямо в выборку столбцов.

Давайте рассмотрим все на примере: в нашу таблицу добавился еще один отдел, теперь в таблице 15 строк. Мы попытаемся вывести работников, их з/п, а также максимальную з/п организации.


В первом поле мы берем имя, во втором зарплату. Дальше мы применяем оконную функцию over(). Используем её для получения максимальной зарплаты по всей организации, так как не указаны размеры окна. Over() с пустыми скобками применяется для всей выборки. Поэтому везде максимальная зарплата 10 000. Результат действия оконной функции добавляется к каждой строчке.

Если убрать из четвертой строки запроса упоминание оконной функции, т.е. остается только max (salary), то запрос не сработает. Максимальную зарплату просто не удалось бы посчитать. Так как данные обрабатывались бы построчно, и на момент вызова max (salary) было бы только одно число текущей строки, т.е. текущего работника. Вот тут и можно заметить преимущество оконной функции. В момент вызова она работает со всем окном и со всеми доступными данными.

Давайте рассмотрим еще один пример, где нужно вывести максимальную з/п каждого отдела:



Фактически мы задаем рамки для окна, разбивая его на отделы. В качестве ранжирующего примера мы указываем department. У нас есть три отдела: dev, qa и sales.

Окно находит максимальную зарплату для каждого отдела. В результате выборки мы видим, что оно нашло максимальную зарплату сначала для dev, затем для qa, потом для sales. Как уже упоминалось выше, результат оконной функции записывается в результат выборки каждой строки.

В предыдущем примере в скобках после over не было указано. Здесь мы использовали PARTITION BY, которое позволило задать размеры нашего окна. Здесь можно указывать какую-то доп информацию, передавать служебные команды, например, номер строки.

Заключение


SQL не так прост, как кажется на первый взгляд. Все описанное выше это базовые возможности оконных функций. С их помощью можно упростить наши запросы. Но в них скрыто намного больше потенциала: есть служебные операторы (например ROWS или RANGE), которые можно комбинировать, добавляя больше функциональности запросам.

Надеюсь, пост был полезен для всех интересующихся данной темой.
Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru