0

テキストファイルを読み取り、booleanタイプの入力配列[]を作成するコードがあります。そのサイズは約100,000〜300,000アイテムです。今私が直面している問題は、連続した真の値を持つサイズN、3> = N>=9のすべてのサブセットを作成することです。

たとえば、N = 3の場合、[true] [true] [true]は、3つのtrueすべてが連続インデックスにある場合に必要なサブセットです。

アルゴリズムを作成しましたが、非常に遅いです。高速で効率的な、より良いソリューションが必要です。

いくつかのアイデアを提案してください。

 public static void createConsecutivePassingDays()
    {       
        for (String siteName  : sitesToBeTestedList.keySet())
        {
            System.out.println("\n*****************Processing for Site--->"+siteName+" ***********************");

            LinkedHashMap<String,ArrayList<String>> cellsWithPassedTripletsDates=new LinkedHashMap<String, ArrayList<String>>();

            for (String cellName : sitesToBeTestedList.get(siteName))
            {

                System.out.println("\n*****************Processing for Cell--->"+cellName+" ***********************");

                boolean failed=false;

                ArrayList<String> passedDatesTriplets=new ArrayList<String>();
                int consecutiveDays=0;
                String tripletDate="";
                String prevDate_day="";
                String today_Date="";

                for (String date : cellDateKpiMetOrNotMap.get(cellName).keySet())
                {
                    System.out.println("\nprocessing for Date-->"+date);
                    if(!(prevDate_day.trim().equals("")))
                        today_Date=getNextDay(prevDate_day.substring(0, prevDate_day.lastIndexOf('_')));

                    if(Connection.props.getProperty("INCLUDE_WEEKENDS").equalsIgnoreCase("FALSE"))
                    {
                        if(date.endsWith("SAT") || date.endsWith("SUN") || (!(date.substring(0, date.lastIndexOf('_')).equalsIgnoreCase(today_Date))))
                        {
                            if(consecutiveDays >= Reader.days)
                            {
                                passedDatesTriplets.add(tripletDate);
                            }

                            tripletDate="";
                            consecutiveDays=0;
                            prevDate_day=date;
                            continue;
                        }
                    }


                    if(cellDateKpiMetOrNotMap.get(cellName).get(date).equalsIgnoreCase("TRUE"))
                    {

                        if(tripletDate.equals(""))
                            tripletDate=date;
                        else
                            tripletDate+="#"+date;

                        consecutiveDays++;

                    }
                    else
                    {
                        failed=true;
                        if(consecutiveDays >= Reader.days)//kd
                        {
                            System.out.println("Triplet to be added-->"+tripletDate);
                            passedDatesTriplets.add(tripletDate);
                        }
                        tripletDate="";
                        consecutiveDays=0;
                    }

                    prevDate_day=date;
                }

                if(!failed)
                    passedDatesTriplets.add(tripletDate);
                else
                {
                    if(tripletDate.trim().split("#").length >= Reader.days)
                    {
                        passedDatesTriplets.add(tripletDate);
                    }
                }

                cellsWithPassedTripletsDates.put(cellName, passedDatesTriplets);

            }

            siteItsCellsWithPassedDates.put(siteName, cellsWithPassedTripletsDates);

        }

        System.out.println("\n************************************************SITES***************************************");
        for (String site : siteItsCellsWithPassedDates.keySet())
        {
            System.out.println("\n********************Site="+site+" ***********************");
            for (String cellName : siteItsCellsWithPassedDates.get(site).keySet())
            {
                System.out.println("\nCellName="+cellName);
                System.out.println(siteItsCellsWithPassedDates.get(site).get(cellName));
            }
            System.out.println("***********************************************************");
        }
        System.out.println("********************************************************************************************");
    }
4

3 に答える 3

4

array[boolean]まず、私はaから離れて、BitSetメモリ効率が高いと思います。あなたの場合も、より高速になると思います。キャッシュをより有効に活用するためです。boolean []とBitSetを参照してください：どちらがより効率的ですか？

アルゴリズムの場合：

データ構造を反復処理します。最初のに出くわしたときは、に達するまでtrueその位置（）を覚えておいてください。これが位置 です。その時点で、値の連続した間隔の開始と終了があり、これが基本的に結果です。サブセットはからから始まるものとして取得します。startfalseendtruestartend - n

データ構造の最後まで繰り返します

nプロセスを開始し、それぞれが配列の異なる部分を処理しfalse、セグメントの開始後の最初の値から開始し、セグメントの終了まで最初の値まで継続することで、これをパラライズすることもできfalseます。

于 2012-10-10T10:58:35.233 に答える
1

最も単純な方法は、インデックスxから始まるN個の値をチェックすることです。falseが少なくとも1つある場合は、インデックスx+Nに直接移動できます。それ以外の場合は、インデックスx+1を確認できます。有効なシーケンスがない場合は、サイズ/Nセルを確認します。

擬似コードで：

int max = array.length - N;
int index = 0;
boolean valid = true;
while (index < max) {
   valid = true;
   for (check = index; check<index+N; check++){
      valid = valid && array[check];
   }
   if (valid) {
      // you got a continous sequence of true of size N
      ;
      index++;
   } else {
      index = index + N;
   }      
}

また、配列の代わりにBitSetを使用すると、nextClearByteを使用して次のfalseのインデックスを取得できます。前のfalseからNを引いたものとの差は、N trueのシーケンスの数を示します（前のfalseは最初は-1と評価されます）。

于 2012-10-10T11:13:04.200 に答える
0

文字列ビルダーを作成し、ブール配列に追加されるすべての「true」値に1を追加し、追加されるすべての「false」値に0を追加することをお勧めします。したがって、stringbuilderには1と0のシーケンスがあります。次に、indexOf（ "111"）を使用して、3つの連続する「true」値の開始インデックスを取得します。これは、stringbuilderおよびブール配列の開始インデックスにもなります。

于 2012-10-10T10:33:03.957 に答える