Petitverse

プチコン非公式コミュニティトピック

こういち ◆.Id/aHiU36hu
2021/1/12 14:19

協力

アクア式重複削除

というのを考えたので、評価して欲しいです。(バグらせずに書けそうか、改良案、変数名のセンスがサイテーなど)

アクア式重複削除とは
・ソート済みの配列の重複した要素を取り除く(1 1 1 2 2 2 3 3 → 1 2 3)
・ある程度の速度を保ちつつバグらせないことを最優先。
・コードを少し変えることでランレングスやスターリンソートに転用可能。
・めぐる式二分探索(https://twitter.com:443/meguru_comp/status/697008509376835584 )を意識。

こういち 2021/1/12 14:24 ◆.Id/aHiU36hu

コード
I=0J=0
WHILE J<N
　REPEAT:J=J+1:UNTIL J>=N||A[J]!=A[J-1]
　A[I]=A[J-1]
　I=I+1
WEND
RESIZE A,I
N=I

こういち 2021/1/12 16:51 ◆.Id/aHiU36hu

I=0J=0
WHILE J<N
　reg=A[J]
　REPEAT:J=J+1:UNTIL J>=N||A[J]!=reg
　A[I]=reg
　I=I+1
WEND
RESIZE A,I
N=I

J-1がサイテーなので消してみた。これで比較の式を変えるだけでスターリンソートに早変わり。

さすらいの名無し 2021/1/12 17:06 ◆LWMA5UzCJb3e

分からない用語だらけ…(ランレングス、スターリンソートって何？)

ところでRESISE A,Iってあるけどこれは事前にDEFしてるものですか？(DEFしないとSyntax errorになる)

りょうTanpo 2021/1/12 17:56 ◆Y/UJfznLVFuX

RESIZE……？

SatoshiMcCloud 2021/1/12 18:20 ◆Z1qfV11i63Jr

REPEATとUNTILを1行で書くの、バグりそうで好きじゃないです。好みの問題かよって言われるとそれまでですけど。

こういち 2021/1/12 18:42 ◆.Id/aHiU36hu

さすらいの名無しさん
りょうTanpoさん
あぁ…フリックミス…
RESIZE
ですね。直しときます。(この部分。別に無いなら無いで問題ないんですけど)

ランレングスは圧縮の手法ですね。
値とその長さを記録するやつ。
すもももももももものうち→す1も8の1う1ち1
スターリンソートはソートアルゴリズムの一種。昇順でない値を粛清するというネタ枠。
4日後にソートされる数列(https://twitter.com:443/unidentifiedexe/status/1270326414777040896 )でもお馴染み。

Na 2021/1/12 20:23 ◆QoELVrBXBQCI

ループを1つにしたい。

IF N THEN
　I=1:reg=A[0]
　FOR J=1 TO N
　　IF J==N || A[J]!=reg THEN A[I]=reg:I=I+1:reg=A[J*(J<N)]
　NEXT
　RESIZE A,I
　N=I
ENDIF

J*(J<N)は無理やり。
MIN(J,N-1)よりはましかなと思って。

60126r露米亜@頭の人 2021/1/12 22:50 ◆.EwMLlgCELmJ

スターリンソート...粛清されそうな並び替えだな

ugly777 2021/1/13 0:33 ◆B7lOIJDWuOqi

↑ワシもそう思う。
(ボックスクラフトネタ)

こういち 2021/1/13 8:43 ◆.Id/aHiU36hu

SatoshiMcCloudさん
どうせ間に1文しかないと思って一行にしましたが、確かにそうかもしれませんね。まぁボクの好みということで。

さすらいの名無し 2021/1/13 10:43 ◆LWMA5UzCJb3e

↑2 粛清だ
(スターリンネタ)

60126r露米亜@頭の人 2021/1/13 20:37 ◆.EwMLlgCELmJ

粛清されそうって書いたけどすでに書いてあった（）

こういち 2021/1/14 9:58 ◆.Id/aHiU36hu

Naさん
確かにループ1つの方が分かりやすいですね。
Jループが外か…
確かに範囲が大きい方を外側にするのは自然。

こういち 2021/1/14 10:36 ◆.Id/aHiU36hu

もはやアクア式ではなくなった。

J=1I=1:reg=a[0]
WHILE I<N
　IF A[I]!=reg THEN
　　reg=A[I]
　　A[J]=reg
　　J=J+1
　ENDIF
　I=I+1
WEND

ツララ 2021/1/14 10:56 ◆ArUdBYOYME1V

＞スターリンソート
これ、除外するってことなら「ハブるソート」って名前でもいいんじゃないんですかね？
統治者が代替わりする時に粛清なんてありふれた話ですし、別にスターリンじゃなくてもネタに走るならポル・ポトとかでもいいような気も。
オリジナル配列には変更を加えないで、設定したルールに則って美味しい部分だけをチョイスして別配列を生成する方が
その分メモリは多く使いますけど便利な気がするんですけど。
なんにせよ安易に人名を使うのはその人の一面しか見てない感じありますし
配慮が足りない感ありますけどね。

並べて”粛清”するならアクア式なんて小洒落た名前じゃなくて
イスラム過激派のISIL式の方が合ってるかも。

こういち 2021/1/14 12:32 ◆.Id/aHiU36hu

ボルポトはともかく、ハブるソートだと多分流行らなかった。インパクト大事。

それとは別に考案した人や貢献した人の名前を付けるのは自然なネーミング。

さすらいの名無し 2021/1/15 10:04 ◆LWMA5UzCJb3e

そもそもアクアって誰ですか()

こういち 2021/1/15 10:32 ◆.Id/aHiU36hu

ボクです。
競技やその他一部のゲームではaqualengthの名前で活動することがよくある。

こういち 2022/1/21 18:27 ◆.Id/aHiU36hu

Lomuto's partitionについて調べてたら既視感を感じたので来てみた。
Naさんの重複削除に似てたのか。
なんとなくアクア式重複削除(J-1を消したやつ)の方が速いと思ってましたが、Naさんのそれも同等かそれ以上に速そう。
(ただ、ヒストグラム作るときとかはアクア式から変形した方が書きやすかった記憶)

コメントを書く

こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
ユーザー登録なしで書き込みができます
秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります

プチコン 非公式コミュニティ トピック

コメント

コメントを書く

プチコン非公式コミュニティトピック