24.12.2024 08:30
fixin 9 636 Источник

Предлагаю вашему вниманию задачу, которую задавал своим коллегам 1сникам. Но они не справились. Возможно, ваши познания в SQL лучше, чем их.

Есть некоторый иерархический справочник, иерархия элементов. У каждого элемента есть поле «Позиция» (может быть дробным и отрицательным). Элементы в пределах одного родителя должны быть пронумерованы в поле «Позиция» по порядку с единицы с шагом один: 1, 2, … N

Таким образом, например, чтобы поменять порядок элементов с позициями 2 и 3 мы можем элементу с позицией 2 установить позицию 2,5 и вызвать процедуру исправления порядка.

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

Пример: в группе с названием Алкоголь есть элементы с позициями:

  • Пиво 1

  • Водка 2

  • Эль 3

Я меняю:

  • Пиво 2.5

  • Водка 2

  • Эль 3

Система должна пересчитать по всей номенклатуре и сделать:

  • Водка 1

  • Пиво 2

  • Эль 3

Причем найти отклонения и сделать изменения максимально эффективно.

По сути можно упростить вопрос — как запросом найти группы, где порядок 1, 2, … N нарушен?

Вот еще пример:

Есть группа Алкоголь 1, в ней элементы:
Водка 2
Пиво 2.5
Эль 3
Есть группа Мясное 2, в ней элементы:
Сосиски 3
Ветчина 5
Есть группа Напитки 3, в ней элементы:
Квас 1
Сок 2

Нужно по этому пример найти запросом группы, где нарушен порядок 1, 2, N.
Правильный ответ: Алкоголь, Мясное.
Неправильные ответы: Напитки, Корень.

Комментарии (9)


  1. Keeper11
    24.12.2024 08:55
    #27707176

    Можно кодировать позицию дробным числом в интервале (0; 1). Таких чисел континуум, так что вам точно хватит. Заодно пропадает необходимость пересчитывать позиции вообще.


    1. fixin Автор
      24.12.2024 08:55
      #27707374

      нет. это большая нагрузка на систему хранения. Так то можно и бесконечную строку для хранения позиции использовать. При перемещении надо сравнивать еще позицию после, чтобы корректно позицию посчитать. Сложно.

      Есть красивый простой алгоритм для этой задачи, но до него надо дойти.


      1. Keeper11
        24.12.2024 08:55
        #27707438

        это большая нагрузка на систему хранения

        Серьёзно? Вы уже храните дробные позиции, такие, как 2,5 из примера.


        1. fixin Автор
          24.12.2024 08:55
          #27707550

          исключительно для удобства перенумерации. Можно было бы завести реквизит Подпозиция.
          Но вы пытаетесь соскочить с решения задачи, цепляясь за детали.
          Рекомендую Вам все же попытаться решить задачу и получить эстетическое удовольствие от красоты ее решения. Напрягите мозг


  1. Mirzapch
    24.12.2024 08:55
    #27707496

    Чтобы поменять... два и три... нужно второму элементу задать позицию с номером, БОЛЬШИМ чем три.

    Имеем очередную задачку, когда "кто-то что-то имел ввиду", но не смог корректно сформулировать условие. Не удивительно, что коллеги не справились.


    1. fixin Автор
      24.12.2024 08:55
      #27707556

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


  1. fixin Автор
    24.12.2024 08:55
    #27707838

    Так, задачу уже все же решили коллеги на Мисте. Рекомендую попробовать решить самостоятельно.


  1. Ildarovich
    24.12.2024 08:55
    #27708648

    Я бы предложил "сортировку подсчетом": посчитать число элементов того же родителя с меньшим значением "числа упорядочивания" и добавить единицу. Это если я правильно понял задачу - здесь именно это самое сложное.


  1. Akina
    24.12.2024 08:55
    #27710926

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

    Соответственно при внесении изменений в нумерацию детей некоего родителя пересчёту следует подвергать только список детей этого родителя. При проверке - рекурсивно обходить всё дерево иерархии, и для каждого узла, имеющего подчинённые, проверять и/или пересчитывать их нумерацию.

    Эффективный обход узлов, имеющих подчинённые узлы - стандартная задача на рекурсивный CTE.

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

    Так что в упор не понимаю, чего в этой задаче такого особенного...