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

в 16:27, , рубрики: glibc, linux, Программирование, Разработка под Linux, сортировка

Введение

Всё началось с короткого скрипта, который должен был объединить информацию об адресах e-mail сотрудников, полученных из списка пользователей почтовой рассылки, с должностями сотрудников, полученными из базы отдела кадров. Оба списка были экспортированы в текстовые файлы в кодировке Юникод UTF-8 и сохранены с юниксовскими концами строк.

Содержимое mail.txt

Иванов Андрей;ia@example.com

Содержимое buhg.txt

Иванова Алла;маляр
Ёлкина Элла;крановщица
Иванов Андрей;слесарь
Абаканов Михаил;маляр

Для объединения файлы были отсортированы юниксовской командой sort и поданы на вход юниксовской программе join, которая неожиданно завершилась с ошибкой: 

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: is not sorted: Иванов Андрей;слесарь

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

$> sort buhg.txt
Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванова Алла;маляр
Иванов Андрей;слесарь

Выглядит как глюк сортировки в Юникоде или как проявление феминизма в алгоритме сортировки. Первое, конечно, правдоподобнее.

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

в 6:37, , рубрики: binomial heap, c++, edisonsoftware, weak heap sort, Алгоритмы, биномиальная куча, Блог компании Edison, высокая производительность, слабая куча, Совершенный код, сортировка

Сортировка слабой кучей - 1


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

При сортировке с помощью слабой кучи всегда меньше количество сравнений и обменов, чем если использовать обычную кучу. Так что да, слабая куча сильнее, чем обычная куча.Читать полностью »

в 12:00, , рубрики: cpu, CUDA, gpgpu, GPU вычисления, Nvidia, opencl, Алгоритмы, Блог компании Технологический Центр Дойче Банка, Видеокарты, высокая производительность, производительность, сортировка

Всем давно известно, что на видеокартах можно не только в игрушки играть, но и выполнять вещи, никак не связанные с играми, например, нейронную сеть обучить, криптовалюту помайнить или же научные расчеты выполнить. Как так получилось, можно прочитать тут, а я хотел затронуть тему того, почему GPU может быть вообще интересен рядовому программисту (не связанному с GameDev), как подступиться к разработке на GPU, не тратя на это много времени, принять решение, нужно ли вообще в эту сторону смотреть, и «прикинуть на пальцах», какой профит можно получить. 

Вычисления на GPU – зачем, когда и как. Плюс немного тестов - 1

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

в 11:00, , рубрики: C, c++, sort, sorting, Алгоритмы, высокая производительность, Программирование, сортировка, сортировки

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

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

в 17:10, , рубрики: Алгоритмы, Программирование, сортировка

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

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

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

в 20:09, , рубрики: Алгоритмы, Блог компании Edison, логические игры, ненормальное программирование, Программирование, сортировка, ханойская башня
Сортировка «Ханойская башня» - 1

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

в 14:56, , рубрики: IBM, ламповая электроника, перфокарты, сортировка, старое железо

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

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

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

в 16:00, , рубрики: big data, антиквариат, математика, перфокарты, сортировка, старое железо

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

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

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

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

в 9:00, , рубрики: Алгоритмы, математика, поиск, поиск ближайшего соседа, сортировка, теория графов

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

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

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

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

в 15:27, , рубрики: android, collections, devcolibri, functional, java, kotlin, sorting, джава, коллекции, никто не читает теги, Программирование, разработка, сортировка, функциональное программирование

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

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

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

1...234...7
Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js