Skip to content

Instantly share code, notes, and snippets.

@kishida

kishida/AdaptiveQuicksort.java

Last active January 26, 2026 15:50
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save kishida/660d1993a3c64cd2437ea1f14bac2a81 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save kishida/660d1993a3c64cd2437ea1f14bac2a81 to your computer and use it in GitHub Desktop.
Download ZIP
patent US7680791B2 orasort implementation in Java
Raw
AdaptiveQuicksort.java
import java.util.*;
/**
* US7680791B2特許の最適化完全実装: Adaptive Quicksort (AQS) v2
*
* 特許の3つの核心技術を完全実装 + 追加最適化:
* 1. Common Prefix Skipping Quicksort (CPS-QS)
* 2. Key Substring Caching (2バイト + 拡張オプション)
* 3. Adaptive Quicksort (Quicksort ↔ Radix Sort 相互再帰)
*
* 追加最適化:
* - 4バイト/8バイト単位での比較（ワードアラインメント活用）
* - キャッシュ効率を意識したメモリレイアウト
* - より積極的な Radix Sort への切り替え
* - 分岐予測を考慮したコード構造
*
* 参照: https://patents.google.com/patent/US7680791B2
*/
public class AdaptiveQuicksortV2 {
// Key Substring Cache のサイズ（特許では2バイト、ここでは8バイトに拡張）
private static final int KEY_SUBSTRING_CACHE_SIZE = 8;
// 小さい配列では挿入ソートに切り替え
private static final int INSERTION_SORT_THRESHOLD = 24;
// Radix Sort への切り替え閾値（共通接頭辞が増えた時）
private static final int RADIX_THRESHOLD = 32;
// Radix Sort のバケット数
private static final int RADIX_BUCKETS = 256;
/**
* Key Substring Caching を含むソート可能アイテム
* メモリレイアウト最適化版
*/
static final class SortableItem {
final byte[] key; // 実際のキー値
final Object data; // 付随データ
long cachedPrefix; // 8バイトのキャッシュ（long型で高速比較）
int cacheOffset; // キャッシュがどのオフセットから始まるか
SortableItem(byte[] key, Object data) {
this.key = key;
this.data = data;
this.cacheOffset = 0;
updateCache(0);
}
/**
* Key Substring Cache を更新（8バイトをlong型にパック）
*/
void updateCache(int newCommonPrefix) {
this.cacheOffset = newCommonPrefix;
this.cachedPrefix = packBytes(key, newCommonPrefix);
}
/**
* バイト配列の指定位置から最大8バイトをlong型にパック
* ビッグエンディアン順（辞書順比較に適合）
*/
private static long packBytes(byte[] arr, int offset) {
long result = 0;
int remaining = arr.length - offset;
int bytesToPack = Math.min(KEY_SUBSTRING_CACHE_SIZE, remaining);
for (int i = 0; i < bytesToPack; i++) {
result = (result << 8) | (arr[offset + i] & 0xFFL);
}
// 残りをゼロパディング
for (int i = bytesToPack; i < KEY_SUBSTRING_CACHE_SIZE; i++) {
result <<= 8;
}
// キー長情報を最下位に埋め込み（比較時の終端処理用）
return result;
}
@Override
public String toString() {
return new String(key) + " -> " + data;
}
}
/**
* 比較結果と共通接頭辞を保持
*/
record CompareResult(int cmp, int commonPrefixAt) {}
/**
* メインのソート関数
*/
public static void sort(SortableItem[] items) {
if (items == null || items.length <= 1) {
return;
}
// 初期化: 全アイテムのキャッシュをオフセット0で設定
for (SortableItem item : items) {
item.updateCache(0);
}
// AQS Quicksort ステップを開始
aqsQuicksort(items, 0, items.length - 1, 0);
}
/**
* AQS Quicksort ステップ (aqs-qs) - 最適化版
*/
private static void aqsQuicksort(SortableItem[] items, int left, int right, int commonPrefix) {
while (true) { // 末尾再帰最適化
int len = right - left + 1;
if (len <= 1) {
return;
}
if (len <= INSERTION_SORT_THRESHOLD) {
insertionSort(items, left, right, commonPrefix);
return;
}
// ピボット選択（ninther - 9点中央値）
SortableItem pivot = selectPivotNinther(items, left, right, commonPrefix);
// 3-way パーティショニング with 共通接頭辞追跡
PartitionResult result = partition3WayOptimized(items, left, right, pivot, commonPrefix);
// 小さい方のパーティションを先に再帰（スタック深さ制限）
int ltLen = result.ltEnd - left + 1;
int gtLen = right - result.gtStart + 1;
boolean processLtFirst = ltLen <= gtLen;
// 最初のパーティション処理
if (processLtFirst) {
processPartition(items, left, result.ltEnd, result.ltCP, commonPrefix);
} else {
processPartition(items, result.gtStart, right, result.gtCP, commonPrefix);
}
// 2番目のパーティションは末尾再帰で処理
if (processLtFirst) {
if (result.gtStart <= right && gtLen > 1) {
if (result.gtCP > commonPrefix) {
aqsRadixSort(items, result.gtStart, right, result.gtCP, commonPrefix);
return;
}
left = result.gtStart;
// commonPrefixはそのまま、ループ継続
} else {
return;
}
} else {
if (result.ltEnd >= left && ltLen > 1) {
if (result.ltCP > commonPrefix) {
aqsRadixSort(items, left, result.ltEnd, result.ltCP, commonPrefix);
return;
}
right = result.ltEnd;
// commonPrefixはそのまま、ループ継続
} else {
return;
}
}
}
}
/**
* パーティション処理のヘルパー
*/
private static void processPartition(SortableItem[] items, int start, int end, int partitionCP, int inputCP) {
int len = end - start + 1;
if (len <= 1) {
return;
}
if (partitionCP > inputCP) {
// 共通接頭辞が増えた → Radix Sort ステップへ
aqsRadixSort(items, start, end, partitionCP, inputCP);
} else {
// 共通接頭辞が同じ → Quicksort を再帰
aqsQuicksort(items, start, end, inputCP);
}
}
/**
* AQS Radix Sort ステップ (aqs-rdx) - 最適化版
*/
@SuppressWarnings("unchecked")
private static void aqsRadixSort(SortableItem[] items, int left, int right,
int partitioningIndex, int inputCommonPrefix) {
int len = right - left + 1;
if (len <= INSERTION_SORT_THRESHOLD) {
// 小さければ挿入ソートで完了
insertionSort(items, left, right, inputCommonPrefix);
return;
}
// バケット配列（再利用のためスレッドローカルも検討可）
List<SortableItem>[] doneBuckets = new ArrayList[RADIX_BUCKETS];
List<SortableItem>[] moreBuckets = new ArrayList[RADIX_BUCKETS];
List<SortableItem> endedList = new ArrayList<>();
for (int i = 0; i < RADIX_BUCKETS; i++) {
doneBuckets[i] = new ArrayList<>();
moreBuckets[i] = new ArrayList<>();
}
// 新しい共通接頭辞
int newCommonPrefix = partitioningIndex + 1;
boolean needCacheUpdate = (newCommonPrefix > inputCommonPrefix + KEY_SUBSTRING_CACHE_SIZE - 1);
// 各アイテムをバケットに分配
for (int i = left; i <= right; i++) {
SortableItem item = items[i];
int keyLen = item.key.length;
if (keyLen <= partitioningIndex) {
// キーが終了
endedList.add(item);
} else {
int byteVal = item.key[partitioningIndex] & 0xFF;
if (keyLen == partitioningIndex + 1) {
// キーがここで終了
doneBuckets[byteVal].add(item);
} else {
// キーが続く
if (needCacheUpdate) {
item.updateCache(newCommonPrefix);
}
moreBuckets[byteVal].add(item);
}
}
}
// 結果を書き戻し
int writeIndex = left;
// 終了したキー
for (SortableItem item : endedList) {
items[writeIndex++] = item;
}
// バケット順に処理
for (int bucket = 0; bucket < RADIX_BUCKETS; bucket++) {
// done バケット
for (SortableItem item : doneBuckets[bucket]) {
items[writeIndex++] = item;
}
// more バケット
List<SortableItem> moreList = moreBuckets[bucket];
int moreSize = moreList.size();
if (moreSize > 0) {
int moreStart = writeIndex;
for (SortableItem item : moreList) {
items[writeIndex++] = item;
}
if (moreSize > 1) {
// Quicksort ステップへ
aqsQuicksort(items, moreStart, writeIndex - 1, newCommonPrefix);
}
}
}
}
/**
* パーティション結果
*/
record PartitionResult(
int ltEnd, // less than の最後のインデックス
int gtStart, // greater than の最初のインデックス
int ltCP, // less than パーティションの共通接頭辞
int gtCP // greater than パーティションの共通接頭辞
) {}
/**
* 最適化された3-way パーティショニング
* Bentley-McIlroy方式 + 共通接頭辞追跡
*/
private static PartitionResult partition3WayOptimized(SortableItem[] items, int left, int right,
SortableItem pivot, int commonPrefix) {
byte[] pivotKey = pivot.key;
int lt = left;
int gt = right;
int i = left;
int ltCP = Integer.MAX_VALUE;
int gtCP = Integer.MAX_VALUE;
while (i <= gt) {
CompareResult result = compareWithCPFast(items[i], pivotKey, commonPrefix);
if (result.cmp < 0) {
ltCP = Math.min(ltCP, result.commonPrefixAt);
swap(items, lt++, i++);
} else if (result.cmp > 0) {
gtCP = Math.min(gtCP, result.commonPrefixAt);
swap(items, i, gt--);
} else {
i++;
}
}
if (ltCP == Integer.MAX_VALUE) ltCP = commonPrefix;
if (gtCP == Integer.MAX_VALUE) gtCP = commonPrefix;
return new PartitionResult(lt - 1, gt + 1, ltCP, gtCP);
}
/**
* 高速キー比較（キャッシュ活用）
*/
private static CompareResult compareWithCPFast(SortableItem item, byte[] pivotKey, int commonPrefix) {
byte[] itemKey = item.key;
int itemLen = itemKey.length;
int pivotLen = pivotKey.length;
int minLen = Math.min(itemLen, pivotLen);
// キャッシュが有効な範囲ではlong比較を使用
if (commonPrefix == item.cacheOffset && commonPrefix + KEY_SUBSTRING_CACHE_SIZE <= minLen) {
// キャッシュ内で比較可能
long itemCached = item.cachedPrefix;
long pivotCached = packBytesStatic(pivotKey, commonPrefix);
// 上位ビットから比較（符号なし比較）
if (itemCached != pivotCached) {
// 最初の相違点を見つける
long diff = itemCached ^ pivotCached;
int leadingZeros = Long.numberOfLeadingZeros(diff);
int diffByte = leadingZeros / 8;
int diffIndex = commonPrefix + diffByte;
int itemByte = (int)((itemCached >>> (56 - diffByte * 8)) & 0xFF);
int pivotByte = (int)((pivotCached >>> (56 - diffByte * 8)) & 0xFF);
return new CompareResult(itemByte - pivotByte, diffIndex);
}
// キャッシュ部分は同じ、続きを比較
int i = commonPrefix + KEY_SUBSTRING_CACHE_SIZE;
while (i < minLen) {
int diff = (itemKey[i] & 0xFF) - (pivotKey[i] & 0xFF);
if (diff != 0) {
return new CompareResult(diff, i);
}
i++;
}
return new CompareResult(itemLen - pivotLen, i);
}
// フォールバック: バイト単位比較
int i = commonPrefix;
while (i < minLen) {
int diff = (itemKey[i] & 0xFF) - (pivotKey[i] & 0xFF);
if (diff != 0) {
return new CompareResult(diff, i);
}
i++;
}
return new CompareResult(itemLen - pivotLen, i);
}
/**
* 静的なバイトパック（ピボット用）
*/
private static long packBytesStatic(byte[] arr, int offset) {
long result = 0;
int remaining = arr.length - offset;
int bytesToPack = Math.min(KEY_SUBSTRING_CACHE_SIZE, remaining);
for (int i = 0; i < bytesToPack; i++) {
result = (result << 8) | (arr[offset + i] & 0xFFL);
}
for (int i = bytesToPack; i < KEY_SUBSTRING_CACHE_SIZE; i++) {
result <<= 8;
}
return result;
}
/**
* Ninther ピボット選択（9点の中央値の中央値）
*/
private static SortableItem selectPivotNinther(SortableItem[] items, int left, int right, int commonPrefix) {
int len = right - left + 1;
if (len < 9) {
return medianOf3(items, left, left + len/2, right, commonPrefix);
}
int step = len / 8;
// 3つの中央値を取得
SortableItem m1 = medianOf3(items, left, left + step, left + 2*step, commonPrefix);
SortableItem m2 = medianOf3(items, left + 3*step, left + 4*step, left + 5*step, commonPrefix);
SortableItem m3 = medianOf3(items, left + 6*step, left + 7*step, right, commonPrefix);
// 3つの中央値の中央値
return medianOf3Items(m1, m2, m3, commonPrefix);
}
private static SortableItem medianOf3(SortableItem[] items, int a, int b, int c, int cp) {
return medianOf3Items(items[a], items[b], items[c], cp);
}
private static SortableItem medianOf3Items(SortableItem a, SortableItem b, SortableItem c, int cp) {
int ab = compareSimple(a.key, b.key, cp);
int bc = compareSimple(b.key, c.key, cp);
int ac = compareSimple(a.key, c.key, cp);
if (ab < 0) {
if (bc < 0) return b;
else if (ac < 0) return c;
else return a;
} else {
if (bc > 0) return b;
else if (ac > 0) return c;
else return a;
}
}
private static int compareSimple(byte[] a, byte[] b, int cp) {
int minLen = Math.min(a.length, b.length);
for (int i = cp; i < minLen; i++) {
int diff = (a[i] & 0xFF) - (b[i] & 0xFF);
if (diff != 0) return diff;
}
return a.length - b.length;
}
/**
* 挿入ソート（小さい配列用）- ガード付き最適化
*/
private static void insertionSort(SortableItem[] items, int left, int right, int commonPrefix) {
// 最小要素を先頭に移動（ガード）
int minIdx = left;
for (int i = left + 1; i <= right; i++) {
if (compareSimple(items[i].key, items[minIdx].key, commonPrefix) < 0) {
minIdx = i;
}
}
if (minIdx != left) {
swap(items, left, minIdx);
}
// ガード付き挿入ソート
for (int i = left + 2; i <= right; i++) {
SortableItem key = items[i];
int j = i - 1;
while (compareSimple(items[j].key, key.key, commonPrefix) > 0) {
items[j + 1] = items[j];
j--;
}
items[j + 1] = key;
}
}
private static void swap(SortableItem[] items, int i, int j) {
SortableItem temp = items[i];
items[i] = items[j];
items[j] = temp;
}
// ========================================
// テストとベンチマーク
// ========================================
public static void main(String[] args) {
System.out.println("=== US7680791B2 Adaptive Quicksort V2 (最適化版) ===\n");
basicTest();
correctnessTest();
performanceTest();
}
private static void basicTest() {
System.out.println("【基本動作テスト】");
SortableItem[] items = {
new SortableItem("apple".getBytes(), 1),
new SortableItem("application".getBytes(), 2),
new SortableItem("apply".getBytes(), 3),
new SortableItem("banana".getBytes(), 4),
new SortableItem("band".getBytes(), 5),
new SortableItem("bandana".getBytes(), 6),
new SortableItem("cat".getBytes(), 7),
new SortableItem("car".getBytes(), 8),
new SortableItem("card".getBytes(), 9),
new SortableItem("apple".getBytes(), 10),
};
System.out.println("ソート前:");
for (SortableItem item : items) {
System.out.println(" " + item);
}
sort(items);
System.out.println("\nソート後:");
for (SortableItem item : items) {
System.out.println(" " + item);
}
boolean isSorted = verifySorted(items);
System.out.println("\n結果: " + (isSorted ? "✓ 成功" : "✗ 失敗"));
System.out.println();
}
private static void correctnessTest() {
System.out.println("【正確性検証テスト】");
int[] testCases = {10, 100, 1000, 5000, 10000};
Random rand = new Random(12345);
for (int size : testCases) {
boolean allPassed = true;
// 様々なパターンでテスト
String[] patterns = {"ランダム", "長接頭辞", "重複多", "ソート済", "逆順"};
SortableItem[][] testData = {
generateRandomData(size, rand),
generateLongPrefixData(size, rand),
generateDuplicateData(size, rand),
generateSortedData(size),
generateReverseSortedData(size)
};
for (int p = 0; p < patterns.length; p++) {
sort(testData[p]);
if (!verifySorted(testData[p])) {
System.out.println(" サイズ " + size + " " + patterns[p] + ": ✗ 失敗");
allPassed = false;
}
}
if (allPassed) {
System.out.println(" サイズ " + size + ": ✓ 全パターン成功");
}
}
System.out.println();
}
private static void performanceTest() {
System.out.println("【パフォーマンステスト】");
System.out.println("各テスト: 15回実行、最初5回ウォームアップ、残り10回の中間値\n");
int[] sizes = {1000, 5000, 10000, 50000, 100000};
System.out.println("1. ランダムデータ:");
for (int size : sizes) {
BenchmarkResult r = runBenchmark(size, AdaptiveQuicksortV2::generateRandomData);
printResult(size, r);
}
System.out.println("\n2. 長い共通接頭辞 (AQS有利なケース):");
for (int size : sizes) {
BenchmarkResult r = runBenchmark(size, AdaptiveQuicksortV2::generateLongPrefixData);
printResult(size, r);
}
System.out.println("\n3. 非常に長い共通接頭辞 (DB的パターン):");
for (int size : sizes) {
BenchmarkResult r = runBenchmark(size, AdaptiveQuicksortV2::generateDatabaseLikeData);
printResult(size, r);
}
System.out.println("\n4. 重複キー多数 (3-way partitioning有利):");
for (int size : sizes) {
BenchmarkResult r = runBenchmark(size, AdaptiveQuicksortV2::generateDuplicateData);
printResult(size, r);
}
System.out.println("\n5. ほぼソート済み:");
for (int size : sizes) {
BenchmarkResult r = runBenchmark(size, AdaptiveQuicksortV2::generateNearlySortedData);
printResult(size, r);
}
System.out.println("\n6. 完全ランダムバイト:");
for (int size : sizes) {
BenchmarkResult r = runBenchmark(size, AdaptiveQuicksortV2::generatePureRandomData);
printResult(size, r);
}
}
// データ生成
private static SortableItem[] generateRandomData(int size, Random rand) {
SortableItem[] items = new SortableItem[size];
for (int i = 0; i < size; i++) {
String prefix = "prefix_" + rand.nextInt(10);
String suffix = "_" + String.format("%08d", rand.nextInt(100000));
items[i] = new SortableItem((prefix + suffix).getBytes(), i);
}
return items;
}
private static SortableItem[] generateLongPrefixData(int size, Random rand) {
SortableItem[] items = new SortableItem[size];
String prefix = "long_common_prefix_that_is_very_long_";
for (int i = 0; i < size; i++) {
String suffix = String.format("%020d", rand.nextInt(1000000));
items[i] = new SortableItem((prefix + suffix).getBytes(), i);
}
return items;
}
private static SortableItem[] generateDatabaseLikeData(int size, Random rand) {
SortableItem[] items = new SortableItem[size];
String prefix = "database_schema_table_column_index_";
for (int i = 0; i < size; i++) {
String suffix = String.format("%010d_%05d", rand.nextInt(10000000), rand.nextInt(100000));
items[i] = new SortableItem((prefix + suffix).getBytes(), i);
}
return items;
}
private static SortableItem[] generateDuplicateData(int size, Random rand) {
SortableItem[] items = new SortableItem[size];
String[] keys = new String[100];
for (int i = 0; i < 100; i++) {
keys[i] = "duplicate_key_" + String.format("%03d", i);
}
for (int i = 0; i < size; i++) {
items[i] = new SortableItem(keys[rand.nextInt(100)].getBytes(), i);
}
return items;
}
private static SortableItem[] generateNearlySortedData(int size, Random rand) {
SortableItem[] items = new SortableItem[size];
String prefix = "sorted_";
for (int i = 0; i < size; i++) {
String suffix = String.format("%010d", i + rand.nextInt(10));
items[i] = new SortableItem((prefix + suffix).getBytes(), i);
}
return items;
}
private static SortableItem[] generatePureRandomData(int size, Random rand) {
SortableItem[] items = new SortableItem[size];
for (int i = 0; i < size; i++) {
byte[] key = new byte[20 + rand.nextInt(30)];
rand.nextBytes(key);
items[i] = new SortableItem(key, i);
}
return items;
}
private static SortableItem[] generateSortedData(int size) {
SortableItem[] items = new SortableItem[size];
for (int i = 0; i < size; i++) {
items[i] = new SortableItem(String.format("key_%010d", i).getBytes(), i);
}
return items;
}
private static SortableItem[] generateReverseSortedData(int size) {
SortableItem[] items = new SortableItem[size];
for (int i = 0; i < size; i++) {
items[i] = new SortableItem(String.format("key_%010d", size - i).getBytes(), i);
}
return items;
}
// ベンチマーク
record BenchmarkResult(double timeAQS, double timeStd, double stdDevAQS, double stdDevStd) {}
@FunctionalInterface
interface DataGenerator {
SortableItem[] generate(int size, Random rand);
}
static class KeyHolder implements Comparable<KeyHolder> {
final byte[] key;
KeyHolder(byte[] key) { this.key = key; }
@Override
public int compareTo(KeyHolder other) {
return Arrays.compareUnsigned(key, 0, key.length, other.key, 0, other.key.length);
}
}
private static BenchmarkResult runBenchmark(int size, DataGenerator generator) {
final int TOTAL_RUNS = 15;
final int WARMUP_RUNS = 5;
final int VALID_RUNS = TOTAL_RUNS - WARMUP_RUNS;
double[] timesAQS = new double[VALID_RUNS];
double[] timesStd = new double[VALID_RUNS];
for (int run = 0; run < TOTAL_RUNS; run++) {
Random rand = new Random(42 + run);
SortableItem[] items1 = generator.generate(size, rand);
KeyHolder[] items2 = new KeyHolder[size];
for (int i = 0; i < size; i++) {
items2[i] = new KeyHolder(items1[i].key.clone());
}
long start1 = System.nanoTime();
sort(items1);
long end1 = System.nanoTime();
double timeAQS = (end1 - start1) / 1_000_000.0;
long start2 = System.nanoTime();
Arrays.sort(items2);
long end2 = System.nanoTime();
double timeStd = (end2 - start2) / 1_000_000.0;
if (run >= WARMUP_RUNS) {
int index = run - WARMUP_RUNS;
timesAQS[index] = timeAQS;
timesStd[index] = timeStd;
}
}
double avgAQS = calculateTrimmedMean(timesAQS);
double avgStd = calculateTrimmedMean(timesStd);
double stdDevAQS = calculateStdDev(timesAQS, avgAQS);
double stdDevStd = calculateStdDev(timesStd, avgStd);
return new BenchmarkResult(avgAQS, avgStd, stdDevAQS, stdDevStd);
}
private static double calculateTrimmedMean(double[] values) {
double[] sorted = values.clone();
Arrays.sort(sorted);
double sum = 0;
for (int i = 1; i < sorted.length - 1; i++) {
sum += sorted[i];
}
return sum / (sorted.length - 2);
}
private static double calculateStdDev(double[] values, double mean) {
double[] sorted = values.clone();
Arrays.sort(sorted);
double sumSquaredDiff = 0;
for (int i = 1; i < sorted.length - 1; i++) {
double diff = sorted[i] - mean;
sumSquaredDiff += diff * diff;
}
return Math.sqrt(sumSquaredDiff / (sorted.length - 2));
}
private static void printResult(int size, BenchmarkResult r) {
double speedup = r.timeStd / r.timeAQS;
String analysis;
if (speedup > 1.1) {
analysis = "AQS有利 ↑";
} else if (speedup < 0.9) {
analysis = "標準有利 ↓";
} else {
analysis = "同等 →";
}
System.out.printf(" N=%,7d: AQS=%.2fms (±%.2f), Std=%.2fms (±%.2f), 比=%.2fx %s%n",
size, r.timeAQS, r.stdDevAQS, r.timeStd, r.stdDevStd, speedup, analysis);
}
private static boolean verifySorted(SortableItem[] items) {
for (int i = 0; i < items.length - 1; i++) {
if (Arrays.compareUnsigned(items[i].key, items[i+1].key) > 0) {
return false;
}
}
return true;
}
}
@kishida
Copy link
Author

kishida commented Jan 26, 2026 

=== US7680791B2 Adaptive Quicksort V2 (最適化版) ===

【基本動作テスト】
ソート前:
  apple -> 1
  application -> 2
  apply -> 3
  banana -> 4
  band -> 5
  bandana -> 6
  cat -> 7
  car -> 8
  card -> 9
  apple -> 10

ソート後:
  apple -> 1
  apple -> 10
  application -> 2
  apply -> 3
  banana -> 4
  band -> 5
  bandana -> 6
  car -> 8
  card -> 9
  cat -> 7

結果: ✓ 成功

【正確性検証テスト】
  サイズ 10: ✓ 全パターン成功
  サイズ 100: ✓ 全パターン成功
  サイズ 1000: ✓ 全パターン成功
  サイズ 5000: ✓ 全パターン成功
  サイズ 10000: ✓ 全パターン成功

【パフォーマンステスト】
各テスト: 15回実行、最初5回ウォームアップ、残り10回の中間値

1. ランダムデータ:
  N=  1,000: AQS=0.47ms (±0.04), Std=0.42ms (±0.15), 比=0.88x 標準有利 ↓
  N=  5,000: AQS=2.59ms (±0.78), Std=4.30ms (±0.92), 比=1.66x AQS有利 ↑
  N= 10,000: AQS=4.99ms (±0.88), Std=5.18ms (±0.99), 比=1.04x 同等 →
  N= 50,000: AQS=34.50ms (±1.09), Std=17.46ms (±1.54), 比=0.51x 標準有利 ↓
  N=100,000: AQS=71.49ms (±4.34), Std=38.51ms (±0.93), 比=0.54x 標準有利 ↓

2. 長い共通接頭辞 (AQS有利なケース):
  N=  1,000: AQS=0.15ms (±0.01), Std=0.18ms (±0.00), 比=1.18x AQS有利 ↑
  N=  5,000: AQS=1.45ms (±0.10), Std=1.14ms (±0.02), 比=0.78x 標準有利 ↓
  N= 10,000: AQS=3.81ms (±0.25), Std=2.78ms (±0.15), 比=0.73x 標準有利 ↓
  N= 50,000: AQS=38.15ms (±0.69), Std=20.65ms (±1.92), 比=0.54x 標準有利 ↓
  N=100,000: AQS=82.76ms (±3.34), Std=48.47ms (±1.38), 比=0.59x 標準有利 ↓

3. 非常に長い共通接頭辞 (DB的パターン):
  N=  1,000: AQS=0.16ms (±0.01), Std=0.18ms (±0.00), 比=1.17x AQS有利 ↑
  N=  5,000: AQS=1.46ms (±0.09), Std=1.16ms (±0.02), 比=0.80x 標準有利 ↓
  N= 10,000: AQS=3.91ms (±0.25), Std=2.48ms (±0.04), 比=0.63x 標準有利 ↓
  N= 50,000: AQS=40.80ms (±1.33), Std=20.21ms (±0.42), 比=0.50x 標準有利 ↓
  N=100,000: AQS=88.82ms (±2.29), Std=47.62ms (±0.63), 比=0.54x 標準有利 ↓

4. 重複キー多数 (3-way partitioning有利):
  N=  1,000: AQS=0.09ms (±0.00), Std=0.18ms (±0.00), 比=2.05x AQS有利 ↑
  N=  5,000: AQS=0.38ms (±0.01), Std=1.44ms (±0.04), 比=3.77x AQS有利 ↑
  N= 10,000: AQS=0.77ms (±0.02), Std=2.77ms (±0.19), 比=3.61x AQS有利 ↑
  N= 50,000: AQS=5.12ms (±0.25), Std=11.53ms (±0.26), 比=2.25x AQS有利 ↑
  N=100,000: AQS=15.14ms (±0.40), Std=23.62ms (±0.19), 比=1.56x AQS有利 ↑

5. ほぼソート済み:
  N=  1,000: AQS=0.13ms (±0.00), Std=0.08ms (±0.01), 比=0.67x 標準有利 ↓
  N=  5,000: AQS=0.96ms (±0.02), Std=0.41ms (±0.02), 比=0.42x 標準有利 ↓
  N= 10,000: AQS=2.30ms (±0.15), Std=0.76ms (±0.01), 比=0.33x 標準有利 ↓
  N= 50,000: AQS=20.69ms (±0.43), Std=3.80ms (±0.06), 比=0.18x 標準有利 ↓
  N=100,000: AQS=53.23ms (±1.41), Std=7.63ms (±0.13), 比=0.14x 標準有利 ↓

6. 完全ランダムバイト:
  N=  1,000: AQS=0.16ms (±0.01), Std=0.33ms (±0.08), 比=2.09x AQS有利 ↑
  N=  5,000: AQS=0.97ms (±0.01), Std=1.57ms (±0.02), 比=1.61x AQS有利 ↑
  N= 10,000: AQS=2.32ms (±0.17), Std=2.57ms (±0.62), 比=1.11x AQS有利 ↑
  N= 50,000: AQS=15.90ms (±0.73), Std=16.74ms (±0.34), 比=1.05x 同等 →
  N=100,000: AQS=40.88ms (±1.22), Std=40.00ms (±0.78), 比=0.98x 同等 →

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment