リードコード-TOpKStringPatterns

3864 ワード

package org.apache.mahout.fpm.pfpgrowth.convertors.string;
public final class TopKStringPatterns implements Writable
patternを格納し、mergeでtop kを見つけるpatternを行う
コア、pairチェーンテーブル、各pairはpatternからなるstringチェーンテーブルとlong型support値からなる.
すなわちチェーンテーブル

private final List<Pair<List<String>,Long>> frequentPatterns;

読み書きフォーマットチェーンテーブル総長pattern長support値patternに含まれるフィールド

  @Override
  public void readFields(DataInput in) throws IOException {
    frequentPatterns.clear();
    int length = in.readInt();
    for (int i = 0; i < length; i++) {
      List<String> items = new ArrayList<String>();
      int itemsetLength = in.readInt();
      long support = in.readLong();
      for (int j = 0; j < itemsetLength; j++) {
        items.add(in.readUTF());
      }
      frequentPatterns.add(new Pair<List<String>,Long>(items, support));
    }
  }
  
  @Override
  public void write(DataOutput out) throws IOException {
    out.writeInt(frequentPatterns.size());
    for (Pair<List<String>,Long> pattern : frequentPatterns) {
      out.writeInt(pattern.getFirst().size());
      out.writeLong(pattern.getSecond());
      for (String item : pattern.getFirst()) {
        out.writeUTF(item);
      }
    }
  }

mergeアクション、2つのTopKStringPatternsを合成して新しいTopKStringPatternsを生成
2つのTopKStringPatternsはそれぞれ1つずつ取って先にsupportを行って、更にpatternは長くて、更にpatternは比較します
勝者は新しいTopKStringPatternsに入り、敗者は次のものと比較した.
全体的な効果はスタックに似ています.
疑问:両者はあらかじめ降順ソート???

  public TopKStringPatterns merge(TopKStringPatterns pattern, int heapSize) {
    List<Pair<List<String>,Long>> patterns = new ArrayList<Pair<List<String>,Long>>();
    Iterator<Pair<List<String>,Long>> myIterator = frequentPatterns.iterator();
    Iterator<Pair<List<String>,Long>> otherIterator = pattern.iterator();
    Pair<List<String>,Long> myItem = null;
    Pair<List<String>,Long> otherItem = null;
    for (int i = 0; i < heapSize; i++) {
      if (myItem == null && myIterator.hasNext()) {
        myItem = myIterator.next();
      }
      if (otherItem == null && otherIterator.hasNext()) {
        otherItem = otherIterator.next();
      }
      if (myItem != null && otherItem != null) {
        int cmp = myItem.getSecond().compareTo(otherItem.getSecond());
        if (cmp == 0) {
          cmp = myItem.getFirst().size() - otherItem.getFirst().size();
          if (cmp == 0) {
            for (int j = 0; j < myItem.getFirst().size(); j++) {
              cmp = myItem.getFirst().get(j).compareTo(
                otherItem.getFirst().get(j));
              if (cmp != 0) {
                break;
              }
            }
          }
        }
        if (cmp <= 0) {
          patterns.add(otherItem);
          if (cmp == 0) {
            myItem = null;
          }
          otherItem = null;
        } else if (cmp > 0) {
          patterns.add(myItem);
          myItem = null;
        }
      } else if (myItem != null) {
        patterns.add(myItem);
        myItem = null;
      } else if (otherItem != null) {
        patterns.add(otherItem);
        otherItem = null;
      } else {
        break;
      }
    }
    return new TopKStringPatterns(patterns);
  }