Algo의 최적화

Question

텍스트 파일을 읽고 입력 배열 []이 boolean 유형 인 코드가 있습니다. 그것의 크기는 약 10 만 -300,000 항목입니다. 이제 내가 직면하고있는 문제는 인접한 참 값을 가진 N> 3> = N> = 9 인 모든 하위 집합을 만드는 것입니다.

예. N = 3 인 경우, [true] [true] [true]는 3 개의 모든 참값이 연속 인덱스에있는 경우 필수 하위 집합입니다.

알고리즘을 만들었지 만 매우 느립니다. 신속하고 효율적인 더 나은 솔루션이 필요합니다.

몇 가지 아이디어를 제안하십시오.

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]에서 BitSet이 더 효율적이라고 생각합니다. 귀하의 경우에도 더 빠르다고 기대합니다. 이후 캐시를 더 잘 활용할 것입니다. 알고리즘의 경우 boolean[] vs. BitSet: Which is more efficient?

를 참조하십시오 자료 구조를 통해

으로 반복합니다. 처음으로 true을 발견하면 false에 도달 할 때까지 위치 (start)를 기억하십시오. 이것은 위치입니다 end 그 시점에서 기본적으로 결과 인 true 값의 연속 간격의 시작과 끝이 있습니다. 하위 집합은 start에서 end - n까지 시작합니다. 당신의 말까지

반복 자료 구조

당신은 각각 segement의 시작 후 첫 false 값으로 시작하는 이상 계속 배열의 다른 부분을 처리, N-프로세스를 시작하여이 parallize 수 있습니다 첫 번째 때까지 세그먼트의 끝 false.

Answer 2

나는 모두 StringBuilder를 만들 수 sugggest하고 부울 배열에 추가 모든 "true"로 값 1을 추가하고 모든 "거짓"에 대한 0 덧붙였다. 따라서 stringbuilder에는 1과 0의 시퀀스가 ​​있습니다. 그런 다음 indexOf ("111")를 사용하여 세 개의 인접한 "true"값의 시작 인덱스를 얻습니다.이 인덱스는 stringbuilder와 boolean 배열의 시작 인덱스가됩니다.

Answer 3

가장 간단한 방법은 인덱스 x에서 시작하는 N 값을 확인하는 것입니다. 하나 이상의 false가 있으면 x + N 인덱스로 직접 이동할 수 있습니다. 그렇지 않으면 인덱스 x + 1을 확인할 수 있습니다. 유효한 순서가 없으면 크기/N 셀을 확인합니다. 의사 코드에서

하십시오 비트 세트 대신에 당신이 다음 거짓의 인덱스를 얻기 위해 nextClearByte 사용할 수있는 배열

또한

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; 
    }  
} 

. 이전의 거짓 마이너스 N과의 차이는 N 참 (Null)의 시퀀스의 nomber를 나타냅니다 (이전 false는 처음에 -1로 평가됨).