java - 算法的优化

Question

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

例如对于 N=3，如果所有 3 个 true 都在连续索引中，则 [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] BitSet 内存效率更高，因为我希望它在您的情况下也会更快。因为它将更好地利用缓存。参见 boolean[] vs. BitSet: Which is more efficient?

对于算法:

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

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

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