powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как отбирать из потока 1/1000 лучших экземпляров?
151 сообщений из 151, показаны все 7 страниц
Как отбирать из потока 1/1000 лучших экземпляров?
    #40069820
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Дано: обрабатывается большой поток неких "цифровых сущностей", представленных неким набором параметров, среди которых, есть параметр Q (от "quality").

Нужно отбирать из потока и сохранять на диске "самые лучшие" из сущностей по параметру Q, так, чтобы сохранялось около 1/1000 от общего объёма "просеянного" потока.

Каков тут может быть достаточно эффективный -- по соотношению "качество/затраты" -- алгоритм отбора?

Заковыка в том, что точного решения задача не имеет, ибо в процессе работы мы не можем определить, попадает ли то или иное Q в 1/1000 от всей выборки.

Также не желательно решение, предполагающее накопление (по ходу работы) всех числовых значений самого Q. Хотя бы потому, что оно является тривиальным.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40069827
пример бы строки привели хоть
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40069828
Иван FXS
Также не желательно решение, предполагающее накопление (по ходу работы) всех числовых значений самого Q. Хотя бы потому, что оно является тривиальным.

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

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

White Owl
Выделяешь себе в памяти массив в который влезет 1/1000 от потока и начинаешь оценивать поток
каждая сущность "большая", много больше, чем числовой параметр Q сам по себе, так что хранить их в памяти нельзя, можно только по очереди каждую оценивать и решать, сбрасывать её на диск или нет.

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

White Owl
Выделяешь себе в памяти массив в который влезет 1/1000 от потока и начинаешь оценивать поток
каждая сущность "большая", много больше, чем числовой параметр Q сам по себе, так что хранить их в памяти нельзя, можно только по очереди каждую оценивать и решать, сбрасывать её на диск или нет.

Сохраняй в БД. Суть алгоритма все-равно не меняется.
SQLite отлично подойдет, управляя размером кэша ты будешь управлять тем какая часть данных останется в памяти.

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

выглядит как типичный кейс streaming аналитики. обычно строят из чего-то типа kafka+spark, flume и т.п.
поток пишем в кафку, ответ с лучшими сущностями в ту же кафку в соседний топик. видимо сначала надо вычитать первый миллион сообщений, что бы определить кто там лучший в первом миллионе, после этого в реалтайме считать среднее и параллельно те что проходят фильтр писать в ответный топик кафки.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40069962
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
Дано: обрабатывается большой поток неких "цифровых сущностей", представленных неким набором параметров, среди которых, есть параметр Q (от "quality").

Нужно отбирать из потока и сохранять на диске "самые лучшие" из сущностей по параметру Q, так, чтобы сохранялось около 1/1000 от общего объёма "просеянного" потока.

На каждую тысячу событий вычисляй случайное число и бери из этой пачки элемент по номеру этого числа.

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

Любая сортированная структура размером в 1/1000 от размера потока. Для твоего миллиарда это будет всего миллион.

Иван FXS
Заковыка в том, что точного решения задача не имеет, ибо в процессе работы мы не можем определить, попадает ли то или иное Q в 1/1000 от всей выборки.

А оно нам и не надо, мы просто отбираем Х лучших, откидывая неудачников с хвоста. В конце берём столько сколько нужно с головы списка.

Иван FXS
Также не желательно решение, предполагающее накопление (по ходу работы) всех числовых значений самого Q.

Всех накапливать и не надо, только лучших. Точнее - только тех, кто попал в вилку между текущим худшим из лучших и текущим лучшим из лучших.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40069991
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
White OwlТы можешь заранее оценить сколько всего сущностей есть в потоке? Тысяча? Десть тысяч? Миллион?
миллиардиспользовать heap
https://ru.wikipedia.org/wiki/Двоичная_куча
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070059
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
Любая сортированная структура размером в 1/1000 от размера потока.
- надеюсь, что вы прочитали словосочетание "набором параметров" в
Иван FXS
"цифровых сущностей", представленных неким набором параметров, среди которых, есть параметр Q
-- каждая из "цифровых сущностей" многократно больше числа Q. Так что хранить в памяти 1/1000 от потока -- понятное решение, но несколько прямолинейное.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070063
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
вычисляй случайное число и бери из этой пачки элемент по номеру этого числа
каким образом случайно выбранный экземпляр окажется одним из лучших (по параметру Q)?
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070065
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
mayton
вычисляй случайное число и бери из этой пачки элемент по номеру этого числа
каким образом случайно выбранный экземпляр окажется одним из лучших (по параметру Q)?

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

1) если Q очередного экземпляра в потоке больше или равно П, то а) сбрасываем экземпляр на диск и б) изменяем порог

П = П + 999*Ш;

2) если Q очередного экземпляра в потоке меньше П, то а) игнорируем экземпляр и б) изменяем порог

П = П - Ш.

Понятно, что П будет колебаться около некоторого равновесного уровня, только если на одно событие (1) будет приходиться 999 событий (2). Не понятно только, как выбрать Ш. И должен ли он быть постоянным в ходе работы алгоритма...

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

1) если Q очередного экземпляра в потоке больше или равно П, то а) сбрасываем экземпляр на диск и б) изменяем порог

П = П + 999*Ш;

2) если Q очередного экземпляра в потоке меньше П, то а) игнорируем экземпляр и б) изменяем порог

П = П - Ш.
ну то есть если в потоке будут такие значения:
Х
X + П + 999*Ш
X + 2П + 2*999*Ш
...

то взяв начальное П <= Х, ты просто накидаешь в файл млн. самых маленьких. Правильно?
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070081
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
Не понятно только, как выбрать Ш. И должен ли он быть постоянным в ходе работы алгоритма...
наверное, полезна будет какая-то зависимость Ш от текущих значений (Q-П), потому что если всё время Ш много меньше, чем Abs(Q-П), то производимая коррекция порога мало влияет на его работу...
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070082
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
Правильно
наверное, правильно, но это -- линейно растущие Q в потоке -- какой-то вычурный пример.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070093
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
Имя пользователя1
Правильно
наверное, правильно, но это -- линейно растущие Q в потоке -- какой-то вычурный пример.
не обязательно делать линейно, или вообще монотонно растущую последовательность, можно нашпиговать промежуточными числами. Суть в том, что до самых жырных поинтов (всех или некоторых) можем вообще не добраться.

ты вот по такому предложению не ответил. Можно или нет?
Dima T
Если доступен второй проход по тому же потоку, то достаточно сохранить порядковый номер сущности. Первым проходом получишь номера лучших, вторым сами сущности.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070095
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
2) если Q очередного экземпляра в потоке меньше П, то а) игнорируем экземпляр и б) изменяем порог

П = П - Ш.
тоже, кстати, хрень: можем сначала добавить несколько хороших значений, задрав П "совсем высоко", так ничего и не добавив в далее.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070097
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Напоминает регулятор уровня записи в моём кассетном Technics. Порог быстро реагирует на уровнь но спадает
медленно.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070103
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
ты вот по такому предложению не ответил. Можно или нет?
конкретно в моем проекте (в нынешнем его состоянии) в самом деле можно не только "второй проход по тому же потоку" сделать, но и любой экземпляр в потоке отдельно воспроизвести повторно по его "ключу"(*). Так что я продолжаю обсуждать постановку задачи более общую (чем в моём проекте).

____________________
* -- типа, вот так https://www.sql.ru/forum/1335743/o-razvorachivanii-dlinnogo-celogo-v-nabor-iz-100-psevdosluchaynyh-deystvitelnyh
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070174
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
Так что я продолжаю обсуждать постановку задачи более общую (чем в моём проекте).
для относительно рандомной, без явных перекосов, перестановки вполне можно добиться, чтобы получилось собрать "подавляющее большинство из 0.1% самых вкусных элементов" - на первых этапах определиться с пороговым значением, примерно по твоей схеме "П + 999*Ш" или около того.

Ну то есть - решение всё равно будет очень хреново работать на некоторых специальных видах перестановок, и почти наверняка не сможет собрать абсолютно все требуемые значения. Такие допуски приемлемы для "общего случая"?
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070176
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1, допуски приемлемы, только я так и не понял, как выбрать Ш.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070179
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS, можешь в Excel показать величину Q в виде графика?
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070194
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton, в виде графика ... у которого что отложено по осям X и Y? И как построен набор отображаемых (в виде точек) элементов -- график всех значений Q, типа, всего "миллиарда"?
...
Рейтинг: 0 / 0
Как отбирать из потока 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
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070634
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если перевести в плоскость примеров. На вход - миллард таких сущностей.

Input:
Код: sql
1.
2.
3.
4.
5.
6.
№,X1,X2,....XN,Q
1,2.......,0.003
2,5.......,0.002
3,5.......,0.002
.....
1000 000 000, 5,...... 0.001



На выходе 1 000 000 штук таких:
Код: sql
1.
2.
3.
4.
5.
№,X1,X2,....XN,Q
732, 5, ...... 1.000
11, 5, ...... 0.999
4346457, 7,......0.998
......



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

Для оперативной памяти - это может быть Куча (Heap) как уже кто-то предлагал.

Также пойдет красно-черное-дерево где ключ будет Q. На С++ ей соотвествует
любая сортируемая мапа.

Если памяти будет не хватать - пойдет Key-Valuе DBMS наподобие LevelDb. Для нее есть
интерфейсы программирования почти на всех языках.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070644
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton, не понимаю, вы настолько технооптимист, что вообще не можете представить задачу, которую нельзя было бы решить брутфорсом? А если бы я тогда сказал "триллион" вместо "миллиард" (ну, да, мне просто фантазии не хватило)...
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070649
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я - не технооптимист.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070657
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Иван FXS
mayton, не понимаю, вы настолько технооптимист, что вообще не можете представить задачу, которую нельзя было бы решить брутфорсом? А если бы я тогда сказал "триллион" вместо "миллиард" (ну, да, мне просто фантазии не хватило)...


Если вы сказали максимум триллион, значит у вас есть диска на миллиард. (Иначе вам некуда 1/1000 сохранить)

Далее следует решение white owl, которое вам отсеивает верхний миллиард. По окончании потока, который не превышает триллион, делите счётчик сущностей на 1000, округляете в удобную для вас сторону (рекомендую вверх), и берете таковое число строчек из отсеянного миллиарда который уже на диске. Готово: точное решение в один проход потока неизвестного заранее размера.

Не забудьте отвести счётчику сущностей хотя бы 40 бит, всё-таки триллион ожидаете.

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

Заковыка в том, что точного решения задача не имеет, ибо в процессе работы мы не можем определить, попадает ли то или иное Q в 1/1000 от всей выборки.
.


А, вижу. Вас наверное не устраивает то, что вы думали что точного решения не существует, а оно оказалось довольно очевидным.

Ну тогда давайте забудем о существовании точного решения и решим неточно, статистическими методами. Только не способом тыка папы Карло, а с формулами.

На основании значений первых N cущностей делаете предположение о статистическом распределении Q. Надеетесь на гауссовое или равномерное в фиксированном интервале. Затем, выбрав погрешность альфа, определяете Qmin, которое с заданной погрешностью альфа будет меньше чем верхний 0.1% значений Q всей популяции, затем отбирает все сущности из потока для которых Q > Qmin.

Не забудьте сохранить первые N сущностей предшествующие анализу; они не бросовые. Число N зависит от альфы.

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

Видел конечно.

Вам в памяти сущности хранить и не требуется, только Q значения уже сохранённых на диске сущностей, чтобы знать какие из них заменять.

Может, у вас какие-то другие ограничения в задаче? Например, входной поток бесконечный, или диск не разрешает перезапись? Тогда точное решение не существует, и можно рассуждать об эвристиках.

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

Если да, то ткните пальцем в то, каким образом "точное решение White Owl-а" будет исполнять это требование. Насколько я вижу, это "точное решение" просто игнорирует этот аспект задания.

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

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

Да. В чём проблема-то? Потом будешь удалять худшие из них по мере прихода лучших. Опять же в чём проблема-то?

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

Dimitry Sibiryakov
весь этот миллион таки влезет в ОЗУ
это вы про мою СУБД (или -- более общо -- систему записи результатов на диск) со своего берега видите, что она, на самом деле, не пишет на диск то, что помещается в ОЗУ? Или мне самому предлагаете изменить "условия задачи" -- переписать "сохранять на диске" на "сохранять в ОЗУ"?

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

вот я создал массив размером миллион под значения Q... и что я должен буду весь первый миллион сущностей на диск забубенить?


Да. Первый миллион точно*. А если Q сущностей монотонно растет, то вообще все сущности потока коснутся диска, по правилу FIFO. Мало того, для монотонно растущих Q ничего лучше и не будет.

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

Не совсем в тему, но эту задачу базы данных решают точно и успешно каждый день. "Отсортировать таблицу неизвестной длины** по колонке Q, показать/сохранить первые 1% строчек". Строчки в БД могут содержать многомегабпйтные объекты.

(*) Предвидя возможные придирки, не всегда. min(1e6,N), где N длина потока.

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

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

Если точное решение не устраивает из-за медленной операции сохранения данных, которое в худшем случае включает в себя *все* сущности потока, ты вы будете оптимизировать сокращение числа сохранений в ущерб точности. Тут придется решать какой выигрыш стоит какой точности.

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

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

" ха-ха, ты что, не знаешь, как из N сущностей отобрать K лучших по параметру Q?! "

-- не является ответом на вопрос:

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

Для первоначальной постановки задачи решение white owl выглядит на мой взгляд превосходно, поэтому появились вопросы чем точное решение не подходит, и есть ли дополнительные критерии.
Не сразу, но выяснилось что есть важный для вас но ранее не упомянутый критерий количества сохранений, который вы связываете со скоростью.

Что я знаю о вашей задаче: у вас есть поток этих сущностей, каждая содержит неотделимую от нее метрику Q. Поток высокоскоростной, неизвестной но конечной длины не превышающей миллиард.
Нужно в один проход выбрать и сохранить верхние 0.1%
сущностей по метрике Q. Диапазон Q неизвестен, порядок следования сущностей может быть любой.
Устройство может сохранить один миллион сущностей, не больше.
Метод сохранения сущностей считается медленным, поэтому точное решение с перезаписью не годится.
Допускается неточное решение, если оно использует меньше сохранений чем точное.

Этого мало для ТЗ. Если бы меня наняли решать такую задачу, я бы задал вопросы:
- прочность критериев. Например, можно ли любую часть потока читать дважды?
- природа данных, происхождение и примеры. Мне известны неудачные данные, которые мочат все эвристики в нулевую точность.
- скоростные характеристики потока данных и механизма сохранения. Это важно. Например, если вход один гигабит, а сохранение всего 100mbps, то при соотношении чтение/запись 10:1 и выше сохранение перестанет тормозить процесс. Оптимизировать вечно нет смысла.
- скоростные параметры железа. Если вычисляла слабая, некоторые подходы исключаются.
- допустимое количество ошибок, как меняется
- допустимое время исполнения.
- есть ли требование регулировки, чтоб заказчик мог сам подкручивать быстрее/точнее
- формат результата: "пришло 100500 шт, самые верхние были #42, #69, .. из них сохранены 88%"

Не исключено, что в итоге после анализа и результатов тестов заказчик решит купить диск побыстрее, и не связываться с эвристикой у которой не полностью исследована связь между характером ввода и ошибкой результата.

Последнее вполне тянет на курсовую, где стоимость усилий и ответственность низкая.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070715
НеофитSQL
Что я знаю о вашей задаче: у вас есть поток этих сущностей, каждая содержит неотделимую от нее метрику Q. Поток высокоскоростной, неизвестной но конечной длины не превышающей миллиард.
Нужно в один проход выбрать и сохранить верхние 0.1% сущностей по метрике Q.
Диапазон Q неизвестен, порядок следования сущностей может быть любой.
Устройство может сохранить один миллион сущностей, не больше.
Метод сохранения сущностей считается медленным, поэтому точное решение с перезаписью не годится.
Допускается неточное решение, если оно использует меньше сохранений чем точное.

вот решение для этих условий:
бабушкин зайчик
размер потока значения не имеет
вы просто сравниваете текущее значение с минимальным в массиве на X элементов
и если больше, то заменяете это минимальное значение в массиве
далее берёте новое минимальное, и т.о. заполняете массив самыми высокими значениями
диск нужен, только когда надо сохранить уже заполненный массив, а так то текущий массив в памяти живёт

0.1% от триллиона? это ярд интов = 4 гигабайта (нужны ведь только Q, а строки из БД брать по необходимости)
ну вообще не бох весть какая память, на каждом втором компе есть
но если вдруг понадобится не 0.1, а 1%, то на диск можно скидывать верхние 500, оставляя в памяти самое мелкое в них значение, и вот его тогда менять (предварительно конечно рассортировав по файлам от меньшего к большему)
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070718
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
бабушкин зайчик
(нужны ведь только Q, а строки из БД брать по необходимости )
если вы это увидели в моём посте, то ... вам это померещилось -- там вообще ни слова нет про "строки из БД брать".
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070719
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
НеофитSQL
Этого мало для ТЗ. Если бы меня наняли решать такую задачу, я бы задал вопросы
я не выдавал ТЗ и не нанимал никого решать такую задачу, а надеялся услышать соображения по поводу этой задачи (желательно, полезные) и -- в ходе дискуссии -- дополнительно прояснить свои собственные представления о ней. Что мне удалось ( 22321734 ) только отчасти ( 22321904 ). И было это на первой странице обсуждения, а сейчас идёт уже третья ... честно говоря, не очень мне понятно, о чём (мне настойчиво объясняют, что есть решение брутфорс, и как оно прекрасно).
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070724
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Несколько слов о задаче, в рамках размышления о которой был написан пост:

1) "сущности" о которых идет речь, генерируются в два этапа;

2) на первом этапе на основании ключа (key) генерируется пачка из 100 пред-сущностей (по числу тикеров [ticker] в индексе NASDAQ100) -- так что (повторно) сгенерировать одну из них не намного легче, чем все сто разом;

3) на втором этапе для каждой из этих 100 пред-сущностей сканируется несколько сотен (пусть будет 200) значений порога [p], каждый из которых даёт своё индивидуальное значение качества Q.

4) то есть вот этой тройкой (key; ticker; p) задаётся та сущность, для которой нужно по её Q решить -- для каждого тикера отдельно , -- попадает ли она в 0.1% лучших, то есть достойна ли она того, чтобы быть сохраненной (на диск).

Итак, хотите накапливать в буфере только значения (key; ticker; p), а потом -- когд-то -- решить, какие из них сохранять? Пожалуйста, только для повторной генерации каждой сущности нужно будет затратить примерно в 100*200 = 20000 больше вычислительных ресурсов, чем тратилось на генерацию её в "пакетном" режиме. Но брутфорс ведь наше всё.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070727
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
накапливать в буфере только значения (key; ticker; p)
только значения (key; ticker; p; Q), конечно.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070750
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
бабушкин зайчик
НеофитSQL
Что я знаю о вашей задаче: у вас есть поток этих сущностей, каждая содержит неотделимую от нее метрику Q. Поток высокоскоростной, неизвестной но конечной длины не превышающей миллиард.
Нужно в один проход выбрать и сохранить верхние 0.1% сущностей по метрике Q.
Диапазон Q неизвестен, порядок следования сущностей может быть любой.
Устройство может сохранить один миллион сущностей, не больше.
Метод сохранения сущностей считается медленным, поэтому точное решение с перезаписью не годится.
Допускается неточное решение, если оно использует меньше сохранений чем точное.

вот решение для этих условий:
бабушкин зайчик
размер потока значения не имеет
вы просто сравниваете текущее значение с минимальным в массиве на X элементов
и если больше, то заменяете это минимальное значение в массиве
далее берёте новое минимальное, и т.о. заполняете массив самыми высокими значениями
диск нужен, только когда надо сохранить уже заполненный массив, а так то текущий массив в памяти живёт

0.1% от триллиона? это ярд интов = 4 гигабайта (нужны ведь только Q, а строки из БД брать по необходимости)
ну вообще не бох весть какая память, на каждом втором компе есть
но если вдруг понадобится не 0.1, а 1%, то на диск можно скидывать верхние 500, оставляя в памяти самое мелкое в них значение, и вот его тогда менять (предварительно конечно рассортировав по файлам от меньшего к большему)

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

Если "строки" уже "в БД", и их можно оттуда "брать" -- то в чём, по-вашему, может состоять задача? Посчитать для этих строк Q и дописать его "в БД" (или куда-то рядом), а потом "ха-ха, из N сущностей суметь выбрать K лучших по критерию Q"? Ну да, это в самом деле "ха-ха".
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070759
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сущности. Строки. DataRows. Tuples. Entities. Objects. Да такая она... проф-деформация.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070761
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вообще, я зря повелся и согласился на предложение (в третьей реплике от начала обсуждения!):

"заранее оценить сколько всего сущностей есть в потоке"

-- поток это поток, труба, в ней течёт вода. А мне говорят: ну, сколько там может быть воды в той трубе -- выкопай бассейн, собери в нем всю воду, и делай с ней всё, что хочешь.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070769
Иван FXS
бабушкин зайчик
(нужны ведь только Q, а строки из БД брать по необходимости )
если вы это увидели в моём посте, то ... вам это померещилось -- там вообще ни слова нет про "строки из БД брать".

не видел я у вас в ТЗ, чтобы вам прямо во время поиска Q надо было пользоваться значениями
в таких задачах обычно сначала отбирают нужное, а потом уже им пользуются
Иван FXS
только значения (key; ticker; p; Q), конечно.

как бы там ни было, в чём проблема сложить эти ваши значения в БД, оставив в памяти лишь Q, из которых отсеять нужные?
Помимо очевидных выгод, таким образом можно надеяться, что данные не выпадут из кэша CPU, что ускорит процесс раз в 50.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070771
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
бабушкин зайчик, то есть вы продолжаете исходить из того, что я не знаю, как из миллиарда значений Q отобрать миллион самых больших?
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070773
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
бабушкин зайчик

как бы там ни было, в чём проблема сложить эти ваши значения в БД, оставив в памяти лишь Q, из которых отсеять нужные?
Помимо очевидных выгод, таким образом можно надеяться, что данные не выпадут из кэша CPU, что ускорит процесс раз в 50.

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

Похоже, Вы не знаете, что 1/1000 от бесконечности это бесконечность и динамически подстраиваете задачу под невозможность её решения. Это бесперспективняк.

PS: Диски быстрее, чем сеть и рассматривать их как ограничение можно только если ваши "сущности" порождаются ГСЧ.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070776
mayton
Это очень жесткие требования.

в БД сохранять? А "не жёсткие" - это какие?
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070779
Иван FXS
бабушкин зайчик, то есть вы продолжаете исходить из того, что я не знаю, как из миллиарда значений Q отобрать миллион самых больших?

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

в БД сохранять? А "не жёсткие" - это какие?

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

Dimitry Sibiryakov
рассматривать их как ограничение можно только если ваши "сущности" порождаются ГСЧ
да, они именно ГСЧ и порождаются, я уже это упоминал, и даже ссылку на тему давал ( https://www.sql.ru/forum/1335743/o-razvorachivanii-dlinnogo-celogo-v-nabor-iz-100-psevdosluchaynyh-deystvitelnyh ) -- неоднократно упоминавшийся мною key -- это и есть то длинное целое, которое разворачивается в сто псевдослучайных действительных.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070784
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я так понимаю Иван FXS хочет заранее предсказать пороговое значение Q, а дальше просто дергать с потока только те сущности у которых Q больше порога. Только придумать не может как порог найти.

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

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

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

я объяснял на предыдущей странице ( 22322961 ), что у меня сущности генерируются "пакетами" по 100*200=20000 штук
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070791
mayton
бабушкин зайчик
пропущено...

в БД сохранять? А "не жёсткие" - это какие?

Не жосткие - это когда человек-от-бизнеса захочет на них взглянуть. Подумать. И принять какое-то решение.

т.е. алгоритм придумывает обыватель?
его дело чётко составить ТЗ и показать требуемый результат.
А он блин ставит задачу так, что её надо непременно сохранять на диск, а потом оказывается, что там всего 20000 сущностей, которые можно в памяти держать не парясь...
Да там ещё под вопросом эта 20... а чё не 1000?
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070793
и почему нельзя прямо во время генерации отсеять нужные?
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070794
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
бабушкин зайчик
а потом оказывается, что там всего 20000 сущностей
ну что, ещё раз разжевать, что

key имеет тип Длинное целое, мощность которого 4 миллиарда, и для каждого значения key я генерирую пакет из 20000 сущностей

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

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

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

И для этой исходной формулировки "наилучшим по соотношению качество/затраты" будет решение, которое Вы назвали "брутфорсом": сохранять на диске текущий набор "лучших", перезаписывая худшие из них новыми по мере поступления.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070815
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
бабушкин зайчик
мощность long int = 4 миллиарда"... што это вообще?!

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

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

Вот, я обрабатываю сущность номер k (k может быть равно 1, 999, 1000, 1001, 145142 или 217363728) -- и Q(k) оказалось равно 1.23456 ... сохранять её на диск или проигнорировать?
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070819
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Только хранить миллион самых лучших на текущий момент
как только вы произнесли "миллион" -- вы перестали работать с потоком как с потоком . Потому что у потока нет никакого ни миллиона, ни миллиарда, ни триллиона.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070820
Иван FXS
Dima T
Только хранить миллион самых лучших на текущий момент
как только вы произнесли "миллион" -- вы перестали работать с потоком как с потоком . Потому что у потока нет никакого ни миллиона, ни миллиарда, ни триллиона.

поток = цикл
у цикла есть счётчик
перестаньте уже за программистов думать
лучше учитесь чётко описывать задачу
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070821
Dima T
бабушкин зайчик
мощность long int = 4 миллиарда"... што это вообще?!

Математики так называют количество возможных значений

а зачем это на форуме программистов и какое отношение имеет к задаче?
ему то что эти 4 ярда? Он вообще знает, что 4 000 000 000 ярда или 1 всё = 8 байт?
а то что long это 9223372036854775807 он вообще никогда не слышал.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070822
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
Dimitry Sibiryakov, можете сформулировать критерий, на основании которого будет приниматься решение о том, что очередную сущность в потоке не следует сохранять на диск?

Вот, я обрабатываю сущность номер k (k может быть равно 1, 999, 1000, 1001, 145142 или 217363728) -- и Q(k) оказалось равно 1.23456 ... сохранять её на диск или проигнорировать?
Это 1.23456 лучше чем самая плохая ранее встреченная сущность? Если да - то сохранять, если нет - не сохранять.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070823
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
Dima T
Только хранить миллион самых лучших на текущий момент
как только вы произнесли "миллион" -- вы перестали работать с потоком как с потоком . Потому что у потока нет никакого ни миллиона, ни миллиарда, ни триллиона.

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

1) из первой тысячи ничего не сохраняю на диск, но выясняю (и запоминаю) Max(Q), и его устанавливаю в качестве порога сохранения П(2) для обработки второй тысячи;

2) из второй тысячи сохраняю на диск всё, что лучше П(2), и начинаю заполнять двоичную кучу -- так, чтобы к концу второй тысячи в этой куче было два элемента; то есть по итогу обработки двух тысяч в куче два значения Q, и минимальный из которых будет порогом П(3) для обработки третьей тысячи;

3) из третьей .................. лучше П(3) ......... к концу третьей тысячи в этой куче было три элемента;

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

1) из первой тысячи ничего не сохраняю на диск, но выясняю (и запоминаю) Max(Q), и его устанавливаю в качестве порога сохранения П(2) для обработки второй тысячи;

2) из второй тысячи сохраняю на диск всё, что лучше П(2), и начинаю заполнять двоичную кучу -- так, чтобы к концу второй тысячи в этой куче было два элемента; то есть по итогу обработки двух тысяч в куче два значения Q, и минимальный из которых будет порогом П(3) для обработки третьей тысячи;

3) из третьей .................. лучше П(3) ......... к концу третьей тысячи в этой куче было три элемента;

и т.д.
Бред какой-то.
Таким образом ты, во первых, потеряешь "лучшие" из первой тысячи если они там были. Во вторых, если в каждой очередной тысяче будут две сущности достойные быть в списке самых лучших, ты запомнишь только одну из них.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070826
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Как уже написали 0,1% от бесконечности - бесконечность
при чем здесь это? Просто забудьте, что на вопрос "сколько всего" я ответил "миллиард". Просто сотрите это из своей памяти. Считайте, что я ответил "не знаю", или "сколько хватит терпения", или "я хочу иметь возможность начать анализировать результаты, пока программа продолжает молотить", или как-то ещё уклонился от ответа.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070828
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
White Owl
Бред какой-то
с удовольствием прочитаю ваш вариант критерия.
White Owl
если в каждой очередной тысяче будут две сущности достойные быть в списке самых лучших, ты запомнишь только одну из них
конечно, нет. Жаль, что вы пишете, не подумав. Если в первой тысяче Max(Q) =1.2345, а во второй тысяче два максимальных значения Q будут 2.3456 и 3.4567, то по итогу двух тысяч в куче останутся именно они.

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

1) из первой тысячи ничего не сохраняю на диск, но выясняю (и запоминаю) Max(Q), и его устанавливаю в качестве порога сохранения П(2) для обработки второй тысячи;

Если Max(Q) окажется абсолютным максимумом, то в итого будет пустой список.

ИМХО не существует алгоритма как в один проход отсечь заданное количество максимальных элементов, при этом не сохраняя лишних. Какая-то избыточность должна быть, чтобы в конце выкинуть лишнее.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070830
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
Dima T
Как уже написали 0,1% от бесконечности - бесконечность
при чем здесь это? Просто забудьте, что на вопрос "сколько всего" я ответил "миллиард". Просто сотрите это из своей памяти. Считайте, что я ответил "не знаю", или "сколько хватит терпения", или "я хочу иметь возможность начать анализировать результаты, пока программа продолжает молотить", или как-то ещё уклонился от ответа.
Тогда ты не можешь, в принципе не можешь сказать что хочешь 1/1000 от потока. Нельзя посчитать N/1000 если N неизвестна.
Зато ты можешь выбрать тысячу или миллион лучших, безотносительно к объему потока.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070831
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Если Max(Q) окажется абсолютным максимумом, то в итого будет пустой список.
о, боже, неужели я так путанно излагаю???
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070832
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
White Owl
Тогда ты не можешь, в принципе не можешь сказать что хочешь 1/1000 от потока.
я не могу встать на улице и бить кулаком в лицо каждому третьему из прохожих ... потому что не знаю, сколько их всего?
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070833
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
White Owl
Бред какой-то
с удовольствием прочитаю ваш вариант критерия.

22321305
Боишься что все "сущности" не влезут в память - сбрасывай их на диск. Лень возится с ручным позиционированием на диске - сбрасывай их в БД.
Все. Задача элементарная же.

А еще можно вообще весь поток скидывать в БД и потом из него: select * from t limit @entity_count/1000 order by Q desc
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070834
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
White Owl
Тогда ты не можешь, в принципе не можешь сказать что хочешь 1/1000 от потока.
я не могу встать на улице и бить кулаком в лицо каждому третьему из прохожих ... потому что не знаю, сколько их всего?
Но это же не то что тебе нужно. Тебе же нужно 1/1000 ЛУЧШИХ. То есть в варианте "бить морды", тебе придется взять всех прохожих, поделить их на три группы и побить одну из них. Просто "каждый третий" это и будет просто каждый третий.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070836
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
White Owl, текст 22321305 , ссылку на который вы дали, не содержит ответа на заданный вопрос

" сформулировать критерий, на основании которого будет приниматься решение о том, что очередную сущность в потоке не следует сохранять на диск"

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

Да.

Иван FXS

Q(k) оказалось равно 1.23456 ... сохранять её на диск или проигнорировать?

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
if (currentQ < worstOfBestQ)
  проигнорировать();
else
{
  сохранить();
  if (countOfBest - 1 > runningCounter / 1000)
    забыть(worstOfBestQ);
}
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070858
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS
White Owl, текст 22321305 , ссылку на который вы дали, не содержит ответа на заданный вопрос

" сформулировать критерий, на основании которого будет приниматься решение о том, что очередную сущность в потоке не следует сохранять на диск"

увы.
Это потому что ты ждешь ответа на свой конкретный вопрос, а он для алгоритма не имеет смысла.
Алгоритм не предполагает решать что "очередную сущность не следует сохранять на диск". Он предполагает решать что "очередную сущность следует сохранить". А все остальные соответственно не будут сохранены, но конкретно решения что "это не нужно" - нету в явном виде. Потому что есть решение "это нужно".

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


Да алгоритмы на отсеивать и на выбирать часто взаимозаменяемы. Но в твоей задаче надо именно выбирать. Отсев не годится для нахождения "лучших" в потоке. Был бы у тебя жесткий критерий "этот элемент хороший, а этот нет" - можно было бы и выбраковку делать, но у тебя этого критерия нет. Так что только накопительный выбор.

Ну или как я уже говорил - загони весь поток в БД. Тогда у тебя уже будет конечный массив, на основе которого ты сможешь и простую сортировку сделать, и медиану посчитать, и девиации проверить, и вообще все что угодно. Любая статистика станет доступной.

А если поток бесконечный - то только выборка по принципу "этот элемент входит в список лучших? если да, запомним его и выкинем самый худший из накопленных лучших".
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070883
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
if (currentQ < worstOfBestQ)
  проигнорировать();
else
{
  сохранить();
  if (countOfBest - 1 > runningCounter / 1000)
    забыть(worstOfBestQ);
}

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

Которые я, впрочем, готов принять: и "-1" (в "countOfBest - 1"), позволяющее сохранять сущности уже из первой тысячи, и подстройка порога непрерывная, а не после каждой обработанной тысячи.

Главное: что куча растет по мере роста runningCounter, составляя 1/1000 него, схвачено одинаково.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070885
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Вариант top 1000 скользящих максимальных
что такое "скользящие максимальные"? Почему их настолько много, что оказывается возможным применять к ним оператор "top"? И откуда возникает параметр 1000 у этого оператора?
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070894
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
if (currentQ < worstOfBestQ)
  проигнорировать();
else
{
  сохранить();
  if (countOfBest - 1 > runningCounter / 1000)
    забыть(worstOfBestQ);
}

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

Хорошо. Top N скользящих максимальных из бесконечного потока сущностей.

Я просто пытаюсь адаптировать вашу формулировку к более формальной.

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

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

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

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

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

Вы можете написать алгоритм чтобы не 0.1% сливок снимать, а с хорошей точностью отделять верхние 50% от нижних?

Просто поделить поток на два похожего размера, и чтобы один был заметно лучше другого. Или на три: получше, похуже и посередине.

Если умеете, примените метод которым обогащали уран в 50х, очень похоже. Берете лучший из двух, и снова делите. Десять раз повторите - приблизитесь к 0.1%
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070953
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
if (currentQ < worstOfBestQ)
  проигнорировать();
else
{
  сохранить();
  if (countOfBest - 1 > runningCounter / 1000)
    забыть(worstOfBestQ);
}

кстати, вот этот ваш алгоритм точно страдает тем недугом, который Dima T (напрасно) приписал моему словарно описанному алгоритму:
Dima T
если Max(Q) окажется абсолютным максимумом, то в итого будет пустой список
только в случае вашего алгоритма нужно говорить не "в итого будет пустой список", а "в итого будет список из одного элемента".

В самом деле, если первый элемент кучи, появившийся в ней в процессе обработке первой тысячи сущностей, окажется достаточно большим, то для всех сущностей из второй тысячи может сработать
Код: sql
1.
2.
if (currentQ < worstOfBestQ)
  проигнорировать();

и по итогу второй тысячи "куча лучших" просто не увеличится до двух элементов (как должна по смыслу).
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070956
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вылечить этот недуг может такая модификация алгоритма:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
if ((currentQ < worstOfBestQ) AND (countOfBest >= runningCounter / 1000))
  проигнорировать();
else
{
  сохранить();
  if (countOfBest - 1 > runningCounter / 1000)
    забыть(worstOfBestQ);
}

которая, кстати, приведёт к заметному увеличению потока сущностей, сбрасываемых на диск:

1001-я сущность, например, будет сброшена полюбасу, потому что для неё (countOfBest >= runningCounter / 1000) перестанет выполняться.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070963
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Часть лучших потеряется, т.к. при добавлении элемента к результату по-хорошему надо заново пересмотреть весь поток.
Например в первой тысяче были значения 100 и 99. Ячейка результата одна, поэтому сохранил только 100, а 99 пришлось пропустить.

Поэтому размер результата надо выбрать на старте.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070964
в цикле потока сразу же заполняется буфер из 1000 любыми значениями
а уже потом из них вытаскивается самое мелкое, по которому ориентируется весь остальной поток
до тех пор, пока в буфере не сменится это "самое мелкое"

ТС уже определился, сколько ему всего значений надо в итоге? Или всё ещё с бесконечностью работаем?
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070971
Ы2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
бабушкин зайчикТС уже определился, сколько ему всего значений надо в итоге? Или всё ещё с бесконечностью работаем?
Довольно очевидно, что он хочет в любой момент времени иметь ≈1/1000 лучших от полученных из потока.

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

А ты не вызывай flush() и они останутся в памяти.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40071047
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
А ты не вызывай flush() и они останутся в памяти
доктор сказал "в морг", значит в морг. Если критерий (он же алгоритм) сказал "сохранить()", значит сохранить.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40071048
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ы2
сколько сущностей нужно оценить, прежде чем лучшие будут иметь хоть какой-то смысл?
я не знаю. Я даже не знаю, буду ли я сбрасывать 1/1000, или 1/10000, или 1/1000000.

Я уже писал вчера, что у меня, на самом деле, "пакетная" обработка данных, то есть мне необходимо осуществлять не один "поток записи на диск (типа, со скважностью 1/1000)", а как минимум 100 таких потоков одновременно.

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

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

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

Только ты пойми что никто не предлагает хранить 100% сущностей.

На всякий случай алгоритм хранения добавлю:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
if ((currentQ < worstOfBestQ) AND (countOfBest >= runningCounter / 1000))
  проигнорировать();
else
{
  uint64_t смещение = сохранить_в_файл_сущностей(current_сущность);
  сохранить(currentQ, смещение);
  if (countOfBest - 1 > runningCounter / 1000)
    забыть(worstOfBestQ);
}


Просто последовательно пишешь нужные на текущий момент (!!! не все) сущности в файл, а в памяти хранишь значение Q и смещение в файле где эта сущность записана. При необходимости получения сущности открываешь файл сдвигаешь указатель на нужное смещение и читаешь.

Дальше тюнинг работы с файлом с промежуточным кэшем в памяти частоиспользуемых значений и т.д. и т.п. Хотя за тебя ОС это сделает не хуже.

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

До тебя так и не дошло, что разница между ними всего лишь в ссылке на саму сущность? Или это Визуальный Бейсик так людей портит?..

Иван FXS
вы понимаете, что означают слова " большая " и " нельзя "? Вы, наверное, думаете, что если нельзя, но очень хочется, то можно??

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

Dima T
Смею предположить что он его отсек этим пунктом ТЗ:
Иван FXS
Также не желательно решение, предполагающее накопление (по ходу работы) всех числовых значений самого Q . Хотя бы потому, что оно является тривиальным.

Только ты пойми что никто не предлагает хранить 100% сущностей .
вы продолжаете путать Q и сущности -- как мне донести до вас, что это не одно и то же?

А "этим пунктом ТЗ" я отсёк ровно то, что я им отсёк. Вы понимаете, что одобрив код, предложенный Dimitry Sibiryakov, и даже немного его поправив, я уже согласился (скрепя сердце) хранить в памяти всю кучу лучших значений Q? Не "всех числовых значений самого Q", как в том "пункте ТЗ", на который вы сейчас ссылаетесь, а "всех отобранных по критерию лучших числовых значений самого Q".

Dima T
Просто последовательно пишешь нужные на текущий момент (!!! не все) сущности в файл
предметом задачи является именно критерий (и алгоритм) отбора сущностей для записывания оных "в файл", но ваш эпитет "нужные" не является таковым критерием (алгоритмом).

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

Эта программа занимается "разыгрыванием" по методу Монте-Карло, для чего создаёт эти сущности из ничего, из ДСЧ (на основе контекста Монте-Карлемой задачи, конечно), после чего их --возможно -- сбрасывает на диск и -- точно! -- уничтожает. И никакие ссылки на них после этого указывать не могут.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40071092
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Модератор: Мне кажется без конкретики (примеров данных, примеров кода) топик можно закрывать.
Если за 6 страниц так и не смогли понять что надо ТСу, то наверно нет смысла продолжать в общих словах.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40071095
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Если за 6 страниц так и не смогли понять что надо ТСу, то наверно нет смысла продолжать в общих словах
замечу, однако, что решение на основе "кучи лучших" более-менее оформилось. По решению "без кучи" -- типа, на основе П и Ш (как давно это было!) -- продвижения, увы, нет.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40071098
Dima T
Если за 6 страниц так и не смогли понять что надо ТСу

проспаться ему надо.
А то 6ю страницу догнать не может, что коли Q привязан к своей сущности, значит сущности можно сложить в БД/файл и дёргать оттуда нужные, когда понадобятся, а вся работа по отсеву идёт именно с Q.
Иван FXS
вы продолжаете путать Q и сущности -- как мне донести до вас, что это не одно и то же?

тут собрались люди очевидно поумнее вас, и путаница вся только у вас в голове.
6ю страницу рассказываете про Q и сущность (из 3х параметров), которая к ней привязана.
Уже давно все всё поняли и решение было ещё на 1-2 страницах.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40071102
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мож тогда лучше создать 2й топик, а этот продолжить? И новый (про Порог и Шаг) начать с необходиммой преамбулой (ну, мол, был 1й вариант - туда, в сад, а этот - сюда прошу)?
Ну и здесь указатель поставиьть: прямо пойдёшь ..., налево пойдёшь ...
Мне только кажется, что сложно с П и Ш ... Да, и нужно хотя бы в этом случае нормальное ТЗ написать, казалось бы, теперь уже возможно.

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

(Писать в БД миллионы записей, которые точно потом не понадобятся -- это великое программистское искусство!)
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40071107
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
Мож тогда лучше создать 2й топик
вы модератор, у вас какие-то модераторские соображения, о которых я могу только догадываться ... но не стану. Я могу только констатировать, что у меня степень разумения задачи повысилась ... хотя и времени потрачено изрядно.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40071108
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я предлагаю этот топик закрыть. Вроде все уже высказались. А выборки из бесконечных труб и хранение поднять
совершенно отдельной темой с другой формулировкой, если надо.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40071110
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иван FXS, нет, я не модер, я другой.
И как раз самое время, ИМХО, на фоне возросшего понимания задачи (своей же задачи, замечу), переформулировать задачу, устранив выявившиеся умолчания и взаимонепонимания.
...
Рейтинг: 0 / 0
Как отбирать из потока 1/1000 лучших экземпляров?
    #40071113
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98, я не понимаю, что значит "переформулировать задачу" ... разве что поднять из 4-й реплики в тело поста
Иван FXS
каждая сущность "большая", много больше, чем числовой параметр Q сам по себе, так что хранить их в памяти нельзя, можно только по очереди каждую оценивать и решать, сбрасывать её на диск или нет.

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

Я тут модератор.

Тут в топике какой-то бесконечный цикл: тебе говорят решение, ты говоришь оно неправильное, но не объясняешь в чем неправильное (или непонятно объясняешь) и так по кругу ...

Боюсь что закрытием топика эту бесконечность не прервать, но давай попробуем.

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


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