#ifndef TOKENIZER_H_
#define TOKENIZER_H_

#include <string>

using namespace std;

enum DelimType
{
  WHITESPACE = 0, ORDINARY = 1
};

class Tokenizer
{
public:
  Tokenizer(const string text);
  virtual ~Tokenizer();

  bool has_next();
  string next();

  void add_delims(int begin, int end, DelimType type);

private:
  void find_token();

private:
  unsigned int _pos;
  string _text;
  string _token;
  bool _token_available;
  DelimType _delims[256];
};

#endif

#include <iostream>

#include "Tokenizer.h"

Tokenizer::Tokenizer(const string text) :
  _pos(0), _text(text), _token_available(false)
{
  _token.clear();
  add_delims(0x0, 0xFF, WHITESPACE);
  add_delims(0x30, 0x39, ORDINARY);
  add_delims(0x41, 0x5A, ORDINARY);
  add_delims(0x61, 0x7A, ORDINARY);
}

Tokenizer::~Tokenizer()
{
}

bool Tokenizer::has_next()
{
  find_token();

  if (_token_available)
  {
    return true;
  }

  return false;
}

string Tokenizer::next()
{
  find_token();

  if (_token_available)
  {
    _token_available = false;
    return _token;
  }

  throw "No next token!";
}

void Tokenizer::add_delims(int begin, int end, DelimType type)
{
  if (begin < 0)
  {
    begin = 0;
  }

  if (end > 255)
  {
    end = 255;
  }

  for (int i = begin; i <= end; ++i)
  {
    _delims[i] = type;
  }
}

void Tokenizer::find_token()
{
  if (_pos >= _text.length() || _token_available)
  {
    return;
  }

  _token.clear();
  _token_available = false;

  while (_pos < _text.length())
  {
    char chr = _text.at(_pos);
    DelimType type = _delims[(int) chr];
    _pos++;

    if (type == ORDINARY)
    {
      _token.append(1, chr);
      _token_available = true;
    }
    else if (_token_available && type == WHITESPACE)
    {
      break;
    }
  }
}

In diesem Artikel möchte ich zeigen, wie man eine einfache Faceted Search mit Lucene umsetzen kann.

Zum Einsammeln der Facetten benötigen wir eine Implementierung der HitCollector Klasse. Hier wird die TopFieldDocCollector Klasse erweitert, wird keine weitere Sortierung außer nach Relevanz benötigt, so kann man auch die Klasse TopDocCollector nutzen.

Zu beachten ist, dass diese Implementierung einer Faceted Search nur funktioniert, wenn Felder die zur Facettenbildung benutzt werden, nur einen einzelnen Wert pro Dokument haben. Andernfalls ist das Verhalten undefiniert, da die Werte für die Facetten über die Klasse FieldCache erzeugt werden. Um mehrere Werte für Facettenfelder zu erlauben ist eine eigene Implementierung einer FieldCache Klasse notwendig, die mehrere Werte pro Feld enthalten kann.

Hier nun die Implementierung:

public class FacetedCollector extends TopFieldDocCollector {

  private Map<String, String[]> fieldCaches;

  private Map<String, Map<String, Integer>> facetsMap;

  public FacetedCollector(String[] fields, IndexReader reader, Sort sort,
      int numHits) throws IOException {
    super(reader, sort, numHits);

    this.facetsMap = new HashMap<String, Map<String, Integer>>();
    this.fieldCaches = new HashMap<String, String[]>();

    for (String field : fields) {
      facetsMap.put(field, new HashMap<String, Integer>());
      fieldCaches.put(field, FieldCache.DEFAULT.getStrings(reader, field));
    }
  }

  @Override
  public void collect(int doc, float score) {
    super.collect(doc, score);

    for (Entry<String, Map<String, Integer>> e : facetsMap.entrySet()) {
      Map<String, Integer> values = e.getValue();
      String value = fieldCaches.get(e.getKey())[doc];

      if (value != null) {
        Integer count = values.get(value);

        if (count == null) {
          values.put(value, 1);
        } else {
          values.put(value, count + 1);
        }
      }
    }
  }

  public Map<String, Map<String, Integer>> getFacetsMap() {
    return facetsMap;
  }

}

Zusätzlich zu den Parametern des Konstrukturs der Klasse TopFieldDocCollector werden die Feldnamen im Stringarray fields übergeben.

Über die fieldCaches kann direkt auf den Wert eines Feldes eines bestimmten Dokumentes zugegriffen werden, ohne im Index suchen zu müssen. Die Arrays für die Werte der verschiedenen Felder befinden sich direkt im Ram und werden von der FieldCache Klasse bei dem ersten Zugriff erzeugt. Damit dauert die erste Suche über den FacetedCollector, je nach Anzahl der Dokumente im Index, einige Zeit.

Um den Speicherbedarf möglichst niedrig zu halten sollte versucht werden die Werte über byte, short oder int Felder im Index abzulegen.

Hier eine beispielhafte Benutzung der FacetedCollector Klasse:

public class FacetedSearch {

  public static void main(String[] args) {
    String path = args[0];
    String queryStr = args[1];

    try {
      QueryParser parser =
          new QueryParser("title", new StandardAnalyzer());
      Query query = parser.parse(queryStr);

      IndexSearcher searcher = new IndexSearcher(path);
      String[] fields = { "language", "year" };
      IndexReader reader = searcher.getIndexReader();
      FacetedCollector collector =
          new FacetedCollector(fields, reader, Sort.RELEVANCE, 10);
      searcher.search(query, collector);

      Map<String, Map<String, Integer>> facetsMap =
          collector.getFacetsMap();

      for (Entry<String, Map<String, Integer>> fieldEntry : facetsMap
          .entrySet()) {
        System.out.println(" - " + fieldEntry.getKey());

        for (Entry<String, Integer> valueEntry : fieldEntry.getValue()
            .entrySet()) {
          System.out.println("   - " + valueEntry.getKey() + " ("
              + valueEntry.getValue() + ")");
        }
      }

      searcher.close();
    } catch (Exception e) {
      e.printStackTrace();
    }
  }

}

Ein einfach einzusetzender Profiler ist The Java Interactive Profiler.

Alles was dafür gebraucht wird ist die profile.jar Datei und eine profile.properties Datei, wie in folgendem Beispiel:

profiler=on
file=profile.txt

Bei dem Start des zu testenden Java Programms müssen nur 2 Parameter mit angegeben werden:

-javaagent:profile.jar -Dprofile.properties=profile.properties

Anschließend findet man in dem aktuellen Verzeichnis eine profile.txt Datei, in der die Auswertung zu finden ist.

Am Besten kann man dieses an einem Beispiel sehen. In einer sortierten Liste versuchen wir einen zufällig erzeugten Wert zu finden, zuerst mit einer einfachen Iteration über das gesamte Array.

public class JIProfilerTest {

    private static int maxRandom = 10000000;

    private int count = 1000000;

    private int[] nums;

    public static void main(String[] args) {
        Random random = new Random(System.currentTimeMillis());

        JIProfilerTest test = new JIProfilerTest();
        test.init(random);

        int numsFound = 0;

        for (int i = 0; i < 10000; i++) {
            int number = random.nextInt(maxRandom) + 1;

            if (test.search(number) > -1) {
                numsFound++;
            }
        }

        System.out.println(numsFound + " Nummern gefunden.");
    }

    private void init(Random random) {
        nums = new int[count];

        for (int i = 0; i < count; i++) {
            nums[i] = random.nextInt(maxRandom);
        }

        Arrays.sort(nums);
    }

     private int search(int number) {
        for (int i = 0; i < nums.length; i++) {
            if (number == nums[i]) {
                return i;
            }
        }

        return -1;
    }

}

Lässt man das oben angezeigt Programm ausführen, erhält man eine profile.txt Datei mit folgendem Inhalt.

+----------------------------------------------------------------------
|  File: profile.txt
|  Date: 2009.03.04 20:44:32 PM
+----------------------------------------------------------------------

+------------------------------
| Thread depth limit: Unlimited
+------------------------------
+------------------------------
| Thread: 1
+------------------------------
              Time            Percent   
       ----------------- ---------------
 Count    Total      Net   Total     Net  Location
 =====    =====      ===   =====     ===  =========
     1  32923,1    293,8   100,0     0,9  +--JIProfilerTest:main    (jiprof)
     1      0,2      0,2     0,0          | +--JIProfilerTest:<init>    (jiprof)
     1    732,4    732,4     2,2     2,2  | +--JIProfilerTest:init    (jiprof)
 10000  31896,8  31896,8    96,9    96,9  | +--JIProfilerTest:search    (jiprof)

+--------------------------------------
| Most expensive methods (by net time)
| Frame Count Limit: Unlimited
+--------------------------------------

               Net
          ------------
 Count     Time    Pct  Location
 =====     ====    ===  ========
 10000  31896,8   96,9  jiprof.JIProfilerTest:search
     1    732,4    2,2  jiprof.JIProfilerTest:init
     1    293,8    0,9  jiprof.JIProfilerTest:main
     1      0,2    0,0  jiprof.JIProfilerTest:<init>

+--------------------------------------+
| Most expensive methods summarized    |
+--------------------------------------+

               Net
          ------------
 Count     Time    Pct  Location
 =====     ====    ===  ========
 10000  31896,8   96,9  jiprof.JIProfilerTest:search
     1    732,4    2,2  jiprof.JIProfilerTest:init
     1    293,8    0,9  jiprof.JIProfilerTest:main
     1      0,2    0,0  jiprof.JIProfilerTest:<init>

An dem Ergebnis kann man sehen, dass allein die search Methode 96,9% der Rechenzeit verbraucht hat.

Jetzt lassen wir dieses Programm nochmal mit einer etwas intelligenteren Suchmethode ausführen und schauen uns das Ergebnis danach an.

public class JIProfilerTest {

    private static int maxRandom = 10000000;

    private int count = 1000000;

    private int[] nums;

    public static void main(String[] args) {
        Random random = new Random(System.currentTimeMillis());

        JIProfilerTest test = new JIProfilerTest();
        test.init(random);

        int numsFound = 0;

        for (int i = 0; i < 10000; i++) {
            int number = random.nextInt(maxRandom) + 1;

            if (test.search(number) > -1) {
                numsFound++;
            }
        }

        System.out.println(numsFound + " Nummern gefunden.");
    }

    private void init(Random random) {
        nums = new int[count];

        for (int i = 0; i < count; i++) {
            nums[i] = random.nextInt(maxRandom);
        }

        Arrays.sort(nums);
    }

    private int search(int number) {
        int left, right, midpt;

        left = 0;
        right = nums.length - 1;

        while (left <= right) {
            midpt = (int) ((left + right) / 2);

            if (number == nums[midpt]) {
                return midpt;
            } else if (number > nums[midpt]) {
                left = midpt + 1;
            } else {
                right = midpt - 1;
            }
        }

        return -1;
    }

}

Das Ergebnis:

+----------------------------------------------------------------------
|  File: profile.txt
|  Date: 2009.03.04 20:49:54 PM
+----------------------------------------------------------------------

+------------------------------
| Thread depth limit: Unlimited
+------------------------------
+------------------------------
| Thread: 1
+------------------------------
              Time            Percent   
       ----------------- ---------------
 Count    Total      Net   Total     Net  Location
 =====    =====      ===   =====     ===  =========
     1    551,2    127,7   100,0    23,2  +--JIProfilerTest:main    (jiprof)
     1      0,1      0,1     0,0          | +--JIProfilerTest:<init>    (jiprof)
     1    319,6    319,6    58,0    58,0  | +--JIProfilerTest:init    (jiprof)
 10000    103,8    103,8    18,8    18,8  | +--JIProfilerTest:search    (jiprof)

+--------------------------------------
| Most expensive methods (by net time)
| Frame Count Limit: Unlimited
+--------------------------------------

               Net
          ------------
 Count     Time    Pct  Location
 =====     ====    ===  ========
     1    319,6   58,0  jiprof.JIProfilerTest:init
     1    127,7   23,2  jiprof.JIProfilerTest:main
 10000    103,8   18,8  jiprof.JIProfilerTest:search
     1      0,1    0,0  jiprof.JIProfilerTest:<init>

+--------------------------------------+
| Most expensive methods summarized    |
+--------------------------------------+

               Net
          ------------
 Count     Time    Pct  Location
 =====     ====    ===  ========
     1    319,6   58,0  jiprof.JIProfilerTest:init
     1    127,7   23,2  jiprof.JIProfilerTest:main
 10000    103,8   18,8  jiprof.JIProfilerTest:search
     1      0,1    0,0  jiprof.JIProfilerTest:<init>

Dieser zweite Versuch hat schon eine insgesamt viel kürzere Laufzeit, außerdem benötigt die search Methode jetzt nur noch 18,8%.

Bei diesem Beispiel konnte man sicherlich auch ohne Profiler sagen, dass die zweite Variante schneller ist. Es gibt aber sicherlich andere Probleme, die nicht so einfach zu überblicken sind. Speziell wenn man versucht einen Flaschenhals in einem Programm zu finden kann ein Profiler gute Dienste leisten.

Interessant ist The Java Interactive Profiler sicherlich auch deswegen, da man ihn remote einsetzen kann und somit auch nützlich für Anwendungen sein kann, die in einem Servlet Container laufen. Das Einschalten des Profilers kann auch remote erfolgen, so dass auch nur spezielle Aspekte einer Anwendung getestet werden können.

• Makefile aus dem GPWiki
• Automating Program Compilation - Writing Makefiles

### Start of user configuration ###########################################

# Name your executable.
TARGET = application

# Additional paths for PKG_CONFIG_PATH.
PKG_CONFIG_PATH =

# Additional libs, flags will be created with pkg-config.
LIBS =

# User flags.
CXXFLAGS =
LDFLAGS =

### End of user configuration #############################################

# Default build type.
TYPE = debug

# Special flags for each build type.
ifeq ($(TYPE),debug)
CXXFLAGS := $(value CXXFLAGS) -O0 -g3
LDFLAGS := $(value LDFLAGS)
endif

ifeq ($(TYPE),profile)
CXXFLAGS := $(value CXXFLAGS) -pg
LDFLAGS := $(value LDFLAGS) -pg
endif

ifeq ($(TYPE),release)
CXXFLAGS := $(value CXXFLAGS) -O3
LDFLAGS := $(value LDFLAGS) -s
endif

# The source, include and object store directory.
SRCDIR = src
INCDIR = include
OBJDIR = .$(TYPE)

# Compiler and compiler options.
CXX = g++
CXXFLAGS := $(value CXXFLAGS) -Wall -I$(INCDIR) -I$(SRCDIR) $(if $(LIBS),\
	$(shell PKG_CONFIG_PATH=$(PKG_CONFIG_PATH) pkg-config --cflags $(LIBS)))

# Linker and linker options.
LD = g++
LDFLAGS := $(value LDFLAGS) $(if $(LIBS),\
	$(shell PKG_CONFIG_PATH=$(PKG_CONFIG_PATH) pkg-config --libs $(LIBS)))

# List of source files.
SRCS := $(foreach FILE,$(shell find $(SRCDIR) -name *.cpp | xargs), \
	$(subst $(SRCDIR)/, , $(FILE)))
# List of object files.
OBJS := $(addprefix $(OBJDIR)/,$(SRCS:.cpp=.o))
# List of dependency files.
DEPS := $(addprefix $(OBJDIR)/,$(SRCS:.cpp=.d))

.PHONY: init clean

$(TARGET): init $(OBJS)
	$(LD) $(LDFLAGS) -fPIC $(OBJS) -o $(TARGET)

$(OBJDIR)/%.o: $(SRCDIR)/%.cpp
	$(CXX) -Wp,-MMD,$(OBJDIR)/$*.dd $(CXXFLAGS) -fPIC -c $< -o $@
	@sed -e '1s/^\(.*\)$$/$(subst /,\/,$(dir $@))\1/' $(OBJDIR)/$*.dd > \
		$(OBJDIR)/$*.d
	@rm -f $(OBJDIR)/$*.dd

init:
	@if [ ! -e $(OBJDIR) ]; then mkdir $(OBJDIR); fi;
	@$(foreach DIR,$(sort $(dir $(SRCS))), if [ ! -e $(OBJDIR)/$(DIR) ]; \
		then mkdir $(OBJDIR)/$(DIR); fi; )

clean:
	@rm -f $(TARGET) $(OBJS)

-include $(DEPS)

Um Sourcecode zu drucken sollte dieser schön formatiert sein und möglichst auf 80 Zeichen begrenzt sein um ihn besser ausdrucken zu können. Für C/C++ Code liefert die Kombination von indent und a2ps gute Ergebnisse.

indent

Zum Anfang muss erst einmal der Sourcecode formatiert werden, dafür kann man folgendes Kommando benutzen:

indent in.cpp -st -bad -bap -bli0 -i4 -l79 -lc79 -ncs -npcs -nut -npsl \
-fca -fc1 > out.cpp

Hier einige Details zu den Optionen:

• -std: Der formatierte Sourcecode wird auf die Standardausgabe geschrieben.
• -bad: Nach jedem Deklarationsblock wird eine Leerzeile eingefügt.
• -bap: Nach jeder Funktions/Methodenblock wird eine Leerzeile eingefügt.
• -bli0: Klammern werden nicht eingerückt.
• -i4: Einrückung um 4 Leerzeichen.
• -l79: Max. Länge einer Zeile auf 79 Zeichen festlegen.
• -lc79: Max. Länge einer Kommentarzeile auf 79 Zeichen festlegen.
• -ncs: Kein Leerzeichen nach einem Cast.
• -npcs: Kein Leerzeichen hinter dem Funktionsnamen bei einem Funktionsaufruf.
• -nut: Keine Tabulatoren verwenden, nur Leerzeichen.
• -npsl: Rückgabewert einer Funktion in der gleichen Zeile wie den Funktionsnamen belassen.
• -fca: Alle Kommentare formatieren.
• -fc1: Kommentare formatieren, die in der ersten Spalte beginnen.

Detailiertere Angaben zu den einzelnen Optionen, inkl. Beispielen, findet man in der Manpage von indent:

man indent

Das Kommando um C/C++ Sourcecode zu formatieren ist fertig, leider kann ich mir eine solche Anzahl von Optionen über einen längeren Zeitraum nicht merken. Dafür bietet das indent Kommando eine profile Datei, die man sich in seinem Home-Verzeichnis anlegen kann.

indent liest die Datei .indent.pro ein, wenn vorhanden. Die einzelnen Optionen können in dieser Datei gespeichert werden, genauso wie man sie für das Kommando angeben würde, als eine Zeile in der Datei.

a2ps

Jetzt geht es ans Drucken. mit folgendem Kommando kann man den gerade formatierten Sourcecode jetzt drucken:

a2ps out.cpp

Hat man keinen Standarddrucker eingestellt oder will man es auf einen anderen Drucker ausgeben kann man den Druckernamen mitgeben:

a2ps -P <druckername> out.cpp

Standardmäßig werden 2 Seiten auf eine DIN-A 4 Seite gedruckt, wer lieber nur eine Seite im Hochformat gedruckt haben will gibt folgendes an:

a2ps -1 out.cpp

Noch 2 kleine Hinweise

Da a2ps keine UTF-8 Kodierung verarbeiten kann, ist es hilfreich die Dateien, sofern sie in der UTF-8 Kodierung vorliegen, zuvor umzuwandeln:

recode utf8..latin1 out.cpp

Möchte man sein Ergebnis zuerst am Bildschirm betrachten sollte man als Drucker display angeben, so wird die Postscript Ausgabe nur am Bildschirm geöffnet.

a2ps -P display out.cpp