配列に対する座標圧縮

LISを求めるときなどに使う座標圧縮をJavaで実装していきます。

ランダム配列の生成と書き込み

座標圧縮ができているか確認するために、ランダムに配列を生成しそれをテキストファイルに書き込んでおきます。(Pythonを使います）

fp = open("data1.txt","w")
for i in set([random.randint(0,100000) for i in range(10000)]):
     fp.write("{} ".format(i))
fp.close()

以上でdata1.txtへの書き込みが終了しました。

圧縮クラス

今回はメンバ変数に３種類の配列を割り当てました。

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;

public class Compress{
    String[] seqStr;
    int[] seqInt;
    int[] seqSorted;
    ...
}

コンストラクタ

ここで、先ほど作ったファイルを読み込んで、配列を生成します。

public Compress(){
        Path file = Paths.get("data1.txt");
        try{
            String text = Files.readString(file);
            seqStr = text.split(" ", -5);
            seqInt = new int[seqStr.length];
            seqSorted = new int[seqStr.length];
            for (int i = 0;i<seqInt.length;i++){
                try{
                    seqInt[i] = Integer.parseInt(seqStr[i]);
                    seqSorted[i] = Integer.parseInt(seqStr[i]);
                }catch(NumberFormatException varIoException){
                    System.out.println("Cannot convert");
                }
            }
        }catch(IOException varIoException){
            System.out.println();
        }
    }

ソートメソッド

座標圧縮するときに対象の値が何番目に大きいのかを知る必要があるため、ソートアルゴリズムを作っておきます。

public void Sort(){
        boolean isSwapped = true;
        while(isSwapped){
            isSwapped = false;
            for (int i = 0;i<seqSorted.length-1;i++){
                if (seqSorted[i]>seqSorted[i+1]){
                    int t = seqSorted[i];
                    seqSorted[i] = seqSorted[i+1];
                    seqSorted[i+1] = t;
                    isSwapped = true;
                }
            }
        }
    }

インデックス探索メソッド

ソート済みの配列を使用して、対象の数字が何番目に大きいかを返します。高速化のため二分探索を使用します。

public int search(int target){
        if (target>seqSorted[seqSorted.length-1]){
         return -1;
        }
        int left = 0;
        int right = seqSorted.length-1;
        int m = (left+right)/2;
        while(target != seqSorted[m]){
         if (target<seqSorted[m]){
             right = m;
             m  = (left+right)/2;
         }else{
             left = m;
             m = (left+right)/2+1;
         }
        }
        return m;
     }

toString

 public String toString(){
        String result = "[";
        int i = 0;
        while(i<seqInt.length-2){
            result += seqStr[i] + ",";
            ++i;
        }result += seqStr[i] + "]\n[";
        i = 0;
        while(i<seqInt.length-2){
            result += seqSorted[i] + ",";
            ++i;
        }result += seqSorted[i] + "]\n";

        return  result;
    }

圧縮メソッド

上で作った二分探索を使用して、座標圧縮を行います。

 public void compressArr(){
        for (int i = 0; i<seqInt.length;i++){
            seqInt[i] = search(seqInt[i]);
        }
    }