
Быстрый поиск
Введите фрагмент названия статьи для поиска

Поиск подстроки в строке по алгоритму Карпа-Рабина
01.06.2022 | Категория: Образ мышления: Assembler | Автор: ManHunter

Поиск подстроки в строке по алгоритму Карпа-Рабина
Когда речь заходит об алгоритмах точного поиска подстроки в строке, то обычно все так или иначе сводится к последовательному сравнению символов. Но есть группа алгоритмов, которые основаны не на сравнении символов, а на сравнении числовых данных - хешей. Одним из таких алгоритмов является алгоритм Карпа-Рабина. Его принцип достаточно простой: вычисляется хеш от строки поиска, затем вычисляется хеш от фрагмента строки, в которой производится поиск. Длина фрагмента равна длине искомой строки. Если хеши равны, то выполняется дополнительное посимвольное сравнение, если не равны, то продвигаемся по строке дальше. Казалось бы, что выигрыша тут никакого быть не может, ведь вместо сравнения вычислительные ресурсы тратятся на хеширование. Однако, как показывает практика, для поиска совпадения это гораздо эффективнее, чем сравнение отдельных символов строк. Вместо O(n*m) операций можно добиться среднего результата O(n+m), где n - длина исходной строки, а m - длина искомой строки. К тому же алгоритм Карпа-Рабина не требует выделения дополнительной памяти для своей работы.
Читать статью целиком »
Просмотров: 407 | Комментариев: 2

Алгоритм быстрой сортировки на Ассемблере
19.05.2022 | Категория: Образ мышления: Assembler | Автор: ManHunter

Алгоритм быстрой сортировки на Ассемблере
Алгоритм быстрой сортировки появился еще на заре компьютерной эпохи в 1960 году. И до сих пор он остается одним из самых быстрых универсальных алгоритмов сортировки массивов. Несмотря на некоторые недостатки в виде наличия рекурсивных вызовов, алгоритм быстрой сортировки очень прост в реализации, не требует выделения дополнительной памяти и даже может быть распараллелен между несколькими подпроцессами.
Читать статью целиком »
Просмотров: 308 | Комментариев: 0

Подгонка размеров поля EDIT под используемый шрифт
07.12.2020 | Категория: Образ мышления: Assembler | Автор: ManHunter
Много чего уже делали и с полями ввода, и со шрифтами. На очереди автоматическая подгонка высоты однострочного элемента EDIT в зависимости от размеров шрифта, который ему назначен. Это необходимо, чтобы при изменении шрифта текст в поле ввода смотрелся правильно. Высота EDIT считается по высоте выбранного шрифта плюс отступ толщиной в двойную рамку, чтобы текст при отображении эту рамку не перекрывал. В случае многострочных полей ввода высоту надо считать по высоте шрифта, умноженной на необходимое количество строк, плюс отступ.Code (Assembler) : Убрать нумерацию
- ;-------------------------------------------------------------
- ; Подгонка размера поля EDIT под заданный шрифт
- ;-------------------------------------------------------------
- ; Параметры:
- ; hEdit - хэндл поля EDIT
- ; hFont - хэндл шрифта
- ;-------------------------------------------------------------
- proc resize_edit hEdit:DWORD, hFont:DWORD
- locals
- rc RECT
- tm TEXTMETRIC
- endl
- pusha
- mov edi,[hEdit]
- ; Получить контекст устройства
- invoke GetDC,edi
- or eax,eax
- ; Поля ввода не существует, на выход
- jz .loc_exit
- xchg eax,esi
- ; Выбрать шрифт
- invoke SelectObject,esi,[hFont]
- or eax,eax
- jnz @f
- ; Шрифт не загружен, на выход
- invoke ReleaseDC,edi,esi
- jmp .loc_exit
- @@:
- ; Получить метрику выбранного шрифта
- lea ebx,[tm]
- invoke GetTextMetrics,esi,ebx
- invoke ReleaseDC,edi,esi
- ; Высота шрифта
- mov ebx,[ebx+TEXTMETRIC.tmHeight]
- ; Добавить к высоте размер рамки
- invoke GetSystemMetrics,SM_CYEDGE
- shl eax,2
- add ebx,eax
- ; Получить размеры поля EDIT
- lea esi,[rc]
- invoke GetWindowRect,edi,esi
- invoke GetParent,edi
- ; Отмасштабировать координаты окна
- invoke MapWindowPoints,HWND_DESKTOP,eax,esi,2
- ; Установить новые размеры поля EDIT
- mov eax,[esi+RECT.right]
- sub eax,[esi+RECT.left]
- invoke MoveWindow,edi,[esi+RECT.left],[esi+RECT.top],eax,ebx,TRUE
- .loc_exit:
- popa
- ret
- endp
Читать статью целиком »
Просмотров: 620 | Комментариев: 1

Перемешивание массива на JavaScript
20.11.2020 | Категория: Web-мастеру и не только | Автор: ManHunter

Перемешивание массива на JavaScript
Несмотря на особенности сортировки массивов в JavaScript, которые нашли отражение даже в интернет-мемах, без этой самой сортировки не обойтись. Случайное перемешивание массива - тоже своеобразный вариант сортировки. Для его реализации в этих ваших интернетах обычно рекомендуют воспользоваться следующим или каким-то подобным кодом:
Code (JavaScript) : Убрать нумерацию
- var test_array=[1,2,3,4,5,6,7,8,9,10];
- test_array.sort(
- function() { return (Math.random()-0.5); }
- );
- // test_array -> перемешанный массив
Читать статью целиком »
Просмотров: 700 | Комментариев: 1

Assembler: сейчас на сайте 2 гостей и 3 новостей
27.10.2020 | Категория: Образ мышления: Assembler | Автор: ManHunter
Немного отдохнем от ковыряния во внутренностях системы. Переписал на Ассемблере свою PHP-шную функцию для правильного склонения языковых конструкций вида "число + слово". Всю суть вопроса и теорию можете почитать в статье по ссылке. Сама функция получилась вот такой:Code (Assembler) : Убрать нумерацию
- ;-------------------------------------------------------
- ; Функция для получения индекса массива с вариантами
- ; склонений слова в зависимости от числового значения.
- ; Массив слов формируется по принципу "1-2-5", то есть
- ; ("гость", "гостя", "гостей")
- ;-------------------------------------------------------
- ; На входе:
- ; dNum - число
- ; На выходе:
- ; EAX = [0..2] - индекс элемента массива
- ;-------------------------------------------------------
- proc num2word dNum:DWORD
- push ecx edx
- mov eax,[dNum]
- cdq
- mov ecx,100
- idiv ecx
- cmp edx,19
- jb @f
- mov eax,edx
- cdq
- mov ecx,10
- idiv ecx
- @@:
- xor eax,eax
- or edx,edx
- jz .case2
- cmp edx,1
- jz .case0
- cmp edx,4
- jbe .case1
- .case2:
- inc eax
- .case1:
- inc eax
- .case0:
- pop edx ecx
- ret
- endp
Читать статью целиком »
Просмотров: 624 | Комментариев: 0
