На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! информация о разделе
user posted imageДанный раздел предназначается для обсуждения вопросов использования баз данных, за исключением составления запросов на SQL. Для этого выделен специальный раздел. Убедительная просьба - соблюдать "Правила форума" и не пренебрегать "Правильным оформлением своих тем". Прежде, чем создавать тему, имеет смысл заглянуть в раздел "Базы данных: FAQ", возможно там уже есть ответ.

Модераторы: Chow, Bas, MIF
  
> Сортировка по совпадающим ответам , [MySQL]
    Приветствую, есть задачка и не могу решить как сделать с максимальной скоростью. Есть в распоряжении mysql и elasticsearch. Задача следующая: юзеры отвечают на вопросы, ответы: да, нет пропуск. Надо иметь возможность сортировать юзеров по совпадению с твоими отетами. Формула для расчета совпадений:
    ExpandedWrap disabled
      matches / matchedQuestions * 100.

    matches - количество совпавших ответов.
    matchedQuestions - количество совпавших вопросов.

    Юзеров много - миллионы.

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

      Цитата domencom @
      Надо иметь возможность сортировать юзеров по совпадению с твоими отетами.

      1) Что должна означать эта фраза? возможных толкований - хренова гора, и все разные.
      2) Допустим, отсортировали - что дальше? Да, их миллионы, так что выводить на экран не получится.
        Цитата Akina @
        1) Что должна означать эта фраза? возможных толкований - хренова гора, и все разные.

        Я формулу привел.
        Цитата

        2) Допустим, отсортировали - что дальше? Да, их миллионы, так что выводить на экран не получится.

        Если будет возможность отсортировать, то выведу. Тут вопрос в подходе - как хранить данные, чтобы сортировка была возможна и была максимально быстрой.
          Да кому нужна эта формула? что есть "твои ответы"? имеется в виду, что юзер, ответив на опросник, должен видеть, сколько юзеров ответило так же хреново, а сколько - ещё хреновше? Или, может, речь об эталонных ответах? или о самых популярных (даже если не все они правильные)? а, может, что-то ещё?

          Цитата domencom @
          Если будет возможность отсортировать, то выведу.

          Отсортировали. Получили набор из миллиона записей. Будем его весь качать в клиента? или достаточно тупо посчитать количества (или сразу соотношения) в штуках?

          PS. Давай посерьёзнее. Ты знаешь о своём проекте всё. Остальные - только то, что скажешь ты.
            Цитата
            Да кому нужна эта формула? что есть "твои ответы"? имеется в виду, что юзер, ответив на опросник, должен видеть, сколько юзеров ответило так же хреново, а сколько - ещё хреновше? Или, может, речь об эталонных ответах? или о самых популярных (даже если не все они правильные)? а, может, что-то ещё?


            Надо сортировать юзеров согласно формуле. Чем выше значение результата форулы, тем выше юзер. Проблема в нахождении алгоритма хранения вот всего массива данных по совпадениям и дальнейшей сортировке юзеров по нему.

            Цитата Akina @
            Отсортировали. Получили набор из миллиона записей. Будем его весь качать в клиента?

            Цитата domencom @
            Есть в распоряжении mysql и elasticsearch.

            Естественно это надо делать средствами вот этих двух технологий (или одной - не важно). Это поиск на проекте, нужна сортировке по описанному выше. Миллионы не надо возвращать.
              Цитата domencom @
              Проблема в нахождении алгоритма хранения вот всего массива данных по совпадениям и дальнейшей сортировке юзеров по нему.

              Нет её, этой проблемы. Для каждого опросника составляется маска ответов. Для каждого участника в его результатах считается и хранится формализация по этой маске в индексированном поле. Для референсного юзера считается аналогичная формализация, после чего во временной таблице формируется соответствие всех возможных масок формализации и их ранга при сортировке (тоже индекс, причём составной). Все эти этапы - одноразовые. А теперь итоговый запрос, который связывает формализованный по маске ответ с таблицей рангов, которая по сути и является поставщиком поля сортировки. Связь по индексированным бинарным полям и сортировка по индексированному полю...

              Ну и наконец сформулируй-таки, что такое "твои ответы" и откуда они берутся.
                Есть вопросы на проекте. Юзер отвечает на них. По сути ответы это да и нет. Каким образом реализовать то что ты описал - не понятно. Что есть "маска ответов", "формализация по маске"?
                  Я правильно понимаю, что для ЭТОГО расчёта в принципе пофиг, насколько ответы пользователя верны (а то и - адекватны)? И это не тест, то есть такое понятие как правильный или неправильный ответ - не существует?

                  А также - я правильно понимаю, что вопросов дохрена, и каждый юзер отвечает лишь на малую часть этих вопросов?
                    Да, понятия правильности нет. Вопросов дохрена - 500+. Каждый юзер отвечает на рандомное кол-во. Есть средства мотивации чтоб он отвечал как можно больше, но это не важно.
                      Угу.. ок. Тогда сдаётся мне, что тебе лучше посмотреть в сторону OLAP. Потому как фильтровать длинные бинарные данные и потом считать по ним интерсект, конечно, можно, но делать это эффективно, как мне кажется, в рамках MySQL совершенно нереально. И ластик тут скорее всего ничем не поможет.
                        Цитата Akina @
                        Тогда сдаётся мне, что тебе лучше посмотреть в сторону OLAP

                        Почитаю, спс.

                        Эластик имеет такое понятие как скоры. Скоры можно формировать исходя из совпадений ответов и это реализовано уже, но пока нет возможности применять формулу для формирования скоров, да ещё и зависящую от промежуточных результатов. Ну или я не знаю о такой возможности эластика...
                          Да там собсно делов-то... результат теста каждого юзера кодируется дохрена-битным тернарным потоком (1-0-null, да-нет-не отвечал). А проверка на совпадение - это побитовый XOR и подсчёт соотношения количества нулевых битов к общему количеству not null битов. Основная проблема упирается в то, что таблица ответов будет сильно разреженной, а (почти) все SQL-серверы, когда без OLAP-надстроек, этого ой как не любят...
                            Цитата domencom @
                            Формула для расчета совпадений:

                            Формула не будет работать для юзеров, у которых нет совавших вопросов.
                              JoeUser, это пример был.
                                Цитата domencom @
                                JoeUser, это пример был.

                                Лучше просить совет на правильных данных - большая вероятность получить правильный ответ.
                                  Цитата Akina @
                                  (1-0-null, да-нет-не отвечал). А проверка на совпадение - это побитовый XOR и подсчёт соотношения количества нулевых битов к общему количеству not null битов. Основная проблема упирается в то, что таблица ответов будет сильно разреженной

                                  Таблица должна быть юзверь + правильно - не правильно (да-нет) ответил, null вообще не нужен.
                                  Цитата domencom @
                                  matches - количество совпавших ответов.
                                  matchedQuestions - количество совпавших вопросов.

                                  Первое понятно, но что такое "количество совпавших вопросов" так и не понял :-? .
                                    Цитата Bas @
                                    "количество совпавших вопросов"

                                    Это вопросы на которые отвечали совместно. Пример: ответил на вопросы: 1, 2, 5. и 1, 5, 8. Кол-во совпавших вопросов = 2 (1 и 5).

                                    Добавлено
                                    Ещё проблема в том что данные в таблицах придется постоянно перестраивать, ибо юзеры могут отвечать на вопросы дальше, либо повторно. Мне таки все ещё не понятно как можно обработать такие объемы данных за вменяемое время ...

                                    Добавлено
                                    Цитата JoeUser @
                                    Лучше просить совет на правильных данных - большая вероятность получить правильный ответ.

                                    Ну и как тебе поможет полная формула, которая вычисляется с учетом различных погрешностей и т.д.? Задача стоит не в создании формулы...
                                      Цитата domencom @
                                      Пример: ответил на вопросы: 1, 2, 5. и 1, 5, 8. Кол-во совпавших вопросов = 2 (1 и 5).

                                      matches тогда что?
                                      Формула тогда будет
                                      1. Первый ответил на все правильно то 3/2*100
                                      2. Второй ответил правильно только на один то 1/2*100.
                                      :scratch:
                                      Сообщение отредактировано: Bas -
                                        Bas Нет понятия правильности. matches это: user1 [1 => 1, 2 => 0, 3=> 1]; user2: [1=>0, 2 => 0, 5 => 0]. matches = 1 (2 => 0). Ключ - номер вопроса, значение - ответ да/нет.
                                          Цитата domencom @
                                          Задача стоит не в создании формулы...

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

                                          Добавлено
                                          И еще ... уточни. Вопросы как-то группируются в "опросники", или это единый список вопросов?
                                            JoeUser, в данном случае - не известно что рассказывать для решения. Поэтому вот так вот - отвечаю на вопросы по-ходу.
                                            Цитата JoeUser @
                                            И еще ... уточни. Вопросы как-то группируются в "опросники", или это единый список вопросов?

                                            Единый список.
                                              Вобщем какая-то мысль витает, но не могу собрать все в "систему".
                                              Поэтому, попробую написать типа "утверждениями" (которые не обязаны быть истинными), а вы уж попробуйте осознать, может вас "осенит" :lol:

                                              Сортировка

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

                                              Расстояния где?

                                              Например, здесь:

                                              user posted image

                                              Формула z=x/(100*y) формирует ни что иное, как трехмерное скалярное поле "расстояний" ответов. Все "расстояния" ответов, в том числе и владельца - лежат на этом поле. По условию задачи, данный график можно интерпретировать и по другому - как криволинейные координаты, относительно которых считаются "расстояния" ответов прочих юзеров. Но в тензорное исчисление залезать не будем, там все бурьяном поросло, а пойдем в обратную сторону - в упрощение.

                                              Упрощаем

                                              Как видно на графике, есть еще поверхность - 1/100 (голубого цвета). Чем она хороша? Она практически инвариантна [1/(колво_совпавших_вопросов*100)] ... 1/100, пусть грубо-грубо [0..0,01]. Почему бы эту величину не взять за базис, и индексы считать не от ответов "хозяина"?

                                              Что получим?
                                              • Единожды пересчитываем сортировочные индексы относительно базиса всех юзеров и "хозяина" в том числе
                                              • В качестве сортировочного поля - используем вычислимое, как ABS(значение_ключа_хозяина - значение_ключа_юзера)
                                              • Ответили на очередной вопрос сами - пересчитали свой "ключ", по затратам - копейки
                                              • Ответил юзер на очередной вопрос сам - пересчитали ему "ключ", по затратам - копейки
                                              • Полный пересчет нужен будет только в том случае, если меняется "базис" - количество вопросов (а если принебреч и оставить 1/100?)

                                              Немножко меда в ваш дёготь

                                              Предлагаемый вариант организации сортировки конечно же имеет ряд недостатков: и вычислимое поле, и неточная формула. С вычислимым полем в моем варианте наверное не избавится, даже если организовать синтетический VIEW с индексом, но в MySQL его нет, нужно делать самому. А вот с формулой можно поиграться ... А почему бы не взять не саму формулу, а ее производную, вернее сумму частных производных. Если я не забыл курс арифметики, то для f(z) = x/(100y) => f'(z) = 1/100y - x/100y2. А это уже не просто разница двух значений.

                                              Вообщем, вот как-то так :-?
                                                Цитата Bas @
                                                Таблица должна быть юзверь + правильно - не правильно (да-нет) ответил, null вообще не нужен.

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


                                                Рейтинг@Mail.ru
                                                [ Script execution time: 0,0600 ]   [ 16 queries used ]   [ Generated: 19.03.24, 03:29 GMT ]