ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как отбирать из потока 1/1000 лучших экземпляров?
25 сообщений из 151, страница 5 из 7
  5  все
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070823
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Иван FXS
Dima T
Только хранить миллион самых лучших на текущий момент
как только вы произнесли "миллион" -- вы перестали работать с потоком как с потоком . Потому что у потока нет никакого ни миллиона, ни миллиарда, ни триллиона.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

увы.
...
Рейтинг: 0 / 0
17.05.2021, 16:50
| Ответить | Цитировать | Написать  
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070842
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вариант top 1000 скользящих максимальных из бесконечного потока подходит?
...
Рейтинг: 0 / 0
17.05.2021, 17:01
| Ответить | Цитировать | Написать  
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070851
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
17.05.2021, 17:14
| Ответить | Цитировать | Написать  
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070858
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
Иван FXS
White Owl, текст 22321305 , ссылку на который вы дали, не содержит ответа на заданный вопрос

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

Если умеете, примените метод которым обогащали уран в 50х, очень похоже. Берете лучший из двух, и снова делите. Десять раз повторите - приблизитесь к 0.1%
...
Рейтинг: 0 / 0
18.05.2021, 03:22
| Ответить | Цитировать | Написать  
Как отбирать из потока 1/1000 лучших экземпляров?
    #40070953
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван 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
18.05.2021, 07:40
| Ответить | Цитировать | Написать  
25 сообщений из 151, страница 5 из 7
  5  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Как отбирать из потока 1/1000 лучших экземпляров?
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru             Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=40070830&tid=1339663]:
 0ms
get settings:
 11ms
get forum list:
 17ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 56ms
get topic data:
 13ms
get forum data:
 3ms
get page messages:
 79ms
get tp. blocked users:
 2ms
others: 247ms
total:  436ms
созд. / загр.: 436ms
x
x
Закрыть


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