Нотатки про пошук, сортування і як я згадував програмування

Несподівано довелося згадати, що є на світі люди, які вважають мене програмістом :-D і заодно підняти свої «творіння» дво- чи трирічної давності. Відразу скажу — задача цікава, заставляє мозок рухатися, а тому робити її було в кайф, а ще кайфовіше — зробити! Друга приємна річ — це те, що вона досі працює, на відміну від більшості того, що мені підсовували писати на роботі — понтоганялки для того, щоб відзвітувати, що щось робиться, а по-факту нікому не потрібні ]:->.

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

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

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

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

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

Ідея наступна:
— до таблиці категорій додаю два автозаповнюваних поля — «рівень вкладення» і «стрічковий кодифікатор», які формую за наступними принципами: «рівень вкладення» — (очевидно) батьківський рівень плюс одиниця, «стрічковий кодифікатор» — значення батьківського кодифікатора плюс стрічка вигляду K{n}-{id}!, де n — рівень вкладення, id — ключове (унікальне) поле. Зайві на перший погляд символи «K», «-» та «!» насправді потрібні для уникання неоднозначності. Таким чином, якщо я додам три категорії вкладені одна в одну, то в останній отримаю стрічку K1-1!K2-2!K3-3! , при додаванні наступної підкатегорії на другий рівень — K1-1!K2-4! . Далі показовою картиною буде, якщо десятий запис додати на перший рівень — його кодифікатор буде K1-10! . Якби не було знаків оклику вкінці кожного рівня, то при пошуку входження стрічки K1-1 знайшовся б і запис K1-10 і була б помилка.

— до звичайного списку крім поля «категорія» додаю також автозаповнюване поле «кодифікатор», яке формую додаванням до кодифікатора категорії стрічки виглядуL-{id}!, на цей раз id — ключове поле вже зі списку

— до всіх таблиць, що посилаються на цей список додаю автозаповнюване поле «кодифікатор», яке просто дублює відповідний кодифікатор зі списку.

Таким чином я у всіх таблицях маю записи у яких міститься кодифікатор не лише самого запису а й ВСІХ батьківських категорій, пошук по якому можна проводити за примітивним входженням стрічки, який давно реалізований, відлагоджений, зі всіма рюшечками для користувача.

Ніби все...

Але не все!

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

Для більш-менш пристойного результату я змінив вигляд кодифікатора на наступний: K{n}{перші дві літери назви}-{id} . Звісно для повного фен-шую двох літер недостатньо, але писати там повну назву чи бодай кілька перших слів — отримаємо скажено довгу і дику стрічку. Я почав, було, думати над якоюсь упаковкою стрічки в число, але всі ідеї виявилися нікудишніми.

То нічого, головне, що зараз в мене є нормально працюючий варіант вирішення і можна нарешті йти спати :-D




 

Працює на AutoGenCMS 0.2.6

А чому це всі вирішили, що в сайта має бути шапка?