Хитрая выборка

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

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

решение в лоб -- очередь с приоритетами размером K.

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

имхо рюкзак тут ни при чем..

точно, походу я прогнал ... в рюкзаке ещё стоимость ... признаю, протупил ...

> Наверно, ты хотел потребовать не просто одного прохода, а такого прохода, чтобы на каждый элемент сразу в онлайне выдавать ответ -- берем/не берем.

Точно. Поэтому очередь не подходит. Задача о рюкзаке тут вообще никаким боком.

обобщение алгоритма невесты:) которая хочет лучшего жениха выбрать

> Задача о рюкзаке тут вообще никаким боком.

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

правильно регистрат говорит, приоритетная очередь (читай массив) длины К, раз К небольшое ... по исходному массиву достаточно пройтись один раз ...

> раз сам такой умный че блин ходишь спрашивать на форумы тада

На что обижаться-то?

> правильно регистрат говорит, приоритетная очередь (читай массив) длины К, раз К небольшое ... по исходному массиву достаточно пройтись один раз ...

Нет, K << N, но совсем не небольшое. Считаем что ни N ни K элементов не влезут в память.

> На что обижаться-то?

да потому что блин тут пытаешься помочь буквально как анонимус анонимусу, так не блин, "никаким боком" ... могут же и анонимусы ошибаться ...

> Нет, K << N, но совсем не небольшое. Считаем что ни N ни K элементов не влезут в память.

тогда если функция распределяет вес каждого элемента примерно равномерно, тупо брать каждый N/K-й элемент ...

а - не ... не каждый N/K-ый ... лучше те у которых функия возвращает знчение больше 1-K/N

> да потому что блин тут пытаешься помочь буквально как анонимус анонимусу, так не блин, "никаким боком" ... могут же и анонимусы ошибаться ...

Я и сказал что задача о рюкзаке не подходит. Только и всего.

> тогда если функция распределяет вес каждого элемента примерно равномерно

Совсем неравномерно.

> тупо брать каждый N/K-й элемент...

Тупо брать каждый N/K-й элемент - получим K элементов вообще без учета веса.

> а - не ... не каждый N/K-ый ... лучше те у которых функия возвращает знчение больше 1-K/N

Да, что-то вроде, только распределение как я уже писал неравномерно.

> обобщение алгоритма невесты:) которая хочет лучшего жениха выбрать

Это что? Где почитать?

> Да, что-то вроде, только распределение как я уже писал неравномерно.

тогда смотреть функцию надо ... надо найти y такое, что интеграл по функции от y до 1 деленный на интеграл по функции от 0 до 1, равнялось бы K/N ... имхо ...

брать оответственно элементы больше y

Я конечно можт ганю сильно, всего лишь учусь, а нельзя делать так (далеко не оптимальный алгоритм конечно) берем 1 элемент массива N кладем, берем второй если он лудше первого кладем, если нет , то не кладем и берем след. Потом берем когда есть 2 элемента уже, то сравниваем следующий элемент с суммой хорошести первых двух деленное на 2. В итоге когда хотим положить k-ый мы берем сумму хорошестей предыдущих k-1 элементов делим на k-1 и получаем типо среднею хорошесть всех элементов и если k больше средней хорошести, то берем. Тем самым на каждом шаге хорошесть суммарная увеличивается. Массив N >> K вполне реально его набить.
Приму критику:)

видимо, первые элементы нужно поскипать, накапливая статистику. Сколько первых элементов нужно поскипать это некая функция от K и N.

Оставшиеся элементы выше некой квантили нужно принимать, одновременно подправляя статистику. Как-то так наверно..

dilmah, кстати да. Можно первый не брать а статистику накапливать, вот только проблема а чо будет если N вдруг кончится все-таки? Брать все последние элемента? И Знаем ли мы это N?

Может тогда так:
kol - кол-во элементов.
например первые N\(k*L) пропускаем(как говорил dilmah) и по ним накапливаем некоторых средюю хорошесть пропущенных элементов. где L>1.
Разбить весь массив на N/K подмассивов как предлагал топикфаундер.
Идем и смотрим хорошесть элементов, если она выше средней то тогда берем и пересчитываем среднюю и делаем kol++, если нет то параллельно делаем например пузырек(нам нужен только 1 максимальный элемент) на макс элемент на данном N/Kом куске. Если мы дошли до конца куска N/K и kol=0 то тогда берем максимальный элемент, который мы нашли с помощью пузырька но среднюю хорошесть не пересчитываем (чтобы ее не ухудшать) и kol все также остается равным 0. Типо взяли в экстренном случае, чтобы не получилось так что N кончился,а K не набрали.
Покритикуйте:)

> тогда смотреть функцию надо ... надо найти y такое, что интеграл по функции от y до 1 деленный на интеграл по функции от 0 до 1, равнялось бы K/N... имхо...

Да, какие-то такие мысли летают. Только тут нужно распределение, а оно неизвестно.

> видимо, первые элементы нужно поскипать, накапливая статистику. Сколько первых элементов нужно поскипать это некая функция от K и N.

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

> Я конечно можт ганю сильно, всего лишь учусь, а нельзя делать так

Вот это уже очень близко. Такая мысль есть:
- храним средний вес всех взятых элементов = M
- следующий элемент берем, если его вес >= M * ((n/N) / (k/K))

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

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

*kol в первый момент времени =0 и увеличивается только в том случае если взяли элемент при увеличенной хорошести. Уменьшается он только в том случае если мы перешли границу N/K подмассива и если kol был >0.

*kol уменьшается при переходе границы на 1, т.е. kol--.
И еще при пересчете средней хорошесть брать макс из текущей хорошести и новой пересчитаной, потомучто мы можем набрать неочень хороших элементов (по 1 с N/K подмассива), которые нам могут портить хорошесть, а так она у нас будет либо прежняя, либо расти.
Это я думаю работать будет плохо, если все таки самые хорошие из хороших элементов находятся в конце массива N.

> а оно неизвестно.

ну так блин, если ниче неизвестно, то ниче и не получится ...

> ну так блин, если ниче неизвестно, то ниче и не получится

Все, успокойся. Несешь чушь, а потом еще и обижаешься.

> - храним средний вес всех взятых элементов = M > - следующий элемент берем, если его вес >= M * ((n/N) / (k/K))

Провел эксперименты, этот алгоритм работает замечательно, на нем и остановлюсь.

Всем спасибо за идеи.

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

Нет, ибо она не одинаковая.

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

> Все, успокойся. Несешь чушь, а потом еще и обижаешься.

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

ну если просто сумма, то почему не взять просто K самых больших чисел из исходного массива?

> ну если просто сумма, то почему не взять просто K самых больших чисел из исходного массива?

именно это и пытаются сделать:)

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

что за бред. ну и в чем тогда проблема? выбрать контейнер для 
хранения K чисел? да хоть обычный массив. этот код можно написать за 
20 минут!
охрененно хитрая выборка. 

> что за бред. ну и в чем тогда проблема? выбрать контейнер для хранения K чисел? да хоть обычный массив. этот код можно написать за 20 минут!

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

смотрим есть ли в массиве меньшее число - если есть то заменяем.
ну сохраняя массив отсортированным.

> смотрим есть ли в массиве меньшее число - если есть то заменяем.

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

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

>ответ по каждому элементу (берем или выбрасываем) надо сразу дать, нельзя смотреть вперед.

И это при том что о потоке заранее ничего неизвестно так как проход возможен всего один ? Это надо было сразу на форум волшебников вопрос :)

Имхо чтобы использовать вероятностный алгоритм надо хотя бы математическое ожидание максимальной величины оценить.

а зачем заглядывать вперед? сначала выбираем первые K чисел из последовательности, потом в зависимости от вновь прочитанного числа - либо заменяем одно из этих K чисел на него, либо нет. результат - K максималных чисел в последовательности

Это конечно очень логично но если размер исходного массива данных N и размер выборки K очень велики то вычисление по твоему алгоритму рискует затянуться во времени :)

> Ткните в подходящий алгоритм.

google quickselect -- дальше ясно будет, если не ошибаюсь.

K по условию не велик. если N очень большой, то можно брать числа из 
него случайно некотрое количество чисел (по усл, нам нужна не точная 
выборка, кроме того любой алгоритм просматривающий весь массив будет 
иметь сложность не меньше O(N)). сложность того что я предложил O(N*K)
разумеется если применить другой контейнер - можно уменьшить 
сложность.

2 Die-Hard
зачем здесь это?

> Чтобы не думали что это задача из ВУЗа

Не надо только гнать тут, да. Таких граничных условий на практике не бывает.

> Нет, K << N, но совсем не небольшое. Считаем что ни N ни K элементов не влезут в память.

Тогда предварительно сортируй всё.

Или считай среднее арифметическое. С отбрасыванием меньшей половины после каждого прохода, пока N не станет меньше 2K.

В любом случае без данных о структуре массива (тупо последовательно цифры) других алгоритмов не будет.

Все алгоритмы на больших объёмах требуют индексирования.

> Нет, K << N, но совсем не небольшое. Считаем что ни N ни K элементов не влезут в память.

вот это я не читал. но поскольку K всеравно придется гдето хранить и
K сразу сортируется, ничего менять не надо

> можно брать числа из него случайно

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

// не ОП

>чтобы их сумма была максимальной (на самом деле не строго, нужно как можно больше)

быдло код не выйдет

> результат - K максимальных чисел в последовательности

+1

> сначала выбираем первые K чисел из последовательности, потом в зависимости от вновь прочитанного числа - либо заменяем одно из этих K чисел на него

+1

минимальное из K заменяем на максимальное из {считанного и имеющегося}