我有读取文本文件并创建 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("********************************************************************************************");
}
最佳答案
首先,我会远离 array[boolean]
BitSet
内存效率更高,因为我希望它在您的情况下也会更快。因为它将更好地利用缓存。参见 boolean[] vs. BitSet: Which is more efficient?
对于算法:
遍历数据结构。
当您遇到第一个 true
时,请记住它的位置 (start
),直到遇到 false
。这是位置 end
那时你有一个连续的 true
值区间的开始和结束,这基本上就是你的结果。您得到的子集从 start
到 end - n
。
重复直到你的数据结构结束
您甚至可以通过启动 n 个进程来并行化它,每个进程处理数组的不同部分,从段开始后的第一个 false
值开始,一直持续到段结束直到第一个 false
。
关于java - 算法的优化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12817042/