商品リストの並べ替え方法をお教えいただけませんでしょうか。

Question

PHP初学者です。

PHPとMySQLで商品管理の仕組みを構築しようとしています。
商品登録とリスト表示は出来たのですが、
並べ替えをどう実装するのかわからず、
質問いたします。

並べ替え方法はネットで調べたところ
「前の順番のIDと次の順番のIDを持ち、それらを入れ替える」
という方法があると知りました。

###【並べ替えの考え方】
以下の様なテーブルを用意します
※例のため単純化しています。

[テーブル名:menutable]
[カラム名:id,title,prev,next]
[並び順:1,2,3,4,5,6,7,8,9,10]
1,apple,0,2
2,orange,1,3
3,grape,2,4
4,strawberry,3,5
5,banana,4,6
6,cherry,5,7
7,peach,6,8
8,pine,7,9
9,melon,8,10
10,raspberry,9,11

8のpineを2番目に移動させるために行う書き換えは、
以下のとおりです。

[並び順:1,8,2,3,4,5,6,7,9,10]
1,apple,0,8
2,orange,8,3
3,grape,2,4
4,strawberry,3,5
5,banana,4,6
6,cherry,5,7
7,peach,6,9
8,pine,1,3
9,melon,7,10
10,raspberry,9,11

この方法だと、自分のprevとnext、
割りこむ先の両隣(1,2)と、元の両隣(7,9)のprevとnextのみの
変更で済むので、レコード数が増えた時に非常に効率的というものです。
以下のようなフォームでデータを投げることを想定しています。
※これも単純化しています

<form action="./" method="post">
    <p>移動元：<input type="text" name="from" value="8" /></p>
    <p>移動先：<input type="text" name="to" value="2" /></p>
    <input type="submit" value="メニュー更新">
</form>

###【質問１】
並べ替えの処理は以下のようにしようとしています。
この考え方はあっていますでしょうか。

1. fromをもとにid=8を持つレコードを取得[idが8のレコード]
2. toをもとにid=2を持つレコードを取得[idが2のレコード]
3. fromをもとにprev=8を持つレコードを取得[idが7のレコード]
4. fromをもとにnext=8を持つレコードを取得[idが9のレコード]
5. toをもとにprev=2を持つレコードを取得[idが1のレコード]
6. id=8のprevとnextをid=2のprevとnextに書き換え
7. id=7のnextとid=9のprevをtoの2に書き換え
8. id=1のnextとid=2のprevをfromの8に書き換え

###【質問２】
並べ方の考え方は以下のように思うのですが、
組み方がわからず、お教えいただけませんでしょうか。
0. prevに0を持っているレコードを取得[idが1のレコード]
0. 取得したレコードのnextをもとに次のレコードを取得[idが8のレコード]
0. 以後2を繰り返し

###【質問３】
この方法は「書き換えが途中で止まって順番がおかしくなる」
という問題への対策が必要、ともありました。
これは「変更前に変更予定の値を別途保存しておいて、
変更後の値に重複があったときは、エラーとして
変更前の値に戻す」というものを想像しているのですが、
これも実現の方法がわかりません。。。

上記３点、お手数をおかけいたしますが
ご教授いただけませんでしょうか。

お手数をおかけいたしますが、
よろしくお願いいたします。

Answer 1

見てて思いついた問題点に関して
・この方法は全てのデータが数珠つながりになっていることを保障(強制)することが困難なように思います。
・ソートのコストが高いように思います。画期的なSQLがあればいいのですが…

質問1に関して
移動先｢2｣と移動元｢8｣の関係は「painを2番目に割り込み」ではなく、「painをorangeの位置に割り込み」なのでしょうか？
もし前者の場合、「fromの8」はidかも知れませんが「toの2」は順番になります。
その場合はこんな感じかも。

1. id=8の元の順番の一つ前(nextが8)のidを割り出し、nextをid=8の次順(prevが8)のidに書き換え
2. id=8の元の順番の一つ後(prevが8)のidを割り出し、prevをid=8の前順(nextが8)のidに書き換え
3. 元2番目のidを割り出しそのprevを8に書き換え
4. 元2番目の一つ前(つまり1番)のidを割り出しそのnextを8に書き換え

5-1. id=8のnextを元2番目のidに書き換え
5-2. id=8のprevを元2番目の一つ前(つまり1番)のidに書き換え

質問2に関して
あるIDの順番を割り出すのはいいですが、一覧を表示等の場合件数が増えるとコストが増大しそうです。
紹介元にソートして一覧を取得するSQLの紹介はなかったのでしょうか？

質問3に関して
トランザクションを用いれば問題無いと思います。
ただ自身の管理するコード以外からテーブルの更新があった場合、順番の連続性が崩壊するかも知れません。冒頭に書いたように連続性をSQLの制約で強制するのは難しいと思います。

思いつきなので欠陥があるかも知れませんが、順位(sort)と更新日(date)で管理するのは駄目でしょうか？
例えばpainを2番に移動したければ、その時点で2番のsortの値を調べて、自身のsortにその値を入れdateにtimestampを記録します。更新するのはこのpainの一行だけです。
ソートは「Order by sort,date desc」
レコードの削除は単に削除すればいいですし、追加も追加したい順番のsortと追加日時を記録するだけです。
最後尾に追加する場合は、sortのmax+1を入れます。
欠点は、2番に移動した経歴のレコードが多い場合、sort欄の記録が2ばかりになることですが、簡単にしか検討していませんがそれでのトラブルは思いつきませんでした。

Comments

[hirohiro]

最後に書いた方法ですが、やはり思いつきは駄目ですね。
この方法だと管理者が1人ならいいですが、不特定多数が同時に更新してsortとtimestampが末尾まで一致した場合問題が出そうです。
timestampじゃなくて、シーケンス生成の連番を利用(順番移動時も一旦そのレコードを消して移動先の順番に新規登録し連番を受け取る)すれば問題は解消できるかも知れませんが…

[kaz99k]

ご回答ありがとうございます

質問１についての回答：
> もし前者の場合、「fromの8」はidかも知れませんが「toの2」は順番になります。
最初、違いがわかりませんでしたがよく考えて仰って頂いている意味がわかりました。
すみません、仰るとおり前者の「２番目の位置に移動」がやりたいことです。
なので私の書いた「toをもとにid=2の…」という部分が間違いということになります。
そうなると、余計に順番の取得が困難になりますね…並べ替えをしようとしているのに先に「2番目の位置にいるidを…」って、どうやって見つけたらいいかわかりません(;_;

質問２についての回答：
> 紹介元にソートして一覧を取得するSQLの紹介はなかったのでしょうか？
はい、nextとprevの理屈と質問３の危惧とだけが書かれていて、
具体的なコードは無かったです。
なので手書きやらコインやらをつかって理屈を整理してどうやらこの理屈で
並べ替えは出来そうだ、ということはわかったのですが、コードがわからないという状態です。

質問３についての回答：
> 冒頭に書いたように連続性をSQLの制約で強制するのは難しいと思います。
おかげ様でトランザクションについて知ることが出来ました（恥ずかしながらトランザクションも知らずにプログラムに挑んでいたことがわかりました//）
連続性を保証するすることはできないという点はなんとなくこの考え方に感じた、
不安の原因の一つかもしれません。

ご提案いただいた並べ替え方法について：
これはコードもシンプルに出来そうで良いですね、
更新の際に書き換えるレコードも一つで済みます。
タイミングが全く同じ人が二人いたとしても、
たとえば「ユーザIDの番号が若い方を優先する」といった
ルールを設ければ回避できる気もします。

ただ、これは私が無学なだけで大変恐縮なのですが、
「並べ替え処理の定石」というものを知りたいとも考えています
（あるかどうかも知らないのでさらに恐縮です）。
根っこの部分を押さえておけばあらゆる場面で応用が効くと思ったからです。
もしもご存知でしたら、お教えいただけますと幸いです。

ご回答に質問を重ねて誠に恐縮です。
お手数をおかけいたしますが、何卒よろしくお願いいたします。

[hirohiro]

>>連続性を保証するすることはできない
ご存知かも知れませんが、SQLではテーブルやその列に制約をかける事ができます。
例えばnullの状態での登録は駄目だとか、ID列は別のtableBのID列に同じ値が必ず存在することだとか、その列の全データはユニークであるべきだなどです。
私が最後に書いた方法なら、「sort+dateは必ずユニーク(固有値)であること」のように制約できます。そのようにしておくと、他人が機能追加してルールを守らないデータを入れようとした際にテーブル側がそのルールを守らないSQLを拒否してエラーを出します。
これによってデータの整合をDB側で保障できます。
でも、prev,nextで全データが数珠繋ぎになっていることを保障する制約を書くのは難しいのではないかと思います。

>>「並べ替え処理の定石」というものを知りたい
私も知らないのでどなたかの回答でスタンダードなものが出ると嬉しいです。
個人的には巨大なリストの並べ替え要求は受けた事がないので
単純にorder_weightのような列を儲けて4桁位の数値を突っ込む設計しかやった事がないです。1000と2000の間に割り込む場合は1500をセットします。値差が2以下になってしまった場合に備えて全レコードを1000区切りに再設定するリセットUIを付けておきます。あまりに頻繁に順位変更が行われると崩壊するお粗末な設計ですがメニューやタグなんかを1人程度の管理者が偶に並べ替えるだけならこれで十分…

[kaz99k]

ありがとうございます。

> ID列は別のtableBのID列に同じ値が必ず存在することだとか
すみません、こちら知りませんでした。

実は実際に組んでいるプログラムでは、カテゴリテーブルを別途持っていて、
メニューテーブルのカテゴリ列に、カテゴリテーブルのidを入れるようにしています。
強制力は持たせていなかったのですが、こういう時に使うのですね。
ありがとうございました。

Answer 2

PHPはやったことがありませんが、一般的なアルゴリズムなのでわかる範囲で回答します。

質問１：
どうしたいのか複雑なので、やりたいことを階層化したほうがいいです。

1．移動元(id=8)をリストから外す。
_1-1．移動元のprev(id=7)から移動元(id=8)を外す
__1-1-1. nextに移動元(id=8)のnextを代入
_1-2．移動元のnext(id=9)から移動元(id=8)を外す
__1-2-1. prevに移動元(id=8)のprevを代入
2．移動元(id=8)を移動先(id=2)の手前に挿入。
_2-1．移動元(id=8)を編集
__2-1-1. prevに移動先(id=2)のprevを代入
__2-1-2. nextに移動先(id=2)を代入
_2-2．移動先(id=2)の編集
__2-2-1. prevに移動元(id=8)を代入
_2-3．移動先のprev(id=1)の編集
__2-3-1. nextに移動元(id=8)を代入

リストの件数にもよりますが、表示順０番目のダミーデータを用意しておくと１の作業が簡単でいいです。（特に質問１のアルゴリズムでは、1番目に移動の場合例外処理が足りていません。）

質問２：
大体あっています。

prevは利用しないのであれば、編集する必要も定義する必要もありません。

質問３：
確かに途中で止まると移動元が消えたり順番が循環したりということがあり得ます。

ただこのロジックは論理的な誤り（バグ）以外には途中で止まることはありえないので、並び替えている途中でほかの処理をさしはさまないようにすればいいのではないかと思います。

私ならロールバックに関してはもう少し複雑なロジックの時にします。

Comments

[kaz99k]

ご回答ありがとうございます

質問１についてのご回答：
> 表示順０番目のダミーデータを用意しておくと
確かに、1番目に移動する時に0番目を用意しておかないと上手く回らなそうですね、ありがとうございます。

質問２についてのご回答：
> prevは利用しないのであれば、編集する必要も定義する必要もありません。
言われてみれば、「並び順をどこから始めるか」さえわかればいいわけですね。
では、順番が１番のレコードに印さえついていれば良い、ということでしょうか。
ただ、nextを拾い続けて順番を整理する繰り返し処理の書き方がわかっていませんが^^;

質問３についてのご回答：
> 並び替えている途中でほかの処理をさしはさまないようにすればいい
別の回答者様（hirohiroさん）が仰ってくださった「トランザクション」ですね、
恥ずかしながらトランザクションとロールバックの意味をいま初めて知りました。

おかげさまで、一応この考えでゴールへ到達することは出来そう、
ということはわかりました。引き続き方法を模索してみようと思います。

ありがとうございました。

[iwamoto_takaaki]

質問２に関してはid=0が0番目と決まっているなら、そこからnextを手繰っていけば簡単です。

prevがないとどれが先頭のデータかわかりずらいですね。その場合は全件調べてみれば判別できます。データ件数が少ない場合はこの方法でも問題ないです。

質問3のトランザクション管理についての話は、そこそこややこしい話で、順番を持ったリストについての話とは別に学んだがいいかなと思います。

ところで、このprevとnextをもったデータ構造は双方向リンクリストと呼ばれるもので、PHPにも実装があると思いますので（ご自身での実装後に！）調べてみてください。

[kaz99k]

ありがとうございます。

フライングでちょっと調べてみましたら「アルゴリズム」と「データ構造」という単語の淵の深さを少し覗き込んでしまい目眩がしました（笑

双方向リストはPHPでもStandard Php Libraryというもので実装されているそうですが、
理屈を知らずに使いはじめると結局どこかでつまづいてしまいそうなので、
iwamotoさんの仰るとおりまずはライブラリに頼らず自分で考えて
実装してみようと思います。

ご回答いただいて、自分で考える機会を得て、何か良く分からない単語とルールの塊だったプログラミングが、
必要に迫られて構築されてきたものだということをほんの少しですが知ることが出来て、
ちょっと楽しくなってきました。

ありがとうございました！