0

我有读取文本文件并创建boolean类型的输入数组 [] 的代码。它的大小约为 100,000-300,000 件。现在我面临的问题是创建所有具有连续真值的大小为 N, 3>=N>=9 的子集。

例如，对于 N=3，如果所有 3 个真值都在连续索引中，则 [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("********************************************************************************************");
    }
4

3 回答 3

4

首先，我会远离内存效率更高的array[boolean]a BitSet，因为我希望它在您的情况下也会更快。因为它将更好地利用缓存。请参阅boolean[] 与 BitSet：哪个更有效？

对于算法：

遍历数据结构。当你遇到第一个true时，记住它的位置 ( start) 直到你到达 a false。这是位置end 那时你有一个连续的true值区间的开始和结束，这基本上是你的结果。你得到你的子集从startto开始end - n。

重复直到你的数据结构结束

您甚至可以通过启动 n 个进程来实现并行化，每个进程处理数组的不同部分，从段开始false后的第一个值开始，一直持续到段结束，直到第一个false.

于 2012-10-10T10:58:35.233 回答
1

最简单的算法是检查从索引 x 开始的 N 个值。如果至少有一个false，那么你可以直接去索引x+N。否则你可以检查索引 x+1；如果没有有效的序列，那么您将检查 size/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 的索引。与前一个假减去 N 的差值表示 N 为真的序列数（前一个假初始值为 -1）。

于 2012-10-10T11:13:04.200 回答
0

我建议您创建一个字符串生成器，并为添加到布尔数组的每个“真”值附加 1，为每个添加的“假”附加 0。因此，您的字符串生成器将具有 1 和 0 的序列。然后只需使用 indexOf("111") 来获取三个连续“真”值的起始索引，它将是字符串构建器和布尔数组中的起始索引。

于 2012-10-10T10:33:03.957 回答