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

Декабрь 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 — Шарахов А.П.

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

Желающим разместить материалы этого блога на своем сайте

Май 25, 2009 — Шарахов А.П.

Автором всех материалов на этой страничке является Александр Шарахов. Некоторые материалы написаны специально для Королевства Delphi и соответственно размещены также на http://www.delphikingdom.com.

Автор приветствует размещение анонсов своих материалов на других сайтах. Автор выступает против размещения полной версии материалов на любом другом сайте, если будет нарушено хотя бы одно из следующих условий:

Параллельное вычисление CRC64

Май 25, 2009 — Шарахов А.П.

Эти заметки дополняют мою статью ”Параллельное вычисление CRC32”. Предлагается алгоритм вычисления CRC64, основанный на тех же идеях. Производительность алгоритма в 2-2.5 раза выше стандартной табличной реализации вычисления CRC64. На компьютере с процессором E6850/3.2GHz он расходует 2.66 такта процессора на байт, т.е. скорость обработки данных при вычислении CRC64 составляет 0.375 байта за такт центрального процессора или 1.2*10^9 байтов в секунду.

Параллельное вычисление CRC32

Апрель 27, 2009 — Шарахов А.П.

Предлагаю вашему вниманию еще один подход к построению алгоритмов вычисления CRC32. Хотя многие использованные в нем идеи в той или иной мере содержатся в известных руководствах по оптимизации кода для IA32 и вычислению CRC32, он может представлять некоторый интерес. Использование свойств CRC-арифметики позволило разработать алгоритм вычисления CRC32, имеющий производительность в 3-5 раз выше стандартной табличной реализации. Например, на компьютере с процессором E6850/3.2GHz он расходует 1.33 такта процессора на байт, т.е. скорость обработки данных при вычислении CRC32 составляет 0.75 байта за такт центрального процессора или 2.4*10^9 байтов в секунду.

Продолжение читайте в статье ”Параллельное вычисление CRC64”.