ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Firebird, InterBase [игнор отключен] [закрыт для гостей] / Случайная выборка
24 сообщений из 24, страница 1 из 1
Случайная выборка
    #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:02
| Ответить | Цитировать | Написать  
Случайная выборка
    #40064564
hvlad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hvlad
Участник
Генерируй случайные числа, по возможности из реального диапазона id, и ищи их в таблице.
Нашёл - возвращай, не нашёл - генери новое число.
...
Рейтинг: 0 / 0
21.04.2021, 21:18
| Ответить | Цитировать | Написать  
Случайная выборка
    #40064566
shalamyansky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
shalamyansky
Участник
Не. Реальный диапазон значений id - почти весь bigint, ну, чуток поменьше - 10^15. А записей всего 10^7. Долго искать попаданий придется.
...
Рейтинг: 0 / 0
21.04.2021, 21:23
| Ответить | Цитировать | Написать  
Случайная выборка
    #40064567
shalamyansky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
shalamyansky
Участник
Но это метод, да, спасибо.
...
Рейтинг: 0 / 0
21.04.2021, 21:26
| Ответить | Цитировать | Написать  
Случайная выборка
    #40064568
romangr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
romangr
Участник
можно так попробовать -
1. Получить COUNT
2. Сгенерировать M случайных чисел в диапазоне 1..COUNT
3. Сделать M запросов SELECT ... OFFSET N FETCH FIRST ROW ONLY
...
Рейтинг: 0 / 0
21.04.2021, 21:34
| Ответить | Цитировать | Написать  
Случайная выборка
    #40064569
shalamyansky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
shalamyansky
Участник
romangr,

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

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

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

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


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

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

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


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

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

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

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

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

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

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

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


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

добавь поле "Номер", и перед операцией заливай значения из генератора. Диапазон будет как раз о значения генератора до операции до значения после.
На поле - индекс. Вот и будет тебе быстро.
...
Рейтинг: 0 / 0
22.04.2021, 19:27
| Ответить | Цитировать | Написать  
Случайная выборка
    #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, 08:52
| Ответить | Цитировать | Написать  
Случайная выборка
    #40065254
shalamyansky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
shalamyansky
Участник
ъъъъъ

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


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

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

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

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

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


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

согласен, хеш не нужен. RAND в поле и индекс по нему достаточно
...
Рейтинг: 0 / 0
23.04.2021, 18:13
| Ответить | Цитировать | Написать  
24 сообщений из 24, страница 1 из 1
Форумы / Firebird, InterBase [игнор отключен] [закрыт для гостей] / Случайная выборка
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=40&msg=40064702&tid=1560050]:
 0ms
get settings:
 11ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 138ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 64ms
get tp. blocked users:
 1ms
others: 234ms
total:  482ms
созд. / загр.: 482ms
x
x
Закрыть


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