こんにちは。Wantedlyでエンジニアをしている小林（@kbys_02）です。最近、ドラッグアンドドロップで並び替えをする機能を実装していて、技術的に面白いトピックだと思ったので記事にしました。

前提

「Pulse」というモチベーション管理ツールにある1on1機能の開発を行なっています。

1on1で話をするトピックの優先度を変更できるようにするという施策を実現するため、ドラッグアンドドロップによる並び替え機能を実装しました。

1on1機能には、1on1に参加する2人が編集した内容がお互い同期更新されるという仕様があります。並び替え時にも同じように、参加者2人が同時に並び替えを行った時にロジックが壊れないようにする必要がありました。

浮動小数を利用した並び替えアルゴリズム

このような、リストにあるアイテムの並び替えを実装しようとした時に最初に思い浮かぶのは、連番による方法です。まず、上から順に1,2,3,4,5 ...と番号を振ります。順序を更新する場合は、移動対象から下にあるアイテムの番号を+1し、変更するアイテムの番号を対象のアイテムの番号に変更します。最後に番号を昇順でソートし直します。これで並び替えを実現できそうです。

一方で、上記の図のように1番下のアイテムを上から2番目に移動することを考えると、1番上以外の全てのアイテムの番号を変更しなければいけません。複数アイテムを更新する必要があるため、アイテムの数が多くなった場合に、この方法では効率が悪そうです。APIの設計においても、あるアイテムの順序を更新するために、移動に絡む他のアイテムも更新しなければいけないというのはあまり筋がよくありません。

並び替えを更新対象だけの変更だけに抑える方法として、浮動小数を利用したアルゴリズムがあります。と言っても、変えるのは番号の更新部分だけで、順序を更新する場合に、移動対象の一つ上と一つ下の番号の中間値にアイテムの番号を更新します。

変更後の値が必ず対象のアイテムの間に決定するので、並び替えが実現できてそうです。更新箇所も、移動するアイテムだけになり、筋が良さそうです。

この浮動小数を使う方法は以下の記事で紹介されています。

追記: このような浮動小数を使った順序変更のアルゴリズムを「Fractional Indexing」と呼ぶようです。

実装

上記の方法を用いて、以下のような感じで並び替えを実装できます。 getNextOrderValue で次のアイテムの値を計算しています。一番先頭または最後尾に移動させるコーナーケースが入っているので少しロジックが複雑になっていますが、基本的には上記にある中間値を求めているだけです。

import React from "react";
import sortBy from "lodash/sortBy";
import { DragDropContext } from "react-beautiful-dnd";

interface Item {
  id: number;
  order: number;
  title: string;
}

// アイテムの間隔。適当な値でおいている。
const INITIAL_ORDER_VALUE = 65535;

const getNextOrderValue = (sourceIndex: number, destinationIndex: number, items: Item[]): number => {
  const otherItems = items.filter((_, index) => index !== sourceIndex);
  const nextUp = otherItems[destinationIndex - 1];
  const nextDown = otherItems[destinationIndex];
  if (!nextDown) return Math.max(...items.map((item) => item.order)) + INITIAL_ORDER_VALUE;
  return ((nextUp?.order ?? 0) + nextDown.order) / 2;
};

type Props = {
  items: Item[];
  onUpdateOrder: (id: number, order: number) => void;
};

const List: React.FC<Props> = (props) => {
  const orderedItems = sortBy(props.items, "order")

  const onDragEnd = (result: DropResult) => {
    if(!result.destination) return;
    const source = orderedItems[result.source.index];
    const nextOrder = getNextOrderValue(result.source.index, result.destination.index, orderedItems);
    props.onUpdateOrder(source.id, nextOrder);
  };

  return (
    <DragDropContext onDragEnd={onDragEnd}>
      // 省略
    </DragDropContext>
  );
};

さて、これであとはアイテムを更新する処理である onUpdateOrder の中身さえ実装すれば、並び替えが実現できそうです。

...本当に？

バックエンドで値を検証する

実際には考慮すべき懸念があります。

• 繰り返しアイテムを移動し続けた場合
• 複数人が同時にリストにあるアイテムを変更できる場合

繰り返しアイテムを移動し続けた場合

浮動小数の表現幅には限界があります。交互に同じアイテムを交換し続けると、どこかで計算機が表現できる幅を超えて、数値が等しいと判定されてしまいます。

上記の例は1番目と2番目のアイテムを交互に移動し続けた場合です。交換し続けるにつれて、値が小さくなり、0に近づいていることがわかります。これを続けていくと、いずれAとBが同じ値としてみなされてしまいます。

浮動小数を使うアルゴリズムでは、同じ数値がリストにないことが前提としてあるため、上記で説明した並び替えのロジックが破綻してしまいます。そのため、アイテム同士の差が小さくなりすぎていないかをチェックする必要があります。

複数人が同時にリストにあるアイテムを変更できる場合

複数人が同時に同じリストにあるアイテムを変更できるようなユースケースがある場合にも、複数のアイテムの値が同じ値になってしまう可能性があります。まさに今回実装しようとしているケースがそれに当たります。

上記の例のようにEを2番目に移動させていて、その一方で別のユーザーがDを同じく2番目に移動させたとします。この時、EとDは同じ値になってしまいます。この状態になると、例えば次にCをDとEの間に持っていくと、Cも同じ値になってしまいます。

先ほどの場合と同様に、並び替えは同じ値がリストにないことが前提としてあるため、並び替えのロジックが壊れてしまいます。そのため、リスト内で値の重複を何らかの形で防ぐ必要があります。

実装

2つのケースの問題は、どちらもリスト内のアイテムに同じ値が含まれてしまうことです。そのため、リストの中のアイテムの値が重複していないか、バックエンド側でフロントエンドから渡ってきた値の検証を行うことにしました。検証を行う Orderable を以下のように実装しました。

# This requires an order column to the table.
module Orderable
  extend ActiveSupport::Concern

  EPSILON = 1e-8
  # フロントエンドで定義している値と同じにする
  INITIAL_ORDER_VALUE = 65535.0

  included do
    before_update :set_more_appropriate_order

    # 設定値を検証しより最適な値に変更する。同時編集などで同じ値を設定してしまう場合があるため。
    def set_more_appropriate_order
      return unless order_changed?
      self.order = get_more_appropriate_order_value(self.order)
    end

    # @param [BigDicimal | Float] next_order
    # @return [BigDicimal | Float]
    def get_more_appropriate_order_value(next_order)
      smaller = -> (item) { item.order < self.order }

      items = all_items()
      items_excepted_own = items - [self]

      larger_or_equal_items = items_excepted_own.reject(&smaller)
      # 対象が一番大きいの場合はそのまま返す
      return next_order if larger_or_equal_items.blank?

      next_up = larger_or_equal_items.map(&:order).min
      # 対象が一番小さい場合は0と一つ下の中間値を返す.
      next_down = items_excepted_own.select(&smaller).map(&:order).max || 0.0

      # 差がEPSILONを超えてしまった場合はエラーを通知し大きな値にリセットする
      if equal_value?(next_up, next_down)
        ErrorReporter.report("equal value in Orderable")
        return append_to_last(items)
      end
      return (next_up + next_down) / 2.0
    end

    # 値を設定するためにリストにある要素を取得する
    # @return [Array]
    def all_items
      raise NotImplementedError.new("You should implement all_items")
    end

    private

    # @param [BigDicimal | Float] v0
    # @param [BigDicimal | Float] v1
    # @return [Boolean]
    def equal_value?(v0, v1)
      (v0 - v1).abs <= EPSILON
    end

    # @param [Array] items
    # @return [BigDicimal | Float]
    def append_to_last(items = [])
      max_order = items.compact.map(&:order).max || 0.0
      max_order + INITIAL_ORDER_VALUE
    end
  end
end

get_more_appropriate_order_value が、フロントエンドから渡ってくるアイテムの値を検証するメソッドです。この中で以下のことをしています。

• DBに入っている最新の値と比較して値を返す。これで同じ値がリストに重複することを避ける。
• アイテム同士の差が小さくなりすぎている場合は、エラーを通知する。
• • 注: 今回は、ほとんどのケースで問題が起こらなさそうだと判断し、問題に気づくために通知を送るようにしています。もっと丁寧にやるならエラーを返し、リストを再更新する指示をフロントエンドに出すと良さそうです。

上記の concern を include することで、並び替えの検証を行うことができます。

class ListItem < ApplicationRecord
  include Orderable

  private

  # Override OrderConcern#all_items
  def all_items
    self.class.where(list_id: self.list_id)
  end
end

最終成果

以下の並び替え機能を実装しました。

まとめ

並び替えの値として浮動小数を使うことで対象のアイテムを更新するだけで並び替え機能を実現できます。そのアルゴリズムの解説とフロントエンドでの実装例を示しました。

また、何回も同じアイテムを繰り返し移動できてしまう場合や複数人が同時に編集できる場合では、リストにあるアイテムの値が等しくなってしまい、並び替えができなくなる可能性があります。そのため、値が問題ないかを検証し正しい値に直す必要があります。この記事では、バックエンド側でフロントエンドから受け取った値を検証し、修正する実装例を示しました。

この記事が並び替えを実装する際の参考になれば幸いです。