Blog. Just Blog

Быстрый поиск

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

Поиск подстроки в строке по алгоритму Карпа-Рабина

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) : Убрать нумерацию
  1. ;-------------------------------------------------------------
  2. ; Подгонка размера поля EDIT под заданный шрифт
  3. ;-------------------------------------------------------------
  4. ; Параметры:
  5. ;   hEdit - хэндл поля EDIT
  6. ;   hFont - хэндл шрифта
  7. ;-------------------------------------------------------------
  8. proc resize_edit hEdit:DWORD, hFont:DWORD
  9.         locals
  10.             rc RECT
  11.             tm TEXTMETRIC
  12.         endl
  13.  
  14.         pusha
  15.  
  16.         mov     edi,[hEdit]
  17.  
  18.         ; Получить контекст устройства
  19.         invoke  GetDC,edi
  20.         or      eax,eax
  21.         ; Поля ввода не существует, на выход
  22.         jz      .loc_exit
  23.  
  24.         xchg    eax,esi
  25.  
  26.         ; Выбрать шрифт
  27.         invoke  SelectObject,esi,[hFont]
  28.         or      eax,eax
  29.         jnz     @f
  30.  
  31.         ; Шрифт не загружен, на выход
  32.         invoke  ReleaseDC,edi,esi
  33.         jmp     .loc_exit
  34. @@:
  35.         ; Получить метрику выбранного шрифта
  36.         lea     ebx,[tm]
  37.         invoke  GetTextMetrics,esi,ebx
  38.         invoke  ReleaseDC,edi,esi
  39.  
  40.         ; Высота шрифта
  41.         mov     ebx,[ebx+TEXTMETRIC.tmHeight]
  42.         ; Добавить к высоте размер рамки
  43.         invoke  GetSystemMetrics,SM_CYEDGE
  44.         shl     eax,2
  45.         add     ebx,eax
  46.  
  47.         ; Получить размеры поля EDIT
  48.         lea     esi,[rc]
  49.         invoke  GetWindowRect,edi,esi
  50.         invoke  GetParent,edi
  51.         ; Отмасштабировать координаты окна
  52.         invoke  MapWindowPoints,HWND_DESKTOP,eax,esi,2
  53.  
  54.         ; Установить новые размеры поля EDIT
  55.         mov     eax,[esi+RECT.right]
  56.         sub     eax,[esi+RECT.left]
  57.         invoke  MoveWindow,edi,[esi+RECT.left],[esi+RECT.top],eax,ebx,TRUE
  58.  
  59. .loc_exit:
  60.         popa
  61.         ret
  62. endp
Функция самодостаточная, не требует дополнительных переменных в сегменте данных. На входе два параметра: hEdit - хэндл поля EDIT, у которого надо изменить размер, и hFont - хэндл шрифта, под размер которого в поле ввода вносятся изменения. Вызывать функцию изменения размера надо сразу после назначения шрифта полю EDIT.

Читать статью целиком »
Просмотров: 620 | Комментариев: 1

Перемешивание массива на JavaScript

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

Перемешивание массива на JavaScript

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

Читать статью целиком »
Просмотров: 700 | Комментариев: 1

Assembler: сейчас на сайте 2 гостей и 3 новостей

27.10.2020 | Категория: Образ мышления: Assembler | Автор: ManHunter
Немного отдохнем от ковыряния во внутренностях системы. Переписал на Ассемблере свою PHP-шную функцию для правильного склонения языковых конструкций вида "число + слово". Всю суть вопроса и теорию можете почитать в статье по ссылке. Сама функция получилась вот такой:
Code (Assembler) : Убрать нумерацию
  1. ;-------------------------------------------------------
  2. ; Функция для получения индекса массива с вариантами
  3. ; склонений слова в зависимости от числового значения.
  4. ; Массив слов формируется по принципу "1-2-5", то есть 
  5. ; ("гость", "гостя", "гостей")
  6. ;-------------------------------------------------------
  7. ; На входе: 
  8. ;    dNum - число
  9. ; На выходе: 
  10. ;    EAX = [0..2] - индекс элемента массива
  11. ;-------------------------------------------------------
  12. proc num2word dNum:DWORD
  13.         push    ecx edx
  14.         mov     eax,[dNum]
  15.         cdq
  16.         mov     ecx,100
  17.         idiv    ecx
  18.         cmp     edx,19
  19.         jb      @f
  20.         mov     eax,edx
  21.         cdq
  22.         mov     ecx,10
  23.         idiv    ecx
  24. @@:
  25.         xor     eax,eax
  26.         or      edx,edx
  27.         jz      .case2
  28.         cmp     edx,1
  29.         jz      .case0
  30.         cmp     edx,4
  31.         jbe     .case1
  32. .case2:
  33.         inc     eax
  34. .case1:
  35.         inc     eax
  36. .case0:
  37.         pop     edx ecx
  38.         ret
  39. endp
Единственный параметр на входе - число, для которого надо получить индекс элемента массива. На выходе EAX - искомый индекс от 0 до 2. Примеры использования смотрите в прилагаемом исходнике, там ничего сложного.

Читать статью целиком »
Просмотров: 624 | Комментариев: 0

prev 01 02 03 04 05 06 07 08
Это я :-)
Если программист в девять утра уже на работе, значит он там же и ночевал
Главная страница Web-мастеру и не только Образ мышления: Assembler Мои программы Software Темная сторона Силы Обзоры техники А еще я туда ем! Жизнь в оффлайне Всякая всячина
Карта сайта Ссылки Обратная связь Правила сайта Настройки сайта RSS-канал
Ограничение по возрасту 16+ Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Метки статей
.NET (24), AJAX (5), Assembler (290), COM (20), CSS (38), Exif (15), FASM (8), Firefox (7), HDD (13), Hello Teddy (9), HTML (45), iconBIT (4), JavaScript (64), MySQL (12), Nikon (19), PDF (9), PHP (103), Samsung (6), SEO (12), Sublime Text (9), TintonLife (4), UGREEN (4), Windows 7 (64), аккумуляторы (22), аксессуары (12), анализаторы файлов (8), архиваторы (5), аттракционы (6), безопасность (50), браузеры (16), бытовая техника (9), варенье (16), ВВЦ (9), ВДНХ (10), видео (20), Воробьевы горы (7), вторые блюда (105), выпечка (20), выставки (110), генератор ПСЧ (10), графика (97), десерты (28), Египет (7), заготовки на зиму (37), закуска (19), закуска к пиву (22), зарядные устройства (22), защита (15), зоопарки (9), игры (30), иконки (20), интерфейс (24), исследование защиты (266), каша (4), клавиатура (7), Коломенское (37), консоль (7), концерты (52), Кузьминки (4), куклы (27), ледяные скульптуры (6), мои программы (63), мониторы (6), музеи (67), мультимедиа (47), мясо (49), напитки (11), ноутбуки (6), обфускация (7), окна (68), оформление сайта (45), парки Москвы (7), песчаные скульптуры (13), плееры (10), подводная съемка (4), поздравления (112), полезные функции (36), прохождения (4), процессы (20), птица (16), путешествия (24), распаковка (16), реверсинг (47), рыба (32), салаты (17), сброс триала (4), сеть (29), система (159), Сокольники (8), соусы (9), супы (13), телефоны (8), Тунис (6), файлы справки (6), фаст-фуд (17), фестиваль цветов (5), флешки (5), фото (23), хеши (16), числа (8), юмор (12), яйца (16)
Вам помог этот сайт?
Сказать спасибо! Поблагодарили 31,054 раза
<< 2022 - ИЮЛЬ >>
Пн Вт Ср Чт Пт Сб Вс
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
День работников морского и речного флота
День ГИБДД МВД России
День работников морского и речного флота России
Нашли на сайте орфографическую ошибку? Выделите ее мышкой и нажмите
Ctrl
+
Enter
Буду очень благодарен, если размеcтите мою кнопочку:
Личный блог ManHunter'а
Valid CSS Valid XHTML 1.0 Transitional Valid mobileOK Basic Valid RSS
Яндекс тИЦ: {YANDEX_TIC} Яндекс ИКС: 390
Сейчас я слушаю
---
Имя:

Сообщение:

Осталось символов: 200

   
-
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2022
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.13 сек. / MySQL: 3 (0.05 сек.) / Память: 4.75 Mb
Наверх