1 Востаннє редагувалося ktretyak (24.05.2015 18:04:39)

Тема: Раціональний алгоритм пошуку випадкових ID, ще відсутніх в БД

При реєстрації, хочу надавати одному користувачу три різні ID, але ці ID:
1. не повинні бути сусідніми
2. потрібно щоб не можливо було вирахувати інші ID користувача, якщо відомо про одну з них.

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

Ніхто не в курсі чи є відомий алгоритм для такої задачі?

2 Востаннє редагувалося ktretyak (25.05.2015 00:24:49)

Re: Раціональний алгоритм пошуку випадкових ID, ще відсутніх в БД

Схоже, що я вже придумав такий алгоритм:
1. придумуємо "кучність" цих випадкових ID, нехай це буде 1000
2.1 якщо в базі даних ще жодної ID немає, то створюємо ці 1000 ID
2.2 якщо в базі невистачає незайнятих ID'шок, то доповнюємо їх щоб було 1000
2.3 якщо в базі вже є 1000 незайнятих ID'шок, то вибираємо випадкову ID
3. робимо вибірку незайнятих ID'шок, доповнюємо їх до 1000 та вибираємо серед них наступну ID і т.д.

Здається повинно працювати, щя перевірю.

3

Re: Раціональний алгоритм пошуку випадкових ID, ще відсутніх в БД

ktretyak написав:

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

Чому ви думаєте, що цей спосіб нерацональний? От візьмете ви шестизначний ID. Вам порахувати, через скільки користувачів варто чекати першої колізії, яка призведе аж до одного зайвого запиту? А ви явно візьмете не шість або не тільки цифр.

4 Востаннє редагувалося VTrim (24.05.2015 21:51:28)

Re: Раціональний алгоритм пошуку випадкових ID, ще відсутніх в БД

цi id мають складатись тiльки з чисел i якоi довжини ?

Можливо генеруйте на основi uniqid() або microtime()

5 Востаннє редагувалося ktretyak (24.05.2015 23:03:17)

Re: Раціональний алгоритм пошуку випадкових ID, ще відсутніх в БД

VTrim написав:

цi id мають складатись тiльки з чисел i якоi довжини ?

Можливо генеруйте на основi uniqid() або microtime()

Ці ID повинні бути цифровими від 1 до 10 символів, новостворені ID повинні відрізнятись від вже існуючих в БД.

6

Re: Раціональний алгоритм пошуку випадкових ID, ще відсутніх в БД

Значить вiдштовхуйтесь вiд microtime()

Час в мiкросекундах,точно не повториться :) ну i +- декiлька цифр,чисел

7

Re: Раціональний алгоритм пошуку випадкових ID, ще відсутніх в БД

Беріть просто досить довгі випадкові числа і не морочте собі голови. Час як випадкова величина - дуже поганий вибір для надійних систем: якщо я знаю день, коли реєструвався той, чий код треба підібрати,  то мені треба перевірити всього 1000(мс/с)*60(с/хв)*60(хв/год)*24(год/доб)=86400000 варіантів, тобто складність підбору - всього 26 біт, це не складність. А для пошуку повторень використовуйте хеш-таблицю (власне, в будь-якій БД десь так і буде по індексу).

Подякували: raxp, yarko, Yola3

8

Re: Раціональний алгоритм пошуку випадкових ID, ще відсутніх в БД

koala написав:

Беріть просто досить довгі випадкові числа і не морочте собі голови. Час як випадкова величина - дуже поганий вибір для надійних систем: якщо я знаю день, коли реєструвався той, чий код треба підібрати,  то мені треба перевірити всього 1000(мс/с)*60(с/хв)*60(хв/год)*24(год/доб)=86400000 варіантів, тобто складність підбору - всього 26 біт, це не складність. А для пошуку повторень використовуйте хеш-таблицю (власне, в будь-якій БД десь так і буде по індексу).

Мені достатньо буде "розкиданість" ID в межах тисячі варіантів.

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

9

Re: Раціональний алгоритм пошуку випадкових ID, ще відсутніх в БД

Ну тоді дійсно ідея з 1000 цілком себе виправдовує: запам'ятовуєте 1000 наступних ID, вибираєте випадково з них 3 номера і додаєте 3 нових послідовних до цієї 1000.

10

Re: Раціональний алгоритм пошуку випадкових ID, ще відсутніх в БД

Щодо публiкуватись пiд анонiмом чи псевдонiмом.

То тут можна зробити все простiше..

Користувач регнувся,далi для свого аккаунта створив нiк-псевдонiм.

При публiкуваннi запису три чекбокси..
Автор: Я,Мiй псевдонiм,Анонiм.

При першому в author_id йде ваш id,при другому в psevdo_user пишеться ваш нiк псевдонiм,при третьому в поле author_id нiчого не пишеться.

А при водoдi з бд, якщо author_id пусте,то Анонiм,якщо psevdo_user не пусте,то виводимо його,iнакше author_id а по ньому справжнiй нiк.
Описав в загальному..

11

Re: Раціональний алгоритм пошуку випадкових ID, ще відсутніх в БД

VTrim написав:

...
При першому в author_id йде ваш id,при другому в psevdo_user пишеться ваш нiк псевдонiм,при третьому в поле author_id нiчого не пишеться.

А при водoдi з бд, якщо author_id пусте,то Анонiм,якщо psevdo_user не пусте,то виводимо його,iнакше author_id а по ньому справжнiй нiк.
Описав в загальному..

Ваш варіант підійшов би, якщо б не було можливості публікуватись від аноніма.

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

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

12 Востаннє редагувалося ktretyak (26.05.2015 13:21:32)

Re: Раціональний алгоритм пошуку випадкових ID, ще відсутніх в БД

Хе-хе... MySQL-функція rand() несподівано багато повторень видає навіть на тисячі варіантів, якщо я правильно розумію те що бачу ...

Оновлено:
Тю, ця функція rand() зовсім несподівано працює у вкладених запитах. Дивно, чому б це...

Оновлено2:
Виявляється, це відома проблема

13

Re: Раціональний алгоритм пошуку випадкових ID, ще відсутніх в БД

Якщо ви розраховуэте на таку активнiсть,то вам так чи iнакше прийдеться брати видiлений сервер.

Доповню свiй попереднiй пост..

Там можна писати в author_id айдi у всiх випадках (i для псевдонiма i анонiма) для запису карми +- при голосуваннi. Просто змiнити умови запису i виводу. В такому випадку навiть для Анонiма буде id юзера.

Але як я зрозумiв,Вам таке не пiдiйде.

Ну i localStorage мабуть не у всiх браузерах э. Що робитимете,коли данi localStorage досягнуть 5МБ? :)

14 Востаннє редагувалося ktretyak (27.05.2015 07:31:57)

Re: Раціональний алгоритм пошуку випадкових ID, ще відсутніх в БД

VTrim написав:

...
Ну i localStorage мабуть не у всiх браузерах э. Що робитимете,коли данi localStorage досягнуть 5МБ? :)

На браузери-динозаври я не розраховую, по статистиці їх надзвичайно мало.

5 МБ у стільникових браузерів і трохи більше 2 МБ в браузерів на мобільниках. Я зробив заміри: 1000 ID довжиною 10 символів займають 14 КБ в текстовому форматі, тобто 100 тисяч ID'шок вміститься легко в будь-якому випадку. Для порівняння - зараз наш форум replace має 57 тисяч повідомлень.

Тобто 100 тисяч ID для одного користувача - це той об'єм, з яким вже можна робити цікаві речі. Зокрема в мене буде фільтри по "прочитаним/непрочитаним" публікаціям якраз завдяки localStorage.

Без localStorage, для сервака слідкувати за "прочитаним/непрочитаним" було б дуже накладно.

15 Востаннє редагувалося VTrim (27.05.2015 08:38:51)

Re: Раціональний алгоритм пошуку випадкових ID, ще відсутніх в БД

А якщо користувач оновить або змiнить браузер (або ж зайде з iншого пристрою) ? Данi втраченi.

Не знаю,для цього я б не використовував localStorage,а добре налаштував би кешування для зменшення навантаження,ну i оптимiзацiя коду.

Втiм,робiть як знаэте.

16

Re: Раціональний алгоритм пошуку випадкових ID, ще відсутніх в БД

VTrim написав:

А якщо користувач оновить або змiнить браузер (або ж зайде з iншого пристрою) ? Данi втраченi.

Не знаю,для цього я б не використовував localStorage,а добре налаштував би кешування для зменшення навантаження,ну i оптимiзацiя коду.

Втiм,робiть як знаэте.

Буде можливість експортувати весь вміст localStorage на сервер, а потім імпорт з сервера в новий браузер.

Що до кешування та оптимізації... уявіть, що сервер пам'ятає хоча б половину прочитаного/непрочитаного для кожного користувача форума replace, в якого в середньому є, скажімо тисяч по 30 цих самих ID'шок. Тобто для теперішньої кількості зареєстрованих користувачів -  це табличка з (30 000 * 2000) == 60 млн. рядків, яку треба смикати за кожним переходом кожного з користувачів. А це вже досить серйозний об'єм, особливо для вставки даних в таку індексовану таблицю.