powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как отбирать из потока 1/1000 лучших экземпляров?
25 сообщений из 151, страница 2 из 7
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070222
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
допуски приемлемы
Тогда с большой вероятностью лучшие поинты относительно равномерно раскиданы по отрезкам, и можно обрабатывать блоки, например, по 100000 штук, используя вышеупомянутый heap и выбрав 100 лучших. Поместятся в оперативу 100 элементов полностью? Потом их скидываешь в файл, затираешь heap, чтобы переиспользовать, и переходишь к другому блоку.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070305
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
Так что хранить в памяти 1/1000 от потока -- понятное решение, но несколько прямолинейное.

Догадаться в памяти хранить только Q, а остальное сбрасывать на диск - это настолько невероятно сложная идея?..
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070314
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
Иван FXS
Так что хранить в памяти 1/1000 от потока -- понятное решение, но несколько прямолинейное.

Догадаться в памяти хранить только Q, а остальное сбрасывать на диск - это настолько невероятно сложная идея?..
автору любопытно, как решить в общем виде, то есть когда нет возможности заново взять элемент из потока
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070317
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
Догадаться в памяти хранить только Q, а остальное сбрасывать на диск - это настолько невероятно сложная идея?.
вы явно, не поняли, до чего мне "нужно было догадаться"-- не "хранить только Q", и уж тем более не " остальное сбрасывать на диск ",

а хранить в памяти Q и key, а все "отчётные данные" для сбрасывания на диск готовить заново по key, когда принимается решение их сбросить на диск.

Но да, правда, не догадался...
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070329
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS,
пробежал тему по диагонали, основное сказанное - скользящее окно и распределение, и в целом согласен.
М.б. полезна будет отсылочка к известным вещам, токмо чтобы порыть инет.

Распределение - для соцопросов, с целью экономии ресурсов, используют понятие репрезентативной выборки. Есть формулы для оценки оптимальной выборки (чтобы и детализация тоже была представительной). При условии, что апостериори предположения о распределении ген.совокупности окажутся достаточно достоверными. И придерживаясь методов обеспечения случайности выборки.

Окно - в простом случае однократного выбора есть задачка. Перед Иваном(хи-хи)-Царевичем чередой проходят царевны (по бесконечной однократной схеме). Какой стратегии он должен придерживаться, чтобы не прогадать с невестой? Кажется, нужно было на основе распределения максимума, но не помню. Типа, выждать некое время и выбрать первую выше мах.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070335
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98

Окно - в простом случае однократного выбора есть задачка. Перед Иваном(хи-хи)-Царевичем чередой проходят царевны (по бесконечной однократной схеме). Какой стратегии он должен придерживаться, чтобы не прогадать с невестой? Кажется, нужно было на основе распределения максимума, но не помню. Типа, выждать некое время и выбрать первую выше мах.

Блин. Вот ты что-то знакомое у меня снял с языка. Кажется из теории игр.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070339
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
exp98

Окно - в простом случае однократного выбора есть задачка. Перед Иваном(хи-хи)-Царевичем чередой проходят царевны (по бесконечной однократной схеме). Какой стратегии он должен придерживаться, чтобы не прогадать с невестой? Кажется, нужно было на основе распределения максимума, но не помню. Типа, выждать некое время и выбрать первую выше мах.

Блин. Вот ты что-то знакомое у меня снял с языка. Кажется из теории игр.
да это вроде бы "задача о разборчивой невесте", где надо максимизировать вероятность оптимального выбора. И там сначала отсматриваем (1/e) от всего потока, и далее берем первый попавшийся пункт, который лучше просмотренных. Но можно ли это обобщить на сабж..
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070378
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Возможно,я это запомнил как 1/3.
Не собирался обобщать, но вопрос вот, если для Р.Р.С.В. оценка матож Mn= n/(n+1) (т.е. M-->1), можно ли оценивать 2-й, 3-й .... мах как соответственно предыдущий по росту, предпредыду-й и т.д. ?..
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070388
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
"задача о разборчивой невесте"
она, типа, для устного счёта?

Я могу другую задачку из своей комсомольской юности пересказать -- её точно полагается в уме решать (без бумажки):

к Белоснежке в гости пришло бесконечное количество гномов, и каждый поставил в прихожей свой зонтик. Потом случился какой-то шухер (гусары, молчать!), и гномы в спешке разбежались, похватав первые попавшиеся им зонтики. Какова вероятность, что ни один из гномов не взял свой зонтик?
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070394
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
к Белоснежке в гости пришло бесконечное количество гномов, и каждый поставил в прихожей свой зонтик. Потом случился какой-то шухер (гусары, молчать!), и гномы в спешке разбежались, похватав первые попавшиеся им зонтики. Какова вероятность, что ни один из гномов не взял свой зонтик?
смутно припоминаю, что там тоже 1/е
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070410
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тут напрашивается решение Lim (1 - 1/n)^n. А чем равен предел, я не помню (мож и 1/e, мож и 0).
Только к СТ отношение отдалённое.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070525
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
а хранить в памяти Q и key, а все "отчётные данные" для сбрасывания на диск готовить заново по key

Ни о каких "отчётных данных" и тем более о их "готовке" в постановке задачи речь не шла. Речь шла о приходящем потоке готовых записей. Каждую из которых можно либо дропуть если она не попадает в диапазон "лучших", либо сохранить во временное хранилище из которого потом и выдать "1/1000 лучших".
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070529
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov, и в чём был глубокий смысл вашего рецепта

Dimitry Sibiryakov
в памяти хранить только Q, а остальное сбрасывать на диск
-- "остальное" -- это ваш ответ на вопрос топика "как отбирать"?

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

Ну и последняя фраза поста -- "Также не желательно решение, предполагающее накопление (по ходу работы) всех числовых значений самого Q.Хотя бы потому, что оно является тривиальным." -- по-моему, вполне выразительна.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070537
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS,

Не знаю как, но может удастся применить к этой задаче алгоритм p-square для расчета квантилей(процентилей) без сохранения всех значений (квадратичной интерполяцией из сэмплов)?

https://pypi.org/project/psquare/
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070544
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
Или вы хотели сказать "в памяти хранить все Q"...

Я сказал в точности то, что хотел сказать. В памяти хранить 1/1000 лучших Q, соответствующие им полные записи хранить на диске. Что именно в этой схеме тебе кажется странным или непонятным?
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070556
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
В памяти хранить 1/1000 лучших Q
1) я должен заранее знать, сколько экземпляров я обработаю, чтобы знать, чему равно 1/1000 от этого числа;

2) таким образом я сохраню на диск около 2/1000 от этого числа, то есть в два раза больше, чем собирался. Причем если я прерву процесс раньше, то сохраню на диск существенно большую долю, чем 2/1000, иными словами, поначалу я буду сохранять многократно больше, чем 1/1000 (первую тысячу, например, сохраню полностью).

Наверное, это не такое уж плохое решение (при условии (1) ). Может быть даже вообще хорошее...
__________________
UPDATE. Не уверен насчет 2/1000 и "в два раза больше" -- это были интуитивные заявления.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070558
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
Не уверен насчет 2/1000 и "в два раза больше" -- это были интуитивные заявления.
Кстати, это интересная задачка -- сколько экземпляров я на самом деле сохраню на диск, если буду действовать по этому алгоритму...
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070565
Иван FXS
1) я должен заранее знать

нет.
Иван FXS
2) таким образом я сохраню на диск около 2/1000 от этого числа

нет.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070582
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Иван FXS,


Вам white owl уже предложил точное решение этой несложной задачи, но Вы теперь хотите найти неточное?

Если на диск помещается Q/1000 потока, то решение White Owl точно отвечает формулировке. Если не помещается, то задача нерешаема, тк в условии надо сохранить 1/1000 всего потока на диске.

Если задача учебная, то напишите текст в оригинале. Иногда студенты так перевирают задачу "своими словами", что вся суть потеряна.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070586
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
НеофитSQL,

когда white owl писал "выделяешь себе в памяти массив" -- он, наверное, всё-таки имел в виду оперативную память (в которой "живут" массивы), вы же ничтоже сумняшеся заменяете "память" на "диск" ... вам, как неофиту, это различение "памяти" и "диска" кажется несущественным?

Не говоря уже о том, что в задаче не сказано, что размер потока заранее известен, а если бы он был известен, то, вообще говоря, слово "поток" было бы не слишком уместно -- тогда это было бы "множество" или "набор"...
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070590
размер потока значения не имеет
вы просто сравниваете текущее значение с минимальным в массиве на X элементов
и если больше, то заменяете это минимальное значение в массиве
далее берёте новое минимальное, и т.о. заполняете массив самыми высокими значениями
диск нужен, только когда надо сохранить уже заполненный массив, а так то текущий массив в памяти живёт
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070595
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
бабушкин зайчик
то заменяете это минимальное значение в массив
на какое значение заменяю?
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070621
на текущее в цикле
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070624
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
1) я должен заранее знать, сколько экземпляров я обработаю, чтобы знать, чему равно 1/1000 от этого числа;

Так ты его уже назвал - миллиард. Если ненароком их окажется меньше - просто на конечном этапе выдашь меньше.

Иван FXS

Кстати, это интересная задачка -- сколько экземпляров я на самом деле сохраню на диск

Совершенно неинтересная - максимум миллион. При размере записи в килобайт - на диске это займёт один гигабайт.

Иван FXS

вам, как неофиту, это различение "памяти" и "диска" кажется несущественным?

Оно кажется несущественным любому, знакомому с понятиями "кэш" и "своп".
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070627
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
Совершенно неинтересная - максимум миллион.
кажется, мы с вами обсуждаем разные задачи. Но пофиг.
...
Рейтинг: 0 / 0
25 сообщений из 151, страница 2 из 7
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как отбирать из потока 1/1000 лучших экземпляров?
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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