# コード例1: サブドメインテイクオーバーの検出スクリプト
import dns.resolver
import requests
 
KNOWN_FINGERPRINTS = {
    "github.io": "There isn't a GitHub Pages site here",
    "herokuapp.com": "No such app",
    "s3.amazonaws.com": "NoSuchBucket",
    "azurewebsites.net": "404 Web Site not found",
    "cloudfront.net": "Bad Request: ERROR: The request could not be satisfied",
    "netlify.app": "Not Found - Request ID:",
}
 
def check_subdomain_takeover(domain: str) -> dict:
    """サブドメインテイクオーバーの脆弱性をチェック"""
    result = {"domain": domain, "vulnerable": False, "details": ""}
 
    try:
        # CNAME レコードを取得
        answers = dns.resolver.resolve(domain, "CNAME")
        for rdata in answers:
            cname_target = str(rdata.target).rstrip(".")
            result["cname"] = cname_target
 
            # 既知のサービスのフィンガープリントをチェック
            for service, fingerprint in KNOWN_FINGERPRINTS.items():
                if service in cname_target:
                    try:
                        resp = requests.get(
                            f"http://{domain}",
                            timeout=10,
                            allow_redirects=True
                        )
                        if fingerprint in resp.text:
                            result["vulnerable"] = True
                            result["details"] = (
                                f"CNAME points to {cname_target} "
                                f"but the resource does not exist"
                            )
                    except requests.RequestException:
                        result["details"] = f"CNAME target unreachable: {cname_target}"
 
    except dns.resolver.NXDOMAIN:
        result["details"] = "Domain does not exist"
    except dns.resolver.NoAnswer:
        result["details"] = "No CNAME record"
    except Exception as e:
        result["details"] = str(e)
 
    return result
 
# 使用例
subdomains = ["blog.example.com", "staging.example.com", "old.example.com"]
for sub in subdomains:
    result = check_subdomain_takeover(sub)
    if result["vulnerable"]:
        print(f"[VULNERABLE] {result['domain']}: {result['details']}")

# コード例2: BIND での DNSSEC 設定
 
# ===== 鍵の生成 =====
 
# ゾーン署名鍵 (ZSK) の生成
# ECDSAP256SHA256 を推奨（RSA より鍵サイズが小さく高速）
dnssec-keygen -a ECDSAP256SHA256 -n ZONE example.com
# 出力: Kexample.com.+013+12345 (.key と .private)
 
# 鍵署名鍵 (KSK) の生成
dnssec-keygen -a ECDSAP256SHA256 -n ZONE -f KSK example.com
# 出力: Kexample.com.+013+67890 (.key と .private)
 
# ===== ゾーンファイルの署名 =====
 
# NSEC3 を使用したゾーン署名
dnssec-signzone -A -3 $(head -c 1000 /dev/urandom | sha1sum | cut -b 1-16) \
  -N INCREMENT -o example.com -t db.example.com
 
# 出力: db.example.com.signed
 
# ===== BIND 設定 (named.conf) =====
# DNSSEC 検証を有効化（リゾルバ側）
options {
    dnssec-validation auto;  # トラストアンカーの自動更新 (RFC 5011)
    # dnssec-validation yes; # 手動でトラストアンカーを管理する場合
};
 
# 権威サーバでの DNSSEC 設定
zone "example.com" {
    type primary;
    file "/etc/bind/zones/db.example.com.signed";
    key-directory "/etc/bind/keys";
 
    # 自動署名 (inline-signing)
    inline-signing yes;
    auto-dnssec maintain;
 
    # NSEC3 パラメータの設定
    # rndc signing -nsec3param 1 0 10 auto example.com
};
 
# ===== 鍵のロールオーバー =====
# ZSK のロールオーバー（推奨: 90日ごと）
# 1. 新しい ZSK を事前公開 (pre-publish)
# 2. TTL 経過後に新 ZSK で署名
# 3. 旧 ZSK を削除
 
# KSK のロールオーバー（推奨: 1-2年ごと）
# 1. 新 KSK を生成・公開
# 2. 親ゾーンに新 DS レコードを登録
# 3. 旧 KSK で新 KSK を署名
# 4. 旧 DS レコードを削除
# 5. 旧 KSK を削除

# コード例3: DNSSEC の検証コマンド集
 
# DNSSEC 情報付きで問い合わせ
dig +dnssec example.com A
 
# 検証結果の確認 (flags に ad が含まれれば検証成功)
# ;; flags: qr rd ra ad; QUERY: 1, ANSWER: 2
# ad = Authenticated Data (DNSSEC検証成功)
 
# DNSKEY レコードの確認
dig example.com DNSKEY +short
# 257 3 13 oJMRESz5E4gYzS/... (KSK, flags=257)
# 256 3 13 2Nwz6FfpJlWey/... (ZSK, flags=256)
 
# DS レコードの確認
dig example.com DS +short
# 67890 13 2 ABC123DEF456...
 
# RRSIG の確認（署名の有効期間を含む）
dig example.com A +dnssec +multi
# example.com. 3600 IN RRSIG A 13 2 3600 (
#     20260301000000 20260201000000 12345 example.com.
#     base64signature... )
 
# NSEC3 による不在証明の確認
dig nonexistent.example.com A +dnssec
# NSEC3 レコードが返り、ドメインが存在しないことを証明
 
# 信頼チェーンの完全な検証
dig +sigchase +trusted-key=./root.keys example.com A
 
# delv コマンドによる検証（BIND 9.10+）
delv @8.8.8.8 example.com A +rtrace
# ;; validating example.com/A: verify rdataset (keyid: 12345)
# ;; fully validated
 
# DNSSEC が有効なドメインの例
dig +dnssec cloudflare.com A   # Cloudflare
dig +dnssec nic.cz A           # CZ NIC
dig +dnssec isc.org A          # ISC (BIND開発元)

# コード例4: 各種 DoH/DoT の設定
 
# ===== dnscrypt-proxy で DoH を利用 =====
# /etc/dnscrypt-proxy/dnscrypt-proxy.toml
listen_addresses = ['127.0.0.1:53']
server_names = ['cloudflare', 'google']
ipv6_servers = false
 
# セキュリティ設定
require_dnssec = true          # DNSSEC 検証必須
require_nofilter = true        # フィルタリングなし
require_nolog = true           # ログなしサーバのみ
 
[sources]
  [sources.public-resolvers]
  urls = ['https://raw.githubusercontent.com/DNSCrypt/dnscrypt-resolvers/master/v3/public-resolvers.md']
  cache_file = 'public-resolvers.md'
  minisign_key = 'RWQf6LRCGA9i53mlYecO4IzT51TGPpvWucNSCh1CBM0QTaLn73Y7GFO3'
 
# ===== systemd-resolved で DoT を有効化 =====
# /etc/systemd/resolved.conf
[Resolve]
DNS=1.1.1.1#cloudflare-dns.com 1.0.0.1#cloudflare-dns.com
FallbackDNS=8.8.8.8#dns.google 8.8.4.4#dns.google
DNSOverTLS=yes
DNSSEC=yes
 
# 設定反映
# sudo systemctl restart systemd-resolved
# resolvectl status で確認
 
# ===== Unbound で DoT を設定 =====
# /etc/unbound/unbound.conf
server:
    interface: 127.0.0.1
    interface: ::1
    tls-cert-bundle: /etc/ssl/certs/ca-certificates.crt
 
    # DNSSEC 検証
    auto-trust-anchor-file: "/var/lib/unbound/root.key"
    val-clean-additional: yes
 
forward-zone:
    name: "."
    forward-tls-upstream: yes
    # Cloudflare DNS over TLS
    forward-addr: 1.1.1.1@853#cloudflare-dns.com
    forward-addr: 1.0.0.1@853#cloudflare-dns.com
    # Google DNS over TLS
    forward-addr: 8.8.8.8@853#dns.google
    forward-addr: 8.8.4.4@853#dns.google

// コード例5: 完全な DoH クライアント実装 (Go)
package main
 
import (
	"bytes"
	"context"
	"crypto/tls"
	"fmt"
	"io"
	"net"
	"net/http"
	"time"
 
	"github.com/miekg/dns"
)
 
// DoHClient は DNS over HTTPS クライアント
type DoHClient struct {
	httpClient *http.Client
	serverURL  string
}
 
// NewDoHClient は新しい DoH クライアントを生成する
func NewDoHClient(serverURL string) *DoHClient {
	return &DoHClient{
		httpClient: &http.Client{
			Timeout: 10 * time.Second,
			Transport: &http.Transport{
				TLSClientConfig: &tls.Config{
					MinVersion: tls.VersionTLS13,
				},
				MaxIdleConns:        100,
				IdleConnTimeout:     90 * time.Second,
				TLSHandshakeTimeout: 10 * time.Second,
			},
		},
		serverURL: serverURL,
	}
}
 
// Query は DoH で DNS クエリを実行する
func (c *DoHClient) Query(domain string, qtype uint16) (*dns.Msg, error) {
	// DNS メッセージを構築
	msg := new(dns.Msg)
	msg.SetQuestion(dns.Fqdn(domain), qtype)
	msg.RecursionDesired = true
 
	// EDNS0 パディング (RFC 7830)
	opt := &dns.OPT{
		Hdr: dns.RR_Header{Name: ".", Rrtype: dns.TypeOPT},
		Option: []dns.EDNS0{
			&dns.EDNS0_PADDING{Padding: make([]byte, 128)},
		},
	}
	opt.SetUDPSize(4096)
	opt.SetDo(true) // DNSSEC OK フラグ
	msg.Extra = append(msg.Extra, opt)
 
	// Wire format にエンコード
	packed, err := msg.Pack()
	if err != nil {
		return nil, fmt.Errorf("failed to pack DNS message: %w", err)
	}
 
	// DoH POST リクエスト
	req, err := http.NewRequest(
		"POST",
		c.serverURL,
		bytes.NewReader(packed),
	)
	if err != nil {
		return nil, err
	}
	req.Header.Set("Content-Type", "application/dns-message")
	req.Header.Set("Accept", "application/dns-message")
 
	resp, err := c.httpClient.Do(req)
	if err != nil {
		return nil, fmt.Errorf("DoH request failed: %w", err)
	}
	defer resp.Body.Close()
 
	if resp.StatusCode != http.StatusOK {
		return nil, fmt.Errorf("DoH server returned status %d", resp.StatusCode)
	}
 
	body, err := io.ReadAll(resp.Body)
	if err != nil {
		return nil, err
	}
 
	response := new(dns.Msg)
	if err := response.Unpack(body); err != nil {
		return nil, fmt.Errorf("failed to unpack DNS response: %w", err)
	}
 
	return response, nil
}
 
// QueryWithDNSSECValidation は DNSSEC 検証付きクエリ
func (c *DoHClient) QueryWithDNSSECValidation(domain string) ([]net.IP, bool, error) {
	resp, err := c.Query(domain, dns.TypeA)
	if err != nil {
		return nil, false, err
	}
 
	var ips []net.IP
	authenticated := resp.AuthenticatedData // AD フラグ
 
	for _, answer := range resp.Answer {
		if a, ok := answer.(*dns.A); ok {
			ips = append(ips, a.A)
		}
	}
 
	return ips, authenticated, nil
}
 
func main() {
	client := NewDoHClient("https://cloudflare-dns.com/dns-query")
 
	ips, dnssecValid, err := client.QueryWithDNSSECValidation("cloudflare.com")
	if err != nil {
		fmt.Printf("Error: %v\n", err)
		return
	}
 
	fmt.Printf("IPs: %v\n", ips)
	fmt.Printf("DNSSEC validated: %v\n", dnssecValid)
}

# コード例6: Python DoH クライアント
import dns.message
import dns.query
import dns.rdatatype
import httpx
import base64
 
class DoHResolver:
    """DNS over HTTPS リゾルバ"""
 
    def __init__(self, server_url: str = "https://cloudflare-dns.com/dns-query"):
        self.server_url = server_url
        self.client = httpx.Client(
            http2=True,
            timeout=10.0,
            headers={"Accept": "application/dns-message"}
        )
 
    def resolve(self, domain: str, rdtype: str = "A") -> list:
        """DoH でドメインを解決"""
        # DNS クエリメッセージの構築
        query = dns.message.make_query(domain, rdtype, want_dnssec=True)
        wire = query.to_wire()
 
        # POST リクエスト
        response = self.client.post(
            self.server_url,
            content=wire,
            headers={"Content-Type": "application/dns-message"}
        )
        response.raise_for_status()
 
        # レスポンスの解析
        dns_response = dns.message.from_wire(response.content)
 
        results = []
        for rrset in dns_response.answer:
            for rdata in rrset:
                results.append({
                    "name": str(rrset.name),
                    "type": dns.rdatatype.to_text(rrset.rdtype),
                    "ttl": rrset.ttl,
                    "data": str(rdata),
                })
 
        return {
            "answers": results,
            "dnssec_validated": bool(dns_response.flags & dns.flags.AD),
            "rcode": dns.rcode.to_text(dns_response.rcode()),
        }
 
    def close(self):
        self.client.close()
 
 
# 使用例
resolver = DoHResolver()
result = resolver.resolve("example.com", "A")
print(f"Answers: {result['answers']}")
print(f"DNSSEC: {result['dnssec_validated']}")
resolver.close()

# コード例7: BIND での RPZ 設定
 
# /etc/bind/named.conf
options {
    response-policy {
        zone "rpz.local" policy given;
        zone "rpz.spamhaus" policy given;
    };
};
 
zone "rpz.local" {
    type primary;
    file "/etc/bind/db.rpz.local";
    allow-query { none; };
};
 
# RPZ ゾーンファイル (/etc/bind/db.rpz.local)
$TTL 300
@ IN SOA localhost. admin.localhost. ( 1 3600 900 604800 300 )
@ IN NS localhost.
 
; ===== マルウェアドメインのブロック =====
; NXDOMAIN を返す（最も安全）
malware.example.com   CNAME .
*.malware.example.com CNAME .
 
; ===== フィッシングサイトをブロックページにリダイレクト =====
phishing.example.com  A     10.0.0.100
*.phishing.example.com A    10.0.0.100
 
; ===== 特定のIPアドレスへのアクセスをブロック =====
; C2サーバのIPをブロック
32.1.168.192.rpz-ip     CNAME .
 
; ===== ワイルドカードによる大量ブロック =====
; DGA (Domain Generation Algorithm) 対策
*.dga-pattern.com  CNAME .
 
; ===== パススルー (ブロック除外) =====
; RPZ ルールの例外
safe.malware.example.com CNAME rpz-passthru.

# コード例8: CAA レコードの設定
 
# CAA (Certificate Authority Authorization) レコード
# 指定した CA のみがドメインの証明書を発行できる
 
# Let's Encrypt のみ許可
example.com.  CAA 0 issue "letsencrypt.org"
 
# ワイルドカード証明書は DigiCert のみ
example.com.  CAA 0 issuewild "digicert.com"
 
# 証明書発行に関する問題を報告するメールアドレス
example.com.  CAA 0 iodef "mailto:security@example.com"
 
# 設定確認
dig example.com CAA +short
# 0 issue "letsencrypt.org"
# 0 issuewild "digicert.com"
# 0 iodef "mailto:security@example.com"

# コード例9: DNS トンネリング検知スクリプト (拡張版)
import collections
import math
import re
from datetime import datetime, timedelta
from dataclasses import dataclass
 
@dataclass
class DNSQuery:
    timestamp: datetime
    src_ip: str
    qname: str
    qtype: str
 
def shannon_entropy(s: str) -> float:
    """文字列のシャノンエントロピーを計算"""
    if not s:
        return 0.0
    probabilities = [
        count / len(s)
        for count in collections.Counter(s).values()
    ]
    return -sum(p * math.log2(p) for p in probabilities)
 
def extract_base_domain(qname: str) -> str:
    """サブドメインを除去してベースドメインを抽出"""
    parts = qname.rstrip(".").split(".")
    if len(parts) >= 2:
        return ".".join(parts[-2:])
    return qname
 
def get_subdomain_labels(qname: str) -> str:
    """ベースドメインを除いたサブドメイン部分を取得"""
    parts = qname.rstrip(".").split(".")
    if len(parts) > 2:
        return ".".join(parts[:-2])
    return ""
 
class DNSTunnelDetector:
    """DNS トンネリングの検知エンジン"""
 
    # しきい値（チューニング可能）
    ENTROPY_THRESHOLD = 3.5      # ランダム文字列のエントロピー
    LABEL_LENGTH_THRESHOLD = 50  # サブドメインラベルの長さ
    QUERY_RATE_THRESHOLD = 100   # 1分間のクエリ数
    TXT_RATIO_THRESHOLD = 0.3    # TXTクエリの割合
    UNIQUE_SUBDOMAIN_THRESHOLD = 50  # ユニークなサブドメイン数/分
 
    def __init__(self):
        self.alerts = []
 
    def analyze(self, queries: list[DNSQuery], window_minutes: int = 5) -> list:
        """クエリログを分析してトンネリングの兆候を検知"""
        # ソースIPごとにグループ化
        by_source = collections.defaultdict(list)
        for q in queries:
            by_source[q.src_ip].append(q)
 
        for src_ip, src_queries in by_source.items():
            indicators = self._check_indicators(src_queries, window_minutes)
            if indicators["score"] >= 3:  # 3つ以上の指標でアラート
                self.alerts.append({
                    "source_ip": src_ip,
                    "severity": "HIGH" if indicators["score"] >= 4 else "MEDIUM",
                    "indicators": indicators,
                    "sample_queries": [q.qname for q in src_queries[:5]],
                })
 
        return self.alerts
 
    def _check_indicators(self, queries: list[DNSQuery], window_min: int) -> dict:
        score = 0
        indicators = {}
 
        # 指標 1: 異常に長いサブドメインラベル
        long_labels = [
            q for q in queries
            if len(get_subdomain_labels(q.qname)) > self.LABEL_LENGTH_THRESHOLD
        ]
        if long_labels:
            score += 1
            indicators["long_labels"] = len(long_labels)
 
        # 指標 2: 高エントロピーのサブドメイン
        high_entropy = []
        for q in queries:
            subdomain = get_subdomain_labels(q.qname)
            if subdomain and shannon_entropy(subdomain) > self.ENTROPY_THRESHOLD:
                high_entropy.append(q)
        if high_entropy:
            score += 1
            indicators["high_entropy"] = len(high_entropy)
 
        # 指標 3: TXT レコードの異常な割合
        txt_queries = [q for q in queries if q.qtype == "TXT"]
        txt_ratio = len(txt_queries) / max(len(queries), 1)
        if txt_ratio > self.TXT_RATIO_THRESHOLD:
            score += 1
            indicators["txt_ratio"] = round(txt_ratio, 3)
 
        # 指標 4: 同一ベースドメインへの高頻度クエリ
        domain_counts = collections.Counter(
            extract_base_domain(q.qname) for q in queries
        )
        high_freq = {d: c for d, c in domain_counts.items()
                     if c > self.QUERY_RATE_THRESHOLD}
        if high_freq:
            score += 1
            indicators["high_freq_domains"] = high_freq
 
        # 指標 5: ユニークなサブドメインの数が異常に多い
        unique_subdomains = collections.defaultdict(set)
        for q in queries:
            base = extract_base_domain(q.qname)
            sub = get_subdomain_labels(q.qname)
            if sub:
                unique_subdomains[base].add(sub)
 
        for base, subs in unique_subdomains.items():
            if len(subs) > self.UNIQUE_SUBDOMAIN_THRESHOLD:
                score += 1
                indicators["unique_subdomains"] = {base: len(subs)}
                break
 
        # 指標 6: Base32/Base64 パターンの検出
        b64_pattern = re.compile(r'^[A-Za-z0-9+/=]{20,}$')
        b32_pattern = re.compile(r'^[A-Z2-7=]{20,}$')
        encoded_count = sum(
            1 for q in queries
            if b64_pattern.match(get_subdomain_labels(q.qname).replace(".", ""))
            or b32_pattern.match(get_subdomain_labels(q.qname).replace(".", ""))
        )
        if encoded_count > 10:
            score += 1
            indicators["encoded_queries"] = encoded_count
 
        indicators["score"] = score
        return indicators

# コード例10: DNS モニタリングの設定
 
# ===== Suricata での DNS 異常検知ルール =====
# /etc/suricata/rules/dns-tunnel.rules
 
# 異常に長い DNS クエリの検出
alert dns any any -> any any (msg:"DNS Tunnel - Long query name";
  dns.query; content:"|00|"; offset:50;
  threshold: type threshold, track by_src, count 10, seconds 60;
  classtype:bad-unknown; sid:1000001; rev:1;)
 
# TXT レコードの大量クエリ
alert dns any any -> any any (msg:"DNS Tunnel - Excessive TXT queries";
  dns.query; content:"|00 10|";  # TXT record type
  threshold: type threshold, track by_src, count 50, seconds 60;
  classtype:bad-unknown; sid:1000002; rev:1;)
 
# ===== Zeek (Bro) での DNS ログ分析 =====
# dns.zeek スクリプト
@load base/protocols/dns
 
event dns_request(c: connection, msg: dns_msg, query: string, qtype: count)
{
    if ( |query| > 60 )
    {
        NOTICE([$note=DNS::Tunneling_Indicator,
                $msg=fmt("Long DNS query from %s: %s", c$id$orig_h, query),
                $conn=c]);
    }
}
 
# ===== tcpdump での DNS トラフィック監視 =====
# DNS クエリをリアルタイム監視
tcpdump -i eth0 -n port 53 -l | awk '/A\?/ {print $NF}'
 
# 長いクエリ名のみ表示
tcpdump -i eth0 -n port 53 -l | awk 'length($NF) > 60 {print}'

# TLSA レコードの生成
openssl x509 -in server.crt -pubkey -noout | \
  openssl pkey -pubin -outform DER | \
  openssl dgst -sha256 -binary | \
  xxd -p -c 256
 
# TLSA レコードの検証
dig _443._tcp.example.com TLSA +short

# 1. DNSSEC 対応ドメインの確認
dig +dnssec cloudflare.com A
 
# 2. DNSSEC 非対応ドメインとの違いを確認
# (AD フラグの有無に注目)
 
# 3. DNSKEY と DS レコードの確認
dig cloudflare.com DNSKEY +short
dig cloudflare.com DS +short
 
# 質問:
# - AD フラグは何を意味するか?
# - KSK と ZSK のフラグ値の違いは?
# - DS レコードはどのゾーンに配置されるか?

# 演習1: 基本実装のテンプレート
class Exercise1:
    """基本的な実装パターンの演習"""
 
    def __init__(self):
        self.data = []
 
    def validate_input(self, value):
        """入力値の検証"""
        if value is None:
            raise ValueError("入力値がNoneです")
        return True
 
    def process(self, value):
        """データ処理のメインロジック"""
        self.validate_input(value)
        self.data.append(value)
        return self.data
 
    def get_results(self):
        """処理結果の取得"""
        return {
            'count': len(self.data),
            'data': self.data
        }
 
# テスト
def test_exercise1():
    ex = Exercise1()
    assert ex.process(1) == [1]
    assert ex.process(2) == [1, 2]
    assert ex.get_results()['count'] == 2
 
    try:
        ex.process(None)
        assert False, "例外が発生するべき"
    except ValueError:
        pass
 
    print("全テスト合格!")
 
test_exercise1()

# 演習2: 応用パターン
from typing import List, Dict, Optional
from datetime import datetime
 
class AdvancedExercise:
    """応用パターンの演習"""
 
    def __init__(self, max_size: int = 100):
        self._items: List[Dict] = []
        self._max_size = max_size
        self._created_at = datetime.now()
 
    def add(self, key: str, value: any) -> bool:
        """アイテムの追加（サイズ制限付き）"""
        if len(self._items) >= self._max_size:
            return False
        self._items.append({
            'key': key,
            'value': value,
            'timestamp': datetime.now().isoformat()
        })
        return True
 
    def find(self, key: str) -> Optional[Dict]:
        """キーによる検索"""
        for item in reversed(self._items):
            if item['key'] == key:
                return item
        return None
 
    def remove(self, key: str) -> bool:
        """キーによる削除"""
        for i, item in enumerate(self._items):
            if item['key'] == key:
                self._items.pop(i)
                return True
        return False
 
    def stats(self) -> Dict:
        """統計情報"""
        return {
            'total_items': len(self._items),
            'max_size': self._max_size,
            'usage_percent': len(self._items) / self._max_size * 100,
            'uptime': str(datetime.now() - self._created_at)
        }
 
# テスト
def test_advanced():
    ex = AdvancedExercise(max_size=3)
    assert ex.add("a", 1) == True
    assert ex.add("b", 2) == True
    assert ex.add("c", 3) == True
    assert ex.add("d", 4) == False  # サイズ制限
    assert ex.find("b")['value'] == 2
    assert ex.remove("b") == True
    assert ex.find("b") is None
    stats = ex.stats()
    assert stats['total_items'] == 2
    print("応用テスト全合格!")
 
test_advanced()

# 演習3: パフォーマンス最適化
import time
from functools import lru_cache
 
# 最適化前（O(n^2)）
def slow_search(data: list, target: int) -> int:
    """非効率な検索"""
    for i in range(len(data)):
        for j in range(i + 1, len(data)):
            if data[i] + data[j] == target:
                return (i, j)
    return (-1, -1)
 
# 最適化後（O(n)）
def fast_search(data: list, target: int) -> tuple:
    """ハッシュマップを使った効率的な検索"""
    seen = {}
    for i, num in enumerate(data):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return (-1, -1)
 
# ベンチマーク
def benchmark():
    import random
    data = list(range(5000))
    random.shuffle(data)
    target = data[100] + data[4000]
 
    start = time.time()
    result1 = slow_search(data, target)
    slow_time = time.time() - start
 
    start = time.time()
    result2 = fast_search(data, target)
    fast_time = time.time() - start
 
    print(f"非効率版: {slow_time:.4f}秒")
    print(f"効率版:   {fast_time:.6f}秒")
    print(f"高速化率: {slow_time/fast_time:.0f}倍")
 
benchmark()