Closed16

push_swap課題メモ

こよdこよd

is_sorted関数でのエラー

  • prev_value = *(int *)(current->content); がセグフォになった

  • 理由：

    1. データの格納方法:parse_args 関数で、整数値を直接 void* にキャストして格納
    2. データの解釈方法:is_sorted 関数で、content を int* としてキャストして、それを逆参照しようとしていた

  • 対策：

    • 整数値を int* として格納・・・データの型が明確になる
    • is_sorted 関数で、content を int* としてキャスト
こよdこよd

次回

  • ft_lst〜系についておさらいする
  • キャストしている方があっているか、エラーの箇所、エラーハンドリング抜けているところ追加　is_sorted
  • sort関数の実装考えてく
こよdこよd

コスト計算の手順:

a. スタックBでの操作コスト:

対象の要素をスタックBの一番上に持ってくるための回転回数を計算
rb（上方向）とrrb（下方向）のどちらが少ない回数で済むかを比較

b. スタックAでの操作コスト:

スタックAで適切な挿入位置を見つける
その位置を一番上に持ってくるための回転回数を計算
ra（上方向）とrra（下方向）のどちらが少ない回数で済むかを比較

c. push操作のコスト:

pa操作のコストは通常1とカウント

d. 総コストの計算:

スタックBでの操作コスト + スタックAでの操作コスト + push操作のコスト

こよdこよd

操作の種類

sa: スタックAの上位2要素を交換
sb: スタックBの上位2要素を交換
ss: saとsbを同時に実行
pa: スタックBの一番上の要素をスタックAに移動
pb: スタックAの一番上の要素をスタックBに移動
ra: スタックAを上に1つシフト（一番上が一番下に）
rb: スタックBを上に1つシフト（一番上が一番下に）
rr: raとrbを同時に実行
rra: スタックAを下に1つシフト（一番下が一番上に）
rrb: スタックBを下に1つシフト（一番下が一番上に）
rrr: rraとrrbを同時に実行

こよdこよd

モジュロ演算

return (max_pos + 1) % stack->size;
スタック内で最大値の次の位置を返すためのものです。ここでの重要なポイントは、スタックを循環構造として扱っていることです。

詳細な説明：
max_pos: これは最大値が見つかった位置（インデックス）です。
max_pos + 1: 最大値の次の位置を指します。通常、これが私たちの求める値になります。
% stack->size: これは剰余（モジュロ）演算です。スタックのサイズで割った余りを求めています。

なぜモジュロ演算が必要か：
もし max_pos がスタックの最後の要素（インデックスで言えば stack->size - 1）だった場合、単純に max_pos + 1 とすると、スタックのサイズを超えてしまいます。
モジュロ演算を使うことで、スタックのサイズを超えた場合に自動的に0（先頭）に戻ります。

例を挙げて説明します：
スタックのサイズが5で、最大値が4番目（インデックス3）にある場合：
(3 + 1) % 5 = 4 となり、正しく次の位置（4）を返します。

スタックのサイズが5で、最大値が最後（インデックス4）にある場合：
(4 + 1) % 5 = 0 となり、スタックの先頭（0）を返します。

この方法により、スタックの「端」を超えても正しく次の位置を計算できます。つまり、最大値がスタックの最後にある場合、その「次」は自動的にスタックの先頭となります。
これは、スタックを円形のデータ構造として扱うことを可能にし、最小値を最大値の直後に配置するという目的に合致します。この循環的な考え方は、スタックを回転させる操作（ra, rb, rra, rrb）との整合性も保ちます。

こよdこよd

ベンチマーク

以下pdf翻訳

  • このプロジェクトを検証するには、最小限の操作回数で特定のソートを実行しなければならない：
  • ミニマリストの検証（80点満点）では、以下のことが要求される。
    100個の乱数を700回以下の操作でソートできなければならない。
  • プロジェクトの検証を最大にし、ボーナスを獲得するためには、次のことを満たさなければならない。
    500個の乱数を並べ替えるには、5500回以下の操作でなければならない。
    5500回以下でなければならない。
    これらはすべて、あなたの評価中に検証されます。
    ボーナス・パートを達成したいのであれば、各ベンチマーク・ステップで以下のことを徹底的に検証しなければならない。
    プロジェクトを徹底的に検証し、各ベンチマーク・ステップで可能な限り高いスコア
    スコアを獲得してください。
こよdこよd

2024/08/12 時点でのコスト
100個のとき
Operation count: 1319
500個のとき
Operation count: 69424
終わってる

8/13
スタックAからBの移動方法を修正したつもりなんだけど、さらに終焉した
100個のとき
Operation count: 2622
？
100個のとき
Operation count: 1319
500個のとき
Operation count: 27264

8/17
100個のとき　壊れた
Operation count: 6066
？？？

8/19
スタックB→Aの手順を修正したら治った
100個のとき
Operation count: 698

こよdこよd

プッシュのコスト計算のパターン
stack_b を上方向に回転させ、stack_a を上方向に回転させる
stack_b を上方向に回転させ、stack_a を下方向に回転させる
stack_b を下方向に回転させ、stack_a を上方向に回転させる
stack_b を下方向に回転させ、stack_a を下方向に回転させる

1つの値でやること
①4パターンのそれぞれのコストを計算
②最小パターン数と最初パターンの番号を決定
③最小パターン数のパターンで、スタックを移動させる

こよdこよd

最適化のためには、必ずしも元の位置に戻す必要はなく、最終的にソートされた状態になっていれば良い

こよdこよd

reak check

valgrind --leak-check=full ./push_swap
valgrind --leak-check=full ./push_swap ""
valgrind --leak-check=full ./push_swap " "
これはなにも表示しないで終了

valgrind --leak-check=full ./push_swap 1 2 3 4 5

valgrind --leak-check=full ./push_swap "1 2 3 4 5"

こよdこよd

より安全な比較方法として、以下のいずれかを使用することが推奨されます：

num < (long long int)INT_MIN
これは明示的にINT_MINをlong long intに変換し、正確な比較を行います。
num > -(long long int)INT_MIN
これは元々提案した方法で、オーバーフローを避けつつ正確な比較を行います。

こよdこよd

#!/usr/bin/python3
import random
import sys

print(" ".join([str(i) for i in random.sample(range(-2147483648, 2147483647), int(sys.argv[1]))]))

ARG="337 12232 3332 -21 -327";valgrind --leak-check=full ./push_swap $ARG | wc -l^C
このスクラップは2024/09/22にクローズされました