Гость
Войти | Профиль | Очистить
Действия ...
Форумы / Firebird, InterBase [игнор отключен] [закрыт для гостей] / Случайная выборка / 24 сообщений из 24, страница 1 из 1
21.04.2021, 21:02
    #40064563
shalamyansky
shalamyansky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
Код: sql
1.
2.
3.
4.
5.
create table test(
    id   bigint not null,    --id - не инкрементный, просто уникальные большие числа
    name varchar(1000)
);
alter table test add constraint pk_test primary key ( test );



В таблице N записей (=10000000). Как сгенерировать случайную выборку из M записей? Желательно за разумное время.

Первое, что приходит в голову, разыграть M чисел от 1 до N, и затем из полного скана выдернуть записи с этими номерами. Но это полный скан, и PSQL какой-никакой. Может, есть более элегантное решение?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.04.2021, 21:18
    #40064564
hvlad
hvlad
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
Генерируй случайные числа, по возможности из реального диапазона id, и ищи их в таблице.
Нашёл - возвращай, не нашёл - генери новое число.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.04.2021, 21:23
    #40064566
shalamyansky
shalamyansky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
Не. Реальный диапазон значений id - почти весь bigint, ну, чуток поменьше - 10^15. А записей всего 10^7. Долго искать попаданий придется.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.04.2021, 21:26
    #40064567
shalamyansky
shalamyansky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
Но это метод, да, спасибо.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.04.2021, 21:34
    #40064568
romangr
romangr
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
можно так попробовать -
1. Получить COUNT
2. Сгенерировать M случайных чисел в диапазоне 1..COUNT
3. Сделать M запросов SELECT ... OFFSET N FETCH FIRST ROW ONLY
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.04.2021, 21:42
    #40064569
shalamyansky
shalamyansky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
romangr,

COUNT - это N. А так почти как у меня, только вместо одного полного скана запускаем M почти полных сканов.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.04.2021, 22:10
    #40064577
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
shalamyanskyА записей всего 10^7. Долго искать попаданий придется.

Тогда делай как в "что, где, почём": получай первую запись с id >= сгенерированного
случайного числа.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.04.2021, 22:21
    #40064578
shalamyansky
shalamyansky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
Dimitry Sibiryakov,

О! Это ценная идея. Только посмотреть надо бы, все ли там хорошо с равномерностью распределения. На первый взгляд вроде не должно быть искажений. Да и моя задача не требует идеальности. Спасибо!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.04.2021, 09:52
    #40064639
a7exander
a7exander
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
Dimitry Sibiryakov

Тогда делай как в "что, где, почём": получай первую запись с id >= сгенерированного
случайного числа.


Тогда вероятность выдергивания записи перед которой много неиспользуемых ID будет выше чем скажем идущих подряд)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.04.2021, 12:39
    #40064702
m7m
m7m
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
shalamyansky
Не. Реальный диапазон значений id - почти весь bigint, ну, чуток поменьше - 10^15. А записей всего 10^7. Долго искать попаданий придется.

Если нет массовых удалений то
добавить еще одно уникальное поле в таблицу, для существующих записей перенумеровать
от 1 до ....
в триггер на вставку генератор на это поле
А далее как в 22312152 , только искать по новому полю
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.04.2021, 14:16
    #40064742
shalamyansky
shalamyansky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
a7exander

Тогда вероятность выдергивания записи перед которой много неиспользуемых ID будет выше чем скажем идущих подряд)


Ага, это неприятность. Сформулирую так: если распределение id в своем пространстве равномерно-случайно, то данный метод тоже даст равновероятностную выборку. Но если существуют кучности и разреженности, то в выходном наборе элементы из кучностей будут представлены неоправданно редко, а элементы из разреженностей - неоправданно часто. Кстати, и в первом случае уже после первых "выемок" появятся неоднородности.

Это хорошо как раз видно на примере волчка "Что, Где, Когда?". Поначалу, когда весь стол заполнен, вероятность выпадения всех вопросов одинакова. Но потом возникают лакуны, и вопросы на их правой границе имеют гораздо больший шанс попасть в игру.

Если же практически, то мне для своей задачи метод вполне подходит.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.04.2021, 14:53
    #40064763
WildSery
WildSery
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
shalamyansky,

меняй "направление волчка"
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.04.2021, 15:06
    #40064767
shalamyansky
shalamyansky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
WildSery,

Очень мало поможет. Левые берега дырок тоже получат большие шансы, но и только.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.04.2021, 15:44
    #40064786
Мимопроходящий
Мимопроходящий
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
когда-то давно обсуждалось.
можно поискать.
если не ошибаюсь, решение свелось к SKIP(Random) + ORDER BY
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.04.2021, 17:02
    #40064834
Дегтярев Евгений
Дегтярев Евгений
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
Мимопроходящий,

оно ж будет сильно не оптимально, когда надо пропустиnь 100500 записей
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.04.2021, 17:10
    #40064839
pastor
pastor
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
shalamyansky,

если свезет - один пробег, не свезет, тоо два
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
i = 0;
m = MaxV;
r = random;

while (все выбралось)
do begin
      for select * from table
           into
           do begin
                  if (i = r)
                    then begin
                              suspend;
                              r = i + random;
                            end
                   else i = i + 1;

                end
     end
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.04.2021, 17:41
    #40064848
shalamyansky
shalamyansky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
pastor,

Это все равно полный скан, а то и не один, только используются не случайные позиции, а случайные дельты. Кстати, совершенно непонятно, и у вас не указано, из какого диапазона надо эти дельты разыгрывать.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.04.2021, 17:51
    #40064852
Шавлюк Евгений
Шавлюк Евгений
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
pastor,

Тогда уже лучше так
Код: sql
1.
select first 1 * from table order by rand()


Тут хоть гарантировано 1 пробег
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.04.2021, 19:27
    #40064892
ъъъъъ
ъъъъъ
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
shalamyansky,

добавь поле "Номер", и перед операцией заливай значения из генератора. Диапазон будет как раз о значения генератора до операции до значения после.
На поле - индекс. Вот и будет тебе быстро.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.04.2021, 08:52
    #40065037
pastor
pastor
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
Шавлюк Евгений
pastor,

Тогда уже лучше так
Код: sql
1.
select first 1 * from table order by rand()


Тут хоть гарантировано 1 пробег


на каждую запись.

я же предложил полный скан (иногда больше), даже для случаев когда размер случайной выборки сравним с размером таблицы.

когда у нас там full scan на 16k странице (200 байт на запись) выгоднее - при 1/80?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.04.2021, 15:46
    #40065254
shalamyansky
shalamyansky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
ъъъъъ

добавь поле "Номер"


"Чтобы прочитать книгу, надо сперва дописать книгу" - это не наш метод. И потом, тут опять полный перебор, да еще и с записью.

Обращаю ваше внимание, что существенная часть задачи состоит именно в избегании полного перебора записей, ибо с полным перебором (одним!) задача решается достаточно тривиально и математически правильно, как описано у меня в топике.

Вот метод hvlad'а и дополнение Dimitry Sibiryakov'а как раз дают решение без полного скана. Больше пока не видно.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.04.2021, 16:09
    #40065266
Шавлюк Евгений
Шавлюк Евгений
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
shalamyansky,

Тогда мое предложение.
Добавь в таблицу поле с хешем, который более-менее равномерно распределен по диапазону.
Например md5(table_id). А далее первых М строк с хешем больше случайного
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.04.2021, 16:38
    #40065272
a7exander
a7exander
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
Шавлюк Евгений
shalamyansky,

Тогда мое предложение.
Добавь в таблицу поле с хешем, который более-менее равномерно распределен по диапазону.


Тогда можно еще проще - поле с Rand() вместо хеша, результат то тот же а распределение может даже лучше выйти
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.04.2021, 18:13
    #40065320
Шавлюк Евгений
Шавлюк Евгений
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Случайная выборка
a7exander,

согласен, хеш не нужен. RAND в поле и индекс по нему достаточно
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Firebird, InterBase [игнор отключен] [закрыт для гостей] / Случайная выборка / 24 сообщений из 24, страница 1 из 1
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
созд. / загр.: 531ms
Закрыть
start [/forum/topic.php?fid=40&mobile=1&tid=1560050]:
 0ms
get settings:
 10ms
get forum list:
 16ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 173ms
get topic data:
 14ms
get forum data:
 3ms
get page messages:
 69ms
get tp. blocked users:
 2ms
others: 236ms
total:  531ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]