Как реализовать выдачу рандомного элемента из массива с учетом рейтинта?

Question

[Roman Prokopets]

Помогите решить задачу, есть на сервере массив с обьектами. В каждом обьекте есть грубо говоря имя(которое не имеет сейчас значения) и рейтинг. Этот рейтинг изменяется с помощью нажатия на кнопку-оценку этого элемента,которая прибавляется и делится на количество оценок. Задача: реализовать механизм рандомного показа элемента на UI с более приоритетным уклоном в сторону элементов с низким рейтингом, то есть не показывать просто элемент с наиболее низким рейтингом, а чтобы элементы с низким рейтингом имели приоритет, желательно без ввода сторонних значений, типа priority

Answer 1

[Developer]

Если я правильно понял задачу, то я решал бы её так.
1. Отсортировать масси по убыванию значения оценки. P.S. На самом деле оказалось, что не обязательно.
2. Далее исходим из таких соображений. Пусть сумма всех оценок sum(M(i)) будет равна S и примем это за 100% вероятность. То есть, со 00% вероятностью один из элементов нашего массива будет выбран.
Тогда вероятность выпадания i-го элемента будет пропорциональна его оценке: P(i) = M(i)/S
3. Будем проходить по каждому элементу отсортированного массива и будем вычислять вероятность P(i). Выбираем случайное число P = random()*N, где N - оставшееся число непройденных элементов. Если P < P(i), то показываем этот рандомный элемент i и завершаем цикл.
4. Пересчитываем S = sum(M(i)) для всех оставшихся элементов.
Сложность алгоритма получается O(N^2)
Это так, сходу решение.
Но его можно улучшить ка минимум до О(N), а, возможно, и до O(1). Но тогда придётся ввести дополнительное поле вероятности.

UPD: Вынесу пример из комментариев:

Пусть у нас массив из оценок [5, 5, 3, 2]
Сумма всех оценок S = 5+5+3+2 = 15
Вероятности выбора каждого элемента:
[5/15, 5/15, 3/15, 2/15] = [0.33333, 0.33333, 0.2, 0.133333], в сумме они дадут 1, как и должно быть.
1. Берём первый элемент с оценкой 5 и с вероятностью 0.3333 выбираем его: P = random()*1.0
Если P<0.333, то выбираем 1-й элемент и заканчиваем работу. Иначе идём дальше
2. Берём 2-й элемент с оценкой 5. Теперь у нас вероятность изменилась и мы её пересчитываем, чтобы в сумме была 1:
S = 5 + 3+ 2 = 10
Пересчитываем вероятности:
[5/10, 3/10, 2/10] = [0.5 ,0.3, 0.2] - в сумме опять 1, как и должно быть.
Теперь с вероятностью 0.5 определяем, берём ли мы 2-й элемент в качестве результата или нет: P = random()*1.0
Если P< 0.5, то заканчиваем работу. Иначе, идём дальше.
3. Пересчитываем общую сумму оценок: S = 3 + 2 = 5
Новые вероятности для оставшихся оценок: [3/5, 2/5] = [0.6, 0.4], в сумме опять 1
С вероятностью 0.6 определяем, оставляем ли 3-й элемент в качестве результата или нет.
Если нет, то дальше
4. Пересчитываем сумму оставшихся оценок: S = 2.
Новые вероятности для оставшихся оценок: [2/2] = [1].
То есть, со 100% вероятностью забираем последний элемент.
Но вот чтобы добраться до последнего элемента надо продраться через тернии более высоких оценок. Сложно, маловероятно, но в принципе это возможно.

UPD: Для оптимизации расчёта новой суммы S просто вычитаем из предыдущей S значение оценки i-го элемента. Сводим алгоритм к O(N)

UPD2: Если надо инвертировать и сделать так, чтобы элементы с минимальными оценками показывались чаще, то надо инвертировать вероятность: 1-P

UPD3, решение за время O(1) Я тут ещё раз подумал и решение оказалось ещё более простым.
Пусть у нас массив из оценок [5, 5, 3, 2]
Сумма всех оценок S = 5+5+3+2 = 15
Вероятности выбора каждого элемента:
[5/15, 5/15, 3/15, 2/15] = [0.33333, 0.33333, 0.2, 0.133333]
Строим отрезок, откладывая на нём эти четыре значения.
Берём случайное число от 0 до 1 и смотрим, в какой из этих четырёх отрезков он попадает. Вот и решение.
Если надо, чтобы маловероятные оценки выпадали, то строим инвертированные вероятности:
[0.6666, 0.6666, 0.8, 0.8666666]

Comments

[Roman Prokopets]

первое прям как у меня, и начало второго, дальше ничего не понял)

[Developer]

Roman Prokopets, Сложно так объяснять.
Основная мысль в том, что Мы идём по массиву и с некоторой вероятносью решаем, берём мы этот элемент или идём дальше. Вероятность зависит от величины оценки. И у нас обязательно должно соблюдаться условие, что среди оставшихся элементов мы на 100% что-то должны выбрать. Сейчас напишу пример для понимания

[Roman Prokopets]

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

[Developer]

Roman Prokopets, да, я так и понял.
Сейчас стал писать пример и понял, что мой алгоритм немного не верный.
Ща подумаю и напишу

[Roman Prokopets]

Developer, ок, буду ждать

[Developer]

Пусть у нас массив из оценок [5, 5, 3, 2]
Сумма всех оценок S = 5+5+3+2 = 15
Вероятности выбора каждого элемента:
[5/15, 5/15, 3/15, 2/15] = [0.33333, 0.33333, 0.2, 0.133333], в сумме они дадут 1, как и должно быть.
1. Берём первый элемент с оценкой 5 и с вероятностью 0.3333 выбираем его: P = random()*1.0
Если P<0.333, то выбираем 1-й элемент и заканчиваем работу. Иначе идём дальше
2. Берём 2-й элемент с оценкой 5. Теперь у нас вероятность изменилась и мы её пересчитываем, чтобы в сумме была 1:
S = 5 + 3+ 2 = 10
Пересчитываем вероятности:
[5/10, 3/10, 2/10] = [0.5 ,0.3, 0.2] - в сумме опять 1, как и должно быть.
Теперь с вероятностью 0.5 определяем, берём ли мы 2-й элемент в качестве результата или нет: P = random()*1.0
Если P< 0.5, то заканчиваем работу. Иначе, идём дальше.
3. Пересчитываем общую сумму оценок: S = 3 + 2 = 5
Новые вероятности для оставшихся оценок: [3/5, 2/5] = [0.6, 0.4], в сумме опять 1
С вероятностью 0.6 определяем, оставляем ли 3-й элемент в качестве результата или нет.
Если нет, то дальше
4. Пересчитываем сумму оставшихся оценок: S = 2.
Новые вероятности для оставшихся оценок: [2/2] = [1].
То есть, со 100% вероятностью забираем последний элемент.
Но вот чтобы добраться до последнего элемента надо продраться через тернии более высоких оценок. Сложно, маловероятно, но в принципе это возможно.

UPD: Для оптимизации расчёта новой суммы S просто вычитаем из предыдущей S значение оценки i-го элемента. Сводим алгоритм к O(N)

[Roman Prokopets]

Developer, не покажусь ли я слишком наглым, если попрошу это изобразить кодом?)
это вот как у меня
const minGrade = cards.reduce((acc, el) => acc.grade < el.grade ? acc : el) - поиск мин элемента

const newGrade = (card.shots * card.grade + grade) / (card.shots + 1);
const updatedCard = {...minGrade, shots: card.shots + 1, grade: newGrade};

[Developer]

На самом деле, получается, что даже сортировать не нужно. Вероятности сделают своё дело.

[Developer]

Roman Prokopets, кодом в лямбдах я слабоват. Не люблю ФП.
Я надеюсь, что мысль относительно алгоритма понятна?

[Roman Prokopets]

Developer, вроде да, мне уже подсказывали нечто подобное, просто с это сложно въехать непосредственно в коде, в любом случае если Вы не сможете прописать кодом и на этом очень благодарен

[Developer]

Roman Prokopets, я бы рад кодом помочь, он тут не сильно сложны. В лямбдах это напишется в одну строку, но я так не умею.
Я напишу циклами, а в 2020-м это не очень модно, тем более, для JS

[Roman Prokopets]

Developer, я разберусь)мне бы только увидеть что да как в коде)

[xmoonlight]

Developer, т.е., чем больше голосов, тем больше вероятность. Так? Разве не наоборот нужно?

[Roman Prokopets]

xmoonlight, чем больше НИЗКИХ голосов, тем больше вероятность

[xmoonlight]

Roman Prokopets, ну я так и подумал. В ответе-то - наоборот!

[Developer]

xmoonlight, Возможно, я ступил и перепутал.
Тогда решается просто инвертированием вероятности: 1-P
Это не суть важно и на сам алгоритм никак не влияет.

[Developer]

Roman Prokopets, Тогда надо вероятность вычесть из единицы: 1-P
Но алгоритм остаётся тем же.

[xmoonlight]

Developer, к алгоритму - никаких претензий! Просто решил оповестить в плане логики)

[Roman Prokopets]

Developer, а можете еще плиз пояснить P<0.333 начал реализовывать, здесь не понял

[Developer]

Roman Prokopets, смотри, тебе надо найти случайное число в промежутке от 0 до 1 с вероятностью 0.333.
Как это сделать?
Делаем случайное число от 0 до 1:
x = random()*1.0
Получили число.
Вероятность того, что оно меньше 0.3333 как раз и есть эта вероятность.
Я не знаю как это описать более доступно.
Поэтому сравниваем x < 0.3333. если меньше, то наше вероятностное событие наступило

[Developer]

Roman Prokopets, приведи код. Попробую помочь

[Roman Prokopets]

Developer,
const sum = cards.reduce((acc, card) => acc.grade + card.grade) - сумма всех рейтингов
const devideCard = cards.map((card) => card.grade / Number(sum)) - деление суммы конкретного рейтинга на их кол-во
допустим x = Math.random()*1
дальше я теряю нить, заранее спс за ответ

[Developer]

Roman Prokopets, посмотри в решении UPD3, там наиболее простое и быстрое решение за O(1)

[Roman Prokopets]

Developer, не знаю что это

[Developer]

Roman Prokopets, что именно? UPD3 - это дополнение к ответу, см. выше

[Roman Prokopets]

Developer, а можете плиз циклом изобразить вот эти варианты с рандомом? я просто никак не могу идеально выверить это все, только такое вот придумал
const next = () => {
for (let i = 0; i < devideCard.length; i++) {
if (x > devideCard[i]) {
return devideCard[i]
} else {
return devideCard[i++]
}
}
}

[Developer]

Roman Prokopets,

var arr = [2, 3, 5, 5];
console.log(arr);
var sum = 0;
for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
}

for (let i = 0; i < arr.length; i++) {
    console.log(i + ") " + (arr[i]/sum));
}

console.log(sum);

var r = Math.random();

console.log("random number: " + r);

var totalP = 0;
for (let i = 0; i < arr.length; i++) {
    var p = arr[i]/sum;
    console.log("p => " + p);
    totalP += p;
    console.log("\ttotalP => " + totalP);
    if(r < totalP) {
        console.log("\t\tBINGO!!!! => item " + i + " with mark: " + arr[i]);
        break;
    }
}

Answer 2

[Роман Александрович]

Достаточно частая задача. Вы должны просто отсортировать массив обьектов. Обычно с сервера уже присылают сортированный массив но можно сделать и на клиенте.
пример украден https://www.sitepoint.com/sort-an-array-of-objects...

const singers = [
  { name: 'Steven Tyler', band: 'Aerosmith', born: 1948 },
  { name: 'Karen Carpenter', band: 'The Carpenters', born: 1950 },
  { name: 'Kurt Cobain', band: 'Nirvana', born: 1967 },
  { name: 'Stevie Nicks', band: 'Fleetwood Mac', born: 1948 },
];

function compareValues(key, order = 'asc') {
  return function innerSort(a, b) {
    if (!a.hasOwnProperty(key) || !b.hasOwnProperty(key)) {
      // property doesn't exist on either object
      return 0;
    }

    const varA = (typeof a[key] === 'string')
      ? a[key].toUpperCase() : a[key];
    const varB = (typeof b[key] === 'string')
      ? b[key].toUpperCase() : b[key];

    let comparison = 0;
    if (varA > varB) {
      comparison = 1;
    } else if (varA < varB) {
      comparison = -1;
    }
    return (
      (order === 'desc') ? (comparison * -1) : comparison
    );
  };
}

// array is sorted by band, in ascending order by default
singers.sort(compareValues('band'));

// array is sorted by band in descending order
singers.sort(compareValues('band', 'desc'));

Comments

[Developer]

а где здесь выбор случайного элемента?

[Roman Prokopets]

да, моя задача нуждается именно в сортировке на фронте, но Ваше решение я не понял

[Роман Александрович]

Roman Prokopets, почитайте статью там вроде не сложно. Смысл в том что вы сортируете массив обьектов по ключу. Если забьете в гугле запрос то уверен найдете аналогичное решение.

[Roman Prokopets]

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

Answer 3

[xmoonlight]

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

Пример:
Было (одна цифра - рейтинг элемента):
5861273
Стало:
1238765 (или 2138765 или 3128765 и т.д.)

Comments

[Roman Prokopets]

нужен еще рандом+ ко всему

[xmoonlight]

Roman Prokopets, ну я ж дал пример. Кластер рандомить.

[Developer]

xmoonlight, а можно кодом? "Кластер рандомить" - это завуалированное "иди нахрен"

[xmoonlight]

Developer, что именно непонятно?