large scale searching and sorting, operation in java for purpose of elimination: the puzzling case of

Question

I have a big list of the following form, for purposes of this question we'll refer to it as Kraftwerk

匹

屯

牙

友

I have another list of there following form, henceforth refered to as KomputerLove

兪
yú
部首：入　
首尾分解: 人折

罙
shēn
部首：冖　
首尾分解: 冖木

叇
dài
部首：厶　
首尾分解: 云逮

Using the Kraftwerk as a reference, I want to whittle down KomputerLove so that if the main index of KomputerLove, i.e. in this example that would be ['兪','罙','叇'] does not appear in Kraftwerk we eliminate it.

I don't have much experience with such kind of searching and sorting operations, what would be the best way to accomplish this? It should be taken into account that both Kraftwerk & KomputerLove are in reality slightly large, on the order of 1,000's of indices.

Those lists are stored just as you see them in .txt files.

Answer 1

From what I understand of your question, kraftwerk isn't actually a list, but a set of strings, and komputerLove is some sort of composite data object (I presume each line of each block is a data field?), keyed by the first line of the block. 1000s of objects isn't particularly large so I'd start off with something simple like the following, and worry about performance if it's shown to be an issue:

Set<String> indexes = new HashSet<>(); //Add the indexes however you do at present
List<KomputerLoveObject> allObjects = new LinkedList<>(); //Add the objects however you do at present
List<KomputerLoveObject> filteredObjects = allObjects.stream()
                              .filter(indexes::contains)
                              .collect(Collectors.toList());

If you're not using Java 8 you can do it in the slightly more verbose way:

Set<String> indexes = new HashSet<>(); //Add the indexes however you do at present
List<KomputerLoveObject> allObjects = new LinkedList<>(); //Add the objects however you do at present
List<KomputerLoveObject> filteredObjects = new LinkedList<>();
for (KomputerLoveObject klo : allObjects) {
    if (indexes.contains(klo)) {
        filteredObjects.add(klo);
    }
}

If performance does prove to be an issue, move the filtering of komputerLove earlier, to the point where you're loading your files so you don't iterate over the whole data set twice, and also don't keep around two Lists. Depending on how you load these objects, you may be able to speed up the loading process as well.

Answer 2

Some simple pseudocode:

public String idunno() {
    // for readFromFile see:
    // http://stackoverflow.com/questions/326390/how-to-create-a-java-string-from-the-contents-of-a-file
    String kraftwerk = readFromFile("kraftwerk.txt");
    String komputerLove = readFromFile("komputerlove.txt");

    Matcher m = Pattern.compile(regex).matcher(komputerLove);
    while(m.find()) {
        // removes the found ideogramm from the first file:
        kraftwerk = kraftwerk.replaceAll(m.group(1), "");
    }

    return kraftwerk;
}

EDIT: A possible regex is: public static String regex = "(.)((\\r\\n|\\r|\\n).+){3}"; This will match a single character followed by 3 non-empty lines, with the first character accessible with the first capture group.

Answer 3

This reads all the single ideograms into a Set. A pass through the file containing the line blocks copies those where the first line is not in the ideogram Set.

public class Filter {
  Set<Character> keys = new HashSet<>();
  PrintWriter osw; 
  void checkAndDump( List<String> lines ) throws Exception {
    if( lines.size() >= 1 &&
        ! keys.contains( lines.get(0).charAt(0) ) ){
      for( String s: lines ){
        osw.println( s );
      }
      osw.println();
    }
    lines.clear();
  }

  void filter( String inpath, String outpath ) throws Exception {
    BufferedReader lr = new BufferedReader( new FileReader( inpath ) );
    osw = new PrintWriter( new FileOutputStream( outpath ) );
    String line;
    List<String> lines = new ArrayList<>();
    while( (line = lr.readLine()) != null ){
      if( line.length() > 0 ){
        lines.add( line );
      } else {
        checkAndDump( lines );
      }
    }
    checkAndDump( lines );
    osw.close();
    lr.close();
  }

  void fillSet( String path ) throws Exception {
    BufferedReader br = new BufferedReader( new FileReader( path ) );
    String line;
    while( (line = br.readLine()) != null ){
      if( line.length() > 0 ){
        keys.add( line.charAt(0) );
      }
    }
    br.close();
  }    

  public static void main( String[] args ) throws Exception {
    Filter f = new Filter();
    f.fillSet( "kraftwerk.txt" );
    f.filter( "love.txt", "lv.txt" );
  }
}