What I give this method is to read each sentence in a large corpus in an input data and select its binary words.
Any ideas on how I should reduce the time complexity?
while (count < fileStream.size()) { // 1st loop
List<String> lineArray = new ArrayList<>(Arrays.asList(fileStream.get(count).split("\\$+")));
//lineArray.forEach(System.out::println);
if (lineArray.size() > 2) {
List<Sentence> sentences = sentenceSplitter.split(shoppingPlatform.getProductDescription());
sentences.replaceAll(sentence -> new Sentence(sentence.toString().toLowerCase(new Locale("tr-TR"))));
for (Sentence sentence : sentences) { // 2nd loop
FsmParseList[] parseLists = fsm.robustMorphologicalAnalysis(sentence);
ArrayList<FsmParse> candidateParses = morphologicalDisambiguator.disambiguate(parseLists);
map = biGramSentences(map, map2, shortcuts, unicodes, candidateParses);
}
//sentences.forEach(System.out::println);
}
count++;
}
The average number of lines in the file is 500000. I have 3 nested loops and O(n³) complexity.
private static Map<String, Integer> biGramSentences(Map<String, Integer> map, Map<String, String> map2, ArrayList<String> shortcuts, ArrayList<String> unicodes, ArrayList<FsmParse> candidateParses) {
Set<String> keys = map2.keySet();
for (int i = 0; i < candidateParses.size() - 1; i++) { // 3rd loop
for (String key : keys) {
if (candidateParses.get(i).getSurfaceForm().equals(key)) {
...
}
if (candidateParses.get(i + 1).getSurfaceForm().equals(key)) {
...
}
}
String temp = candidateParses.get(i).getSurfaceForm() + " " + candidateParses.get(i + 1).getSurfaceForm();
if (map.get(temp) != null) {
map.put(temp, map.get(temp) + 1);
} else if (map.get(temp) == null) {
for (String unicode : unicodes) {
if (candidateParses.get(i).getSurfaceForm().contains(unicode)) {
...
}
if (candidateParses.get(i + 1).getSurfaceForm().contains(unicode)) {
...
}
}
boolean flag2 = true;
for (String shortcut : shortcuts) {
if (candidateParses.get(i).getSurfaceForm().equals(shortcut)
|| candidateParses.get(i + 1).getSurfaceForm().equals(shortcut)) {
...
}
}
if (flag2 && (Objects.equals(candidateParses.get(i).getFinalPos(), "VERB") || Objects.equals(candidateParses.get(i + 1).getFinalPos(), "VERB")
|| Objects.equals(candidateParses.get(i).getFinalPos(), "NUM") || Objects.equals(candidateParses.get(i + 1).getFinalPos(), "NUM")
|| Objects.equals(candidateParses.get(i).getPos(), "PUNC") || Objects.equals(candidateParses.get(i + 1).getPos(), "PUNC"))) {
...
}
if (flag2 && (candidateParses.get(i).isPunctuation() || candidateParses.get(i + 1).isPunctuation()
|| candidateParses.get(i).isNumber() || candidateParses.get(i + 1).isNumber())) {
...
}
if (flag2)
map.put(temp, 1);
}
}
return map;
}
The program runs extremely slow.