# 機能設計書 112-ソート・検索操作

## 概要

本ドキュメントは、TensorFlowにおけるテンソルのソート・TopK・ユニーク値抽出などの検索操作機能の設計を記述する。

### 本機能の処理概要

テンソル内の値を昇順・降順にソートしたり、ソートインデックスを取得する機能を提供する。内部的にはTopK操作を利用した効率的な実装となっている。

**業務上の目的・背景**：機械学習パイプラインにおいて、推論結果のランキング、Top-K抽出、特徴量の順序付け、重複排除などソート・検索操作は頻繁に必要となる。特にレコメンデーションシステムや情報検索タスクでは、スコアの高い上位K件を効率的に取得する必要がある。

**機能の利用シーン**：推論結果の上位K件取得、テンソル値のソート、argsortによるインデックス取得、ユニーク値の抽出などで利用される。

**主要な処理内容**：
1. `tf.sort` - テンソルの値を指定軸に沿って昇順または降順にソート
2. `tf.argsort` - テンソルのソート順序を示すインデックスを返却
3. 内部実装として`nn_ops.top_k`を活用した降順ソートと、値の否定による昇順ソート

**関連システム・外部連携**：TensorFlowのnn_ops（top_k操作）、array_ops（transpose操作）と内部連携する。

**権限による制御**：特になし。全ユーザが利用可能。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | 該当なし | - | 本機能はバックエンドAPI機能であり、直接的な画面関連はない |

## 機能種別

計算処理

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| values | Tensor（1次元以上、数値型） | Yes | ソート対象のテンソル | float型またはint型 |
| axis | int | No（デフォルト: -1） | ソートする軸 | 定数スカラーであること |
| direction | string | No（デフォルト: 'ASCENDING'） | ソート方向 | 'ASCENDING'または'DESCENDING' |
| stable | bool | No（デフォルト: False） | 安定ソートかどうか（argsortのみ） | 現在は未実装のため無視される |
| name | string | No | 操作名 | - |

### 入力データソース

Python API呼び出し（tf.sort, tf.argsort）

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| sorted_values | Tensor | ソート済みテンソル（tf.sortの場合、入力と同じdtype/shape） |
| indices | Tensor（int32） | ソートインデックス（tf.argsortの場合、入力と同じshape） |

### 出力先

呼び出し元への戻り値として返却

## 処理フロー

### 処理シーケンス

```
1. 入力検証
   └─ direction が ASCENDING/DESCENDING のいずれかであることを確認
   └─ axis が定数スカラーであることを確認

2. 降順ソート（_descending_sort）
   └─ 最終軸でない場合はtransposeで軸を最終軸に移動
   └─ nn_ops.top_k(input, k) でソート
   └─ 必要に応じてtransposeで元の軸配置に戻す

3. 昇順ソート（_ascending_sort）
   └─ unsigned整数型: offset - values で降順ソートし、結果を元に戻す
   └─ signed整数型: -values - 1 で降順ソートし、結果を元に戻す
   └─ 浮動小数点型: -values で降順ソートし、結果を否定
```

### フローチャート

```mermaid
flowchart TD
    A[入力テンソル] --> B{direction}
    B -->|DESCENDING| C[_descending_sort]
    B -->|ASCENDING| D[_ascending_sort]
    C --> E{軸が最終軸?}
    E -->|Yes| F[top_k実行]
    E -->|No| G[transpose → top_k → transpose]
    D --> H{データ型}
    H -->|unsigned int| I[offset - values で降順ソート]
    H -->|signed int| J[-values - 1 で降順ソート]
    H -->|float| K[-values で降順ソート]
    F --> L[結果返却]
    G --> L
    I --> L
    J --> L
    K --> L
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-112-01 | 安定ソート | stable引数は現在無視される（将来のために予約） | argsort呼び出し時 |
| BR-112-02 | 軸定数制約 | axis引数は定数スカラーでなければならない | sort/argsort呼び出し時 |
| BR-112-03 | 数値型制約 | float型またはint型のみサポート | sort/argsort呼び出し時 |
| BR-112-04 | 整数型の安定性 | 符号付き整数の昇順ソートは安定性を保持する | signed int型の場合 |

### 計算ロジック

- 降順ソート: `top_k(values, k=size_of_axis)` を利用
- 昇順ソート（float）: `top_k(-values, k)` の結果を否定
- 昇順ソート（signed int）: `top_k(-values - 1, k)` の結果を `-result - 1`
- 昇順ソート（unsigned int）: `top_k(dtype.max - values, k)` の結果を `dtype.max - result`

## データベース操作仕様

該当なし

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| ValueError | 不正なdirection | 'ASCENDING'/'DESCENDING'以外を指定 | 正しい値を指定 |
| ValueError | 非定数axis | axisが定数スカラーでない場合 | 定数値を指定 |
| InvalidArgumentError | 不正なdtype | float/int以外のdtypeの場合 | float/int型にキャスト |

### リトライ仕様

該当なし

## トランザクション仕様

該当なし

## パフォーマンス要件

内部でtop_k操作を使用するため、計算量はO(n log k)（kは軸のサイズ）。全要素ソートの場合はk=nとなりO(n log n)。

## セキュリティ考慮事項

特になし。

## 備考

- 現在の実装はtop_kベースであり、将来的に専用ソートカーネルに置き換わる可能性がある（ソースコードのTODO b/190410105参照）。
- unsigned整数の減算が全デバイスでサポートされていないため、signed整数型の実装が採用されている。

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | sort_ops.py | `tensorflow/python/ops/sort_ops.py` | _SORT_IMPL辞書（282-285行目）がソート方向と実装関数のマッピングを定義 |

**読解のコツ**: ソート操作はdirectionパラメータにより`_ascending_sort`または`_descending_sort`に分岐する。この分岐はPythonの辞書ルックアップで実装されている。

#### Step 2: エントリーポイントを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | sort_ops.py | `tensorflow/python/ops/sort_ops.py` | sort関数（29-83行目）とargsort関数（86-150行目） |

**主要処理フロー**:
1. **29-83行目**: `sort`関数 - `@tf_export('sort')`で公開。内部的に`_sort_or_argsort`を`return_argsort=False`で呼び出す
2. **86-150行目**: `argsort`関数 - `@tf_export('argsort')`で公開。stable引数は無視される（148行目`del stable`）
3. **153-183行目**: `_sort_or_argsort` - direction検証、axis定数化、値テンソル変換の共通処理

#### Step 3: ソート実装を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | sort_ops.py | `tensorflow/python/ops/sort_ops.py` | _descending_sort（186-238行目）と_ascending_sort（241-279行目） |

**主要処理フロー**:
- **186-238行目**: `_descending_sort` - 軸が最終軸でない場合はtransposeで移動（206-230行目）し、top_kを実行（232行目）
- **241-279行目**: `_ascending_sort` - データ型に応じた値変換を行い、_descending_sortに委譲。unsigned int（256-260行目）、signed int（262-273行目）、float（275-279行目）の3パターン

### プログラム呼び出し階層図

```
tf.sort() / tf.argsort()
    │
    └─ _sort_or_argsort()
           ├─ direction検証
           ├─ axis定数化
           └─ _SORT_IMPL[direction]()
                  ├─ _ascending_sort()
                  │      └─ _descending_sort(negated_values)
                  │             ├─ transpose（軸移動）
                  │             ├─ nn_ops.top_k()
                  │             └─ transpose（軸復元）
                  └─ _descending_sort()
                         ├─ transpose（軸移動）
                         ├─ nn_ops.top_k()
                         └─ transpose（軸復元）
```

### データフロー図

```
[入力]                 [処理]                          [出力]

values(Tensor) ──▶ direction分岐 ──▶ top_k ──────▶ sorted values
axis(int)      ──▶ transpose制御                      or indices
direction(str) ──▶ 値変換（昇順時）
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| sort_ops.py | `tensorflow/python/ops/sort_ops.py` | ソース | sort/argsort関数の全実装 |
| nn_ops.py | `tensorflow/python/ops/nn_ops.py` | ソース | top_k操作の定義 |
| array_ops.py | `tensorflow/python/ops/array_ops.py` | ソース | transpose、shape操作 |
| math_ops.py | `tensorflow/python/ops/math_ops.py` | ソース | range関数 |
| constant_op.py | `tensorflow/python/framework/constant_op.py` | ソース | 定数テンソル生成 |
| tensor_util.py | `tensorflow/python/framework/tensor_util.py` | ソース | constant_value取得 |
