回答編集履歴
25
fixed code
test
CHANGED
@@ -23,7 +23,7 @@
|
|
23
23
|
|
24
24
|
a = [12, 43, 7, 15, 9]
|
25
25
|
rank = [0] * len(a)
|
26
|
-
for idx
|
26
|
+
for r, idx in enumerate(argsort(a)): # r: 順位, idx: argsortで求めたソート前のindex
|
27
27
|
rank[idx] = r # ソート前のindexであるidxを使ってrank配列のidx番目の順位をrにする
|
28
28
|
print(rank) # [2, 4, 0, 3, 1]
|
29
29
|
```
|
@@ -56,16 +56,16 @@
|
|
56
56
|
def argsort(arr, reverse = False):
|
57
57
|
return sorted(range(len(arr)), key = arr.__getitem__, reverse = reverse)
|
58
58
|
|
59
|
-
def calc_rank1(arr): # 重複があっても左から順に順位付け
|
59
|
+
def calc_rank1(arr, reverse = False): # 重複があっても左から順に順位付け
|
60
60
|
rank = [0] * len(arr)
|
61
|
-
for r, idx in enumerate(argsort(arr)):
|
61
|
+
for r, idx in enumerate(argsort(arr, reverse)):
|
62
62
|
rank[idx] = r
|
63
63
|
return rank
|
64
64
|
|
65
|
-
def calc_rank2(arr): # 重複は同じ順位
|
65
|
+
def calc_rank2(arr, reverse = False): # 重複は同じ順位
|
66
66
|
rank = [0] * len(arr)
|
67
67
|
rank_no = set()
|
68
|
-
for idx in argsort(arr):
|
68
|
+
for idx in argsort(arr, reverse):
|
69
69
|
rank_no.add(arr[idx])
|
70
70
|
rank[idx] = len(rank_no) - 1
|
71
71
|
return rank
|
24
fix result
test
CHANGED
@@ -75,5 +75,5 @@
|
|
75
75
|
print("original:", a) # [9, 6, 9, 19, 9, 9, 15, 3, 10, 12]
|
76
76
|
print("argsort :", argsort(a)) # [7, 1, 0, 2, 4, 5, 8, 9, 6, 3]
|
77
77
|
print("rank1 :", calc_rank1(a)) # [2, 1, 3, 9, 4, 5, 8, 0, 6, 7]
|
78
|
-
print("rank2 :", calc_rank2(a)) # [
|
78
|
+
print("rank2 :", calc_rank2(a)) # [2, 1, 2, 6, 2, 2, 5, 0, 3, 4]
|
79
79
|
```
|
23
fix code
test
CHANGED
@@ -23,8 +23,8 @@
|
|
23
23
|
|
24
24
|
a = [12, 43, 7, 15, 9]
|
25
25
|
rank = [0] * len(a)
|
26
|
-
for x,
|
26
|
+
for idx, r in enumerate(argsort(a)): # r: 順位, idx: argsortで求めたソート前のindex
|
27
|
-
rank[
|
27
|
+
rank[idx] = r # ソート前のindexであるidxを使ってrank配列のidx番目の順位をrにする
|
28
28
|
print(rank) # [2, 4, 0, 3, 1]
|
29
29
|
```
|
30
30
|
また,`argsort()`の実装方法はこれに限りません.あくまで一例です.他にも
|
@@ -36,12 +36,44 @@
|
|
36
36
|
|
37
37
|
[stack overflow - How to get indices of a sorted array in Python](https://stackoverflow.com/questions/6422700/how-to-get-indices-of-a-sorted-array-in-python)
|
38
38
|
|
39
|
-
|
39
|
+
今回はこれを使ってindexを保持したソートをすることで,`O(N log N)`の時間計算量で順位を反映させることができました.
|
40
|
+
このままだと同じ値でも別々の順位を割り振られる実装になっていますので,次のように変更することもできます.
|
40
41
|
|
42
|
+
```Python
|
41
|
-
|
43
|
+
rank = [0] * len(a)
|
44
|
+
rank_no = set()
|
42
|
-
|
45
|
+
for idx in argsort(a):
|
46
|
+
rank_no.add(a[idx])
|
43
|
-
|
47
|
+
rank[idx] = len(rank_no)
|
48
|
+
```
|
44
49
|
|
45
|
-
|
50
|
+
余談ですが「たまたま」例示いただいたデータ`[12, 43, 7, 15, 9]`において`argsort()`の結果と求めた順位`rank`が同じになっています(非常にややこしいです).`argsort()`の結果を例示しなかったのは混乱するからです...
|
46
51
|
|
52
|
+
### 結論
|
53
|
+
```Python
|
54
|
+
import random
|
55
|
+
|
56
|
+
def argsort(arr, reverse = False):
|
57
|
+
return sorted(range(len(arr)), key = arr.__getitem__, reverse = reverse)
|
58
|
+
|
59
|
+
def calc_rank1(arr): # 重複があっても左から順に順位付け
|
60
|
+
rank = [0] * len(arr)
|
61
|
+
for r, idx in enumerate(argsort(arr)):
|
62
|
+
rank[idx] = r
|
63
|
+
return rank
|
64
|
+
|
65
|
+
def calc_rank2(arr): # 重複は同じ順位
|
66
|
+
rank = [0] * len(arr)
|
67
|
+
rank_no = set()
|
68
|
+
for idx in argsort(arr):
|
69
|
+
rank_no.add(arr[idx])
|
70
|
+
rank[idx] = len(rank_no) - 1
|
71
|
+
return rank
|
72
|
+
|
73
|
+
a = [random.randint(0, 20) for _ in range(10)]
|
74
|
+
|
75
|
+
print("original:", a) # [9, 6, 9, 19, 9, 9, 15, 3, 10, 12]
|
47
|
-
|
76
|
+
print("argsort :", argsort(a)) # [7, 1, 0, 2, 4, 5, 8, 9, 6, 3]
|
77
|
+
print("rank1 :", calc_rank1(a)) # [2, 1, 3, 9, 4, 5, 8, 0, 6, 7]
|
78
|
+
print("rank2 :", calc_rank2(a)) # [3, 2, 3, 7, 3, 3, 6, 1, 4, 5]
|
79
|
+
```
|
22
fixed code
test
CHANGED
@@ -8,7 +8,7 @@
|
|
8
8
|
for i in range(len(new_list)): # その配列の順番を
|
9
9
|
for j in range(len(a)): # aの配列に
|
10
10
|
if new_list[i] == a[j]:
|
11
|
-
rank[j] = i # 反映させる
|
11
|
+
rank[j] = i # 反映させる
|
12
12
|
|
13
13
|
print(rank) # [2, 4, 0, 3, 1]
|
14
14
|
```
|
@@ -23,8 +23,8 @@
|
|
23
23
|
|
24
24
|
a = [12, 43, 7, 15, 9]
|
25
25
|
rank = [0] * len(a)
|
26
|
-
for x, y in enumerate(argsort(a)): # x: 順位, y: argsortで求めたindex
|
26
|
+
for x, y in enumerate(argsort(a)): # x: 順位, y: argsortで求めたソート前のindex
|
27
|
-
rank[y] = x
|
27
|
+
rank[y] = x # ソート前のindexであるyを使ってrank配列のy番目の順位をxにする
|
28
28
|
print(rank) # [2, 4, 0, 3, 1]
|
29
29
|
```
|
30
30
|
また,`argsort()`の実装方法はこれに限りません.あくまで一例です.他にも
|
21
update code
test
CHANGED
@@ -4,13 +4,13 @@
|
|
4
4
|
a = [12, 43, 7, 15, 9]
|
5
5
|
new_list = sorted(a) # aの配列をソートして、新しい配列を作り
|
6
6
|
|
7
|
-
r
|
7
|
+
rank = [0] * len(a)
|
8
8
|
for i in range(len(new_list)): # その配列の順番を
|
9
9
|
for j in range(len(a)): # aの配列に
|
10
10
|
if new_list[i] == a[j]:
|
11
|
-
r
|
11
|
+
rank[j] = i # 反映させる
|
12
12
|
|
13
|
-
print(r
|
13
|
+
print(rank) # [2, 4, 0, 3, 1]
|
14
14
|
```
|
15
15
|
配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.また,要素に重複がある場合正しく動作しないので,もっとコードを書く必要があります.
|
16
16
|
|
20
fix context
test
CHANGED
@@ -14,11 +14,11 @@
|
|
14
14
|
```
|
15
15
|
配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.また,要素に重複がある場合正しく動作しないので,もっとコードを書く必要があります.
|
16
16
|
|
17
|
-
この問題を解決すべく,ソートする際に元
|
17
|
+
この問題を解決すべく,ソートする際に,元の配列のインデックス情報の方を並び替えてしまえば良い,という発想が必要になります.ここではソートにかかる時間計算量そのまま`O(N log N)`で済みます.
|
18
18
|
|
19
19
|
これは一般に,`argsort()`と呼ばれる動作になり,順位を求める実装と合わせて次のようになります.
|
20
20
|
```Python
|
21
|
-
def argsort(arr, reverse = False):
|
21
|
+
def argsort(arr, reverse = False): # ソート前のindexを返す
|
22
22
|
return sorted(range(len(arr)), key = arr.__getitem__, reverse = reverse)
|
23
23
|
|
24
24
|
a = [12, 43, 7, 15, 9]
|
@@ -27,7 +27,7 @@
|
|
27
27
|
rank[y] = x
|
28
28
|
print(rank) # [2, 4, 0, 3, 1]
|
29
29
|
```
|
30
|
-
|
30
|
+
また,`argsort()`の実装方法はこれに限りません.あくまで一例です.他にも
|
31
31
|
```Python
|
32
32
|
def argsort(arr, reverse = False):
|
33
33
|
return [x for x, y in sorted(enumerate(arr), key = lambda x: x[1], reverse = reverse)]
|
@@ -42,6 +42,6 @@
|
|
42
42
|
* [torch.argsort](https://pytorch.org/docs/stable/generated/torch.argsort.html)
|
43
43
|
* [tensorflow.argsort](https://www.tensorflow.org/api_docs/python/tf/argsort)
|
44
44
|
|
45
|
-
今回はこれを使ってindexを保持したソートすることで,`O(N log N)`の時間計算量で順位を反映させることができました.
|
45
|
+
今回はこれを使ってindexを保持したソートをすることで,`O(N log N)`の時間計算量で順位を反映させることができました.
|
46
46
|
|
47
47
|
余談ですが「たまたま」例示いただいたデータ`[12, 43, 7, 15, 9]`において`argsort()`の結果と求めた順位`rank`が同じになっています(非常にややこしいです).`argsort()`の結果を例示しなかったのは混乱するからです...`[9, 1, 8, 2, 7, 3, 6, 4, 5]`とかでやると異なる配列が得られてわかりやすいかと思います.
|
19
fix suffix
test
CHANGED
@@ -42,6 +42,6 @@
|
|
42
42
|
* [torch.argsort](https://pytorch.org/docs/stable/generated/torch.argsort.html)
|
43
43
|
* [tensorflow.argsort](https://www.tensorflow.org/api_docs/python/tf/argsort)
|
44
44
|
|
45
|
-
今回はこれを使ってindexを保持した
|
45
|
+
今回はこれを使ってindexを保持したソートすることで,`O(N log N)`の時間計算量で順位を反映させることができました.
|
46
46
|
|
47
|
-
余談ですが「たまたま」例示いただいたデータ`[12, 43, 7, 15, 9]`において`argsort()`の結果と求めた順位が同じになっています.
|
47
|
+
余談ですが「たまたま」例示いただいたデータ`[12, 43, 7, 15, 9]`において`argsort()`の結果と求めた順位`rank`が同じになっています(非常にややこしいです).`argsort()`の結果を例示しなかったのは混乱するからです...`[9, 1, 8, 2, 7, 3, 6, 4, 5]`とかでやると異なる配列が得られてわかりやすいかと思います.
|
18
fix code
test
CHANGED
@@ -43,3 +43,5 @@
|
|
43
43
|
* [tensorflow.argsort](https://www.tensorflow.org/api_docs/python/tf/argsort)
|
44
44
|
|
45
45
|
今回はこれを使ってindexを保持したままソートすることで,`O(N log N)`の時間計算量で順位を反映させることができました.
|
46
|
+
|
47
|
+
余談ですが「たまたま」例示いただいたデータ`[12, 43, 7, 15, 9]`において`argsort()`の結果と求めた順位が同じになっています.
|
17
fix code exp
test
CHANGED
@@ -23,7 +23,7 @@
|
|
23
23
|
|
24
24
|
a = [12, 43, 7, 15, 9]
|
25
25
|
rank = [0] * len(a)
|
26
|
-
for x, y in enumerate(argsort(a)): # x: 順位
|
26
|
+
for x, y in enumerate(argsort(a)): # x: 順位, y: argsortで求めたindex
|
27
27
|
rank[y] = x
|
28
28
|
print(rank) # [2, 4, 0, 3, 1]
|
29
29
|
```
|
16
fix context
test
CHANGED
@@ -16,18 +16,18 @@
|
|
16
16
|
|
17
17
|
この問題を解決すべく,ソートする際に元あったインデックス情報ごと一緒に並び替えてしまえば良い,という発想が必要になります.ここではソートにかかる時間計算量そのまま`O(N log N)`で済みます.
|
18
18
|
|
19
|
-
これは一般に,`argsort()`と呼ばれる動作になり,次のように
|
19
|
+
これは一般に,`argsort()`と呼ばれる動作になり,順位を求める実装と合わせて次のようになります.
|
20
20
|
```Python
|
21
21
|
def argsort(arr, reverse = False):
|
22
22
|
return sorted(range(len(arr)), key = arr.__getitem__, reverse = reverse)
|
23
23
|
|
24
24
|
a = [12, 43, 7, 15, 9]
|
25
25
|
rank = [0] * len(a)
|
26
|
-
for x, y in enumerate(argsort(a)):
|
26
|
+
for x, y in enumerate(argsort(a)): # x: 順位,y: argsortで求めたindex
|
27
27
|
rank[y] = x
|
28
28
|
print(rank) # [2, 4, 0, 3, 1]
|
29
29
|
```
|
30
|
-
と書かれたりします.また,
|
30
|
+
と書かれたりします.また,`argsort()`の実装方法はこれに限りません.あくまで一例です.他にも
|
31
31
|
```Python
|
32
32
|
def argsort(arr, reverse = False):
|
33
33
|
return [x for x, y in sorted(enumerate(arr), key = lambda x: x[1], reverse = reverse)]
|
@@ -41,3 +41,5 @@
|
|
41
41
|
* [numpy.argsort](https://numpy.org/doc/stable/reference/generated/numpy.argsort.html)
|
42
42
|
* [torch.argsort](https://pytorch.org/docs/stable/generated/torch.argsort.html)
|
43
43
|
* [tensorflow.argsort](https://www.tensorflow.org/api_docs/python/tf/argsort)
|
44
|
+
|
45
|
+
今回はこれを使ってindexを保持したままソートすることで,`O(N log N)`の時間計算量で順位を反映させることができました.
|
15
fixed code
test
CHANGED
@@ -18,23 +18,19 @@
|
|
18
18
|
|
19
19
|
これは一般に,`argsort()`と呼ばれる動作になり,次のように実装することができます.
|
20
20
|
```Python
|
21
|
-
a = [12, 43, 7, 15, 9]
|
22
|
-
print(sorted(range(len(a)), key = a.__getitem__)) # [2, 4, 0, 3, 1]
|
23
|
-
```
|
24
|
-
せっかく`argsort()`という名前がついているので関数に落として
|
25
|
-
```Python
|
26
21
|
def argsort(arr, reverse = False):
|
27
22
|
return sorted(range(len(arr)), key = arr.__getitem__, reverse = reverse)
|
28
23
|
|
29
24
|
a = [12, 43, 7, 15, 9]
|
25
|
+
rank = [0] * len(a)
|
26
|
+
for x, y in enumerate(argsort(a)):
|
27
|
+
rank[y] = x
|
30
|
-
print(
|
28
|
+
print(rank) # [2, 4, 0, 3, 1]
|
31
29
|
```
|
32
30
|
と書かれたりします.また,色んな方が回答している通り,実装方法はこれに限りません.あくまで一例です.他にも
|
33
31
|
```Python
|
34
32
|
def argsort(arr, reverse = False):
|
35
33
|
return [x for x, y in sorted(enumerate(arr), key = lambda x: x[1], reverse = reverse)]
|
36
|
-
|
37
|
-
print(argsort(a)) # [2, 4, 0, 3, 1]
|
38
34
|
```
|
39
35
|
などがあります.なお基本構造はどれも同じで,ソートの対象`key`の指定を,`key = arr.__getitem__`として値を指定するか,`enumerate()`で列挙される要素の1番目に対象の値があることを利用した`key = lambda x: x[1]`とするなど,複数のテクニックが存在します.ソートの対象はリストの値,実際に並び替えられたのはリストのインデックス.といった具合です.
|
40
36
|
|
14
fix answer
test
CHANGED
@@ -12,7 +12,7 @@
|
|
12
12
|
|
13
13
|
print(result) # [2, 4, 0, 3, 1]
|
14
14
|
```
|
15
|
-
配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.また,
|
15
|
+
配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.また,要素に重複がある場合正しく動作しないので,もっとコードを書く必要があります.
|
16
16
|
|
17
17
|
この問題を解決すべく,ソートする際に元あったインデックス情報ごと一緒に並び替えてしまえば良い,という発想が必要になります.ここではソートにかかる時間計算量そのまま`O(N log N)`で済みます.
|
18
18
|
|
13
delete with value
test
CHANGED
@@ -25,19 +25,16 @@
|
|
25
25
|
```Python
|
26
26
|
def argsort(arr, reverse = False):
|
27
27
|
return sorted(range(len(arr)), key = arr.__getitem__, reverse = reverse)
|
28
|
+
|
28
29
|
a = [12, 43, 7, 15, 9]
|
29
30
|
print(argsort(a)) # [2, 4, 0, 3, 1]
|
30
31
|
```
|
31
32
|
と書かれたりします.また,色んな方が回答している通り,実装方法はこれに限りません.あくまで一例です.他にも
|
32
33
|
```Python
|
33
|
-
def argsort
|
34
|
+
def argsort(arr, reverse = False):
|
34
35
|
return [x for x, y in sorted(enumerate(arr), key = lambda x: x[1], reverse = reverse)]
|
35
36
|
|
36
|
-
def argsort_with_value(arr, reverse = False):
|
37
|
-
return [(y, x) for x, y in sorted(enumerate(arr), key = lambda x: x[1], reverse = reverse)]
|
38
|
-
|
39
|
-
print(argsort
|
37
|
+
print(argsort(a)) # [2, 4, 0, 3, 1]
|
40
|
-
print(argsort_with_value(a)) # [(7, 2), (9, 4), (12, 0), (15, 3), (43, 1)]
|
41
38
|
```
|
42
39
|
などがあります.なお基本構造はどれも同じで,ソートの対象`key`の指定を,`key = arr.__getitem__`として値を指定するか,`enumerate()`で列挙される要素の1番目に対象の値があることを利用した`key = lambda x: x[1]`とするなど,複数のテクニックが存在します.ソートの対象はリストの値,実際に並び替えられたのはリストのインデックス.といった具合です.
|
43
40
|
|
12
add another answer links
test
CHANGED
@@ -12,7 +12,7 @@
|
|
12
12
|
|
13
13
|
print(result) # [2, 4, 0, 3, 1]
|
14
14
|
```
|
15
|
-
配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.また,これはmelianさんの実装と同じ動作をします.要素に重複がある場合正しく動作しません.
|
15
|
+
配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.また,これは[melianさんの実装](https://teratail.com/questions/7zpgalsr1vo6rx#reply-30d6ynd2xhxp7z)と同じ動作をします.要素に重複がある場合正しく動作しません.
|
16
16
|
|
17
17
|
この問題を解決すべく,ソートする際に元あったインデックス情報ごと一緒に並び替えてしまえば良い,という発想が必要になります.ここではソートにかかる時間計算量そのまま`O(N log N)`で済みます.
|
18
18
|
|
11
swap xy
test
CHANGED
@@ -34,10 +34,10 @@
|
|
34
34
|
return [x for x, y in sorted(enumerate(arr), key = lambda x: x[1], reverse = reverse)]
|
35
35
|
|
36
36
|
def argsort_with_value(arr, reverse = False):
|
37
|
-
return [(
|
37
|
+
return [(y, x) for x, y in sorted(enumerate(arr), key = lambda x: x[1], reverse = reverse)]
|
38
38
|
|
39
39
|
print(argsort_only_index(a)) # [2, 4, 0, 3, 1]
|
40
|
-
print(argsort_with_value(a)) # [(
|
40
|
+
print(argsort_with_value(a)) # [(7, 2), (9, 4), (12, 0), (15, 3), (43, 1)]
|
41
41
|
```
|
42
42
|
などがあります.なお基本構造はどれも同じで,ソートの対象`key`の指定を,`key = arr.__getitem__`として値を指定するか,`enumerate()`で列挙される要素の1番目に対象の値があることを利用した`key = lambda x: x[1]`とするなど,複数のテクニックが存在します.ソートの対象はリストの値,実際に並び替えられたのはリストのインデックス.といった具合です.
|
43
43
|
|
10
append code
test
CHANGED
@@ -14,24 +14,30 @@
|
|
14
14
|
```
|
15
15
|
配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.また,これはmelianさんの実装と同じ動作をします.要素に重複がある場合正しく動作しません.
|
16
16
|
|
17
|
-
この問題を解決すべく,ソートする際に元あったインデックス情報ごと一緒に並び替えてしまえば良い,という発想が必要になります.ここではソート
|
17
|
+
この問題を解決すべく,ソートする際に元あったインデックス情報ごと一緒に並び替えてしまえば良い,という発想が必要になります.ここではソートにかかる時間計算量そのまま`O(N log N)`で済みます.
|
18
18
|
|
19
19
|
これは一般に,`argsort()`と呼ばれる動作になり,次のように実装することができます.
|
20
20
|
```Python
|
21
21
|
a = [12, 43, 7, 15, 9]
|
22
|
-
|
22
|
+
print(sorted(range(len(a)), key = a.__getitem__)) # [2, 4, 0, 3, 1]
|
23
23
|
```
|
24
|
-
関数に落として
|
24
|
+
せっかく`argsort()`という名前がついているので関数に落として
|
25
25
|
```Python
|
26
26
|
def argsort(arr, reverse = False):
|
27
27
|
return sorted(range(len(arr)), key = arr.__getitem__, reverse = reverse)
|
28
28
|
a = [12, 43, 7, 15, 9]
|
29
|
-
|
29
|
+
print(argsort(a)) # [2, 4, 0, 3, 1]
|
30
30
|
```
|
31
31
|
と書かれたりします.また,色んな方が回答している通り,実装方法はこれに限りません.あくまで一例です.他にも
|
32
32
|
```Python
|
33
|
-
def argsort(arr, reverse = False):
|
33
|
+
def argsort_only_index(arr, reverse = False):
|
34
|
-
return [x for x,y in sorted(enumerate(arr), key = lambda x: x[1], reverse = reverse)]
|
34
|
+
return [x for x, y in sorted(enumerate(arr), key = lambda x: x[1], reverse = reverse)]
|
35
|
+
|
36
|
+
def argsort_with_value(arr, reverse = False):
|
37
|
+
return [(x, y) for x, y in sorted(enumerate(arr), key = lambda x: x[1], reverse = reverse)]
|
38
|
+
|
39
|
+
print(argsort_only_index(a)) # [2, 4, 0, 3, 1]
|
40
|
+
print(argsort_with_value(a)) # [(2, 7), (4, 9), (0, 12), (3, 15), (1, 43)]
|
35
41
|
```
|
36
42
|
などがあります.なお基本構造はどれも同じで,ソートの対象`key`の指定を,`key = arr.__getitem__`として値を指定するか,`enumerate()`で列挙される要素の1番目に対象の値があることを利用した`key = lambda x: x[1]`とするなど,複数のテクニックが存在します.ソートの対象はリストの値,実際に並び替えられたのはリストのインデックス.といった具合です.
|
37
43
|
|
9
fix context
test
CHANGED
@@ -2,13 +2,13 @@
|
|
2
2
|
これを実現すると以下になります.
|
3
3
|
```Python
|
4
4
|
a = [12, 43, 7, 15, 9]
|
5
|
-
new_list = sorted(a)
|
5
|
+
new_list = sorted(a) # aの配列をソートして、新しい配列を作り
|
6
6
|
|
7
7
|
result = [0] * len(a)
|
8
|
-
for i in range(len(new_list)):
|
8
|
+
for i in range(len(new_list)): # その配列の順番を
|
9
|
-
for j in range(len(a)):
|
9
|
+
for j in range(len(a)): # aの配列に
|
10
10
|
if new_list[i] == a[j]:
|
11
|
-
result[j] = i
|
11
|
+
result[j] = i # 反映させる
|
12
12
|
|
13
13
|
print(result) # [2, 4, 0, 3, 1]
|
14
14
|
```
|
8
fix code
test
CHANGED
@@ -5,14 +5,12 @@
|
|
5
5
|
new_list = sorted(a)
|
6
6
|
|
7
7
|
result = [0] * len(a)
|
8
|
-
idx = 0
|
9
8
|
for i in range(len(new_list)):
|
10
9
|
for j in range(len(a)):
|
11
10
|
if new_list[i] == a[j]:
|
12
|
-
result[j] = i
|
11
|
+
result[j] = i
|
13
|
-
idx += 1
|
14
12
|
|
15
|
-
print(result)
|
13
|
+
print(result) # [2, 4, 0, 3, 1]
|
16
14
|
```
|
17
15
|
配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.また,これはmelianさんの実装と同じ動作をします.要素に重複がある場合正しく動作しません.
|
18
16
|
|
7
fixed code
test
CHANGED
@@ -16,7 +16,7 @@
|
|
16
16
|
```
|
17
17
|
配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.また,これはmelianさんの実装と同じ動作をします.要素に重複がある場合正しく動作しません.
|
18
18
|
|
19
|
-
|
19
|
+
この問題を解決すべく,ソートする際に元あったインデックス情報ごと一緒に並び替えてしまえば良い,という発想が必要になります.ここではソートがボトルネックになり時間計算量が`O(N log N)`で済みます.
|
20
20
|
|
21
21
|
これは一般に,`argsort()`と呼ばれる動作になり,次のように実装することができます.
|
22
22
|
```Python
|
@@ -39,7 +39,7 @@
|
|
39
39
|
|
40
40
|
[stack overflow - How to get indices of a sorted array in Python](https://stackoverflow.com/questions/6422700/how-to-get-indices-of-a-sorted-array-in-python)
|
41
41
|
|
42
|
-
他のPythonライブラリでも同様,この配列を得るソートを`argsort()`と
|
42
|
+
他のPythonライブラリでも同様,この配列を得るソートを`argsort()`という名前で実装されていますので覚えておくと良いでしょう.
|
43
43
|
|
44
44
|
* [numpy.argsort](https://numpy.org/doc/stable/reference/generated/numpy.argsort.html)
|
45
45
|
* [torch.argsort](https://pytorch.org/docs/stable/generated/torch.argsort.html)
|
6
fixed context
test
CHANGED
@@ -14,7 +14,7 @@
|
|
14
14
|
|
15
15
|
print(result)
|
16
16
|
```
|
17
|
-
配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.
|
17
|
+
配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.また,これはmelianさんの実装と同じ動作をします.要素に重複がある場合正しく動作しません.
|
18
18
|
|
19
19
|
そこでソートする際に,元あったインデックス情報ごと一緒に並び替えてしまえば,ソートがボトルネックになり時間計算量が`O(N log N)`で済みます.
|
20
20
|
|
5
append your answer
test
CHANGED
@@ -1,9 +1,29 @@
|
|
1
|
+
> 個人的にはaの配列をソートして、新しい配列を作り、その配列の順番をaの配列に反映させるプログラムを作ってみたいと思っています。
|
2
|
+
これを実現すると以下になります.
|
3
|
+
```Python
|
4
|
+
a = [12, 43, 7, 15, 9]
|
5
|
+
new_list = sorted(a)
|
6
|
+
|
7
|
+
result = [0] * len(a)
|
8
|
+
idx = 0
|
9
|
+
for i in range(len(new_list)):
|
10
|
+
for j in range(len(a)):
|
11
|
+
if new_list[i] == a[j]:
|
12
|
+
result[j] = idx
|
13
|
+
idx += 1
|
14
|
+
|
15
|
+
print(result)
|
16
|
+
```
|
17
|
+
配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.
|
18
|
+
|
19
|
+
そこでソートする際に,元あったインデックス情報ごと一緒に並び替えてしまえば,ソートがボトルネックになり時間計算量が`O(N log N)`で済みます.
|
20
|
+
|
1
|
-
`argsort()`と呼ばれる動作です
|
21
|
+
これは一般に,`argsort()`と呼ばれる動作になり,次のように実装することができます.
|
2
22
|
```Python
|
3
23
|
a = [12, 43, 7, 15, 9]
|
4
24
|
a_sorted_index = sorted(range(len(a)), key = a.__getitem__)
|
5
25
|
```
|
6
|
-
|
26
|
+
関数に落として
|
7
27
|
```Python
|
8
28
|
def argsort(arr, reverse = False):
|
9
29
|
return sorted(range(len(arr)), key = arr.__getitem__, reverse = reverse)
|
@@ -15,7 +35,7 @@
|
|
15
35
|
def argsort(arr, reverse = False):
|
16
36
|
return [x for x,y in sorted(enumerate(arr), key = lambda x: x[1], reverse = reverse)]
|
17
37
|
```
|
18
|
-
などがあります.なお基本構造はどれも同じで,ソートの対象`key`の指定を,`key = arr.__getitem__`として値を指定するか,`enumerate()`で列挙される要素の1番目に対象の値があることを利用した`key = lambda x: x[1]`とするなど,複数のテクニックが存在します.
|
38
|
+
などがあります.なお基本構造はどれも同じで,ソートの対象`key`の指定を,`key = arr.__getitem__`として値を指定するか,`enumerate()`で列挙される要素の1番目に対象の値があることを利用した`key = lambda x: x[1]`とするなど,複数のテクニックが存在します.ソートの対象はリストの値,実際に並び替えられたのはリストのインデックス.といった具合です.
|
19
39
|
|
20
40
|
[stack overflow - How to get indices of a sorted array in Python](https://stackoverflow.com/questions/6422700/how-to-get-indices-of-a-sorted-array-in-python)
|
21
41
|
|
4
append reverse
test
CHANGED
@@ -12,8 +12,8 @@
|
|
12
12
|
```
|
13
13
|
と書かれたりします.また,色んな方が回答している通り,実装方法はこれに限りません.あくまで一例です.他にも
|
14
14
|
```Python
|
15
|
-
def argsort(arr):
|
15
|
+
def argsort(arr, reverse = False):
|
16
|
-
return [x for x,y in sorted(enumerate(arr), key = lambda x: x[1])]
|
16
|
+
return [x for x,y in sorted(enumerate(arr), key = lambda x: x[1], reverse = reverse)]
|
17
17
|
```
|
18
18
|
などがあります.なお基本構造はどれも同じで,ソートの対象`key`の指定を,`key = arr.__getitem__`として値を指定するか,`enumerate()`で列挙される要素の1番目に対象の値があることを利用した`key = lambda x: x[1]`とするなど,複数のテクニックが存在します.
|
19
19
|
|
3
fix context
test
CHANGED
@@ -1,16 +1,25 @@
|
|
1
1
|
`argsort()`と呼ばれる動作ですね.
|
2
2
|
```Python
|
3
3
|
a = [12, 43, 7, 15, 9]
|
4
|
-
a_sorted_index = sorted(range(len(a)), key=a.__getitem__)
|
4
|
+
a_sorted_index = sorted(range(len(a)), key = a.__getitem__)
|
5
5
|
```
|
6
6
|
のように実装できるため,関数に落として
|
7
7
|
```Python
|
8
|
-
def argsort(
|
8
|
+
def argsort(arr, reverse = False):
|
9
|
-
return sorted(range(len(
|
9
|
+
return sorted(range(len(arr)), key = arr.__getitem__, reverse = reverse)
|
10
10
|
a = [12, 43, 7, 15, 9]
|
11
11
|
a_sorted_index = argsort(a)
|
12
12
|
```
|
13
|
+
と書かれたりします.また,色んな方が回答している通り,実装方法はこれに限りません.あくまで一例です.他にも
|
14
|
+
```Python
|
15
|
+
def argsort(arr):
|
16
|
+
return [x for x,y in sorted(enumerate(arr), key = lambda x: x[1])]
|
17
|
+
```
|
18
|
+
などがあります.なお基本構造はどれも同じで,ソートの対象`key`の指定を,`key = arr.__getitem__`として値を指定するか,`enumerate()`で列挙される要素の1番目に対象の値があることを利用した`key = lambda x: x[1]`とするなど,複数のテクニックが存在します.
|
19
|
+
|
20
|
+
[stack overflow - How to get indices of a sorted array in Python](https://stackoverflow.com/questions/6422700/how-to-get-indices-of-a-sorted-array-in-python)
|
21
|
+
|
13
|
-
|
22
|
+
他のPythonライブラリでも同様,この配列を得るソートを`argsort()`と呼ばれますので覚えておくと良いでしょう.
|
14
23
|
|
15
24
|
* [numpy.argsort](https://numpy.org/doc/stable/reference/generated/numpy.argsort.html)
|
16
25
|
* [torch.argsort](https://pytorch.org/docs/stable/generated/torch.argsort.html)
|
2
fix code
test
CHANGED
@@ -1,12 +1,14 @@
|
|
1
1
|
`argsort()`と呼ばれる動作ですね.
|
2
2
|
```Python
|
3
3
|
a = [12, 43, 7, 15, 9]
|
4
|
-
a = sorted(range(len(a)), key=a.__getitem__)
|
4
|
+
a_sorted_index = sorted(range(len(a)), key=a.__getitem__)
|
5
5
|
```
|
6
6
|
のように実装できるため,関数に落として
|
7
7
|
```Python
|
8
8
|
def argsort(x, reverse = False):
|
9
9
|
return sorted(range(len(x)), key=x.__getitem__, reverse=reverse)
|
10
|
+
a = [12, 43, 7, 15, 9]
|
11
|
+
a_sorted_index = argsort(a)
|
10
12
|
```
|
11
13
|
と書かれたりします.他のPythonライブラリでも同様,この配列を得るソートを`argsort()`呼ばれますので覚えておくと良いでしょう.
|
12
14
|
|
1
fixed code
test
CHANGED
@@ -5,8 +5,8 @@
|
|
5
5
|
```
|
6
6
|
のように実装できるため,関数に落として
|
7
7
|
```Python
|
8
|
-
def argsort(x):
|
8
|
+
def argsort(x, reverse = False):
|
9
|
-
return sorted(range(len(x)), key=x.__getitem__)
|
9
|
+
return sorted(range(len(x)), key=x.__getitem__, reverse=reverse)
|
10
10
|
```
|
11
11
|
と書かれたりします.他のPythonライブラリでも同様,この配列を得るソートを`argsort()`呼ばれますので覚えておくと良いでしょう.
|
12
12
|
|