回答編集履歴
4
説明を差し替え、図を追加
test
CHANGED
|
@@ -1,10 +1,9 @@
|
|
|
1
1
|
yの上位ビット、xの上位ビット、…の順で下位ビットへと交互に比較してソートします。
|
|
2
2
|
座標が近ければデータも近い、とか
|
|
3
3
|
データが近ければ座標も近い、という保証はありませんが、
|
|
4
|
-
座標が近いデータは近くに並びやすくな
|
|
4
|
+
座標が近いデータは近くに並びやすくなります。
|
|
5
|
-
一般的な状況は改善するでしょう。
|
|
6
5
|
|
|
7
|
-
あらかじめ、xとyの値を
|
|
6
|
+
あらかじめ、xとyの値をスケーリングしておく必要があります。
|
|
8
7
|
(または、下のコードでは、ビットマスク mask をy座標・x座標で別々にするなど)
|
|
9
8
|
|
|
10
9
|
C言語の例を示します。(xもyも0〜255の場合)
|
|
@@ -50,42 +49,31 @@
|
|
|
50
49
|
}
|
|
51
50
|
|
|
52
51
|
```
|
|
52
|
+
図にすると、x,y 各1ビットでは
|
|
53
|
+
┌─┬─┐
|
|
54
|
+
│０→１│
|
|
55
|
+
├─／─┤
|
|
56
|
+
│２→３│
|
|
57
|
+
└─┴─┘
|
|
53
|
-
|
|
58
|
+
x,y 各2ビットでは、これを再帰的に適用して
|
|
59
|
+
┌─┬─┬─┬─┐
|
|
60
|
+
│０→①│④→⑤│
|
|
61
|
+
├─／─／─／─┤
|
|
62
|
+
│②→③│⑥→⑦│
|
|
63
|
+
├─┼─┼─┼─┤
|
|
64
|
+
│⑧→⑨│⑫→⑬│
|
|
65
|
+
├─／─／─／─┤
|
|
66
|
+
│⑩→⑪│⑭→⑮│
|
|
67
|
+
└─┴─┴─┴─┘
|
|
54
|
-
|
|
68
|
+
のようになります。
|
|
55
|
-
x y
|
|
56
|
-
2 12
|
|
57
|
-
13 8
|
|
58
|
-
23 2
|
|
59
|
-
18 15
|
|
60
|
-
25 13
|
|
61
|
-
5 20
|
|
62
|
-
14 21
|
|
63
|
-
8 31
|
|
64
|
-
17 29
|
|
65
|
-
26 27
|
|
66
|
-
32 6
|
|
67
|
-
36 12
|
|
68
|
-
59 0
|
|
69
|
-
62 7
|
|
70
|
-
49 15
|
|
71
|
-
57 12
|
|
72
|
-
33 19
|
|
73
|
-
42 16
|
|
74
|
-
39 24
|
|
75
|
-
45 31
|
|
76
|
-
48 23
|
|
77
|
-
54 31
|
|
78
|
-
3 46
|
|
79
|
-
11 40
|
|
80
|
-
21 36
|
|
81
|
-
30 36
|
|
82
|
-
24 44
|
|
83
|
-
37 32
|
|
84
|
-
36 40
|
|
85
|
-
40 47
|
|
86
|
-
48 39
|
|
87
|
-
54 43
|
|
88
|
-
62 47
|
|
89
|
-
49 51
|
|
90
|
-
52 58
|
|
91
69
|
|
|
70
|
+
座標の近傍をすべて探し出すには、
|
|
71
|
+
やはりcoco_bauerさんのようにインデックスを2本用意する必要があるかもしれません。
|
|
72
|
+
|
|
73
|
+
あまり厳密でない用途では、上記コードのxy混成ソートが役に立つかもしれません。
|
|
74
|
+
・地図アプリで近くの店を提案する
|
|
75
|
+
・戦略ゲームで近くの基地を提案する など
|
|
76
|
+
|
|
77
|
+
座標にひもづけられた大きなデータを格納する場合に、
|
|
78
|
+
図のようなソート順にするとキャッシュのヒット率が上がるといった
|
|
79
|
+
メリットがあるかもしれません。
|
3
説明補足
test
CHANGED
|
@@ -1,10 +1,15 @@
|
|
|
1
|
-
yの上位ビット、xの上位ビット、…の順で下位ビットへと交互に比較します。
|
|
1
|
+
yの上位ビット、xの上位ビット、…の順で下位ビットへと交互に比較してソートします。
|
|
2
|
+
座標が近ければデータも近い、とか
|
|
3
|
+
データが近ければ座標も近い、という保証はありませんが、
|
|
4
|
+
座標が近いデータは近くに並びやすくなるので、
|
|
5
|
+
一般的な状況は改善するでしょう。
|
|
6
|
+
|
|
2
7
|
あらかじめ、xとyの値を正規化しておく必要があります。
|
|
3
|
-
(下のコードでは、ビットマスク mask をy座標・x座標で別々にするなど)
|
|
8
|
+
(または、下のコードでは、ビットマスク mask をy座標・x座標で別々にするなど)
|
|
9
|
+
|
|
10
|
+
C言語の例を示します。(xもyも0〜255の場合)
|
|
4
11
|
一般的なコンピュータでは、上から下、左から右の順に並びます。
|
|
5
12
|
(数学のxy座標では下から上、左から右の順になります)
|
|
6
|
-
|
|
7
|
-
C言語の例を示します。(xもyも0〜255の場合)
|
|
8
13
|
|
|
9
14
|
```C言語
|
|
10
15
|
#include <stdlib.h>
|
2
スケーリングについて補足
test
CHANGED
|
@@ -1,5 +1,6 @@
|
|
|
1
1
|
yの上位ビット、xの上位ビット、…の順で下位ビットへと交互に比較します。
|
|
2
2
|
あらかじめ、xとyの値を正規化しておく必要があります。
|
|
3
|
+
(下のコードでは、ビットマスク mask をy座標・x座標で別々にするなど)
|
|
3
4
|
一般的なコンピュータでは、上から下、左から右の順に並びます。
|
|
4
5
|
(数学のxy座標では下から上、左から右の順になります)
|
|
5
6
|
|
1
座標の向き、並べ替えの順序を訂正
test
CHANGED
|
@@ -1,6 +1,7 @@
|
|
|
1
1
|
yの上位ビット、xの上位ビット、…の順で下位ビットへと交互に比較します。
|
|
2
2
|
あらかじめ、xとyの値を正規化しておく必要があります。
|
|
3
|
-
|
|
3
|
+
一般的なコンピュータでは、上から下、左から右の順に並びます。
|
|
4
|
+
(数学のxy座標では下から上、左から右の順になります)
|
|
4
5
|
|
|
5
6
|
C言語の例を示します。(xもyも0〜255の場合)
|
|
6
7
|
|