ПЕРЕЛІК ДИСЦИПЛІН:
  • Адміністративне право
  • Арбітражний процес
  • Архітектура
  • Астрологія
  • Астрономія
  • Банківська справа
  • Безпека життєдіяльності
  • Біографії
  • Біологія
  • Біологія і хімія
  • Ботаніка та сільське гос-во
  • Бухгалтерський облік і аудит
  • Валютні відносини
  • Ветеринарія
  • Військова кафедра
  • Географія
  • Геодезія
  • Геологія
  • Етика
  • Держава і право
  • Цивільне право і процес
  • Діловодство
  • Гроші та кредит
  • Природничі науки
  • Журналістика
  • Екологія
  • Видавнича справа та поліграфія
  • Інвестиції
  • Іноземна мова
  • Інформатика
  • Інформатика, програмування
  • Юрист по наследству
  • Історичні особистості
  • Історія
  • Історія техніки
  • Кибернетика
  • Комунікації і зв'язок
  • Комп'ютерні науки
  • Косметологія
  • Короткий зміст творів
  • Криміналістика
  • Кримінологія
  • Криптология
  • Кулінарія
  • Культура і мистецтво
  • Культурологія
  • Російська література
  • Література і російська мова
  • Логіка
  • Логістика
  • Маркетинг
  • Математика
  • Медицина, здоров'я
  • Медичні науки
  • Міжнародне публічне право
  • Міжнародне приватне право
  • Міжнародні відносини
  • Менеджмент
  • Металургія
  • Москвоведение
  • Мовознавство
  • Музика
  • Муніципальне право
  • Податки, оподаткування
  •  
    Бесплатные рефераты
     

     

     

     

     

     

         
     
    Максимальне прискорення алгоритму пошуку
         

     

    Інформатика, програмування

    Максимальне прискорення алгоритму пошуку

    Дмитро Сахань

    Тимчасові витрати алгоритму пошуку відчутно відчуваються при обробці великих обсягів інформації. Якщо проводиться пошук DWORD-числа серед набору (масиву) таких же значень, то найбільш оптимальним і швидкісним буде послідовне порівняння заданого значення з усіма елементами масиву до виявлення збіги. Однак для пошуку рядків або деяких об'єктів, коли дані представлені в вигляді досить великого набору байт, справи йдуть інакше. Рядок або вміст об'єкта - це не DWORD-значення, і порівнювати доводиться побайтно все вміст до першого розходження або повного збігу. Саме це і з'їдає основну частину витраченого на пошук часу.

    Але програмісти швидко вирахували, як удосконалити алгоритм пошуку, щоб він не витрачав зайвий час. Суть полягала в тому, щоб спочатку порівнювати довжини шуканою і аналізованої строк (для об'єктів - розміри їх вмісту). Різниця в довжинах/розмірах точно свідчить про різницю вмісту строк/об 'єктів, тому немає сенсу витрачати час на побайтно порівняння їх вмісту. І тільки при збігу довжин виконується "повільний" код порівняння вмісту.

    Ось як виглядає простий алгоритм порівняння. Є глобальний масив M з якимись рядками, є вхідна строкою мінлива S з текстом шуканої рядка, і потрібно знайти таку ж рядок у масиві M. Приклад перебільшений і просто показує, що насправді виконується при порівнянні рядків (адже програміст просто написав б код if s = m [i] then замість зазначених мною рядків з if .... then).

    var

    m: array [1 .. 1000] of AnsiString;

    procedure Find (s: AnsiString);

    var

    i: Integer;

    begin

    for i = 1 to Length (m) do

    if Довжина (s) = Довжина (m [i]) then

    if Вміст (s) = Вміст (m [i]) then

    знайшли рядок у m [i];

    end;

    Однак таке вдосконалення має на увазі прискорення тільки при різних довжинах розташованих у масиві рядків. Вже при розташуванні в масиві понад 100 тисяч строк ефективність порівняння "довжина-вміст" починає знижуватися, так як масив заповнюється великою кількістю однакових по довжинах рядків. І чим більше мати у своєму розпорядженні в масиві рядків, тим менш ефективним стає дане удосконалення.

    Але найнеприємніше для цього методу порівняння починається, коли в силу якихось обставин або заздалегідь заданих умов в масиві розташовані однакові по довжині рядка/об'єкти. Тоді порівняння доводиться вести тільки за вмісту, а порівняння довжин виявляється зайвою операцією. При величезних обсягах інформації падіння продуктивності дуже велике. Тут потрібно або використовувати похідний (від даного) алгоритм пошуку, або написати більш універсальний алгоритм. Програмістам добре відомо, що універсальність рідко поєднується з ресурсами. І все ж хочу запропонувати свою ідею, оскільки вона добре поєднує універсальність з ресурсами.

    Для Спершу хочу згадати, що довгі рядки (AnsiString) розташовуються в пам'яті разом з довжиною рядка. Отримавши адреса рядка, потім відібравши від нього 4 байти, ви потрапляєте на адресу довжини рядка. Розповідаю це для системних програмістів, так як програмістів на Delphi, Visual Basic та C + + мало цікавить, як там зберігаються і порівнюються рядка або масиви. Реалізувавши новий алгоритм на асемблері, ви отримаєте універсальну і швидку функцію пошуку. Так ось, поле довжини рядка завжди задано типом DWord (4 байти). У загальному випадку той же відноситься і до байтовий масивів. Погано, що в стандарт "довжина-вміст" складно впровадити ще одне DWORD-поле, тому доведеться робити якось інакше.

    Суть моєї пропозиції полягає в тому, щоб розташувати перед довжиною рядки ще одне DWORD-поле. Для зручності назвемо його "Контрольний код вмісту". Установка вмісту будь-який рядок включає в себе: обчислення контрольного коду, встановлення довжини рядка та її вмісту. Обчислення контрольного коду виконується як побайтно складання всіх байт вмісту рядка в DWORD-суму.

    Новий алгоритм пошуку включає в себе додаткове порівняння - спочатку порівнюються контрольні коди вмісту двох рядків, при їх збігу порівнюються довжини рядків, і при збігу довжин порівнюється рядки. Формально алгоритм пошуку приймає такий вигляд (для наочності я вивів тип TNewString, щоб ви бачили, що робота ведеться зі зміненим типом рядка).

    type TNewString = packed record

    CRC: DWord;

    Text: AnsiString;

    end;

    var

    m: array [1 .. 1000] of TNewString;

    procedure Find (s: TNewString);

    var

    i: Integer;

    begin

    for i = 1 to Length (m) do

    if s.CRC = m [i]. CRC then

    if Довжина (s.Text) = Довжина (m [i]. Text) then

    if Вміст (s.Text) = Вміст (m [i]. Text) then

    знайшли рядок у m [i];

    end;

    На перший погляд здається, що додаткове порівняння додасть до часу пошуку ще зайвий час, але на ділі це не так. Контрольний код дозволяє з великою часткою ймовірності визначати не рівні рядки, навіть не вдаючись до аналізу їх довжин. Сенс у тому, що однакові рядки дадуть однаковий контрольний код. Але за будь-яку універсальність доводиться розплачуватися певними винятками, коли нововведення замість користі приносить зайві витрати. А будь-яке нововведення добре тільки в тому випадку, якщо його "закономірні" витрати менше витрат без нього. І тут нововведення з контрольним кодом справляється найкращим чином. Справа в тому, що контрольний код може бути однаковим у завідомо різних рядків. Поясню це на прикладі.

    Припустимо, ми порівнюємо рядок "ось так" з рядком "отож". Контрольний код у них буде однаковий, оскільки в обох рядках є ті ж самі символи. Алгоритм з контрольним кодом порівняє контрольні коди рядків, потім довжини рядків, потім перший символ рядків і знайде відмінність. Звичайний алгоритм порівняє довжини рядків, а потім перший символ рядків і також знайде відмінність. Виграш звичайного алгоритму складе одне зайве DWORD-порівняння алгоритму з контрольним кодом. У кризових ситуаціях (ті самі винятки) алгоритм з контрольним кодом несе з собою самі мінімальні витрати у вигляді зайвого DWORD-порівняння.

    А тепер подивимося, наскільки перевершує алгоритм з контрольним кодом в "важких" випадках порівняння. Припустимо, ми порівнюємо рядок "Які чудові квіти" з рядком "Які чудові кольору ". Звичайний алгоритм виявить розходження в рядках, коли дійде до порівняння останнього символу строк, у той час як алгоритм з контрольним кодом виявить розходження вже в результаті порівняння контрольних кодів рядків. Виграш вимірюється відсутністю значної кількості зайвих операцій.

    Втрачаючи мінімум у своїх кризових ситуаціях, алгоритм з контрольним кодом дає максимум продуктивності в кризових місцях алгоритму-суперника. Новий алгоритм піднімає продуктивність пошуку на порядок. При обробці надвисоких обсягів інформації такий алгоритм може надати неоціненну послугу, вивільняючи з часу пошуку вагому його частку.

    Список літератури

    Для підготовки даної роботи були використані матеріали з сайту http://www.sciteclibrary.ru

         
     
         
    Реферат Банк
     
    Рефераты
     
    Бесплатные рефераты
     

     

     

     

     

     

     

     
     
     
      Все права защищены. Reff.net.ua - українські реферати ! DMCA.com Protection Status