1 Востаннє редагувалося koala (02.02.2016 00:08:27)

Тема: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

Є набір сутностей, які користувач має впорядковувати, як хоче. Як зберігати такий список в SQL?
Популярний (в CMS) варіант, де пропонується виставляти порядок числами, мені видається дуже незручним. Як це можна оптимізувати?
Якби мова йшла не за БД, то тут оптимальним рішенням був би список; але структура, де кожен запис посилається на інший, засобами SQL витягається не дуже зручно.
Мені вбачається таке рішення:
1. Кожному елементу надається особистий номер (з певним кроком, скажімо, 16), тобто:

Елемент1 0
Елемент2 16
Елемент3 32
Елемент4 48

і т.д.
2. Користувачу номери не показуються; він може перетягати елемент, як завгодно. Коли елемент перетягається між двох інших, його номер змінюється на середнє арифметичне їхніх номерів:

Елемент1 0
Елемент4 8 < вставили між 1 та 3
Елемент2 16
Елемент3 32

Особливі випадки - пересування в початок і кінець списку - обробляються особливо, скажімо, відкиданням на 16 від попереднього краю (в т.ч. у від'ємні). Або ж вважається, що існують умовні номери 0 і 16*(кількість елементів), які завжди стоять на краях.
3. Якщо таке перетягування стає неможливим, бо номери, між якими додають елемент, сусідні, запускається процедура перенумерації. Наприклад, весь список отримує нові номери з кроком 16, або ж обчислюється певний окіл елементів, де номери розташовані надто щільно, і перенумерація відбувається тільки в ньому.
В принципі, нескладно, але мені чомусь здається, що тут може бути простіше рішення, до якого я чомусь не можу дійти.

Подякували: leofun011

2 Востаннє редагувалося quez (02.02.2016 00:00:50)

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

koala написав:

2. Користувачу номери не показуються; він може перетягати елемент, як завгодно. Коли елемент перетягається між двох інших, його номер змінюється на середнє арифметичне їхніх номерів:

Елемент1 0
Елемент4 8 < вставили між 1 та 3
Елемент2 16
Елемент3 32

А якщо далі переставляти з кінця на другу позицію, то елемент отримуватиме 4, 2, 1, ½?

upd: Звиняйте, недочитав.

3

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

Може коли вставляємо наприклад на другу позицію,то просто оновлювати ідентифікатори,шляхом видалення старого AUTO_INCREMENTу поля і запуску нового (через SQL) ? Тоді всі поля наново пронумеруються по порядку.

4 Востаннє редагувалося mike (02.02.2016 00:16:17)

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

стикався із таким, вирішував дуже просто.

Самі сущності нехай будуть хоч пронумеровані, хоч будуть мати інікальні ід-шки, це не важливо. Додатково до них добавляв поле "order" (INT) і по цьому полю робив сортування.

Але тут одна заковика, коли даних буже багато, то це варіант взагалі не рентабельний, бо перегенерювати прийдеться кожного разу.

5

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

VTrim написав:

Може коли вставляємо наприклад на другу позицію,то просто оновлювати ідентифікатори,шляхом видалення старого AUTO_INCREMENTу поля і запуску нового (через SQL) ? Тоді всі поля наново пронумеруються по порядку.

Так вся суть задачі — уникнення перенумерування всіх полів, наскільки я розумію.

Подякували: koala1

6

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

Так, питання - як зробити мінімальне навантаження на БД.

7

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

мені здається із вашим варіантом перегенеровувати прийдеться лише у випадку коли елемент будуть перетягувати в початок, якщо пересунуть в кінець то просто додати +16 до максимального значення яке знайдете.

а що заважає так само рухатись і в іншу сторону -2, -4, -6 ... ? тут взагалі не треба нічого перегенеровувати

8 Востаннє редагувалося koala (02.02.2016 00:30:24)

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

Напишемо в стовпчик три номери і "позаплітаємо косу" - перекидаємо то верхній, то нижній в середину, десь так:

 0 16 16 20 20
16 24 20 22 21
32 32 24 24 22

як тепер перекинути верхній елемент до середини?

9

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

хм, треба уберігтись від такого випадку

20
21
22

тобто може є сенс відсувати 20 в меншу сторону і 22 в більшу, тоді навантаження буде, але все ж таки менше ніж якщо всі перегенерювати

10 Востаннє редагувалося VTrim (02.02.2016 00:50:15)

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

Варіант з трьох є простим. Бо 0, 16, 32 можуть бути унікальними і можемо просто апдейтити дані, змінюючи всі значення одного рядка на всі іншого, унікальні поля не чіпаючи.
Наводьте приклад, де треба перенести наприклад з 5 на 2 і т.д...

UPD: та навіть з першого на третій і завдання вже "не те"

11

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

koala написав:

Є набір сутностей, які користувач має впорядковувати, як хоче. Як зберігати такий список в SQL?

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

12

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

Люди, це пізно просто чи у вас з абстрактним мисленням проблеми?

(1000 елементів з номерами від -16000 до -16)
0
16
32
(1000 елементів з номерами від 48 до 16048)

а далі - описані перекидання елементів всередині. Причому час від часу і інші елементи перекидаються десь там у себе. Тепер бачите проблему? Через ці 3 елементи доводиться перегенеровувати номери для 2000 елементів. Та й навіть для 10 - виходить, іноді пересування змінює тільки 1 номер, а іноді - одразу 10. А от чи можливо зробити, скажімо, так, щоб кожне пересування змінювало тільки 2-3 номери?

13 Востаннє редагувалося VTrim (02.02.2016 01:26:37)

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

А якщо так наприклад..

0
16
32
48

З 4 позиції на 2, з 48 на 16, то тримаємо числа в FLOAT і до 0 додаємо наприклад 0.0001 (INSERT даних) ,а 48 (DELETE) видаляємо.

Виходить
0
0.0001
16
32

:D

З 2 на 3

0.0001 видаляємо
А 16 + 0.0001

0
16
16.0001
32

14

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

koala написав:

абстрактним мисленням проблеми?

Пишете власну СУБД ?
Підняти продуктивність роботи бд за рахунок специфічної структури файлу (або файлів) звичайно можна, але в основі цих структур лежать ті самі звязні списки і графи, і затрати пам'яті будуть значно більші ніж у класичного двозвязного списку.
Таке собі можуть дозволити хіба що всякі googlи :)

15

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

VTrim написав:

А якщо так наприклад..

0
16
32
48

З 4 позиції на 2, з 48 на 16, то тримаємо числа в FLOAT і до 0 додаємо наприклад 0.0001 (INSERT даних) ,а 48 (DELETE) видаляємо.

Виходить
0
0.0001
16
32

:D

З 2 на 3

0.0001 видаляємо
А 16 + 0.0001

0
16
16.0001
32

Те ж саме, ні? Float'ів рівно стільки ж, скільки й int'ів.

16 Востаннє редагувалося VTrim (02.02.2016 08:39:31)

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

quez написав:
VTrim написав:

А якщо так наприклад..

0
16
32
48

З 4 позиції на 2, з 48 на 16, то тримаємо числа в FLOAT і до 0 додаємо наприклад 0.0001 (INSERT даних) ,а 48 (DELETE) видаляємо.

Виходить
0
0.0001
16
32

:D

З 2 на 3

0.0001 видаляємо
А 16 + 0.0001

0
16
16.0001
32

Те ж саме, ні? Float'ів рівно стільки ж, скільки й int'ів.

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

17

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

З float-ами теж думав (от тільки не 0.0001, ми не знаємо, куди полізе наступний елемент, тому просто середнє - між 20 і 21 буде 20.5). Але тоді треба буде епсилони ловити, що складніше, ніж одиниці.
До речі, тоді вже буде кращим вважати, що є два псевдоелементи INT_MIN та INT_MAX, які не виводяться і не зсуваються, але використовуються при обчисленнях середніх, при початковому вирівнюванні всі елементи розставляються рівномірно між ними, а при локальних перенумераціях шукаємо блок елементів розміром, що збільшується удвічі (4, 8, 16 і т.д.) з середньою щільністю хоча б удвічі більшою за середню щільність по масиву. Середня щільність - це кількість елементів, ділена на відстань між крайніми елементами.
Подумав, що по кількості елементів складно зробити запит, треба робити навпаки - у нас є два суміжні елементи, а має між ними бути відстань (в середньому по множині) n. Запитуємо, що робиться в їхньому околі довжиною n. Маємо там ще кілька елементів. Обчислюємо щільність, якщо влаштовує - впорядковуємо, якщо ні - збільшуємо окіл до 2*n і т.д. Але під час цього треба ще й блокувати таблицю... йой...

Подякували: leofun011

18

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

Є набір сутностей, які користувач має впорядковувати, як хоче. Як зберігати такий список в SQL?

Щось я не зрозумів у чому проблема...
По-перше не у SQL а у базі.
По-друге, хіба сама СУБД не предоставляє можливість индексування як забажає АБД? Тобто можливо же (як вище сказав muhasjo) зробити стовбчик, який мае буті порядковим номером, та тягати його зі всим записом, або микшувати його різною індексацією?

Подякували: leofun011

19

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

Itari написав:

Є набір сутностей, які користувач має впорядковувати, як хоче. Як зберігати такий список в SQL?

Щось я не зрозумів у чому проблема...
По-перше не у SQL а у базі.
По-друге, хіба сама СУБД не предоставляє можливість индексування як забажає АБД? Тобто можливо же (як вище сказав muhasjo) зробити стовбчик, який мае буті порядковим номером, та тягати його зі всим записом, або микшувати його різною індексацією?

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

Подякували: leofun011

20

Re: Цікава (сяк-так) задача. Довільно впорядкований список з SQL

Itari написав:

Є набір сутностей, які користувач має впорядковувати, як хоче. Як зберігати такий список в SQL?

Щось я не зрозумів у чому проблема...
По-перше не у SQL а у базі.
По-друге, хіба сама СУБД не предоставляє можливість индексування як забажає АБД? Тобто можливо же (як вище сказав muhasjo) зробити стовбчик, який мае буті порядковим номером, та тягати його зі всим записом, або микшувати його різною індексацією?

Так-так-так, у SQL-базі. Головне, що не NoSQL. Реляційна БД, так легше?
І що ви маєте на увазі під "тягати"? Якщо записи впорядковані за цими номерами, то як можна перетягнути запис на інше місце, не змінивши номера? Приклади вище бачили?