Алго подскажите

[TerVer]

Хай!
Чет за три дня не могу придумать.
Имеется к примеру 2000 страниц и определенное кол-во ссылок (от 5 до 5000).
Так же для каждой ссылки есть статистика, которая выражается числом от 10 до 20000. (ну типа $link[$url]=$numder)
В каждую страничку хочу вставить до 5 ссылок.
Как бы ссылки распределить по сраничкам в соответствии со статистикой покрасивее?!

[TerVer]

да - равномерно расставить ссылки, согласно весам (статой).
Приведеные решения были бы хороши, если линков было бы штук 10-20 и веса их не сильно разнились бы. А так например линков может быть 500 а веса от 10 до 20000. На 2000 страницах рандом - ну ошеньма некрасиво сработает.

ЗЫ: alexpotemkin, вы изобретали велосипед! В универе на ОС помню разжевывали распеределение ресурсов по задачам. Рассматривали всякие способы, этот был самый понятный сцука без всяких хэшов, кэшов ...

[alexpotemkin]

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

[seeker]

Сообщение от TerVer

да - равномерно расставить ссылки, согласно весам (статой).
Приведеные решения были бы хороши, если линков было бы штук 10-20 и веса их не сильно разнились бы. А так например линков может быть 500 а веса от 10 до 20000. На 2000 страницах рандом - ну ошеньма некрасиво сработает.

разбей свои линки по массивам/файлам
в каждом по 10 штук
и бери оттуда иногда

а вообще такие хитровыебанные задачи представляются так:
есть такие-то линки: линк1 линк2 линк3 и есть такие-то паги: пага1 пага2 пага3
хочу получить: пага1 линк1 -> пага2; пага2 линк3 -> пага4
и т.д.
т.е., что было и что надо, а то тут элементы телепатии мешают сосредоточиться

[chesser]

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

[TerVer]

Решили как-то мемберы гоуфака подарить подарки детям на новый год. Определились - коробка конфет каждому ребенку. Закупили K коробок. Опытным путем выяснили, в одну коробку помещается N конфет.
Пошли в магазин. Узнали, сортов конфет S и также узнали(спиздили наверно или в гугле нашли) сколько каких конфет было продано за последний год. В магазине условие: что одного сорта конфет можно покупать не меньше M. Решили, что покупать конфеты будут всех сортов(ну чтобы редкий сорт можно было бы хотя бы у кого-нибудь выменять) И в каждой коробке все конфеты будут разных сортов.
Теперь бы придумать им как разложить эти конфеты в соответствии со статистикой продаж. Т.е. % закупленных конфет каждого сорта от общего кол-ва конфет был бы наиболее близок к проценту продаж в стате.
Для всех примеров: конфет одного сорта купить можно не меньше 3,стата для каждого сорта от 10 до 20000
Пример1: Подарков 2000, сортов 10, в коробку помещается 5 штук,
Пример2: Подарков 700, сортов 200, в коробку помещается 7 штук
Пример1: Подарков 2000, сортов 500, в коробку помещается 5 штук

chesser рандом хорошо работает на больших дистанциях, тут он будет работать не красиво.

[alexpotemkin]

)))) с конфетами сильный пример

[chesser]

Сообщение от TerVer

chesser рандом хорошо работает на больших дистанциях, тут он будет работать не красиво.

Так я рандомом предлагал только выбирать кол-во страниц на странице, а то ты написал "ДО 5 ссылок", если ссылок будет ровно 5(или др константа), то первый рандом можно убрать, будет так

for (page=1 to 2000)  { // цикл по страницам
  for (page_url=1 to 5) {
    page_url = weight_random ($link[$url]) // выбор урл, согласно заданным весам распределений вероятностей, см ф-ю выше
  }
}

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

PHP код:

function getRand($arr) {

    $sum = array_sum($arr);
    $rnd = rand(1, $sum);
    $delta_prev = 1;
    foreach($arr as $k=>$v) {
      if($rnd >= $delta_prev && $rnd < ($v + $delta_prev)) {
        return $k;
      }
      else {
        $delta_prev += $v;
      }
    }
    return;
  } 


т.е. суешь ей массив

PHP код:

array(
  'url1' => 100,
  'url2' => 1000,
  'url3' => 500,
  'url4' => 10000
) 


и тогда url1 будет возвращаться функцией в 10 раз реже чем url2, в 5 раз реже url3 и в 100 раз реже url4. Т.е. при таком подходе чаще будет мелькать ссылка url4, т.к. у нее самый большой вес.
Осталось только пройтись по все страницам/подаркам и вынуть ссылки этой функцие 5 раз, если по 5 конфет/урлов на странице.
ну может опять не понял, но мне мой вариант нравится

[Юнга]

1) делаешь огромный массив в который добавляешь урлы
"для каждой ссылки есть статистика, которая выражается числом от 10 до 20000"
то бишь каждую ссылку добавляешь "число" раз.
2) потом мешаешь, мешаешь, мешаешь..
...???????...
4) профит.

результирующие наборы можно собирать хоть рандомом, хоть последовательно.

[Юнга]

иначе - надо исследовать природу статистики - и вводить соответствующие коэффициенты, чтобы ссылки с весом 20000 не забивали ссылки с весом 10.

[TerVer]

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

всем откликнувшимся спасибо