За последние 24 часа нас посетил 20881 программист и 1111 роботов. Сейчас ищет 391 программист ...

Тест-задание от TiBiDaBo

Тема в разделе "PHP и базы данных", создана пользователем Chushkin, 6 авг 2015.

  1. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    Там есть задание viewtopic.php?f=3&t=54192#p432911.
    Понятно, что хрень полная, но...
    Насколько я понял условия (ТС шифруется - не уточнишь, чего он хотел), чтобы рассчитать рейтинг, там будет пересечение двух таблиц. А это очень много и очень плохо.
    Может я что-то не знаю и есть другие алгоритмы?
    Т.е. можно ли избежать квадратичной зависимости от числа записей, чтобы рассчитать рейтинг и получить 50 записей с максимальным рейтингом?
    п.с. ничего на ум не приходит с ходу... :(
     
  2. runcore

    runcore Старожил

    С нами с:
    12 окт 2012
    Сообщения:
    3.625
    Симпатии:
    158
    соединяем львов с львицами. для каждой потенциальной пары вычисляем абсолютную разницу по шерсти и цвету. складываем их. сортируем по этому значению. как сделать именно одни запросом. пока не думал.

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

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    Да это элементарно. Просто будет квадратичная зависимость от числа записей в таблице. На обработку каждых ~4 тыс.записей в таблице будет зарачено ~1 сек. (~4М считанных строк из таблицы, движком)
    В моём понимании 4К записей это не есть большая таблица. Вот поэтому и заинтересовало - может есть алгоритм, который позволяет просчитать быстро именно для большой таблицы (порядка несколько М записей, ещё лучше - десятков М).

    В условии не сказано, что пара лев+львица должна быть уникальна. Поэтому на каждого льва придётся сканировать всех львиц.
     
  4. runcore

    runcore Старожил

    С нами с:
    12 окт 2012
    Сообщения:
    3.625
    Симпатии:
    158
    естественно всех.
    мало того. большая вероятность того что для одного льва будет найдено множество оптимальных львиц, с одинаковыми весовыми коэффициентами. а выбрать придется только одну.
    причем непонятно, исключать её уже для других львов или нет.
     
  5. Maputo

    Maputo Активный пользователь

    С нами с:
    30 июл 2015
    Сообщения:
    1.136
    Симпатии:
    173
    Максимальный рейтинг никому не нужен (в условии этого нет)
    я так полагаю - не более 10к львиц. Если и среди них нет подходящей - льва в топку. И можно ускорить поиск не выбирая пол. Попался первым лев - ищем львицу, попалась следующей львица - ищем льва. (и искать начиная с индекса, на котором находимся +1). "Важное замечание" - говорит только о том, что берем первую попавшуюся.
    От сюда следует, что не надо к каждому искать пару перебирая 10к записей противоположного пола, а найти оптимальный вариант (ограничение) - например 101 запись (кроме случаев, когда wool или color равны 0 - тогда 10к), после которого стоит перейти к поиску другой пары.

    А вот это значит % несовпадения по цвету и шерсти в паре должен быть одинаковым?
    Мне кажется вся задача сводится не к перебору всей таблицы, а к обоснованию - сколько надо львов и львиц найти, чтобы собрать 25 пар, отвечающих ЭТОМУ условию. А первое - это для сортировки.
    Спорный вопрос - их должно быть 50, а не меньше
     
  6. runcore

    runcore Старожил

    С нами с:
    12 окт 2012
    Сообщения:
    3.625
    Симпатии:
    158
    ну здрасте. а если самая оптимальная львица для него 102-я, а мы уже её игнорим.
    имхо это неправильно. если уж искать лучшую пару, то она должна быть лучшей из всех. текст задания это косвенно подтверждает, в замечаниях. где предполагается что реально будет найдено даже больше одной подходящей львицы. так что сканировать нужно всех. иначе не торт
     
  7. Maputo

    Maputo Активный пользователь

    С нами с:
    30 июл 2015
    Сообщения:
    1.136
    Симпатии:
    173
    А если следующая пара оптимальнее этой?
     
  8. runcore

    runcore Старожил

    С нами с:
    12 окт 2012
    Сообщения:
    3.625
    Симпатии:
    158
    потому и нужно сравнить всех со всеми. и выбрать самые оптимальные.
     
  9. Maputo

    Maputo Активный пользователь

    С нами с:
    30 июл 2015
    Сообщения:
    1.136
    Симпатии:
    173
    Этого нет в условии
    а не в максимальной.
    Выбрать нужно подходящие, а не самые подходящие.
     
  10. runcore

    runcore Старожил

    С нами с:
    12 окт 2012
    Сообщения:
    3.625
    Симпатии:
    158
    в задании сказано:
    учитывая это, получается что нужно выбрать 50 САМЫХ подходящих друг другу пар
     
  11. Maputo

    Maputo Активный пользователь

    С нами с:
    30 июл 2015
    Сообщения:
    1.136
    Симпатии:
    173
    вот так надо читать - слева на право
    В таблице с 4к записей - слишком мала вероятность найти среди 25 САМЫХ подходящих пар менее подходящие.
     
  12. runcore

    runcore Старожил

    С нами с:
    12 окт 2012
    Сообщения:
    3.625
    Симпатии:
    158
    какой ты трудный.
    допустим у нас 1000 львов и 1000 львиц.
    мы пишем запрос, который правильно подберет пары подходящие.
    получаем 1000 пар.
    сортируем его от самых подходящих к менее подходящим.
    так? так.
    далее от этого списка берем только 50 начальных.
    какие пары туда попадут? очевидно - самые подходящие друг другу. ибо список то был отсортирован именно так.

    вот и получается. что мы в итоге будет иметь 50 самых подходящих пар.
    где я неправ?
     
  13. Maputo

    Maputo Активный пользователь

    С нами с:
    30 июл 2015
    Сообщения:
    1.136
    Симпатии:
    173
    Я гарантирую, что при таком подходе у Вас 25 первых пар можно будет отсортировать в любом порядке и условие не будет нарушено.

    И мне кажется я немного увёл в сторону от темы обсуждения. Автор вроде спрашивал про другое:
     
  14. runcore

    runcore Старожил

    С нами с:
    12 окт 2012
    Сообщения:
    3.625
    Симпатии:
    158
    каком "таком" подходе?
    условие сортировки описано в самом задании. что ты конкретно предлагаешь, не сортировать?
    а если пар будет 100000 или миллион? или больше?
     
  15. Maputo

    Maputo Активный пользователь

    С нами с:
    30 июл 2015
    Сообщения:
    1.136
    Симпатии:
    173
    Re: Тест-задание от

    Если брать задание, то сначала надо найти 25 пар чтобы был
    а потом отсортировать.
    Это как раз вопрос к Вам об экономичности запроса - находить миллион пар, если нужно 25.
     
  16. runcore

    runcore Старожил

    С нами с:
    12 окт 2012
    Сообщения:
    3.625
    Симпатии:
    158
    во-первых, почему 25 а не 50.
    во-вторых, чтоб найти эти самые (пусть) 25 - нужно просмотреть Всю тысячу, ибо наиболее подходящей для отдельного льва может быть любая из этой тысячи львиц.
     
  17. Maputo

    Maputo Активный пользователь

    С нами с:
    30 июл 2015
    Сообщения:
    1.136
    Симпатии:
    173
    или миллиона. Этот запрос будет выполняться семь с половиной миллионов лет и выдаст ответ "42".
    50 особей. Там написано
    а не
    Суть вобщем не меняет количество.
    Да не нужны никому САМЫЕ. (кроме автора темы, наверное)

    P.S.: Я выхожу из спора до появления автора.
     
  18. runcore

    runcore Старожил

    С нами с:
    12 окт 2012
    Сообщения:
    3.625
    Симпатии:
    158
    неправда. там написано совсем не так.
    "50 подходящих львов и львиц" ------ это и есть 50 пар. слово "подходящих" тут главное. ибо подходить они должны друг-другу. следовательно 50 львов и 50 подходящих к ним львиц. всего 50 пар. все просто. странно что такое простое предложение поставило тебя в тупик.

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

    Добавлено спустя 4 минуты 38 секунд:
    опять мимо. ну прочти ты условие. прежде чем бредить.
    отсортированный список как раз будет содержать вначале САМЫЕ подходящие пары. непонятно почему ты с этим вообще споришь.
     
  19. artoodetoo

    artoodetoo Суперстар
    Команда форума Модератор

    С нами с:
    11 июн 2010
    Сообщения:
    11.068
    Симпатии:
    1.231
    Адрес:
    там-сям
    Давайте рассуждать логически: сортировка по вычисленному "весу" приведет к полному перебору. То есть квадрат от числа особей.

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

    У нас должен быть ключ по (x,y).
    Сначала запрашиваем where x=x and y=y limit 50. Если записей хватит, то на этом и остановимся.
    Если получено n < 50, то следующий запрос: x=x and y<>y limit (50-n)
    ... не более 4 быстрых запросов

    Добавлено спустя 1 минуту 22 секунды:
    Вариация на тему: четыре запроса с limit 50 клеим через union all и оборачиваем в еще один запрос с limit 50
     
  20. Maputo

    Maputo Активный пользователь

    С нами с:
    30 июл 2015
    Сообщения:
    1.136
    Симпатии:
    173
    Отображение строк 0 - 24 (25 всего, Запрос занял 2.2053 сек.)
    При выборе 50 особей(к сожалению не уникальных, но совпадений не было) из 10к совпадающих на 100% - тут и сортировать нечего.
    Если нужен дамп таблицы (заполненной с помощью rand()) - могу скинуть.
    Условие для определения диапазона перебираемых записей при поиске:
    Код (PHP):
    1. WHERE s2.id > s1.id
    2. AND s2.id < ( s1.id + IF( s1.wool = s1.color, 101, 
    3.                                   IF( s1.wool =0 OR s1.color =0, 10201, 
    4.                                   IF( s1.wool > s1.color, 
    5.                                                    10201 / ( LEAST( ( 100 - s1.wool ) , s1.color ) ) , 
    6.                                                    10201 / ( LEAST( ( 100 - s1.color ) , s1.wool ) ) 
    7.                                   ) ) ) 
    8. )
    Сыровато, но результат дает.
    P.S.: Деление на 0 еще одно просмотрел, но это лечится и мне не попалось значений равных 100
     
  21. artoodetoo

    artoodetoo Суперстар
    Команда форума Модератор

    С нами с:
    11 июн 2010
    Сообщения:
    11.068
    Симпатии:
    1.231
    Адрес:
    там-сям
    2 секунды на таблице в 10тыс записей? это ужасно.
     
  22. Maputo

    Maputo Активный пользователь

    С нами с:
    30 июл 2015
    Сообщения:
    1.136
    Симпатии:
    173
    Результат такой, что диапазон поиска, который я предлагаю - подходит для нахождения 25 идеальных пар. Чего уже говорить о частично соответствующих.
    P.S.: и 2 секунды - это не из-за диапазона, а из-за огромного костыля в моем запросе(который мне стыдно выкладывать целиком)
    P.P.S.: Отображение строк 0 - 24 (25 всего, Запрос занял 0.1116 сек.) - Не кеш. С тем же костылем, но составным ключем по полям wool, color, sex
     
  23. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    Maputo, Вы зря спорите с runcore, - он прав. По контексту должны быть именно "самые подходящие".
    Но... если подходить формально (без контекста), то достаточно любых 50 подходящих.
     
  24. runcore

    runcore Старожил

    С нами с:
    12 окт 2012
    Сообщения:
    3.625
    Симпатии:
    158
    тоже была такая мысль. но хотелось решить задачу академически, чтоб именно одним запросом и както хитро раскидать по парам)
     
  25. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    Вообще, в задании меня заинтересовали критерии:
    - "Большая" это сколько?
    - Что есть критерий "максимально экономичный"?
    Задал вопрос ТС-у и получил ответ:
    - 10млн записей
    - запрос занимающий минимальное кол-во времени

    Добавлено спустя 6 минут 29 секунд:
    Не всё так просто. Я думал и пытал такое, -для x=x and y=y при равномерном случайном распределении даёт порядка ~5 на 1000 записей. Т.е. выигрыша даёт мало. Кроме того, при НЕравномерном распределении (кто сказал, что в ральной базе rand()?), таких записей вообще может не быть.
    С другой стороны, такой подход может быть оптимальным и быстрым (тысячные доли сек), если в базе достаточно таких значений.
    И с третьей стороны, runcore прав - есть частное решение, а есть универсальное ("академическое").

    Добавлено спустя 32 минуты 29 секунд:
    Я посчитал немного...
    На таблице в 2000 записей с равномерным распределением универсальный расчёт выполняется ~0.65 сек. и производит ~1 млн. чтений из таблицы (Innodb_rows_read# в SQLyog).
    Т.е. на 10 млн. будет выполняться порядка 188 дней. :)
    Кстати, в результат попадаю всего 2 значения с (x=x and y=y).
    п.с. могу выложить код, если нужно.