Как быстро заменить символы в строке

Июль 28, 2018 — Шарахов А.П.

Совсем нетрудно написать на Delphi простейший цикл, реализующий замену символов в Ansi-строке. Только есть одна проблема - это будет медленный цикл.

Как завершить расстановку ферзей (N queens completion problem)

Сентябрь 17, 2017 — Шарахов А.П.

Рассмотрим известные решения задач, связанных с расстановкой ферзей на доске NxN: завершение расстановки, конструирование расстановки, генерация всех завершений, генерация всех расстановок, в том числе с учетом симметрии.

Умножая вычеты

Август 19, 2017 — Шарахов А.П.

В известном алгоритме замены деления умножением произведение имеет двойную длину. Существует ли вариант с "коротким" произведением?

Генератор случайных чисел

Февраль 7, 2017 — Шарахов А.П.

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

Хеширование и хеш-таблицы

Январь 7, 2017 — Шарахов А.П.

Рассмотрим особенности реализации в Delphi 7 класса хеш-таблицы с открытой адресацией и линейным зондированием для хранения данных с целочисленными, строковыми и двоичными ключами, а также для работы с множествами и мультимножествами целых чисел. Исходники и текст статьи обновлены 12.05.2021.

Целочисленное умножение и обратный элемент

Декабрь 16, 2015 — Шарахов А.П.

Рассмотрим простые примеры алгоритмов, использующих обратный элемент.

Base86, формат представления данных

Февраль 1, 2015 — Шарахов А.П.

В статье предлагается новый удобный формат, использующий для текстового представления данных меньше памяти, чем Base64. Табличные алгоритмы кодирования и декодирования обеспечивают ему более высокую скорость по сравнению с Base85. Кроме того, английский текст после кодирования сохраняет некоторую читаемость, и это еще не все...

Поиск непарных чисел в массиве

Апрель 24, 2014 — Шарахов А.П.

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

Примеры использования JSON в Synopse mORMot Framework

Февраль 27, 2013 — Шарахов А.П.

Поддержка JSON довольно сильно интегрирована в mORMot. Возможности сериализации весьма широки, хотя не все из них находятся на поверхности.

Давай сделаем это медленно

Декабрь 8, 2012 — Шарахов А.П.

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

Перебор перестановок, размещений, сочетаний

Ноябрь 9, 2012 — Шарахов А.П.

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

Замечания к алгоритму Луна (Luhn algorithm)

Июль 11, 2012 — Шарахов А.П.

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

Замечания к алгоритму Верхоффа (Verhoeff algorithm)

Июль 9, 2012 — Шарахов А.П.

Известно, Верхофф (Verhoeff) поставил точку в вопросе вычисления десятичной контрольной цифры. Но слишком интригует эта тема. Примите мои 4400 чатлов.

Delphi compiler bug

Июнь 24, 2012 — Шарахов А.П.

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

Другой цикл

Июнь 9, 2012 — Шарахов А.П.

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

RadixSort, сортировка из красной книги

Май 8, 2012 — Шарахов А.П.

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

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

Май 7, 2012 — Шарахов А.П.

Особенно арифметика, не так ли? Не верится, что можно программировать, не зная целочисленной арифметики. Хотя…

Юникодная елка

Февраль 4, 2012 — Шарахов А.П.

Лишь годные дятлы собираются в стаи,
Юникодом пугая мозги января.
Их песни не стихнут, они не устанут.
А елка как кактус беспокоит меня.

Скорый поиск

Январь 13, 2012 — Шарахов А.П.

Что может быть быстрее бинарного поиска? Другой бинарный поиск.

Забыть все

Декабрь 25, 2011 — Шарахов А.П.

Есть множество маленьких хитростей, с помощью которых можно добиться быстрой работы с ANSI-строками в Delphi. Забавно, что большинство трюков основано на отказе от услуг, навязанных компилятором. Я тут кое-что записал, чтобы удержать в голове все способы заставить компилятор забыть, что мы работаем со строками.

О пользе лени

Октябрь 29, 2011 — Шарахов А.П.

Давно уже пора начать программировать, но как-то не начинается. Может быть, если еще немного подождать, все произойдет само собой? А вдруг, лениться полезно?

Реверс битов (перестановка битов в обратном порядке)

Сентябрь 13, 2011 — Шарахов А.П.

Как переставить младшие биты двойного слова в обратном порядке?

Алгоритм Grayscale на Delphi

Август 26, 2011 — Шарахов А.П.

Преобразовать цветное изображения в черно-белое (оттенки серого) можно очень быстро, потратив 3 такта CPU на пиксель.

Наибольшая возрастающая подпоследовательность (longest increasing subsequence problem)

Май 21, 2011 — Шарахов А.П.

Требуется найти в массиве чисел возрастающую подпоследовательность наибольшей длины за время O(n log n).
Статья не содержит ничего нового. Просто еще одна реализация классического алгоритма на Delphi.

Упорядочить 5 элементов за 7 сравнений

Март 13, 2011 — Шарахов А.П.

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

О QuickSort не говори

Август 9, 2010 — Шарахов А.П.

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

Эмуляция операторов SAR, ROR, ROL в Delphi

Июль 14, 2010 — Шарахов А.П.

Среди логических операторов Delphi нет операторов SAR (арифметический сдвиг вправо), ROR (циклический сдвиг вправо), ROL (циклический сдвиг влево). В качестве альтернативы отсутствующим операторам обычно используют вызовы ассемблерных функций. Но можно поступить иначе – сэмулировать их при помощи операторов Delphi. Интересно, что эмуляция оказывается примерно в 2 раза быстрее вызова ассемблерной функции.

Компиляция в ранних версиях Delphi

Октябрь 3, 2009 — Шарахов А.П.

Для программирования я использую Delphi 7. У меня нет возможности проверить все исходники с другими версиями Delphi. Скорее всего, в поздних версиях не потребуется изменений исходного кода, а в ранних версиях (обычно начиная с Delphi 4) изменения будут незначительными. Если вы любите программировать и немного знакомы с Delphi и BASM, то легко справитесь с этим, руководствуясь общими замечаниями.

Почему мне не нравится TDateTime

Сентябрь 3, 2009 — Шарахов А.П.

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

Now речь пойдет об одной функции

Август 2, 2009 — Шарахов А.П.

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