Реалізація гріду для роботи з великими таблицями. Частина 2

попередній частині статті був розібраний загальний принцип роботи системи: ми побачили, що двома основними її блоками є інтерполятор і нумератор. Ми побудували схему взаємодії, а також повністю обговорили реалізацію интерполятора. У цій частині ми розглянемо реалізацію нумератора: оборотної функції, що переводить набір значень ключових полів натуральне число (BigInteger) таким чином, що набір менше набору з точки зору СУБД тоді і тільки тоді, коли . Кажучи простіше — навчимося інтерполювати набори значень і, що найцікавіше, рядки:




Нумератор для складеного ключа
Назвемо потужністю типу даних кількість різних значень, які представимы за допомогою цього типу. Тип BIT, наприклад, має потужність 2, а тип INT — 232. Нехай типи даних складеного ключа мають потужності . Тоді загальна кількість можливих комбінацій значень ключових полів складеного ключа дорівнює . Припустимо, що ми вже вміємо обчислювати функції нумераторів для значення кожного з полів, — порядковий номер значення -го поля. Тоді функція нумератора складеного ключа може бути представлена через функції нумераторів кожного з полів


Легко перевірити, що 1) значення має найбільшу вагу, — найменший, і основна вимога до функції-нумератору виконано, 2) .

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


Тепер нам потрібен алгоритм обчислення зворотної функції . Зауважимо, що значення схоже на інтерпретацію числа у позиційній системі числення, тільки з постійно мінливим від «цифри» до «цифри» основою. Соответветвенно, перетворити значення назад в набір цифр» можна за алгоритмом, що є варіацією алгоритму представлення числа в систему числення з заданим підставою (тут value = , keys[i].cardinality() = ):

BigInteger v = value;
BigInteger[] vr;
for (int i = keys.length - 1; i >= 0; i--) {
vr = v.divideAndRemainder(keys[i].cardinality());
keys[i].setOrderValue(vr[1]);
v = vr[0];
}


Нумератори для примітивних типів даних
З складовим ключем розібралися, залишилося побудувати нумератори для зустрічаються на практиці типів.

  1. Нумерація значень типу BIT тривіальна: false — 0, true — 1.
  2. Нумерація значень типу INT трохи сложенее: INT-значення (32-бітове ціле зі знаком) є число між -2147483648 і 2147483647. Таким чином, нумератор для типу INT є просто . Звичайно, слід виконувати додавання, вже привівши до типу BigInteger. Зворотна функція .
  3. Подібним же чином можна побудувати нумератор і для 64-бітових цілих чисел зі знаком (додавати треба 9223372036854775808).
  4. DOUBLE (подвійної точності із плаваючою точкою), представлені у форматі IEEE 754, володіють тим властивістю, що їх можна (за несуттєвими винятками на кшталт NaN і ±0) порівнювати як цілі 64-бітові числа зі знаком. Наприклад, в Java отримати для значення типу double його 64-бітовий образ в форматі IEEE 754 можна з допомогою методу Double.doubleToLongBits.
  5. Нарешті, значення DATETIME, що визначають момент часу з точністю до мілісекунди, також можуть бути зведені до 64-бітовому цілого числа зі знаком, заданому так зване «UNIX-час», т. е. кількість мілісекунд від півночі 1 січня 1970 року. Наприклад, в Java це робиться за допомогою методу Date.getTime().
  6. Рядка (VARCHAR) вимагають окремої великої розмови.


Нумератор для рядків (перше наближення)

Якщо довжина рядка не обмежена, то завдання створення нумератора нездійсненна: між рядками 'a' і 'b' в лексикографічному порядку знаходиться нескінченно багато рядків 'aa', 'aaa', 'aaaa'..., а між будь-якими двома натуральними числами знаходиться завжди кінцеве кількість натуральних чисел. Математик скаже, що порядки безлічі лексикографічно впорядковані рядків і безлічі натуральних чисел неизоморфны. На щастя, у відомих нам СУБД індекс можна побудувати тільки за рядками обмеженої довжини, і це в корені міняє справу.

Якщо алфавіт містить символів, то загальна кількість рядків довжини не більше у цьому алфавіті одно


Тут одиниця відповідає порожньому рядку, — кількість рядків з одного символу,   — кількість рядків з двох символів і т. д., а в підсумку виходить стара добра сума геометричної прогресії.

Уявімо тепер довільну рядок довжини як масив , де — номер -го символу рядка в алфавіті (починаючи з нуля), позиції символів в рядку теж вважаємо з нуля. Тоді рядок у простому лексикографічному порядку буде мати номер



Доказ цієї формулипровадиться, природно, методом індукції. Дійсно: якщо , то єдиний варіант — це порожній рядок з номером 0.

Якщо , то порожній рядок буде мати номер 0, а кожна односимвольная буде мати номер . Одиниця додається тому, що при порівнянні рядків порожній рядок буде менше будь односимвольной рядки: 0 — ", 1 — 'a', 2 — 'b'…

Якщо , як і раніше 0 — ", 1 — 'a'. Але тепер між рядками 'a' і 'b' в просторі лексикографічно впорядковані рядків знаходяться всі можливі рядки виду «'a' плюс будь-який рядок довжиною не більше »: 'a', 'aa', 'aaa'..., 'aab'...:


Кількість таких рядків дорівнює , і остаточно для односимвольных рядків


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

Для оптимізації обчислення і зворотної функції необхідно заздалегідь заготовити масив коефіцієнтів


Зрозуміло, користуватися цією формулою безпосередньо при заготівлі значень не потрібно: заощадити на арифметичні операції можна, зауваживши, що всі є частковими сумами геометричній прогресії, яку можна обчислювати «на ходу» при заповненні масиву .

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

for (int i = 0; i < m; i++) {
r = r.subtract(BigInteger.ONE);
cr = r.divideAndRemainder(q[i]);
r = cr[1];
int c = cr[0].intValue();
arr[i] = c;
if (r.equals(BigInteger.ZERO)) {
if (i + 1 < m)
arr[i + 1] = END_OF_STRING;
break;
}
}


Нумератор для рядків з урахуванням правил зіставлень
Порядок, в якому база даних сортує рядкові значення, насправді відрізняється від простого лексикографічного і використовує так звані правила зіставлення (Unicode collation rules).

Базою даних при порівнянні рядків з урахуванням цих правил кожен символ розглядається в трьох аспектах: власне символ, його регістр (case) і варіант написання (accent). Наприклад, російська буква «е» в більшості випадків розглядається як має два варіанти написання, кожен з яких має два регістри: е, Е, е, Тобто Це дозволяє при сортуванні, нечутливою до варіанту написання (accent insensitive), не розрізняти «е» і «е», а при сортуванні, нечутливою до регістру (case insensitive), не розрізняти малі і великі літери. При цьому, що вважати окремою літерою, а що — варіантом написання іншої літери, залежить від культурних традицій і може відрізнятися навіть в мовах, що використовують один і той же алфавіт.

Наприклад, якщо в російської культурної традиції ще зустрічаються розбіжності про статус літери «е», то ні в кого не викликає сумніву, що «і» та «ї» — це різні літери. В алфавітному переліку міст «Йошкар-Ола» повинна слідувати після «Іркутська», який би не був режим сортування. Якщо, проте, в базі даних PostgreSQL задати accent insensitive collation English-US і ввести в таблицю перелік міст, то, відсортувавши їх за назвою, можна виявити, що «Йошкар-Ола» буде слідувати перед «Іркутськом», хоча і після «Іжевська». Причина, зрозуміло, в тому, що вибраний набір правил зіставлення вважає «й» не самостійним символом, а варіантом написання букви «і»:



Загальний алгоритм порівняння рядків з урахуванням правил зіставлення наступний:

  1. Рядки порівнюються посимвольно без урахування регістрів і варіантів. Якщо виявлено розбіжність, повертається результат («більше» або «менше»).
  2. Якщо сортування accent sensitive, порівнюються номери варіантів кожного з символів. Якщо виявлено розбіжність, повертається результат.
  3. Якщо сортування case sensitive, порівнюються регістри кожного з символів. Якщо виявлено розбіжність, повертається результат.
  4. Якщо вихід з алгоритму не стався до цих пір — рядки рівні.


Всі ці тонкощі істотні для реалізації нашої задачі, т. к. адекватна робота гріду можлива лише в тому випадку, коли значення, що повертаються нумератором, зростають на зростаючому (з точки зору бази даних!) наборі аргументів.

Таким чином, нам, по-перше, необхідно модифікувати алгоритм роботи нумератора для рядків таким чином, щоб він враховував правила співставлення, а по-друге, необхідно вміти задавати різні правила співставлення, «навчаючи» грід роботі з тією або іншою базою даних.

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

Якщо відомі  — кількість символів в алфавіті,  — максимальне число варіантів написання і  — максимальне число регістрів (у відомих нам мовах : «великі» і «малі»),


де — обчислене за першим компонентів значення рядка формули (),


Зворотну функцію легко побудувати, використовуючи вже вищевикладені принципи: спершу необхідно розділити на три компоненти , потім отримати масив трикомпонентних значень, на підставі якого відновлюється вихідна рядок.

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

Тому для рішення нашої задачі знадобилося створити інтерпретатор правил зіставлень самостійно.

Цю задачу полегшило вивчення класу RuleBasedCollator. Головною запозиченої ідеєю став мова визначення правил сортування, формальний опис якого наведено в документації. Зрозуміти принцип роботи цієї мови найпростіше, розглянувши приклад правила:

<р,Р<д,Д<е,Е, е,Е<ж,Ж<з,З<і,І;ї,Ї<,<л,Л


Такі знаки є службовими у мові правил зіставлення:

  1. < — поділ символів,
  2. ; — поділ варіантів написання,
  3. , — поділ регістрів.
За допомогою виразів, подібних до наведеного вище, можна визначити правила, що відповідають різним зіставленням різних баз даних. Оскільки мова правил зіставлень досить примітивний, для розбору виразів на ньому виявилося достатньо алгоритму, що працює як детермінований скінченний автомат. У підсумку по заданому висловом правил ми отримуємо екземпляр класу, здатний

  1. за заданими правилами отримати значення (кількість символів), а також (максимальне число варіантів) і (максимальне число регістрів) для обчислення прямих і зворотних функцій нумератора,
  2. по заданому символу визначити три його компоненти (номер символу в алфавіті, номер варіанту, номер регістру),
  3. за заданою трійці компонентів визначити символ.
Нумератор для значень рядка побудований, можна збирати систему за схемою, описаною у першій частині статті.

Останні штрихи

Вже після того, як система була зібрана і почалося тестування, відкрилися особливості, які потягли за собою деякі доопрацювання.

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

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

У цьому випадку, однак, використання интерполятора і не виправдано. Якщо відомий попередній набір значень ключових полів, то отримати одну попередню (або одну наступну) запис можна швидким запитом до бази даних. Проробивши це кілька разів, можна отримати кілька попередніх або наступних записів всі ще за непомітне для користувача час.
Після отримання цих даних, крім відображення їх користувачеві, можна поповнити интерполяционную таблицю ще однією точкою, не вдаючись до запитом на підрахунок записів, т. к. отримана запис має номер, що відрізняється від попередньої на відоме значення.

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

Немає нічого дивного в тому, що номери комбінацій на основі даних в реальному таблиці розподіляються на числовій прямій дуже нерівномірно. Тому, при недостатній кількості точок у інтерполяційної таблиці, користувач, змістивши бігунок смуги прокрутки на деяку відстань, може отримати після уточнення позиції сильний «відскік» вперед або назад. У підсумку реальна позиція перегляду даних переміститься або набагато далі, або, навпаки, набагато ближче, ніж хотів користувач.

Випробування показують, що похибка на 20-25% від довжини смуги прокручування при позиціонуванні є психологічно допустимою, але не більше того. Тому після відображення гріду користувачеві бажано забезпечити, щоб максимальна довжина «відскоку» становила не більше ніж 20-25% довжини смуги прокручування навіть в самому початку роботи, коли статистика в інтерполяційної таблиці ще не накопичена.

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

Практична реалізація
Грід за наведеними тут принципам був реалізований на мові Java з використанням в якості СУБД PostgreSQL. В якості одного з навантажувальних тестових наборів даних використовується база даних КЛАДР, містить 1075429 назв вулиць населених пунктів Росії, ведеться сортування по різних полях і їх комбінацій. Всі викладені тут принципи працюють. При постійному переміщенні бігунка вертикальної смуги прокручування для користувача створюється повна ілюзія прокручування всіх записів в реальному часі, через короткий час після закінчення прокручування (коли спрацьовує уточнюючий запит і в интерполяционную таблицю додається ще одна точка) позиція бігунка смуги прокручування уточнюється, перескакуючи на невелику відстань. Позиціонування дозволяє моментально переглянути записи і відразу ж приблизно виставити бігунок смуги прокрутки, через короткий час його позиція також уточнюється. По мірі роботи з гридом і накопичення інтерполяційних точок, «відскоки» стають все менш і менш помітними.

***

По виконаній роботі я готую наукову публікацію, і ви можете також ознайомитися з препринтом наукової версії цієї статті arxiv.org.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.