Разработать алгоритм хранения

Ответ 1

Предположим, что у вас есть память для хранения элементов k. Сохраните первые k элементы в памяти массива. Теперь, когда вы получаете n-й элемент (где n > k), создайте случайное число r между 1 и n. Если r > k отбросить элемент n ^th. В противном случае замените элемент r ^th в массиве элементом n ^th.

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

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

После получения n-го элемента вероятность того, что элемент будет вставлена ​​в массив = k/n.

Для любого другого элемента вероятность того, что он представлен в текущей итерации = вероятность того, что он представлен в предыдущей итерации * вероятность того, что он не будет заменен в текущей итерации

= (k/(n-1)) * (n-1)/n = k/n.

Ответ 2

Во-первых, кредит, где он принадлежит. Я подробно остановимся, а не заменим подход крямпани: действительно приятно и понятно.

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

Прежде всего заметим, что мы можем переформулировать результат, просмотрев его под другим углом, если вы хотите, чтобы в течение любого определенного периода времени точки (данные) от интервала времени между нулем и этим временем были ( пусть говорят: предполагается, что равномерно распределены по интервалу [1-n], из которого следует (заявленный результат), что их относительный счет в фиксированном интервале [1-k] должен быть k/n, предположительно оптимальным способом быть репрезентативным.

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

Статистическое "математическое ожидание", однако, конечно, редко является тем, что мы фактически получаем: это всего лишь среднее значение по сравнению с концептуально бесконечным числом попыток повторить одно и то же. Независимо от того, будет ли фактическое распределение данных из некоторого "периода времени" в течение интервала [1-n] и соответствующего производного значения их относительного счета в [1-k], вероятно, будет близко к (идеальному) значение ожидания зависит, в данном случае, от способа генерации случайных чисел (между 1 и n). Если это действительно случайное, мы будем делать выборку по методу Монте-Карло, что приведет к распределению результатов по гауссовскому типу, то есть к фактическим распределениям точек, если мы будем делать то же самое снова и снова, вокруг равномерного распределения, мы стремились. В качестве следствия, пока у нас не будет очень большого количества точек, статистический спред будет оставаться довольно большим, подразумевая, что, хотя "ожидаемая ценность" нашего точечного распределения является совершенной (то есть, когда мы нацелены), вероятность того, что в в однократной реальности у нас фактически есть что-то близкое к тому, что распределение не так велико.

Небольшое мышление сделает очевидным, что нет никакого способа всегда, после каждого добавления снова. идеальное равномерное распределение, независимо от того, как мы решаем заменить старые на более новые точки. Поэтому наша цель должна состоять в том, чтобы как можно больше увеличить ОЖИДАЕМОЕ ОТКЛОНЕНИЕ.

Проблема, переформулированная, заключается в следующем: с учетом интервала вам необходимо размещать баллы все больше без ограничений на этом интервале, так что их распределение всегда "как можно ближе" к однородности. Способ состоит в том, чтобы принять фиксированный "шаг" для каждой точки относительно предыдущей, где эта процедура является относительно простой и предпочтительно с двумя большими штрихами - до длины интервала. Пример с небольшими числами: интервал составляет 11 (в некоторой единице: "реальные" значения могут быть реальными, а не целыми), steplength берется как 5; шаги (k * 5) mod11: 0, 5, 10, 4, 9, 3, 8,.. В нашем случае у нас есть дополнительное усложнение, что интервал изменяется по длине. Возможно, нам потребуется адаптировать точечное поколение, например (я не уверен), установив, что любая новая точка будет размещена там, где она будет иметь исходные параметры (размер, шаг), а затем ее местоположение будет увеличено с помощью фактический интервал-длина: интервал снова 11, увеличиваясь на 1 каждый раз, и шаг = 5; пункты: 0, 5 * (12/11), 10 * (13/11) и т.д. В нашем случае, требуя целого "слота" для замены (или отсутствия) сохраненного значения, нам нужно округлить до ближайшего целого числа (и последствия этого округления по статистике могут вызвать дополнительную настройку точечного генератора), У меня больше ничего нет, есть еще кое-что, что нужно проработать.

Я прихожу к финальной - скрытой теме: Во всем вышеизложенном мы молчаливо предположили, что равномерная выборка - распределение точек поровну по интервалу - это лучший способ получить репрезентативный результат. Предположительно, мы можем интерпретировать "репрезентативный результат", поскольку, скажем, мы рассматриваем конкретную измерительную ценность - справедливую среднюю величину ее значений за определенный период времени. Изображая, что измеряемое значение ведет себя как определенная функция с течением времени, мы на самом деле смотрим на INTEGRAL этой функции в течение интервала времени (разделенного на длину интервала). Теперь, если изменения этой функции с течением времени не будут полностью дикими, прыгать вверх и вниз и делать всевозможные причудливые вещи - в этом случае все ставки будут выключены, и вы также можете сделать что-нибудь случайное - есть (теоретически и практически) установленные методы о том, как вы должны пробовать функцию ( "нормально себя вести" ) за интервал, чтобы получить "оптимальное" приближение его интеграла. Случайное (Монте-Карло) действительно плохо (сходится как 1/sqrt (N) с количеством точек выборки N); однородная выборка намного лучше (1/N) - и в некоторых особых случаях эффектно оптимальна, но оба они обычно затмеваются путем отбора проб на нулях конкретных полиномов, где - запрещающие больные случаи - вы обычно повышаете точность где угодно между 0,5 и несколькими ЗНАЧИТЕЛЬНЫМИ ЦИФРЫ при каждом добавлении только ОДНОЙ БОЛЬШЕ точки.

С приведенным выше в качестве точки зрения мы сталкиваемся с нашей первоначальной проблемой следующим образом: Как мы можем систематически генерировать точки на постоянно увеличивающемся интервале, так что во все времена распределение точек на интервале максимально приближается к распределению нулей тех конкретных (в зависимости от того, что вы знаете о функции, которую вы пожелать такой выборки, но при отсутствии какой-либо конкретной информации: Legendre) полиномы по этому интервалу (нормированные на [-1:1]).

Таким образом, мой (теоретический) подход будет заключаться в использовании метода с постоянным шагом по сравнению с первичным интервалом, где - в дополнение к корректировке того факта, что интервал увеличивается, см. выше - измерение длины вдоль интервала, для "вычисления" шага, взвешивается по распределению (функции) нулей (Лежандра) многочленов.