回答編集履歴

25

fixed code

2022/10/16 05:46

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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, r in enumerate(argsort(a)): # r: 順位, idx: argsortで求めたソート前のindex
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

2022/10/16 04:17

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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)) # [3, 2, 3, 7, 3, 3, 6, 1, 4, 5]
78
+ print("rank2 :", calc_rank2(a)) # [2, 1, 2, 6, 2, 2, 5, 0, 3, 4]
79
79
  ```

23

fix code

2022/10/16 04:15

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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, y in enumerate(argsort(a)): # x: 順位, y: argsortで求めたソート前のindex
26
+ for idx, r in enumerate(argsort(a)): # r: 順位, idx: argsortで求めたソート前のindex
27
- rank[y] = x # ソート前のindexであるyを使ってrank配列のy番目の順位をxにする
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
- 他のPythonライブラリでも同様,の配列得るソートを`argsort()`という名前実装れていますので覚えておく良いでしょう
39
+ 今回は使ってindexを保持したソートをすることで,`O(N log N)`の時間計算量順位を反映せるこきま
40
+ このままだと同じ値でも別々の順位を割り振られる実装になっていますので,次のように変更することもできます.
40
41
 
42
+ ```Python
41
- * [numpy.argsort](https://numpy.org/doc/stable/reference/generated/numpy.argsort.html)
43
+ rank = [0] * len(a)
44
+ rank_no = set()
42
- * [torch.argsort](https://pytorch.org/docs/stable/generated/torch.argsort.html)
45
+ for idx in argsort(a):
46
+ rank_no.add(a[idx])
43
- * [tensorflow.argsort](https://www.tensorflow.org/api_docs/python/tf/argsort)
47
+ rank[idx] = len(rank_no)
48
+ ```
44
49
 
45
- 今回はこれを使ってindexを保持しトをすることで,`O(N log N)`の時間計算量で順位を反映させることできました
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
- 余談ですが「たまたま」例示いただいたデータ`[12, 43, 7, 15, 9]`において`argsort()`の結果と求めた順位`rank`が同じになっています(非常にややこしいです).`argsort()`の結果を例示しなかったのは混乱するからです...`[9, 1, 8, 2, 7, 3, 6, 4, 5]`とかでやると異なる配列が得られてわかりやすいかと思います.
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

2022/10/16 03:56

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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

2022/10/16 03:52

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -4,13 +4,13 @@
4
4
  a = [12, 43, 7, 15, 9]
5
5
  new_list = sorted(a) # aの配列をソートして、新しい配列を作り
6
6
 
7
- result = [0] * len(a)
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
- result[j] = i # 反映させる
11
+ rank[j] = i # 反映させる
12
12
 
13
- print(result) # [2, 4, 0, 3, 1]
13
+ print(rank) # [2, 4, 0, 3, 1]
14
14
  ```
15
15
  配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.また,要素に重複がある場合正しく動作しないので,もっとコードを書く必要があります.
16
16
 

20

fix context

2022/10/16 03:49

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -14,11 +14,11 @@
14
14
  ```
15
15
  配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.また,要素に重複がある場合正しく動作しないので,もっとコードを書く必要があります.
16
16
 
17
- この問題を解決すべく,ソートする際に元あったインデックス情報ごと一緒に並び替えてしまえば良い,という発想が必要になります.ここではソートにかかる時間計算量そのまま`O(N log N)`で済みます.
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
- と書かれたりしす.また,`argsort()`の実装方法はこれに限りません.あくまで一例です.他にも
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

2022/10/16 03:46

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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を保持したままソートすることで,`O(N log N)`の時間計算量で順位を反映させることができました.
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

2022/10/16 03:40

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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

2022/10/16 03:34

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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: 順位y: argsortで求めたindex
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

2022/10/16 03:33

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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

2022/10/16 03:28

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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(argsort(a)) # [2, 4, 0, 3, 1]
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

2022/10/16 02:58

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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さんの実装](https://teratail.com/questions/7zpgalsr1vo6rx#reply-30d6ynd2xhxp7z)と同じ動作をします.要素に重複がある場合正しく動作しません
15
+ 配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.また,要素に重複がある場合正しく動作しないので,もっとコードを書く必要があり
16
16
 
17
17
  この問題を解決すべく,ソートする際に元あったインデックス情報ごと一緒に並び替えてしまえば良い,という発想が必要になります.ここではソートにかかる時間計算量そのまま`O(N log N)`で済みます.
18
18
 

13

delete with value

2022/10/16 02:54

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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_only_index(arr, reverse = False):
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_only_index(a)) # [2, 4, 0, 3, 1]
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

2022/10/16 02:48

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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

2022/10/16 02:42

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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 [(x, y) for x, y in sorted(enumerate(arr), key = lambda x: x[1], reverse = reverse)]
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)) # [(2, 7), (4, 9), (0, 12), (3, 15), (1, 43)]
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

2022/10/16 02:41

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -14,24 +14,30 @@
14
14
  ```
15
15
  配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.また,これはmelianさんの実装と同じ動作をします.要素に重複がある場合正しく動作しません.
16
16
 
17
- この問題を解決すべく,ソートする際に元あったインデックス情報ごと一緒に並び替えてしまえば良い,という発想が必要になります.ここではソートがボトルネックなり時間計算量`O(N log N)`で済みます.
17
+ この問題を解決すべく,ソートする際に元あったインデックス情報ごと一緒に並び替えてしまえば良い,という発想が必要になります.ここではソートにかかる時間計算量そのまま`O(N log N)`で済みます.
18
18
 
19
19
  これは一般に,`argsort()`と呼ばれる動作になり,次のように実装することができます.
20
20
  ```Python
21
21
  a = [12, 43, 7, 15, 9]
22
- a_sorted_index = sorted(range(len(a)), key = a.__getitem__)
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
- a_sorted_index = argsort(a)
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

2022/10/16 02:33

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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

2022/10/16 01:43

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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] = idx
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

2022/10/16 01:41

投稿

ps_aux_grep
ps_aux_grep

スコア1579

test CHANGED
@@ -16,7 +16,7 @@
16
16
  ```
17
17
  配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため,要素数`N`に対して時間計算量`O(N^2)`のアルゴリズムとなっており,非常に低速な実装です.また,これはmelianさんの実装と同じ動作をします.要素に重複がある場合正しく動作しません.
18
18
 
19
- ソートする際に元あったインデックス情報ごと一緒に並び替えてしまえば,ソートがボトルネックになり時間計算量が`O(N log N)`で済みます.
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

2022/10/16 01:39

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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

2022/10/16 01:37

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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

2022/10/16 01:25

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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

2022/10/16 01:24

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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(x, reverse = False):
8
+ def argsort(arr, reverse = False):
9
- return sorted(range(len(x)), key=x.__getitem__, reverse=reverse)
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
- と書かれたりします.他のPythonライブラリでも同様,この配列を得るソートを`argsort()`呼ばれますので覚えておくと良いでしょう.
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

2022/10/16 01:13

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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

2022/10/16 01:08

投稿

ps_aux_grep
ps_aux_grep

スコア1579

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