|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Дано: обрабатывается большой поток неких "цифровых сущностей", представленных неким набором параметров, среди которых, есть параметр Q (от "quality"). Нужно отбирать из потока и сохранять на диске "самые лучшие" из сущностей по параметру Q, так, чтобы сохранялось около 1/1000 от общего объёма "просеянного" потока. Каков тут может быть достаточно эффективный -- по соотношению "качество/затраты" -- алгоритм отбора? Заковыка в том, что точного решения задача не имеет, ибо в процессе работы мы не можем определить, попадает ли то или иное Q в 1/1000 от всей выборки. Также не желательно решение, предполагающее накопление (по ходу работы) всех числовых значений самого Q. Хотя бы потому, что оно является тривиальным. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 02:31 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
пример бы строки привели хоть ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 05:50 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Также не желательно решение, предполагающее накопление (по ходу работы) всех числовых значений самого Q. Хотя бы потому, что оно является тривиальным. а что с ними делать? как тривиальным, если среди них надо найти 1/1000 лучших? с каждой проверенной 1000 надо вынимать лучший и хранить ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 05:51 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Заковыка в том, что точного решения задача не имеет, ибо в процессе работы мы не можем определить, попадает ли то или иное Q в 1/1000 от всей выборки. Также не желательно решение, предполагающее накопление (по ходу работы) всех числовых значений самого Q. Хотя бы потому, что оно является тривиальным. Ты можешь заранее оценить сколько всего сущностей есть в потоке? Тысяча? Десть тысяч? Миллион? Миллиард? Выделяешь себе в памяти массив в который влезет 1/1000 от потока и начинаешь оценивать поток. Сначала просто набиваешь все оцененные сущности в массив (предполагая что они "самые лучшие"), массив естественно сортированный от лучших к худшим. А как массив заполнился начинаешь выкидывать из него с конца списка те что не оправдали ожиданий и записывать в него новые. В итоге и получишь массив с самыми лучшими, ну и заодно узнаешь точное число сущностей в исходном потоке и сможешь откорректировать чему равняется 1/1000 от него. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 06:30 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
White Owl Ты можешь заранее оценить сколько всего сущностей есть в потоке? Тысяча? Десть тысяч? Миллион? White Owl Выделяешь себе в памяти массив в который влезет 1/1000 от потока и начинаешь оценивать поток Наверное, мне стоило сразу сказать, что речь идет о методе Монте-Карло, так что то, что часть "не самых плохих" сущностей потеряется -- не критично. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 09:16 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS White Owl Ты можешь заранее оценить сколько всего сущностей есть в потоке? Тысяча? Десть тысяч? Миллион? White Owl Выделяешь себе в памяти массив в который влезет 1/1000 от потока и начинаешь оценивать поток Сохраняй в БД. Суть алгоритма все-равно не меняется. SQLite отлично подойдет, управляя размером кэша ты будешь управлять тем какая часть данных останется в памяти. Если доступен второй проход по тому же потоку, то достаточно сохранить порядковый номер сущности. Первым проходом получишь номера лучших, вторым сами сущности. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 09:31 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS, выглядит как типичный кейс streaming аналитики. обычно строят из чего-то типа kafka+spark, flume и т.п. поток пишем в кафку, ответ с лучшими сущностями в ту же кафку в соседний топик. видимо сначала надо вычитать первый миллион сообщений, что бы определить кто там лучший в первом миллионе, после этого в реалтайме считать среднее и параллельно те что проходят фильтр писать в ответный топик кафки. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 09:32 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Дано: обрабатывается большой поток неких "цифровых сущностей", представленных неким набором параметров, среди которых, есть параметр Q (от "quality"). Нужно отбирать из потока и сохранять на диске "самые лучшие" из сущностей по параметру Q, так, чтобы сохранялось около 1/1000 от общего объёма "просеянного" потока. На каждую тысячу событий вычисляй случайное число и бери из этой пачки элемент по номеру этого числа. Здесь еще надо-бы вспомнить про теорвер и доверительный интервал. Но мои знания уже протухли в этой части и поэтому пока я помню только термин. И кажется он посчитан для нормальных распределений. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 13:13 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Каков тут может быть достаточно эффективный -- по соотношению "качество/затраты" -- алгоритм отбора? Любая сортированная структура размером в 1/1000 от размера потока. Для твоего миллиарда это будет всего миллион. Иван FXS Заковыка в том, что точного решения задача не имеет, ибо в процессе работы мы не можем определить, попадает ли то или иное Q в 1/1000 от всей выборки. А оно нам и не надо, мы просто отбираем Х лучших, откидывая неудачников с хвоста. В конце берём столько сколько нужно с головы списка. Иван FXS Также не желательно решение, предполагающее накопление (по ходу работы) всех числовых значений самого Q. Всех накапливать и не надо, только лучших. Точнее - только тех, кто попал в вилку между текущим худшим из лучших и текущим лучшим из лучших. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 13:59 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS White OwlТы можешь заранее оценить сколько всего сущностей есть в потоке? Тысяча? Десть тысяч? Миллион? https://ru.wikipedia.org/wiki/Двоичная_куча ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 14:29 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov Любая сортированная структура размером в 1/1000 от размера потока. Иван FXS "цифровых сущностей", представленных неким набором параметров, среди которых, есть параметр Q ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 16:50 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
mayton вычисляй случайное число и бери из этой пачки элемент по номеру этого числа ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 16:55 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS mayton вычисляй случайное число и бери из этой пачки элемент по номеру этого числа Тогда извиняюсь. Я неправильно понял твою задачу. А как ты вообще собрался выбирать из потока по параметру Q когда ты не знаешь гистограмму Q в этом потоке? ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 16:58 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Я размышляю над таким алгоритмом: имеем два параметра -- порог П и "шаг порога" Ш 1) если Q очередного экземпляра в потоке больше или равно П, то а) сбрасываем экземпляр на диск и б) изменяем порог П = П + 999*Ш; 2) если Q очередного экземпляра в потоке меньше П, то а) игнорируем экземпляр и б) изменяем порог П = П - Ш. Понятно, что П будет колебаться около некоторого равновесного уровня, только если на одно событие (1) будет приходиться 999 событий (2). Не понятно только, как выбрать Ш. И должен ли он быть постоянным в ходе работы алгоритма... (Упссс, знаки попутал, теперь правильно.) ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 17:09 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Я размышляю над таким алгоритмом: имеем два параметра -- порог П и "шаг порога" Ш 1) если Q очередного экземпляра в потоке больше или равно П, то а) сбрасываем экземпляр на диск и б) изменяем порог П = П + 999*Ш; 2) если Q очередного экземпляра в потоке меньше П, то а) игнорируем экземпляр и б) изменяем порог П = П - Ш. Х X + П + 999*Ш X + 2П + 2*999*Ш ... то взяв начальное П <= Х, ты просто накидаешь в файл млн. самых маленьких. Правильно? ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 17:24 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Не понятно только, как выбрать Ш. И должен ли он быть постоянным в ходе работы алгоритма... ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 17:25 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Имя пользователя1 Правильно ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 17:27 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Имя пользователя1 Правильно ты вот по такому предложению не ответил. Можно или нет? Dima T Если доступен второй проход по тому же потоку, то достаточно сохранить порядковый номер сущности. Первым проходом получишь номера лучших, вторым сами сущности. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 17:58 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS 2) если Q очередного экземпляра в потоке меньше П, то а) игнорируем экземпляр и б) изменяем порог П = П - Ш. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 18:02 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Напоминает регулятор уровня записи в моём кассетном Technics. Порог быстро реагирует на уровнь но спадает медленно. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 18:10 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Имя пользователя1 ты вот по такому предложению не ответил. Можно или нет? ____________________ * -- типа, вот так https://www.sql.ru/forum/1335743/o-razvorachivanii-dlinnogo-celogo-v-nabor-iz-100-psevdosluchaynyh-deystvitelnyh ... |
|||
:
Нравится:
Не нравится:
|
|||
13.05.2021, 18:40 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Так что я продолжаю обсуждать постановку задачи более общую (чем в моём проекте). Ну то есть - решение всё равно будет очень хреново работать на некоторых специальных видах перестановок, и почти наверняка не сможет собрать абсолютно все требуемые значения. Такие допуски приемлемы для "общего случая"? ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2021, 00:23 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Имя пользователя1, допуски приемлемы, только я так и не понял, как выбрать Ш. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2021, 00:39 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS, можешь в Excel показать величину Q в виде графика? ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2021, 00:58 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
mayton, в виде графика ... у которого что отложено по осям X и Y? И как построен набор отображаемых (в виде точек) элементов -- график всех значений Q, типа, всего "миллиарда"? ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2021, 06:29 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS допуски приемлемы ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2021, 10:25 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Так что хранить в памяти 1/1000 от потока -- понятное решение, но несколько прямолинейное. Догадаться в памяти хранить только Q, а остальное сбрасывать на диск - это настолько невероятно сложная идея?.. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2021, 13:44 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov Иван FXS Так что хранить в памяти 1/1000 от потока -- понятное решение, но несколько прямолинейное. Догадаться в памяти хранить только Q, а остальное сбрасывать на диск - это настолько невероятно сложная идея?.. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2021, 14:09 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov Догадаться в памяти хранить только Q, а остальное сбрасывать на диск - это настолько невероятно сложная идея?. а хранить в памяти Q и key, а все "отчётные данные" для сбрасывания на диск готовить заново по key, когда принимается решение их сбросить на диск. Но да, правда, не догадался... ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2021, 14:19 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS, пробежал тему по диагонали, основное сказанное - скользящее окно и распределение, и в целом согласен. М.б. полезна будет отсылочка к известным вещам, токмо чтобы порыть инет. Распределение - для соцопросов, с целью экономии ресурсов, используют понятие репрезентативной выборки. Есть формулы для оценки оптимальной выборки (чтобы и детализация тоже была представительной). При условии, что апостериори предположения о распределении ген.совокупности окажутся достаточно достоверными. И придерживаясь методов обеспечения случайности выборки. Окно - в простом случае однократного выбора есть задачка. Перед Иваном(хи-хи)-Царевичем чередой проходят царевны (по бесконечной однократной схеме). Какой стратегии он должен придерживаться, чтобы не прогадать с невестой? Кажется, нужно было на основе распределения максимума, но не помню. Типа, выждать некое время и выбрать первую выше мах. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2021, 14:45 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
exp98 Окно - в простом случае однократного выбора есть задачка. Перед Иваном(хи-хи)-Царевичем чередой проходят царевны (по бесконечной однократной схеме). Какой стратегии он должен придерживаться, чтобы не прогадать с невестой? Кажется, нужно было на основе распределения максимума, но не помню. Типа, выждать некое время и выбрать первую выше мах. Блин. Вот ты что-то знакомое у меня снял с языка. Кажется из теории игр. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2021, 14:56 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
mayton exp98 Окно - в простом случае однократного выбора есть задачка. Перед Иваном(хи-хи)-Царевичем чередой проходят царевны (по бесконечной однократной схеме). Какой стратегии он должен придерживаться, чтобы не прогадать с невестой? Кажется, нужно было на основе распределения максимума, но не помню. Типа, выждать некое время и выбрать первую выше мах. Блин. Вот ты что-то знакомое у меня снял с языка. Кажется из теории игр. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2021, 15:08 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Возможно,я это запомнил как 1/3. Не собирался обобщать, но вопрос вот, если для Р.Р.С.В. оценка матож Mn= n/(n+1) (т.е. M-->1), можно ли оценивать 2-й, 3-й .... мах как соответственно предыдущий по росту, предпредыду-й и т.д. ?.. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2021, 16:19 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Имя пользователя1 "задача о разборчивой невесте" Я могу другую задачку из своей комсомольской юности пересказать -- её точно полагается в уме решать (без бумажки): к Белоснежке в гости пришло бесконечное количество гномов, и каждый поставил в прихожей свой зонтик. Потом случился какой-то шухер (гусары, молчать!), и гномы в спешке разбежались, похватав первые попавшиеся им зонтики. Какова вероятность, что ни один из гномов не взял свой зонтик? ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2021, 16:33 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS к Белоснежке в гости пришло бесконечное количество гномов, и каждый поставил в прихожей свой зонтик. Потом случился какой-то шухер (гусары, молчать!), и гномы в спешке разбежались, похватав первые попавшиеся им зонтики. Какова вероятность, что ни один из гномов не взял свой зонтик? ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2021, 16:54 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Тут напрашивается решение Lim (1 - 1/n)^n. А чем равен предел, я не помню (мож и 1/e, мож и 0). Только к СТ отношение отдалённое. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2021, 17:41 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS а хранить в памяти Q и key, а все "отчётные данные" для сбрасывания на диск готовить заново по key Ни о каких "отчётных данных" и тем более о их "готовке" в постановке задачи речь не шла. Речь шла о приходящем потоке готовых записей. Каждую из которых можно либо дропуть если она не попадает в диапазон "лучших", либо сохранить во временное хранилище из которого потом и выдать "1/1000 лучших". ... |
|||
:
Нравится:
Не нравится:
|
|||
15.05.2021, 13:39 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov, и в чём был глубокий смысл вашего рецепта Dimitry Sibiryakov в памяти хранить только Q, а остальное сбрасывать на диск Или вы хотели сказать "в памяти хранить все Q"... тогда замена слова "все" на конструкцию "только-остальное" была не слишком удачной. Ну и последняя фраза поста -- "Также не желательно решение, предполагающее накопление (по ходу работы) всех числовых значений самого Q.Хотя бы потому, что оно является тривиальным." -- по-моему, вполне выразительна. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.05.2021, 14:35 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS, Не знаю как, но может удастся применить к этой задаче алгоритм p-square для расчета квантилей(процентилей) без сохранения всех значений (квадратичной интерполяцией из сэмплов)? https://pypi.org/project/psquare/ ... |
|||
:
Нравится:
Не нравится:
|
|||
15.05.2021, 15:59 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Или вы хотели сказать "в памяти хранить все Q"... Я сказал в точности то, что хотел сказать. В памяти хранить 1/1000 лучших Q, соответствующие им полные записи хранить на диске. Что именно в этой схеме тебе кажется странным или непонятным? ... |
|||
:
Нравится:
Не нравится:
|
|||
15.05.2021, 18:10 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov В памяти хранить 1/1000 лучших Q 2) таким образом я сохраню на диск около 2/1000 от этого числа, то есть в два раза больше, чем собирался. Причем если я прерву процесс раньше, то сохраню на диск существенно большую долю, чем 2/1000, иными словами, поначалу я буду сохранять многократно больше, чем 1/1000 (первую тысячу, например, сохраню полностью). Наверное, это не такое уж плохое решение (при условии (1) ). Может быть даже вообще хорошее... __________________ UPDATE. Не уверен насчет 2/1000 и "в два раза больше" -- это были интуитивные заявления. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.05.2021, 22:40 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Не уверен насчет 2/1000 и "в два раза больше" -- это были интуитивные заявления. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.05.2021, 22:51 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS 1) я должен заранее знать нет. Иван FXS 2) таким образом я сохраню на диск около 2/1000 от этого числа нет. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.05.2021, 00:15 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS, Вам white owl уже предложил точное решение этой несложной задачи, но Вы теперь хотите найти неточное? Если на диск помещается Q/1000 потока, то решение White Owl точно отвечает формулировке. Если не помещается, то задача нерешаема, тк в условии надо сохранить 1/1000 всего потока на диске. Если задача учебная, то напишите текст в оригинале. Иногда студенты так перевирают задачу "своими словами", что вся суть потеряна. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.05.2021, 07:12 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
НеофитSQL, когда white owl писал "выделяешь себе в памяти массив" -- он, наверное, всё-таки имел в виду оперативную память (в которой "живут" массивы), вы же ничтоже сумняшеся заменяете "память" на "диск" ... вам, как неофиту, это различение "памяти" и "диска" кажется несущественным? Не говоря уже о том, что в задаче не сказано, что размер потока заранее известен, а если бы он был известен, то, вообще говоря, слово "поток" было бы не слишком уместно -- тогда это было бы "множество" или "набор"... ... |
|||
:
Нравится:
Не нравится:
|
|||
16.05.2021, 09:00 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
размер потока значения не имеет вы просто сравниваете текущее значение с минимальным в массиве на X элементов и если больше, то заменяете это минимальное значение в массиве далее берёте новое минимальное, и т.о. заполняете массив самыми высокими значениями диск нужен, только когда надо сохранить уже заполненный массив, а так то текущий массив в памяти живёт ... |
|||
:
Нравится:
Не нравится:
|
|||
16.05.2021, 10:38 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
бабушкин зайчик то заменяете это минимальное значение в массив ... |
|||
:
Нравится:
Не нравится:
|
|||
16.05.2021, 10:59 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
на текущее в цикле ... |
|||
:
Нравится:
Не нравится:
|
|||
16.05.2021, 13:39 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS 1) я должен заранее знать, сколько экземпляров я обработаю, чтобы знать, чему равно 1/1000 от этого числа; Так ты его уже назвал - миллиард. Если ненароком их окажется меньше - просто на конечном этапе выдашь меньше. Иван FXS Кстати, это интересная задачка -- сколько экземпляров я на самом деле сохраню на диск Совершенно неинтересная - максимум миллион. При размере записи в килобайт - на диске это займёт один гигабайт. Иван FXS вам, как неофиту, это различение "памяти" и "диска" кажется несущественным? Оно кажется несущественным любому, знакомому с понятиями "кэш" и "своп". ... |
|||
:
Нравится:
Не нравится:
|
|||
16.05.2021, 13:52 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov Совершенно неинтересная - максимум миллион. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.05.2021, 14:16 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Если перевести в плоскость примеров. На вход - миллард таких сущностей. Input: Код: sql 1. 2. 3. 4. 5. 6.
На выходе 1 000 000 штук таких: Код: sql 1. 2. 3. 4. 5.
Тогда цена вопроса - просто выбор оптимальной дисковой структуры данных котора способна втянуть в себя произвольное число таких записей (records) ранжированных по Q. Для оперативной памяти - это может быть Куча (Heap) как уже кто-то предлагал. Также пойдет красно-черное-дерево где ключ будет Q. На С++ ей соотвествует любая сортируемая мапа. Если памяти будет не хватать - пойдет Key-Valuе DBMS наподобие LevelDb. Для нее есть интерфейсы программирования почти на всех языках. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.05.2021, 15:35 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
mayton, не понимаю, вы настолько технооптимист, что вообще не можете представить задачу, которую нельзя было бы решить брутфорсом? А если бы я тогда сказал "триллион" вместо "миллиард" (ну, да, мне просто фантазии не хватило)... ... |
|||
:
Нравится:
Не нравится:
|
|||
16.05.2021, 17:19 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Я - не технооптимист. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.05.2021, 18:08 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS mayton, не понимаю, вы настолько технооптимист, что вообще не можете представить задачу, которую нельзя было бы решить брутфорсом? А если бы я тогда сказал "триллион" вместо "миллиард" (ну, да, мне просто фантазии не хватило)... Если вы сказали максимум триллион, значит у вас есть диска на миллиард. (Иначе вам некуда 1/1000 сохранить) Далее следует решение white owl, которое вам отсеивает верхний миллиард. По окончании потока, который не превышает триллион, делите счётчик сущностей на 1000, округляете в удобную для вас сторону (рекомендую вверх), и берете таковое число строчек из отсеянного миллиарда который уже на диске. Готово: точное решение в один проход потока неизвестного заранее размера. Не забудьте отвести счётчику сущностей хотя бы 40 бит, всё-таки триллион ожидаете. Чем вас не устраивает точное решение задачи? ... |
|||
:
Нравится:
Не нравится:
|
|||
16.05.2021, 19:49 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Заковыка в том, что точного решения задача не имеет, ибо в процессе работы мы не можем определить, попадает ли то или иное Q в 1/1000 от всей выборки. . А, вижу. Вас наверное не устраивает то, что вы думали что точного решения не существует, а оно оказалось довольно очевидным. Ну тогда давайте забудем о существовании точного решения и решим неточно, статистическими методами. Только не способом тыка папы Карло, а с формулами. На основании значений первых N cущностей делаете предположение о статистическом распределении Q. Надеетесь на гауссовое или равномерное в фиксированном интервале. Затем, выбрав погрешность альфа, определяете Qmin, которое с заданной погрешностью альфа будет меньше чем верхний 0.1% значений Q всей популяции, затем отбирает все сущности из потока для которых Q > Qmin. Не забудьте сохранить первые N сущностей предшествующие анализу; они не бросовые. Число N зависит от альфы. Вуаля, неточное решение зато с формулами и ограничениями на распределение Q. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.05.2021, 20:10 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
НеофитSQL, вы увидели мой ответ White Owl-у Иван FXS White Owl Выделяешь себе в памяти массив в который влезет 1/1000 от потока и начинаешь оценивать поток ... |
|||
:
Нравится:
Не нравится:
|
|||
16.05.2021, 21:06 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS, Видел конечно. Вам в памяти сущности хранить и не требуется, только Q значения уже сохранённых на диске сущностей, чтобы знать какие из них заменять. Может, у вас какие-то другие ограничения в задаче? Например, входной поток бесконечный, или диск не разрешает перезапись? Тогда точное решение не существует, и можно рассуждать об эвристиках. И при условиях выше (поток произвольной длины, диск одноразовый) все эвристики разваливаются при Q = n, где n номер сущности в потоке. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.05.2021, 23:58 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
НеофитSQL, вы прочитали в моём посте требование к обсуждаемому коду " сохранять на диске "самые лучшие" из сущностей по параметру Q"? Если да, то ткните пальцем в то, каким образом "точное решение White Owl-а" будет исполнять это требование. Насколько я вижу, это "точное решение" просто игнорирует этот аспект задания. Ну и у вас словарные расхождения, потому что там говорится " набиваешь все оцененные сущности в массив ", а вы это прочитываете как "в памяти сущности хранить и не требуется"... ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 00:39 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
НеофитSQL, в сухом остатке, ответьте мне, вот я создал массив размером миллион под значения Q... и что я должен буду весь первый миллион сущностей на диск забубенить? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 00:52 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS и что я должен буду весь первый миллион сущностей на диск забубенить? Да. В чём проблема-то? Потом будешь удалять худшие из них по мере прихода лучших. Опять же в чём проблема-то? PS: Но сдаётся мне, что весь этот миллион таки влезет в ОЗУ. Потому что, как я уже сказал, при размере записи в килобайт это всего гигабайт суммарного объёма. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 00:59 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov, проблема в том, например, что запись на диск это медленная операция. Я на другом форуме параллельно эту тему обсуждал, там люди, менее ленивые, чем я, быстренько сделали прогоны, и получилось, что при такой схеме работы на диск будет сбрасываться примерно в семь раз больше сущностей, чем 1/1000. Dimitry Sibiryakov весь этот миллион таки влезет в ОЗУ Или, типа, вместо "сохранять на диске" -- "буферизовать в ОЗУ, а потом когда-то (логика это "когда-то" не предъявлена) сохранять на диск"? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 01:28 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS НеофитSQL, в сухом остатке, ответьте мне, вот я создал массив размером миллион под значения Q... и что я должен буду весь первый миллион сущностей на диск забубенить? Да. Первый миллион точно*. А если Q сущностей монотонно растет, то вообще все сущности потока коснутся диска, по правилу FIFO. Мало того, для монотонно растущих Q ничего лучше и не будет. В зависимости от размера диск кэша и стратегии отложенных записей, механический диск может и не трепыхнуться до самого конца задачи. Не совсем в тему, но эту задачу базы данных решают точно и успешно каждый день. "Отсортировать таблицу неизвестной длины** по колонке Q, показать/сохранить первые 1% строчек". Строчки в БД могут содержать многомегабпйтные объекты. (*) Предвидя возможные придирки, не всегда. min(1e6,N), где N длина потока. (**) Иногда таблицы в БД не имеют известного числа строк. Это встречается, но не все с этим знакомы. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 01:35 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS, Я прочитал ваши недавние ответы, заметил что вас беспокоит скорость сохранения сущностей на диск. Если точное решение не устраивает из-за медленной операции сохранения данных, которое в худшем случае включает в себя *все* сущности потока, ты вы будете оптимизировать сокращение числа сохранений в ущерб точности. Тут придется решать какой выигрыш стоит какой точности. Например, отсортированный поток даст точность 0 (всегда не то что надо) для любой экономящей записи эвристики. Если поток можно читать в два подхода, задача решается легко. Если Q перемешаны хорошо, можно что-то мудрить, все остальное разбивается об отсортированный поток. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 02:01 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
НеофитSQL, дело даже не в том, беспокоит ли меня, а в том, что " ха-ха, ты что, не знаешь, как из N сущностей отобрать K лучших по параметру Q?! " -- не является ответом на вопрос: " как организовать сохранение 1/1000 лучших экземпляров из обрабатываемого потока? " ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 02:13 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
К сожалению, неуважительное отношение к собеседнику это часто, но не всегда особенность русскоязычных форумов. Причина возможно в том, что ценность специалиста в первую очередь определяется не знанием, а умением продуктивно общаться с коллегами, и улучшать эффективность команды. Для людей значительных знаний в какой-то технической области добавляется обязательное требование уметь преподавать: связно и доходчиво выражать мысли, точку зрения и т.д. Для первоначальной постановки задачи решение white owl выглядит на мой взгляд превосходно, поэтому появились вопросы чем точное решение не подходит, и есть ли дополнительные критерии. Не сразу, но выяснилось что есть важный для вас но ранее не упомянутый критерий количества сохранений, который вы связываете со скоростью. Что я знаю о вашей задаче: у вас есть поток этих сущностей, каждая содержит неотделимую от нее метрику Q. Поток высокоскоростной, неизвестной но конечной длины не превышающей миллиард. Нужно в один проход выбрать и сохранить верхние 0.1% сущностей по метрике Q. Диапазон Q неизвестен, порядок следования сущностей может быть любой. Устройство может сохранить один миллион сущностей, не больше. Метод сохранения сущностей считается медленным, поэтому точное решение с перезаписью не годится. Допускается неточное решение, если оно использует меньше сохранений чем точное. Этого мало для ТЗ. Если бы меня наняли решать такую задачу, я бы задал вопросы: - прочность критериев. Например, можно ли любую часть потока читать дважды? - природа данных, происхождение и примеры. Мне известны неудачные данные, которые мочат все эвристики в нулевую точность. - скоростные характеристики потока данных и механизма сохранения. Это важно. Например, если вход один гигабит, а сохранение всего 100mbps, то при соотношении чтение/запись 10:1 и выше сохранение перестанет тормозить процесс. Оптимизировать вечно нет смысла. - скоростные параметры железа. Если вычисляла слабая, некоторые подходы исключаются. - допустимое количество ошибок, как меняется - допустимое время исполнения. - есть ли требование регулировки, чтоб заказчик мог сам подкручивать быстрее/точнее - формат результата: "пришло 100500 шт, самые верхние были #42, #69, .. из них сохранены 88%" Не исключено, что в итоге после анализа и результатов тестов заказчик решит купить диск побыстрее, и не связываться с эвристикой у которой не полностью исследована связь между характером ввода и ошибкой результата. Последнее вполне тянет на курсовую, где стоимость усилий и ответственность низкая. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 05:19 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
НеофитSQL Что я знаю о вашей задаче: у вас есть поток этих сущностей, каждая содержит неотделимую от нее метрику Q. Поток высокоскоростной, неизвестной но конечной длины не превышающей миллиард. Нужно в один проход выбрать и сохранить верхние 0.1% сущностей по метрике Q. Диапазон Q неизвестен, порядок следования сущностей может быть любой. Устройство может сохранить один миллион сущностей, не больше. Метод сохранения сущностей считается медленным, поэтому точное решение с перезаписью не годится. Допускается неточное решение, если оно использует меньше сохранений чем точное. вот решение для этих условий: бабушкин зайчик размер потока значения не имеет вы просто сравниваете текущее значение с минимальным в массиве на X элементов и если больше, то заменяете это минимальное значение в массиве далее берёте новое минимальное, и т.о. заполняете массив самыми высокими значениями диск нужен, только когда надо сохранить уже заполненный массив, а так то текущий массив в памяти живёт 0.1% от триллиона? это ярд интов = 4 гигабайта (нужны ведь только Q, а строки из БД брать по необходимости) ну вообще не бох весть какая память, на каждом втором компе есть но если вдруг понадобится не 0.1, а 1%, то на диск можно скидывать верхние 500, оставляя в памяти самое мелкое в них значение, и вот его тогда менять (предварительно конечно рассортировав по файлам от меньшего к большему) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 08:07 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
бабушкин зайчик (нужны ведь только Q, а строки из БД брать по необходимости ) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 08:36 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
НеофитSQL Этого мало для ТЗ. Если бы меня наняли решать такую задачу, я бы задал вопросы ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 08:38 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Несколько слов о задаче, в рамках размышления о которой был написан пост: 1) "сущности" о которых идет речь, генерируются в два этапа; 2) на первом этапе на основании ключа (key) генерируется пачка из 100 пред-сущностей (по числу тикеров [ticker] в индексе NASDAQ100) -- так что (повторно) сгенерировать одну из них не намного легче, чем все сто разом; 3) на втором этапе для каждой из этих 100 пред-сущностей сканируется несколько сотен (пусть будет 200) значений порога [p], каждый из которых даёт своё индивидуальное значение качества Q. 4) то есть вот этой тройкой (key; ticker; p) задаётся та сущность, для которой нужно по её Q решить -- для каждого тикера отдельно , -- попадает ли она в 0.1% лучших, то есть достойна ли она того, чтобы быть сохраненной (на диск). Итак, хотите накапливать в буфере только значения (key; ticker; p), а потом -- когд-то -- решить, какие из них сохранять? Пожалуйста, только для повторной генерации каждой сущности нужно будет затратить примерно в 100*200 = 20000 больше вычислительных ресурсов, чем тратилось на генерацию её в "пакетном" режиме. Но брутфорс ведь наше всё. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 09:31 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS накапливать в буфере только значения (key; ticker; p) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 09:43 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
бабушкин зайчик НеофитSQL Что я знаю о вашей задаче: у вас есть поток этих сущностей, каждая содержит неотделимую от нее метрику Q. Поток высокоскоростной, неизвестной но конечной длины не превышающей миллиард. Нужно в один проход выбрать и сохранить верхние 0.1% сущностей по метрике Q. Диапазон Q неизвестен, порядок следования сущностей может быть любой. Устройство может сохранить один миллион сущностей, не больше. Метод сохранения сущностей считается медленным, поэтому точное решение с перезаписью не годится. Допускается неточное решение, если оно использует меньше сохранений чем точное. вот решение для этих условий: бабушкин зайчик размер потока значения не имеет вы просто сравниваете текущее значение с минимальным в массиве на X элементов и если больше, то заменяете это минимальное значение в массиве далее берёте новое минимальное, и т.о. заполняете массив самыми высокими значениями диск нужен, только когда надо сохранить уже заполненный массив, а так то текущий массив в памяти живёт 0.1% от триллиона? это ярд интов = 4 гигабайта (нужны ведь только Q, а строки из БД брать по необходимости) ну вообще не бох весть какая память, на каждом втором компе есть но если вдруг понадобится не 0.1, а 1%, то на диск можно скидывать верхние 500, оставляя в памяти самое мелкое в них значение, и вот его тогда менять (предварительно конечно рассортировав по файлам от меньшего к большему) Я тоже самое хотел предложить. Но непонятно почему Иван ведет себя так агрессивно по отношению к программистам, придя в форум программирования. И почему очередь с приоритетами он называет "брутфорсом". С моей точки зрения это просто структура данных. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 11:32 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
mayton Но непонятно почему Иван ведет себя так агрессивно по отношению к программистам, Если "строки" уже "в БД", и их можно оттуда "брать" -- то в чём, по-вашему, может состоять задача? Посчитать для этих строк Q и дописать его "в БД" (или куда-то рядом), а потом "ха-ха, из N сущностей суметь выбрать K лучших по критерию Q"? Ну да, это в самом деле "ха-ха". ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 11:47 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Сущности. Строки. DataRows. Tuples. Entities. Objects. Да такая она... проф-деформация. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 11:58 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
вообще, я зря повелся и согласился на предложение (в третьей реплике от начала обсуждения!): "заранее оценить сколько всего сущностей есть в потоке" -- поток это поток, труба, в ней течёт вода. А мне говорят: ну, сколько там может быть воды в той трубе -- выкопай бассейн, собери в нем всю воду, и делай с ней всё, что хочешь. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 12:08 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS бабушкин зайчик (нужны ведь только Q, а строки из БД брать по необходимости ) не видел я у вас в ТЗ, чтобы вам прямо во время поиска Q надо было пользоваться значениями в таких задачах обычно сначала отбирают нужное, а потом уже им пользуются Иван FXS только значения (key; ticker; p; Q), конечно. как бы там ни было, в чём проблема сложить эти ваши значения в БД, оставив в памяти лишь Q, из которых отсеять нужные? Помимо очевидных выгод, таким образом можно надеяться, что данные не выпадут из кэша CPU, что ускорит процесс раз в 50. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 13:01 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
бабушкин зайчик, то есть вы продолжаете исходить из того, что я не знаю, как из миллиарда значений Q отобрать миллион самых больших? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 13:27 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
бабушкин зайчик как бы там ни было, в чём проблема сложить эти ваши значения в БД, оставив в памяти лишь Q, из которых отсеять нужные? Помимо очевидных выгод, таким образом можно надеяться, что данные не выпадут из кэша CPU, что ускорит процесс раз в 50. Это очень жесткие требования. На такое можно пойти только в том случае, когда система, принимающая решение так-же быстро должна реагировать. Синхронно с фронтом приходящих новых данных. Но такое бывает редко IMHO. Тем более что биржевые индексы - это инфа вторичная. Для нее тоже есть свой источник данных и расчет этого индекса не факт что такой-же быстрый. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 13:37 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS вы продолжаете исходить из того, что я не знаю, как из миллиарда значений Q отобрать миллион самых больших? Похоже, Вы не знаете, что 1/1000 от бесконечности это бесконечность и динамически подстраиваете задачу под невозможность её решения. Это бесперспективняк. PS: Диски быстрее, чем сеть и рассматривать их как ограничение можно только если ваши "сущности" порождаются ГСЧ. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 13:41 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
mayton Это очень жесткие требования. в БД сохранять? А "не жёсткие" - это какие? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 13:48 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS бабушкин зайчик, то есть вы продолжаете исходить из того, что я не знаю, как из миллиарда значений Q отобрать миллион самых больших? при вашем регулярно растущем ТЗ вы скоро забудете, зачем вообще приходили вы до сих пор так и не сделали главного... не показали исходную строку И конечную строку. ну отберите, в чём проблема? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 13:51 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
бабушкин зайчик mayton Это очень жесткие требования. в БД сохранять? А "не жёсткие" - это какие? Не жосткие - это когда человек-от-бизнеса захочет на них взглянуть. Подумать. И принять какое-то решение. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 13:54 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov Похоже, Вы не знаете, что 1/1000 от бесконечности это бесконечность Dimitry Sibiryakov рассматривать их как ограничение можно только если ваши "сущности" порождаются ГСЧ ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 13:58 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Я так понимаю Иван FXS хочет заранее предсказать пороговое значение Q, а дальше просто дергать с потока только те сущности у которых Q больше порога. Только придумать не может как порог найти. ИМХУ тут разве что нейросети тренировать, и то решение будет негарантированным. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 14:03 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS, Если каждая сущность генерится из трех чисел, то хранить сущности нет необходимости. Сгенерите, посчитайте Q, запомните интересующие тройки. По тройкам сгенерите второй (и третий, и четвертый) раз. У вас скорость генерации превышает скорость высокоскоростных дисков. Такое хранить смысла нет, быстрее сгенерить чем прочитать. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 14:04 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS да, они именно ГСЧ и порождаются, я уже это упоминал, и даже ссылку на тему давал В пределах той темы не нужно "1/1000 лучших", достаточно и просто "миллиона лучших". А с учётом того, что они генерятся из одного целого - этот миллион займёт четыре мегабайта памяти, на диск сбрасывать ничего не нужно. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 14:15 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
НеофитSQL, я объяснял на предыдущей странице ( 22322961 ), что у меня сущности генерируются "пакетами" по 100*200=20000 штук ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 14:19 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
mayton бабушкин зайчик пропущено... в БД сохранять? А "не жёсткие" - это какие? Не жосткие - это когда человек-от-бизнеса захочет на них взглянуть. Подумать. И принять какое-то решение. т.е. алгоритм придумывает обыватель? его дело чётко составить ТЗ и показать требуемый результат. А он блин ставит задачу так, что её надо непременно сохранять на диск, а потом оказывается, что там всего 20000 сущностей, которые можно в памяти держать не парясь... Да там ещё под вопросом эта 20... а чё не 1000? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 14:24 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
и почему нельзя прямо во время генерации отсеять нужные? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 14:31 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
бабушкин зайчик а потом оказывается, что там всего 20000 сущностей key имеет тип Длинное целое, мощность которого 4 миллиарда, и для каждого значения key я генерирую пакет из 20000 сущностей ... или всё бесполезно? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 14:43 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS или всё бесполезно? Без точной формулировки задачи - бесполезно. Твоё "хочу поработать с большим количеством" - пустое сотрясение воздуха. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 15:13 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
а вам разжевать значение слова "разжевать"? вы 4 страницы только запутываете мозги беззащитных программистов. " мощность long int = 4 миллиарда"... што это вообще?! ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 15:14 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov, я продолжаю считать, что если вы перестанете пытаться убедить меня и себя, что в моей задаче поток -- это никакой не поток , а его целиком можно залить в бассейн, и работать с ним как с целиком доступным набором , то исходная формулировка задачи окажется вполне точной. Просто повторите десять раз: поток, поток, поток, поток, поток, поток, поток, поток, поток, поток . ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 15:22 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS исходная формулировка задачи окажется вполне точной. И для этой исходной формулировки "наилучшим по соотношению качество/затраты" будет решение, которое Вы назвали "брутфорсом": сохранять на диске текущий набор "лучших", перезаписывая худшие из них новыми по мере поступления. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 15:32 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
бабушкин зайчик мощность long int = 4 миллиарда"... што это вообще?! Математики так называют количество возможных значений ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 15:52 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Dimitry Sibiryakov, я продолжаю считать, что если вы перестанете пытаться убедить меня и себя, что в моей задаче поток -- это никакой не поток , а его целиком можно залить в бассейн, и работать с ним как с целиком доступным набором , то исходная формулировка задачи окажется вполне точной. Передергивать не надо. Никто не предлагал сохранять все. Только хранить миллион самых лучших на текущий момент. Ты сам выше писал что сохранить придется в 7 раз больше чем надо, это нормальный оверхэд, не 0.1%, а 0,7%. Что тут плохого? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:01 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov, можете сформулировать критерий, на основании которого будет приниматься решение о том, что очередную сущность в потоке не следует сохранять на диск? Вот, я обрабатываю сущность номер k (k может быть равно 1, 999, 1000, 1001, 145142 или 217363728) -- и Q(k) оказалось равно 1.23456 ... сохранять её на диск или проигнорировать? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:02 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dima T Только хранить миллион самых лучших на текущий момент ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:06 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Dima T Только хранить миллион самых лучших на текущий момент поток = цикл у цикла есть счётчик перестаньте уже за программистов думать лучше учитесь чётко описывать задачу ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:12 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dima T бабушкин зайчик мощность long int = 4 миллиарда"... што это вообще?! Математики так называют количество возможных значений а зачем это на форуме программистов и какое отношение имеет к задаче? ему то что эти 4 ярда? Он вообще знает, что 4 000 000 000 ярда или 1 всё = 8 байт? а то что long это 9223372036854775807 он вообще никогда не слышал. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:14 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Dimitry Sibiryakov, можете сформулировать критерий, на основании которого будет приниматься решение о том, что очередную сущность в потоке не следует сохранять на диск? Вот, я обрабатываю сущность номер k (k может быть равно 1, 999, 1000, 1001, 145142 или 217363728) -- и Q(k) оказалось равно 1.23456 ... сохранять её на диск или проигнорировать? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:15 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Dima T Только хранить миллион самых лучших на текущий момент Как уже написали 0,1% от бесконечности - бесконечность. В такой постановке задача не решаема. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:19 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS критерий, на основании которого будет приниматься решение о том, что очередную сущность в потоке не следует сохранять 1) из первой тысячи ничего не сохраняю на диск, но выясняю (и запоминаю) Max(Q), и его устанавливаю в качестве порога сохранения П(2) для обработки второй тысячи; 2) из второй тысячи сохраняю на диск всё, что лучше П(2), и начинаю заполнять двоичную кучу -- так, чтобы к концу второй тысячи в этой куче было два элемента; то есть по итогу обработки двух тысяч в куче два значения Q, и минимальный из которых будет порогом П(3) для обработки третьей тысячи; 3) из третьей .................. лучше П(3) ......... к концу третьей тысячи в этой куче было три элемента; и т.д. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:20 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Иван FXS критерий, на основании которого будет приниматься решение о том, что очередную сущность в потоке не следует сохранять 1) из первой тысячи ничего не сохраняю на диск, но выясняю (и запоминаю) Max(Q), и его устанавливаю в качестве порога сохранения П(2) для обработки второй тысячи; 2) из второй тысячи сохраняю на диск всё, что лучше П(2), и начинаю заполнять двоичную кучу -- так, чтобы к концу второй тысячи в этой куче было два элемента; то есть по итогу обработки двух тысяч в куче два значения Q, и минимальный из которых будет порогом П(3) для обработки третьей тысячи; 3) из третьей .................. лучше П(3) ......... к концу третьей тысячи в этой куче было три элемента; и т.д. Таким образом ты, во первых, потеряешь "лучшие" из первой тысячи если они там были. Во вторых, если в каждой очередной тысяче будут две сущности достойные быть в списке самых лучших, ты запомнишь только одну из них. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:24 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dima T Как уже написали 0,1% от бесконечности - бесконечность ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:25 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
White Owl Бред какой-то White Owl если в каждой очередной тысяче будут две сущности достойные быть в списке самых лучших, ты запомнишь только одну из них По итогу обработки любых N тысяч в куче будут находиться N максимальных значений из всех этих N тысяч. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:29 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS 1) из первой тысячи ничего не сохраняю на диск, но выясняю (и запоминаю) Max(Q), и его устанавливаю в качестве порога сохранения П(2) для обработки второй тысячи; Если Max(Q) окажется абсолютным максимумом, то в итого будет пустой список. ИМХО не существует алгоритма как в один проход отсечь заданное количество максимальных элементов, при этом не сохраняя лишних. Какая-то избыточность должна быть, чтобы в конце выкинуть лишнее. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:30 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS Dima T Как уже написали 0,1% от бесконечности - бесконечность Зато ты можешь выбрать тысячу или миллион лучших, безотносительно к объему потока. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:31 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dima T Если Max(Q) окажется абсолютным максимумом, то в итого будет пустой список. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:32 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
White Owl Тогда ты не можешь, в принципе не можешь сказать что хочешь 1/1000 от потока. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:33 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS White Owl Бред какой-то 22321305 Боишься что все "сущности" не влезут в память - сбрасывай их на диск. Лень возится с ручным позиционированием на диске - сбрасывай их в БД. Все. Задача элементарная же. А еще можно вообще весь поток скидывать в БД и потом из него: select * from t limit @entity_count/1000 order by Q desc ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:40 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS White Owl Тогда ты не можешь, в принципе не можешь сказать что хочешь 1/1000 от потока. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:44 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
White Owl, текст 22321305 , ссылку на который вы дали, не содержит ответа на заданный вопрос " сформулировать критерий, на основании которого будет приниматься решение о том, что очередную сущность в потоке не следует сохранять на диск" увы. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 16:50 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Вариант top 1000 скользящих максимальных из бесконечного потока подходит? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 17:01 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS неужели я так путанно излагаю??? Да. Иван FXS Q(k) оказалось равно 1.23456 ... сохранять её на диск или проигнорировать? Код: sql 1. 2. 3. 4. 5. 6. 7. 8.
... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 17:14 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS White Owl, текст 22321305 , ссылку на который вы дали, не содержит ответа на заданный вопрос " сформулировать критерий, на основании которого будет приниматься решение о том, что очередную сущность в потоке не следует сохранять на диск" увы. Алгоритм не предполагает решать что "очередную сущность не следует сохранять на диск". Он предполагает решать что "очередную сущность следует сохранить". А все остальные соответственно не будут сохранены, но конкретно решения что "это не нужно" - нету в явном виде. Потому что есть решение "это нужно". Ты начал решать задачу задом наперед. Тебе с самого начала нужно сохранить лучшие, но ты уперся в поиск худших. И пытаешься изобрести отсев этих худших, вместо того чтобы делать выборку лучших (как требовалось изначально). Да алгоритмы на отсеивать и на выбирать часто взаимозаменяемы. Но в твоей задаче надо именно выбирать. Отсев не годится для нахождения "лучших" в потоке. Был бы у тебя жесткий критерий "этот элемент хороший, а этот нет" - можно было бы и выбраковку делать, но у тебя этого критерия нет. Так что только накопительный выбор. Ну или как я уже говорил - загони весь поток в БД. Тогда у тебя уже будет конечный массив, на основе которого ты сможешь и простую сортировку сделать, и медиану посчитать, и девиации проверить, и вообще все что угодно. Любая статистика станет доступной. А если поток бесконечный - то только выборка по принципу "этот элемент входит в список лучших? если да, запомним его и выкинем самый худший из накопленных лучших". ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 17:33 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov Код: sql 1. 2. 3. 4. 5. 6. 7. 8.
Которые я, впрочем, готов принять: и "-1" (в "countOfBest - 1"), позволяющее сохранять сущности уже из первой тысячи, и подстройка порога непрерывная, а не после каждой обработанной тысячи. Главное: что куча растет по мере роста runningCounter, составляя 1/1000 него, схвачено одинаково. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 18:15 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
mayton Вариант top 1000 скользящих максимальных ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 18:19 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov Код: sql 1. 2. 3. 4. 5. 6. 7. 8.
... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 18:33 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS mayton Вариант top 1000 скользящих максимальных Хорошо. Top N скользящих максимальных из бесконечного потока сущностей. Я просто пытаюсь адаптировать вашу формулировку к более формальной. Можно без скользящих. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 18:41 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
mayton, посмотрите код, предложенный Дмитрием Сибиряковым в 22323204 -- на мой взгляд, он решает задачу для обозримых объемов обрабатываемого потока. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 18:54 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS на мой взгляд, он решает задачу для обозримых объемов обрабатываемого потока. Так себе у тебя взгляд, но раз ты сказал, что некоторые лучшие (в данном случае до 99,9%) можно терять, то и такой алгоритм сойдёт. Если сумеешь его правильно написать. И да, об этом коде тебе твердят ещё с первой страницы. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 19:00 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov И да, об этом коде тебе твердят ещё с первой страницы. То есть вот даже "размером в 1/1000 от размера потока" можно теперь интерпретировать как "runningCounter / 1000"... ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 19:16 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS То есть вот даже "размером в 1/1000 от размера потока" можно теперь интерпретировать как "runningCounter / 1000"... Это поток. Повторяй: "поток", "поток", "поток". Как ещё можно интерпретировать его размер? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.05.2021, 22:02 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван, Вы можете написать алгоритм чтобы не 0.1% сливок снимать, а с хорошей точностью отделять верхние 50% от нижних? Просто поделить поток на два похожего размера, и чтобы один был заметно лучше другого. Или на три: получше, похуже и посередине. Если умеете, примените метод которым обогащали уран в 50х, очень похоже. Берете лучший из двух, и снова делите. Десять раз повторите - приблизитесь к 0.1% ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 03:22 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov Код: sql 1. 2. 3. 4. 5. 6. 7. 8.
Dima T если Max(Q) окажется абсолютным максимумом, то в итого будет пустой список В самом деле, если первый элемент кучи, появившийся в ней в процессе обработке первой тысячи сущностей, окажется достаточно большим, то для всех сущностей из второй тысячи может сработать Код: sql 1. 2.
и по итогу второй тысячи "куча лучших" просто не увеличится до двух элементов (как должна по смыслу). ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 07:40 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
вылечить этот недуг может такая модификация алгоритма: Код: sql 1. 2. 3. 4. 5. 6. 7. 8.
которая, кстати, приведёт к заметному увеличению потока сущностей, сбрасываемых на диск: 1001-я сущность, например, будет сброшена полюбасу, потому что для неё (countOfBest >= runningCounter / 1000) перестанет выполняться. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 08:09 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Часть лучших потеряется, т.к. при добавлении элемента к результату по-хорошему надо заново пересмотреть весь поток. Например в первой тысяче были значения 100 и 99. Ячейка результата одна, поэтому сохранил только 100, а 99 пришлось пропустить. Поэтому размер результата надо выбрать на старте. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 08:45 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
в цикле потока сразу же заполняется буфер из 1000 любыми значениями а уже потом из них вытаскивается самое мелкое, по которому ориентируется весь остальной поток до тех пор, пока в буфере не сменится это "самое мелкое" ТС уже определился, сколько ему всего значений надо в итоге? Или всё ещё с бесконечностью работаем? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 08:51 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
бабушкин зайчикТС уже определился, сколько ему всего значений надо в итоге? Или всё ещё с бесконечностью работаем? Довольно очевидно, что он хочет в любой момент времени иметь ≈1/1000 лучших от полученных из потока. Иван FXS, сколько сущностей нужно оценить, прежде чем лучшие будут иметь хоть какой-то смысл? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 09:41 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Ы2, ну тогда эта задача была решена ещё на 1-2 странице, в т.ч. и мной а далее ТС въезжал в очевидное и подбрасывал костыли. Динамический буфер тут идеальное решение, которое в конце потока выдаст 1000 самых-самых высоких значений. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 09:56 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
бабушкин зайчик ТС уже определился, сколько ему всего значений надо в итоге? Или всё ещё с бесконечностью работаем? бабушкин зайчик которое в конце потока выдаст 1000 самых-самых высоких значений. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 13:27 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS приведёт к заметному увеличению потока сущностей, сбрасываемых на диск: А ты не вызывай flush() и они останутся в памяти. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 13:49 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov А ты не вызывай flush() и они останутся в памяти ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 13:51 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Ы2 сколько сущностей нужно оценить, прежде чем лучшие будут иметь хоть какой-то смысл? Я уже писал вчера, что у меня, на самом деле, "пакетная" обработка данных, то есть мне необходимо осуществлять не один "поток записи на диск (типа, со скважностью 1/1000)", а как минимум 100 таких потоков одновременно. Но публика же на слове ловит: раз на вопрос "Тысяча? Десть тысяч? Миллион?" ( 22321305 ) ответил "миллиард" -- значит все, лапка завязла, птичке конец -- 1/1000 от миллиарда это миллион -- "ха-ха, всего-то". ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 13:54 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS доктор сказал "в морг", значит в морг. Вот поэтому-то выше я и говорил о программистах, которые в курсе работы кэша (который cache, а не cash). Но да, с диагнозом согласен. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 14:21 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
бабушкин зайчик Динамический буфер тут идеальное решение, которое в конце потока выдаст 1000 самых-самых высоких значений И я не буду накапливать их в "динамическом буфере" -- посмотрите четвертую реплику в обсуждении (сейчас какая по счёту, черт, сколько тут реплик на странице помещается?!): Иван FXS каждая сущность " большая ", много больше, чем числовой параметр Q сам по себе, так что хранить их в памяти нельзя , можно только по очереди каждую оценивать и решать, сбрасывать её на диск или нет ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 14:33 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Стандартное решение многократно предложено на первой странице, ТС его знает, но почему-то не приемлет. Смею предположить что он его отсек этим пунктом ТЗ: Иван FXS Также не желательно решение, предполагающее накопление (по ходу работы) всех числовых значений самого Q. Хотя бы потому, что оно является тривиальным. Только ты пойми что никто не предлагает хранить 100% сущностей. На всякий случай алгоритм хранения добавлю: Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9.
Просто последовательно пишешь нужные на текущий момент (!!! не все) сущности в файл, а в памяти хранишь значение Q и смещение в файле где эта сущность записана. При необходимости получения сущности открываешь файл сдвигаешь указатель на нужное смещение и читаешь. Дальше тюнинг работы с файлом с промежуточным кэшем в памяти частоиспользуемых значений и т.д. и т.п. Хотя за тебя ОС это сделает не хуже. Да, часть сущностей в какой-то момент станет ненужными, но повторяю что это далеко не все. Чтобы оценить точнее надо просто проверить. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 15:15 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS на шестой странице топика вы всё ещё не поняли, что мне не нужны ни 1000, ни даже 1/1000 (будем считать, что вы просто описАлись) "самых-самых высоких значений". Мне нужны сущности с "самыми высокими значениями", а не сами эти значения. До тебя так и не дошло, что разница между ними всего лишь в ссылке на саму сущность? Или это Визуальный Бейсик так людей портит?.. Иван FXS вы понимаете, что означают слова " большая " и " нельзя "? Вы, наверное, думаете, что если нельзя, но очень хочется, то можно?? Таки да, даже если большой дяденька запретил, "закон - как столб, можно и обойти". Способы-то обхода большинства ограничений и запретов самоочевидны или общеизвестны. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 15:33 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dima T Стандартное решение многократно предложено на первой странице, ТС его знает Dima T Смею предположить что он его отсек этим пунктом ТЗ: Иван FXS Также не желательно решение, предполагающее накопление (по ходу работы) всех числовых значений самого Q . Хотя бы потому, что оно является тривиальным. Только ты пойми что никто не предлагает хранить 100% сущностей . А "этим пунктом ТЗ" я отсёк ровно то, что я им отсёк. Вы понимаете, что одобрив код, предложенный Dimitry Sibiryakov, и даже немного его поправив, я уже согласился (скрепя сердце) хранить в памяти всю кучу лучших значений Q? Не "всех числовых значений самого Q", как в том "пункте ТЗ", на который вы сейчас ссылаетесь, а "всех отобранных по критерию лучших числовых значений самого Q". Dima T Просто последовательно пишешь нужные на текущий момент (!!! не все) сущности в файл Dima T При необходимости получения сущности ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 15:35 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov разница ... в ссылке на саму сущность Иван FXS сущность ... хранить их в памяти нельзя, можно только по очереди каждую оценивать и решать, сбрасывать её на диск или нет Эта программа занимается "разыгрыванием" по методу Монте-Карло, для чего создаёт эти сущности из ничего, из ДСЧ (на основе контекста Монте-Карлемой задачи, конечно), после чего их --возможно -- сбрасывает на диск и -- точно! -- уничтожает. И никакие ссылки на них после этого указывать не могут. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 15:45 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Модератор: Мне кажется без конкретики (примеров данных, примеров кода) топик можно закрывать. Если за 6 страниц так и не смогли понять что надо ТСу, то наверно нет смысла продолжать в общих словах. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 15:52 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dima T Если за 6 страниц так и не смогли понять что надо ТСу, то наверно нет смысла продолжать в общих словах ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 16:09 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Dima T Если за 6 страниц так и не смогли понять что надо ТСу проспаться ему надо. А то 6ю страницу догнать не может, что коли Q привязан к своей сущности, значит сущности можно сложить в БД/файл и дёргать оттуда нужные, когда понадобятся, а вся работа по отсеву идёт именно с Q. Иван FXS вы продолжаете путать Q и сущности -- как мне донести до вас, что это не одно и то же? тут собрались люди очевидно поумнее вас, и путаница вся только у вас в голове. 6ю страницу рассказываете про Q и сущность (из 3х параметров), которая к ней привязана. Уже давно все всё поняли и решение было ещё на 1-2 страницах. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 16:33 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Мож тогда лучше создать 2й топик, а этот продолжить? И новый (про Порог и Шаг) начать с необходиммой преамбулой (ну, мол, был 1й вариант - туда, в сад, а этот - сюда прошу)? Ну и здесь указатель поставиьть: прямо пойдёшь ..., налево пойдёшь ... Мне только кажется, что сложно с П и Ш ... Да, и нужно хотя бы в этом случае нормальное ТЗ написать, казалось бы, теперь уже возможно. П.с Поскольку пишу из танка, то так и не понял, запрет ли писать в БД часть промежуточных значений Q или других параметров? или это обсуждаемо, а если запрет, надо так и сказать: не обсуждать, или что-то ещё... мало ли кому что тривиально, и что для него из этого следует. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 16:43 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
бабушкин зайчик коли Q привязан к своей сущности, значит сущности можно сложить в БД /файл и дёргать оттуда нужные, когда понадобятся, а вся работа по отсеву идёт именно с Q Иван FXS Нужно отбирать из потока и сохранять на диске "самые лучшие" из сущностей (Писать в БД миллионы записей, которые точно потом не понадобятся -- это великое программистское искусство!) ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 16:45 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
exp98 Мож тогда лучше создать 2й топик ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 16:50 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Я предлагаю этот топик закрыть. Вроде все уже высказались. А выборки из бесконечных труб и хранение поднять совершенно отдельной темой с другой формулировкой, если надо. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 16:55 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS, нет, я не модер, я другой. И как раз самое время, ИМХО, на фоне возросшего понимания задачи (своей же задачи, замечу), переформулировать задачу, устранив выявившиеся умолчания и взаимонепонимания. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 16:59 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
exp98, я не понимаю, что значит "переформулировать задачу" ... разве что поднять из 4-й реплики в тело поста Иван FXS каждая сущность "большая", много больше, чем числовой параметр Q сам по себе, так что хранить их в памяти нельзя, можно только по очереди каждую оценивать и решать, сбрасывать её на диск или нет. Наверное, мне стоило сразу сказать, что речь идет о методе Монте-Карло, так что то, что часть "не самых плохих" сущностей потеряется -- не критично ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 17:07 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS, моё дело предложить. И ещё раз напомнить, что краткость не всегда естть сестра таланта. И снова напомнить, что следствия из умолчаний или неоднозначностей часто отличаются у разных людей, несмотря даже на некую, якобы строгую, терминологию. Банальность, а не все это понимают по умолчанию. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 17:21 |
|
Как отбирать из потока 1/1000 лучших экземпляров?
|
|||
---|---|---|---|
#18+
Иван FXS exp98 Мож тогда лучше создать 2й топик Я тут модератор. Тут в топике какой-то бесконечный цикл: тебе говорят решение, ты говоришь оно неправильное, но не объясняешь в чем неправильное (или непонятно объясняешь) и так по кругу ... Боюсь что закрытием топика эту бесконечность не прервать, но давай попробуем. Попробуй задачу четче сформулировать с учетом полученных тут знаний. Соберись с мыслями и новый топик начни. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.05.2021, 18:02 |
|
|
start [/forum/topic.php?all=1&fid=16&tid=1339663]: |
0ms |
get settings: |
12ms |
get forum list: |
14ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
51ms |
get topic data: |
13ms |
get forum data: |
3ms |
get page messages: |
163ms |
get tp. blocked users: |
2ms |
others: | 247ms |
total: | 511ms |
0 / 0 |