关于排序的算法問題。

dalaohu

Sorting number 的计算方法。跟语言无关，想看看大家有什么有效的，好的方法。

比如说UI是这样的。

AAA     |    UP DOWN
BBB     |    UP DOWN
CCC     |    UP DOWN

用户点击 UP或Down的话，那么那一行就会向上或向下移动。
那么相依的DB 里的Sorting order也会改变。 （UI的排序是根据DB 的sorting order来的）

要求是每点击一下，db只update该行的sorting number而不是重新排列所有的number。这样最有效。

比方说，现在用户点了CCC 的 UP。

那么首先我会吧 DB 的Sorting Order设为 float+unique.
我会找到跟CCC 最相邻的比他大的2行 (AAA, BBB), 然后我在这两个之间取个Random值来Update CCC。

这个是可行的，但我觉得效率不高。 我想知道有没有更好的algorithm？

xxmplus

没怎么看懂问题描述啊。。。

sorting order是干嘛用的

如果只是按照序号来排列的话，BBB和CCC的序号对调不就好了吗

jungle

2楼说的很对啊，我也实在不明白在什么情况下需要“重新排列所有的number”。最多只需UPDATE 两条记录的SORTING NUMBER而已。

LZ可能一下子思维陷入了误区

dalaohu

对调也可以，但要2个update。 效率不够高。

dalaohu

原帖由 jungle 于 2011-8-9 10:00 发表
2楼说的很对啊，我也实在不明白在什么情况下需要“重新排列所有的number”。最多只需UPDATE 两条记录的SORTING NUMBER而已。

LZ可能一下子思维陷入了误区

不是，这个是防止某些tx说出每按一下就全部重新排列

xxmplus

恩。。。。做那么多处理，又是比较又是取随机数的，究竟能不能比多update一条数据更高效呢

IMHO，你一下就违反了kiss和don't optimize prematurely两条原则呀

鱼羊鲜

虽然你update一次，但是你查找比2楼复杂啊，总觉得随机数会有出问题的时候

[ 本帖最后由 鱼羊鲜 于 2011-8-9 10:22 编辑 ]

dalaohu

所以想看看大家有什么好算法啊。
我也不满意自己的才来问的。

dalaohu

原帖由 鱼羊鲜 于 2011-8-9 10:19 发表
虽然你update一次，但是你查找比2楼复杂啊，总觉得随机数会有出问题的时候

我的倒是不用query， 所有的数据都在client了。 client计算好，就一个db update就够了。

jungle

我会找到跟CCC 最相邻的比他大的2行 (AAA, BBB), 然后我在这两个之间取个Random值来Update CCC。

我不明白你取这个RANDOM值有啥优势？直接取AAA, BBB的中间点不行么？

不管怎么说，这种算法在操作一定次数以后，都有可能达到FLOAT精度的极限，而导致移动失败。其缺陷是先天的

dalaohu

原帖由 jungle 于 2011-8-9 10:59 发表


我不明白你取这个RANDOM值有啥优势？直接取AAA, BBB的中间点不行么？

不管怎么说，这种算法在操作一定次数以后，都有可能达到FLOAT精度的极限，而导致移动失败。其缺陷是先天的

大哥啊，我是打个比方，说了不满意自己的才来问的。

你说的这个中间点很好啊！

鱼羊鲜

如果是这样，那解决了10楼的问题，就比较理想了，问题是，解决不了,还是对调安全

原帖由 dalaohu 于 2011-8-9 10:52 发表

我的倒是不用query， 所有的数据都在client了。 client计算好，就一个db update就够了。

[ 本帖最后由 鱼羊鲜 于 2011-8-9 11:13 编辑 ]

xxmplus

如果真的这么在乎多更新一次少更新一次的话，能不能考虑在客户端先缓存一下，降低后台数据库的更新频率？

dalaohu

当然，但是UI design不允许，没有save button。
否则绝对client tracking然后最后一次更新。

kr2000

没有save是很不好的design啊
user动一动都要进行query

原帖由 dalaohu 于 2011-8-9 11:29 发表
当然，但是UI design不允许，没有save button。
否则绝对client tracking然后最后一次更新。

鱼羊鲜

javascript onUnload() ?

[ 本帖最后由 鱼羊鲜 于 2011-8-9 11:37 编辑 ]

dalaohu

unload()有个最大的问题就是，他是不可逆的。
万一 有什么excepiton或其他的问题，那用户也看不到了。

典

如果可以用javascript,
能不能让客户把事情作完，然后用submit? 我们这里大都是这样做的。

dalaohu

这个我全部是js，mvvm，ajax做的。全部在client。
这个sorting是在grid里的，没有submit button。

stevenbian

数据库里up和down都记录下来，order 按照序号-up*1.00001+down*1.00001的结果来排序，更新就更新该记录up和down的次数
name order    up            down
AAA      1           0               0
BBB      2           0               0
CCC     3           0               0

典

每次点一下就update db, 是不太好的,要是用户连着点，就悲剧了

dalaohu

那个我会UI block的。

jungle

原帖由 stevenbian 于 2011-8-9 12:07 发表
数据库里up和down都记录下来，order 按照序号-up*1.00001+down*1.00001的结果来排序，更新就更新该记录up和down的次数
name order    up            down
AAA      1           0               0
BBB      2           0               0
CCC     3           0               0

这个算法明显是错误的。

1. 点CCC UP 一下，变成
AAA   1
CCC   1.99999
BBB   2

2. 再点 BBB UP 一下，变成
BBB   0.99999
AAA   1
CCC   1.99999

这就已经错了，BBB连跳2级。

典

我觉得三楼说得对啊，对调两个sorting number而已啊，一个update做不到更新两条记录？

鱼羊鲜

一个update 怎么更新两条记录

xxmplus

那就保持客户端不变，在数据库前面加一层逻辑，由它来负责缓存并trigger数据库更新

beta_caojin

修改Sorting order的含义，让它记录该记录下一条记录的id,这样每次修改的时候，只要修改该记录上一条记录的Sorting order和，该记录自身的Sorting order，其他都不用改。
说白了，就是把数据库中原来的数组结构，改成链表结构。

混不到坑的萝卜

我想了一下，为什么不能这么搞呢？一个Update互换两条记录的SortOrder栏：

CREATE TABLE [dbo].[AAA](
        [SortOrder] [int] NOT NULL,
        [Name] [nvarchar](max) NULL,
        [Description] [nvarchar](max) NULL
)
go

insert into AAA values(1, 'AAA', 'asasa')
insert into AAA values(2, 'BBB', 'bbbbb')
insert into AAA values(3, 'CCC', 'ccccc')
insert into AAA values(4, 'DDD', 'ddddd')
insert into AAA values(5, 'EEE', 'eeeee')


declare @num int = 3
declare @direction int = -1 /* -1 Up, 1 down */

/* Swap BBB & CCC rows' SortOrder */
Update AAA
set SortOrder =
                case
                        when SortOrder = @num then @num + @direction
                        when SortOrder = @num + @direction then @num
                end
where
        SortOrder = @num or SortOrder = @num + @direction

--select * from AAA

混不到坑的萝卜

当然啦，还得再考虑边际值，比如第一条记录和最后一条记录怎么个搞法，但这个应该不难吧？

Limitless

同意二楼的，sort by id就行了，然后调换id。嫌效率低的话写个stored procedure，如果id都是unique的话update3次就行了，用sp效率绝对不低