Рубрика «сортировка»

В продолжение темы хочу поделиться своим кодом, который обгоняет std::sort() из актуальных версий GNU C++ Library и (примерно, нет точных данных) повторяет результат "Сортировки Александреску" с CppCon 2019.

Читать полностью »

Как нетрудно догадаться, я знаю ответ на этот вопрос, но, поскольку моя статья с описанием алгоритма сортировки «воронкой» была здесь встречена, мягко говоря, нервозно, я решил провести-таки тестирование «по образу и подобию» тех, которые обычно проводятся — в основном, конечно, по материалам статей, представленных здесь же, на Хабре.

В Интернете не представлены трудные массивы для алгоритмов сортировки (мне, во всяком случае, их найти не удалось), а многочисленные «сравнительные анализы» алгоритмов на массивах в несколько сотен или тысяч элементов, просто смешны, а потому я решил прогнать «воронкой» те массивы, на которых проводились исследования с количеством элементов, по крайней мере, 10^5 и более.

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

Сортировка «Ханойская башня» - 1

Ханойские башни
Про знаменитую игру Эдуарда Люка́ на Хабре не писа́л только ленивый. Кажется, все покровы сорваны и что-то ещё по поводу алгоритма добавить уже невозможно. Но нет, у данной темы есть ещё скрытые ресурсы. Сегодня, в частности, мы переделаем алгоритм решения этой головоломки в полноценную сортировку. (Зачем? Just for fun. В пятницу можно.) Читать полностью »

Поняв, как работать с электромеханическим сортировщиком перфокарт (с точки зрения обычного пользователя), и приступая к более тесному знакомству с ним (с точки зрения инженера), – ожидаешь увидеть в нём несколько датчиков для считывания отверстий в перфокартах и с десяток манипуляторов, каждый из которых забирает перфокарту в свой карман. Однако электромеханика сортировщика намного более элегантна и проста: весь его интеллект держится на одном датчике и на одном электромагните. Как именно, читайте ниже.

Тесное знакомство с электромеханическим сортировщиком перфокарт (экскурс в начало XX века) - 1

Читать полностью »

В период 1890-1970 вся обработка больших данных осуществлялась через перфокарты. Перфокарты в свою очередь обрабатывались при помощи т.н. «регистрирующей аппаратурой», центральным звеном которой был электромеханический «сортировщик перфокарт». Перфокарты и сопутствующую аппаратуру применяли для решения самых разнообразных задач: перепись населения, бухгалтерский учёт, инвентаризация, расчёт заработной платы и т.д.

Как люди работали с перфокартами? Какому алгоритму следовал электромеханический сортировщик перфокарт? Как осуществлялась сортировка по числовым полям данных? А по строковым? Обо всём этом – ниже.

Ликбез по работе с перфокартами (или история о том, как с 1890-го по 1970-й «большие данные» обрабатывались) - 1

Читать полностью »

Обнаружен универсальный метод сортировки сложной информации - 1

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

Это пример задачи поиска "ближайшего соседа", которую широко изучают в информатике. Дан набор сведений и новая точка, и требуется найти, к какой точке из уже существующих она окажется ближайшей? Такой вопрос возникает во множестве повседневных ситуаций в таких областях, как исследование генома, поиск картинок и рекомендации на Spotify.

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

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

Мои любимые примеры функционального программирования в языке Kotlin

Читать полностью »

Экзамен в школе прапорщиков.
— Вот смотрите. Это большой палец, это — указательный, это — средний, это — безымянный, это — мизинец. Мешаем, мешаем, мешаем (двигает пальцами)… Теперь где какой?

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

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

var shuffledArr = arr.sort(function{
  return Math.random() - 0.5;
});

Сегодня я решил написать о том, какие преимущества и недостатки есть у такого подхода.
Читать полностью »

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

На мой взгляд, указатели на функции является как раз таким примером. Дело в том, что синтаксис объявления и использования указателей на функции не слишком очевиден, особенно для не очень опытных программистов, и, если сразу «сыпать» деталями и синтаксическими возможностями, то за деревьями не будет видно леса. В этом посте я хочу поделиться своим видением указателей на функции и привести простой пример, который, смею надеяться, порадует своей легкостью и убьет еще одного зайца — продемонстрирует страшного монстра под названием «полиморфный вызов».
Читать полностью »

imageДанная статья является продолжением моей статьи "Python: коллекции, часть 1: классификация, общие подходы и методы, конвертация".

В данной статье мы продолжим изучать общие принципы работы со стандартными коллекциями (модуль collections в ней не рассматривается) Python.

Для кого: для изучающих Python и уже имеющих начальное представление о коллекциях и работе с ними, желающих систематизировать и углубить свои знания, сложить их в целостную картину.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js