java- удаление подстроки в списке строк

Question

Рассмотрим случай со списком строк Пример: list = ['apple', 'bat', 'cow,' dog ',' applebat ',' cowbat ',' dogbark ',' help ']

Код java должен проверить, не является ли какой-либо элемент строки подмножеством другого элемента, и если он больше, то строковый элемент должен быть удален.

так что в этом случае струнные «апплеты», «ковбой», «собака» удаляются.

Подход, который я взял был взять два списка и перебирать их следующим образом,

ArrayList<String> list1 = new ArrayList<String>(strings); 
ArrayList<String> list2 = new ArrayList<String>(strings); 
for(int i = 0; i<list1.size();i++) 
    { 
     String curr1 = list1.get(i); 

     for(int j = 0;j<list2.size();j++) 
     { 
      String curr2 = list2.get(j); 

      if(curr2.contains(curr1)&&!curr2.equals(curr1)) 
      { 
       list2.remove(j); 
       j--; 
     } 
     } 
    } 

ВАЖНО У меня есть списки с размерами 200К до 400К elements.I хотели бы найти способ улучшить производительность. Я даже пробовал хэшсеты, но они не очень помогли. Я сталкиваюсь с проблемами с временем, затраченным программой.

Может ли кто-нибудь предложить какие-либо улучшения в моем коде или какие-либо другие подходы в java для повышения производительности?

Answer 1

import java.util.ArrayList; 
import java.util.*; 
// our main class becomes a file but the main method is still found 
public class HelloWorld 
{ 
    public static void main(String[] args) 
    { 
    String[] strings = {"apple","bat","cow","dog","applebat","cowbat","dogbark","help"}; 
    ArrayList<String> list1 = new ArrayList<String>(Arrays.asList(strings)); 
ArrayList<String> list2 = new ArrayList<String>(Arrays.asList(strings)); 
ArrayList<String> result = new ArrayList<String>(Arrays.asList(strings)); 
for(int i = 0; i<8;i++) 
{ 

    String curr1 = list1.get(i); 
    System.out.println(curr1); 
    int flag = 0; 
    for(int j = i+1;j<8;j++) 
    { 
     String curr2 = list2.get(j); 

     if((curr2.contains(curr1)&&!curr2.equals(curr1))) 
     { 

      result.remove(curr2); 
     } 
    } 

} 
System.out.println(result); 

    } 
} 

Answer 2

Предположим, что здесь будет быстрее. Вы можете легко сделать это с помощью java8 stream api.

Попробуйте это:

private Set<String> delete() { 
     Set<String> startSet = new HashSet<>(Arrays.asList("a", "b", "c", "d", "ab", "bc", "ce", "fg")); 
     Set<String> helperSet = new HashSet<>(startSet); 

     helperSet.forEach(s1 -> helperSet.forEach(s2 -> { 
      if (s2.contains(s1) && !s1.equals(s2)) { 
       startSet.remove(s2); 
      } 
     })); 

     return startSet; 
    } 

Не удалять элементы из набора вы перебор для или вы будете иметь ConcurrentModificationException.

Answer 3

Для полного увеличения производительности огромного списка слов я бы подумал, что комбинация рода и string searching algorithm, такая как Aho–Corasick algorithm, является тем, что вам нужно, если вы готовы реализовать такую ​​сложную логику.

Сначала произведите сортировку слов по длине.

Затем создайте словарь Ахо-Корасика в порядке длины слова. Для каждого слова сначала проверьте, существует ли подстрока в словаре. Если это так, пропустите слово, иначе добавьте слово в словарь.

Когда закончите, дамп словаря или список поддерживаемых параллелей, если словарь нелегко/возможно сбросить.

Answer 4

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Date; 
import java.util.List; 
import java.util.Random; 

public class SubStrRmove { 
    public static List<String> randomList(int size) { 
     final String BASE = "abcdefghijklmnopqrstuvwxyz"; 
     Random random = new Random(); 
     List<String> list = new ArrayList<>(); 
     for (int i = 0; i < size; i++) { 
      int length = random.nextInt(3) + 2; 
      StringBuffer sb = new StringBuffer(); 
      for (int j = 0; j < length; j++) { 
       int number = random.nextInt(BASE.length()); 
       sb.append(BASE.charAt(number)); 
      } 
      list.add(sb.toString()); 
      sb.delete(0, sb.length()); 
     } 
     return list; 
    } 

    public static List<String> removeListSubStr(List<String> args) { 
     String[] input = args.toArray(new String[args.size()]); 
     Arrays.parallelSort(input, (s1, s2) -> s1.length() - s2.length()); 
     List<String> result = new ArrayList<>(args.size()); 
     for (int i = 0; i < input.length; i++) { 
      String temp = input[i]; 
      if (!result.stream().filter(s -> temp.indexOf(s) >= 0).findFirst().isPresent()) { 
       result.add(input[i]); 
      } 
     } 
     return result; 
    } 

    public static List<String> removeListSubStr2(List<String> args) { 
     String[] input = args.toArray(new String[args.size()]); 
     Arrays.parallelSort(input, (s1, s2) -> s1.length() - s2.length()); 
     List<String> result = new ArrayList<>(args.size()); 
     for (int i = 0; i < input.length; i++) { 
      boolean isDiff = true; 
      for (int j = 0; j < result.size(); j++) { 
       if (input[i].indexOf(result.get(j)) >= 0) { 
        isDiff = false; 
        break; 
       } 
      } 
      if (isDiff) { 
       result.add(input[i]); 
      } 
     } 
     return result; 
    } 

    public static void main(String[] args) throws InterruptedException { 
     List<String> list = randomList(20000); 
     Long start1 = new Date().getTime(); 
     List<String> listLambda = removeListSubStr(list); 
     Long end1 = new Date().getTime(); 
     Long start2 = new Date().getTime(); 
     List<String> listFor = removeListSubStr2(list); 
     Long end2 = new Date().getTime(); 
     System.out.println("mothod Labbda:" + (end1 - start1) + "ms"); 
     System.out.println("mothod simple:" + (end2 - start2) + "ms"); 
     System.out.println("" + listLambda.size() + listLambda); 
     System.out.println("" + listFor.size() + listFor); 

    } 

} 

Answer 5

Я испытал это на небольших данных и надеюсь, что это поможет вам найти решение ...

import java.util.ArrayList; 
import java.util.Arrays; 

public class Main { 
    public static void main(String[] args){ 
     String []list = {"apple","bat","cow","dog","applebat","cowbat","dogbark","help","helpless","cows"}; 
     System.out.println(Arrays.toString(list)); 
     int prelenght = 0; 
     int prolenght = 0; 
     long pretime = System.nanoTime(); 
     for(int i=0;i<list.length;i++){ 
      String x = list[i]; 
      prelenght = list[i].length(); 
      for(int j=i+1;j<list.length;j++){    
       String y = list[j]; 
       if(y.equals(x)){ 
        list[j] = "0"; 
       }else if(y.contains(x)||x.contains(y)){ 
        prolenght = list[j].length();     
        if(prelenght<prolenght){ 
         list[j] = "0"; 
        }      
        if(prelenght>prolenght){ 
         list[i] = "0"; 
         break; 
        } 
       } 
      } 
     }  
     long protime = System.nanoTime(); 
     long time = (protime - pretime); 
     System.out.println(time + "ns"); 
     UpdateArray(list);  
    } 

    public static void UpdateArray(String[] list){ 
     ArrayList<String> arrayList = new ArrayList<>(); 
     for(int i=0;i<list.length;i++){ 
      if(!list[i].equals("0")){ 
       arrayList.add(list[i]); 
      } 
     } 
     System.out.println(arrayList.toString()); 
    } 
} 

Выход:

[apple, bat, cow, dog, applebat, cowbat, dogbark, help, helpless, cows] 
time elapsed : 47393ns 
[apple, bat, cow, dog, help]