Алгоритм выборки топ 10 фотографий?

Question

[nexus0]

Есть n фотографий, из них нужно найти топ k самых "красивых" и составить рейтинг-список (список в котором фото расположены в порядке убывания по красоте) для этих k фотографий.
Топ k красивых определяет один пользователей, делая выборки между двумя фотографиями.
Пример: есть 200 фотографий котов, из них нужно определить 10 самых милых и из этих 10 составить рейтинг-список по убыванию милости.
Надеюсь доступно что объяснил доступно.

Comments

[AWEme]

Ща ща ща, не подсказывай, я почти угадал критерии топовости

[nexus0]

AWEme, пользователь выбирает между двумя фотографиями

[Владислав Лысков]

nexus0, фотографий 200, пользователь выбирает между 2умя и получаем топ 10?

[AWEme]

nexus0, често, яснее не стало. Может есть ещё какие-то детали?

[Developer]

nexus0, ну так и выбирай первую

[Владислав Лысков]

Алгоритм от Влатьки
Эксклюзив
Помещаешь фотографии в массив
Сортируешь его в случайном порядке
Выбираешь первые 10 элементов
Что там выбрал пользователь из 2ух вообще не важно
Благодари, можешь выслать пива

[Ксения]

nexus0, сочувствую пользователю.

Answer 1

[Сергей Соколов]

Посмотрите алгоритмы сортировки. Например, методом пузырька придётся до 10 раз пройти по всему массиву, итого 199+198+197+...+189 = 2123 сравнений.

Но т.к. интересует только верхушка, можно оптимизировать. Разбить фотогрфии на пары, сравнить попарно, отбросить проигравших. Так уменьшается вдвое число кандидатов. 200 -> 100 -> 50 -> 25 -> 13 за 100+50+12=162 сравнения. Оставшиеся 13 надо уже пузырьковым методом отсортировать до отбора топ-10: 12+11+10+...+3 = 75
Итого всего 237 сравнений, если не ошибаюсь.

В фильме «Социальная сеть» (2010) есть эпизод, где молодой Цукерберг якобы использовал алгоритм начисления шахматного рейтинга ELO в своём первом приложении FaseMash для сравнения, какая из девушек привлекательнее. Там тоже посетители выбирают одну из двух фотографий. Может ли это сократить число необходимых сравнений, вопрос открытый.

Comments

[ⓒⓢⓢ]

Если топ из 10ти, то это значит или всего участвуют 20 фотографий (что маловероятно) , или же за фотографию можно проголосовать несколько раз.

По моей идее
1. Тогда или в бесконечность, при одинаковом везде рейтинге
2. Или в худший вариант [200,0,0,0,0,0,0,0, ... ,0]
Тут уже попарно не отбросить, за один полный проход всех фотографий будет отсеиваться 1 фото ... эффективность пузырька

1. +200 сравнений - вырезать нулевой рейтинг (оставить 10 фоток)
2. Проход с попарной оптимизацией 200 -> 100 -> 50 -> 25 -> 13
3. Пузырёк
4. Если осталось фоток < 10 взять из п.1

на ~210 сравнений будет больше, но тогда не уйдём в бесконечность

[Сергей Соколов]

JRK_DV, не понял, откуда цитата и как ваш комментарий относится к моему ответу

[ⓒⓢⓢ]

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

[Сергей Соколов]

JRK_DV, а, понял. Да, при равном рейтинге в попарном сравнении придётся откладывать обоих кандидатов в пузырьковую ванну )

Answer 2

[Олег]

Как понимаю это лабораторная работа по языку.

Есть оценки А Лучше б.

Топ 10 фото с максимальным колвом отмеченных лучше чем другое.

Select idea from tcomare group by idea sort by count(*) desc limit 10

А вот дальше уже извращения друг фото на з ей позиции чаще оценивают лучше чем первое . и т.д и т.п

Answer 3

[Александр Скуснов]

Случайный выбор двух фото. Выигрышную плюсуем, проигрышную минусуем.