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

void ext_sort(const std::string filename, const size_t memory)

Я использовал алгоритм из Effective Performance of External Sorting with No Additional Disk Space:

1. Разделим файл на блоки, которые помещаются в доступную память. Обозначим эти блоки Block_1, Block_2, …, Block_(S-1), Block_S. Установим P = 1.
2. Читаем Block_P в память.
3. Отсортируем данные в памяти и запишем назад в Block_P. Установим P = P + 1, и если P ≤ S, то читаем Block_P в память и повторяем этот шаг. Другими словами, отсортируем каждый блок файла.
4. Разделим каждый блок на меньшие блоки B_1 и B_2. Каждый из таких блоков занимает половину доступной памяти.
5. Читаем блок B_1 блока Block_1 в первую половину доступной памяти. Установим Q = 2.
6. Читаем блок B_1 блока Block_Q во вторую половину доступной памяти.
7. Объеденим массивы в памяти с помощью in-place слияния, запишем вторую половину памяти в блок B_1 блока Block_Q и установим Q = Q + 1, если Q ≤ S, читаем блок B_1 блока Block_Q во вторую половину доступной памяти и повторяем этот шаг.
8. Записываем первую половину доступной памяти в блок B_1 блока Block_1. Так как мы всегда оставляли в памяти меньшую половину элементов и провели слияние со всеми блоками, то в этой части памяти хранятся M минимальных элементы всего файла.
9. Читаем блок B_2 блока Block_S во вторую половину доступной памяти. Установим Q = S −1.
10. Читаем блок B_2 блока Block_Q в первую половину доступной памяти.
11. Объеденим массивы в памяти с помощью in-place слияния, запишем первую половину доступной памяти в блок B_2 блока Block_Q и установим Q = Q −1. Если Q ≥ 1 читаем блок B_2 блока Block_Q в первую половину доступной памяти и повторяем этот шаг.
12. Записываем вторую половину доступной памяти в блок B_2 блока Block_S. Аналогично шагу 8, тут хранятся максимальные элементы всего файла.
13. Начиная от блока B_2 блока Block_1 и до блока B_1 блока Block_S, определим новые блоки в файле и снова пронумеруем их Block_1 to Block_S. Разделим каждый блок на блоки B_1 и B_2. Установим P = 1.
14. Читаем B_1 и B_2 блока Block_P в память. Объеденим массивы в памяти. запишем отсортированный массив назад в Block_P и установим P = P +1. Если P ≤ S, повторяем этот шаг.
15. Если S > 1, возвращаемся к шагу 5. Каждый раз мы выделяем M минимальных и максимальных элементов, записываем их в начало и конец файла соответственно, а потом делаем то же самое с оставшимися элементами, пока не дойдем до середины файла.

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

Реализуем алгоритм на C++.

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

array.sort()

И все. Кому нужен вообще какой-то алгоритм. В задании было установлено ограничение от 0 до 100, мы же не лентяи, сделаем в общем виде, для любых значений и с повторениями чисел. Немного подумав, пришел вот к такому решению:

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

Самый простой способ – задавать порядок вручную. В физических магазинах на полках делается именно так, и это называется «выкладка». У нас её делают продавцы по планограммам под каждую точку (это входит в обучение), а в тех же больших продуктовых – специальные чуваки-мерчендайзеры, которые следят, чтобы всё было ок. В Интернете, конечно, хочется сделать так же, но метод хорош до 50 позиций.

На другой стороне шкалы методы больших данных, когда все данные о вас начиная от сборки браузера, типа девайса (точнее, его цены) и разрешения экрана, плюс все данные профиля и оценка ваших действий на сайте ведут к оптимальному результату. Самый простой способ использования таких данных – за первые 20-30 секунд нахождения на сайте строить ваш профиль и сравнивать с профилями таких же людей. И предлагать вам в итоге не самые дешёвые квартиры и отели, например, а начинать с тех цен, которые для вас будут приемлемыми. Вы наверняка знаете эту сортировку, которую почему-то подают в прессе под соусом «самой удобной для клиента».

По моим ощущениям, самая удобная для нашего покупателя – это такая, которая понятна и поддаётся контролю.

Исторически так сложилось, что комплексный компонент 1С-Битрикс не позволяет пользователю в публичной части отсортировать товары, хотя бы по цене, дате, наименованию, а также выбрать сколько товаров на странице ему выбрать. Но ни один из интернет-магазинов не обходится без такого функционала, который кстати включен в почти все шаблоны готовых интернет-магазинов в Маркетплэйс. Но для реализовать блоки «Сортировать по: ...» и «Показать по: ...» достаточно просто. Нужно всего-лишь использовать массив $_REQUEST и метод API 1С-Битрикс GetCurPageParam() для передачи данных в этот массив.

Приступим!

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

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

В данной статье постараемся это выяснить. Для обеспечения наилучших результатов все представленные алгоритмы будут сортировать целочисленный массив из 200 элементов. Компьютер, на котором будет проводится тестирование имеет следующие характеристики: процессор AMD A6-3400M 4x1.4 GHz, оперативная память 8 GB, операционная система Windows 10 x64 build 10586.36.

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

Как вам, возможно, известно, спецификация языка JavaScript не предписывает какой-то определённой реализации метода sort у массивов. Алгоритм, находящийся «под капотом», может отличаться (и отличается) в различных браузерах. Теоретически, можно представить себе ситуацию, когда от того, как именно реализована сортировка массивов в конкретном движке, зависит производительность вашего веб-приложения.
Если речь идёт о браузере с открытым исходным кодом, то можно просто открыть этот код и посмотреть, какой там использован алгоритм. Однако существуют браузеры с закрытым исходным кодом (не будем показывать пальцем). Что делать в таком случае?

Поскольку мы на Хабре, я готов предположить, что некоторые читатели уже потянулись к своим любимым дизассемблерам, в то время как некоторые другие готовятся звонить своим друзьям из одной небольшой и нетвёрдой компании. Однако сегодня мы не будем копаться в машинном коде или использовать инсайдерскую информацию. Мы будем смотреть весёлые картинки.

Привет Хабр! Недавно пришло интересное задание:

Имеется многогигабайтный файл, содержащий массив целых чисел от 1 до 10000. Элементы расположены хаотично с повторениями. Необходимо его отсортировать. Принять во внимание ограниченность в ресурсах.

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

Часть 1	Часть 2	Часть 3	Часть 4

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

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

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

ОГЛАВЛЕНИЕ:

1. Индексирование
2. Срезы
3. Сортировка

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

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

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

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

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

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

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

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


Приходится десять раз скролить список вверх и вниз, пока пытаешься установить фильтр на трёх (Дата, Товар, Клиент) полях. Работать с этим каждый день никаких нервов не хватит.

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

Но пользователи — это одна сторона медали, им такой подход удобен. А как же разработчики?
Ведь оно как должно быть: начинаешь писать в формуле имя измерения, а студия подсказки выдает, верно? Вот только в случае с допсимволами все это выглядит в коде, скажем так… не очень. В VS2017 уже сделали поиск по вхождению, а в предыдущих такого не было и приходилось писать Календарь не с буквы К, а с цифры 5, потому что 5 Календарь. Запросы в других программах приходится писать без подсказок и упомнить какая цифра у какого измерения или поля — тот еще квест.



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

Но выход есть.

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

1. Замена символов в файле
2. Уберание windows-like переносов
3. Быстрый подсчёт строк
4. Вырезать столбцы из CSV-like файла
5. Сортировка файла по столбцам
6. Разбор базы на основе ini-файла

Я использую в п. 4,6 awk. Если кто не знает, то это специализированный с-подобный язык (кстати, напоминает очень пхп) для обработки текстовых данных. Работает очень и очень быстро.

Думаю, многие знакомы с этим расширением, но всё же:

django-voting позволяет ввести оценку любой сущности по digg-принципу (+1/-1) максимум за 30 минут (с учётом включения асинхронных запросов JS).
Сайт проекта: django-voting.googlecode.com

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

Хотелось бы иметь возможность:
1. Отсортировать или отфильтровать вакансии/резюме по региону.
2. Искать по ключевому слову в названии вакансии.
3. Иметь фильтр по зарплате.
4. Сортировать по дате.

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

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

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

Итак, о чем хотел сказать. Думаю, что не плохо было бы добавить в Вакансии/Работа/Хабархабр возможность группировки вакансий не только по рубрикам, но и по регионам. Чтобы в самом начале показывались вакансии доступные в том регионе, в котором находится хаброчеловек. С моей точки зрения, это будет гораздо удобнее, нежели сейчас.

Компания Google провела эксперимент по сортировке 1 ПБ данных при помощи фреймворка MapReduce. Данные были представлены в виде 10 триллионов записей, каждая длиной 100 байт. Для сортировки были задействованы 4000 компьютеров. Этот беспрецедентный для такого типа задач объем данных удалось отсортировать за 6 часов 2 минуты.

В ходе эксперимента сотрудникам Google пришлось решать проблему с размещением 1 ПБ данных. Дело в том, что при каждом новом запуске сортировки, выходил из строя хотя бы один из 48 000 используемых жестких дисков. В итоге, было решено дать Google File System команду хранить по три копии каждого файла на разных жестких дисках.

Сортировка меньшего объема данных в 1 ТБ на 1000 компьютерах заняла 68 секунд. Этим самым в Google побили предыдущий рекорд по сортировке аналогичного объема данных, составляющий 209 секунд на 910 компьютерах.

Для сравнения, общий объем фотографий, хранимых в Facebook, составляет 1 ПБ, Большой Адронный Коллайдер будет производить 15 ПБ данных в год, а Google обрабатывает около 20 ПБ данных в день.