算法的優化

Question

我有讀取文本文件並創建boolean類型的輸入數組[]的代碼。它的大小約爲100,000-300,000個物品。現在我面臨的問題是創建所有那些大小爲N，3> = N> = 9的子集，它們具有連續的真值。

E.g.對於N = 3，如果所有3個trues都在連續索引中，[true] [true] [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("********************************************************************************************"); 
    } 

Answer 1

首先，我會遠離array[boolean] a BitSet是更高的內存效率，我希望它在你的情況下更快。因爲它會更好地利用緩存。見boolean[] vs. BitSet: Which is more efficient?

對於算法：通過數據結構

迭代。 當您遇到第一個true時，請記住它的位置（start），直到達到false。這是位置end 在這一點上，你有一個true值的連續間隔的開始和結束，這基本上是你的結果。你從start到end - n得到你的子集。

重複，直到你最終數據結構

，你甚至可以通過啓動正進程，每個處理陣列的不同部分，該segement開始後開始與第一false值，並繼續在parallize這直到第一個false結束。

Answer 2

我會sugggest你創建一個StringBuilder和追加1添加到布爾數組每一個「真」值，併爲每一個「假」 0添加。因此你的stringbuilder將有一個1和0的序列。然後，只需使用indexOf（「111」）來獲取三個連續的「true」值的起始索引，它將成爲stringbuilder和布爾數組中的起始索引。

Answer 3

最簡單的算法是檢查從索引x開始的N個值。如果至少存在一個錯誤，則可以直接進入索引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; 
    }  
} 

也，有位集合，而不是你可以使用nextClearByte獲得下一個虛假的索引的數組。與前面的假負N的差值表示N真的序列的序數（其中前面的假初始值爲-1）。