Monday, September 16, 2013

Algoritmos de ordenação String (char) e o uso de Collator no Java 7

Um dos temas que eu mais gosto na área da computação é a Análise de Algoritmos, especificamente a ordenação de estrutura de dados. O Java utiliza diversos algoritmos na classificação de dados em sua API, com o foco em unir a eficiência com a performance. Inclusive, no Java 7 foram implementadas algumas melhorias no uso de algoritmos de ordenação. Nesse post eu descrevo as características sobre ordenação de caracteres e String em Java.

Arrays de char

Pra começar, um exemplo simples demonstrando como ordenar os caracteres que compõe uma String:
  String content = "ebdca";
  char[] chars = content.toCharArray();
  
  Arrays.sort(chars);
  
  String sorted = new String(chars);
  System.out.println(sorted); //abcde

A classe Arrays do Java ordena o array chars na ordem natural, alfabética. Mas o que acontece dentro do método sort? Como o array é pequeno o algoritmo utilizado para ordenação é o Insertion Sort, aonde a comparação ocorre no sentido de elementos da esquerda para a direita, garantindo que todos os elementos à esquerda estejam ordenados.

Simulação:

Array original -> e b d c a
Comparação 1 -> b < e, sim  -> Resultado: b e d c a
Comparação 2 -> de, sim  -> Resultado: b d e c a
Comparação 3 -> d < b, não
Comparação 4 -> ce, sim  -> Resultado: b d c e a
Comparação 5 -> c < d, sim  -> Resultado: b c d e a
Comparação 6 -> c < b, não
...

A análise matemática de Insertion Sort varia de acordo com o conteúdo do array. No melhor caso, quando o array já está ordenado, o número de comparações seria linear O(n). Enquanto no pior caso, se os elementos estiverem em ordem decrescente, o número de comparações seria quadrático O( N^2). Em arrays pequenos Insertion Sort é uma ótima opção.

Em um array maior, com mais de 47 caracteres, o algoritmo utilizado é o QuickSort c/ Dual-Pivot. Como o nome diz, trata-se de uma variação de QuickSort com dois pivôs, abordagem parecida com QuickSort 3-way. Alguns estudos apontam que essa estratégia pode reduzir em até 10% o tempo em relação ao QuickSort tradicional. O algoritmo é recente, reformulado em 2009 por Vladimir Yaroslavskiy. O uso desses algoritmos fazem parte de melhorias do Java 7, verifique a classe DualPivotQuicksort.java.

Um detalhe muito importante sobre a comparação de char, é que o Java utiliza o Unicode para determinar a pontução de cada caracter. Nesse caso 'A' vem bem antes de 'a', e 'ã' vai bem depois de 'a'. Modificando o conteúdo da variável content para "abcdeãA", o valor de sorted seria "Aabcdeã". Volto a falar sobre isso no decorrer do post.

Array de String

O próximo trecho de código também é bem simples, nele coloco quatro strings em um array e peço para a classes Arrays realizar a ordenação:
  String content[] = { "Jose", "Andre", "Claudia", "Bruna" };
  
  Arrays.sort(content);
  for (String s: content) {
    System.out.print(s+" ");
  }

Por se tratar de um array pequeno, a API do Java utiliza o Binary Insertion Sort, uma alternativa um pouco mais performática que usa a busca binária (binary search) para determinar a posição correta da troca. No pior caso o número de comparações é linearítmica O(n log n).

Já em arrays maiores, a partir de 32 elementos, o algoritmo de ordenação é o TimSort. TimSort é um algoritmo derivado de Merge Sort e Insertion Sort, no melhor caso o número de comparações é linear O(n), no pior é linearítmico O(n log n). Esse também é um algoritmo recente, descoberto em 2002 por Tim Peters, para a linguagem Python. O uso desses algoritmos também fazem parte de melhorias do Java 7, verifique a classes  TimSort.java e ComparableTimSort.java.

Importante a ressalva de quem define a classificação de cada objeto durante o sort é o método compareTo de Comparable.

Coleções de String

No próximo exemplo uso a coleção TreeSet para organizar algumas Strings:
  Collection<String> content = new TreeSet<>();
  content.add("Jose");
  content.add("Andre");
  content.add("Claudia");
  content.add("Bruna");

O TreeSet mantém os elementos classificados via Comparator ou Comparable, nesse caso através do método compareTo de Comparable. O TreeSet, como em versões anteriores do Java, mantém os elementos em TreeMap, que por sua vez continua utilizando o Red-Black Tree como algoritmo de ordenação. Por manter os elementos em uma ãrvore balanceada, esse algoritmo é extremamente eficiente, suas as operações são logaritmicas O(log n).

O trecho a seguir, um exemplo de ordenação em uma lista de String:
  List<String> content = new ArrayList<>();
  content.add("Jose");
  content.add("Andre");
  content.add("Claudia");
  content.add("Bruna");
  Collections.sort(content);

Em listas o Java usa o mesmo mecanismo de ordenação aplicado em arrays. O método sort de Collections usa o toArray da lista p/ recuperar os elementos contidos em um array, realiza a ordenação do array (Arrays.sort) e por fim atualiza os elementos na lista de acordo com resultado da ordenação.

O compareTo não funciona como o esperado?

A classificação natural da String é a ordem alfabética (lexicographically), ela ocorre através do método compareTo de Comparable. Esse método funciona perfeitamente quando não há necessidade de usar caracteres especiais, ou diferenciar letras minúsculas e maiúsculas. No começo do post, citei algumas dificuldades com o uso de caracteres com acentuação e maiúsculas com char, o mesmo vale para a String!

Veja um exemplo:
  String content[] = { "Andrei", "Andréa", "Cláudia", "Claudio" };
  Arrays.sort(content);

O resultado desse sort é: "Andrei", "Andréa", "Claudio" e "Cláudia".

Uma solução simples para esse tipo de problema é usar classe Collator, introduzida a partir do Java 5. Collator é uma classe abstrata, que implementa Comparator e define um conjunto de regras para realizar a comparação entre strings a partir de um determinado locale. Os principais idiomas são suportados por Collator, através de sua classe filha RuleBasedCollator. Uma sobrecarga do método sort, de Arrays, recebe um Comparator como argumento viabilizando o uso de Collator.
Veja:
  String content[] = { "Andrei", "andréa", "Cláudia", "Claudio" };
  Collator colPtBr = Collator.getInstance(new Locale("pt_BR"));
  Arrays.sort(content, colPtBr);

Note o valor "andréa", usando somente letras minúsculas. Agora o resultado do sort é: "andréa", "Andrei", "Cláudia" e "Claudio".

O Collator em pt_BR determina que caso duas palavras sejam semelhantes, variando apenas a acentuação, a palavra com acento vem logo após a palavra sem acento. Veja o resultado de comparações via Collator e Comparable com algumas Strings:
  System.out.println(colPtBr.compare("Andréa", "andrea"));  // 1: Andréa após andrea
  System.out.println("Andréa".compareTo("andrea"));  // -32: Andréa antes andrea

  System.out.println(colPtBr.compare("maca", "maçã"));  // -1: maca antes de maçã
  System.out.println("maca".compareTo("maçã"));  // -132: maca antes de maçã 

Mais um detalhe sobre o Collator pt_BR, é em relação a letras minúsculas e maiúsculas. No caso de duas strings semelhantes, variando apenas letras minúsculas e maiúsculas, o Collator assume que a String com letra minúscula fica antes da String com maiúscula. Veja:
  System.out.println(colPtBr.compare("pedro", "PEDRO")); // -1: pedro antes de PEDRO
  System.out.println("pedro".compareTo("PEDRO")); // 32: pedro após PEDRO

A classe Collator permite o uso de estragégias "mais fortes" de comparação. No método setStrength é possível, por exemplo, pedir ao Collator que as diferenças entre acentuação, maiúsculas e minúsculas sejam ignoradas. Veja um exemplo:
  colPtBr.setStrength(Collator.PRIMARY);
  
  System.out.println(colPtBr.compare("pedro", "PEDRO")); // 0
  System.out.println(colPtBr.compare("Andréa", "andrea"));  // 0
  System.out.println(colPtBr.compare("maca", "maçã"));  // 0

Em casos mais simples, cuja a ordenação deve apenas desconsiderar diferenças entre letras maísculas e minúsculas, é possível usar um Comparator pronto e disponível na classe String: a constante CASE_INSENSITIVE_ORDER.
  String content[] = { "A", "x", "c", "B", "d", "a" };
  Arrays.sort(content, String.CASE_INSENSITIVE_ORDER);

Resultado da ordenação é: A a B c d x

Collator vs performance

O uso em de Collator em grande volume de objetos pode degradar a performance. Uma alternativa para reverter esse problema é utilizar a classe CollationKey, que armazena a chave binária em representação a uma string. Veja como funcionaria essa estratégia:
  String content[] = { "Andrei", "andréa", "Cláudia", "Claudio" };
  CollationKey[] collKeys = new CollationKey[content.length];
  
  Collator colPtBr = Collator.getInstance(new Locale("pt_BR"));
  for (int i = 0; i < collKeys.length; i++) {
    //guarda a chave da string
    collKeys[i] = colPtBr.getCollationKey(content[i]);
  }
  
  Arrays.sort(collKeys); //ordeno as chaves do collator
  
  for (int i=0; i < collKeys.length; i++) {
    System.out.print(content[i]+" ");
  }

O truque desse último trecho é colocar as chaves geradas pelo Collator em um array, ordenar esse array e por fim exibir o as strings de acordo com a ordem das chaves.

Coloquei boa parte do código desse post no github.

@edermag

Wednesday, September 04, 2013

Como extrair um diretório de um Zip c/ Java

Exemplo de um programa simples, com Java 7, para extrair um diretório (e filhos se existir) contido em um arquivo zip (tar / war / ear / jar ...).
public class ExtractZipDir {
 
  public static void main(String[] args ) {
    if (args.length < 2) {
      System.out.println("Informe o arquivo zip e a pasta");
      return;
    }
    
    String zipName = args[0];
    String dirName =  args[1];
    extract(zipName, dirName);
  }
  
  static void extract(String zipName, String dirName) {
    long before = currentTimeMillis();
    try (ZipFile zip = new ZipFile(new File(zipName))) {
      ZipContent zContent = new ZipContent(zip);
      int files = zContent.extract(dirName);
      System.out.printf("Extraiu %s arquivos (e, %sms)", files,
        currentTimeMillis() - before);
    } catch (Exception ex) {
      ex.printStackTrace();
    }
  }
    
  private static class ZipContent {
    private final ZipFile zip;
    private Map<String, List<ZipEntry>> content = new HashMap<>();
    private int count;
    
    private static final String SEPARATOR = "/";
    private static final String ROOT_DIRECTORY = ".";
    private static final int BUFFER = 2048;
    
    private ZipContent (ZipFile zipFile) {
      zip = zipFile;
      organizeEntries(zip.entries());
    }
      
    private void organizeEntries(Enumeration<? extends ZipEntry> entries) {
      putRootDir();
       
      while (entries.hasMoreElements()) {
        ZipEntry entry = entries.nextElement();
        putEntry(entry);
      }
    }
      
    private void putEntry(ZipEntry entry) {
      String path = extractDirNameFromEntry(entry);
      List<ZipEntry> entries = content.get(path);
      if (entries == null) {
        content.put(path, new LinkedList<ZipEntry>());
      } else {
        entries.add(entry);
      }
    }
    
    private void putRootDir() {
      content.put(ROOT_DIRECTORY, new LinkedList<ZipEntry>());
    }
    
    private List<ZipEntry> listContent(String folder) {
      return content.get(folder);
    }
    
    private boolean hasDirectory(String folder) {
      return content.keySet().contains(folder);
    }
    
    private Queue<String> getAllDirectoriesFromParent(String dir) {
      Queue<String> q = new LinkedList<>();
      for (String d: content.keySet()) {
        if (d.contains(dir) && !d.equals(dir))
          q.add(d);
      }
      q.add(dir);
      return q;
    }
      
    private int extract(String dir) {
      if (!dir.equals(ROOT_DIRECTORY)) {
        if (!dir.endsWith(SEPARATOR)) {
          dir = dir.concat(SEPARATOR);
        }
        
        if (!hasDirectory(dir)) {
          throw new RuntimeException("Directory not found!");
        }
      }
      
      count = 0;
      Queue<String> dirs = getAllDirectoriesFromParent(dir);
      while (!dirs.isEmpty()) {
        String path = dirs.poll();
        List<ZipEntry> entries = listContent(path);
        File parent = new File(path);
        parent.mkdirs();
        
        for (ZipEntry entry: entries) {
          extract(parent, entry);
          count++;
        }
      }
      return count;
    }
      
    private void extract(File path, ZipEntry e) {
      String fileName = extractFilenameFromEntry(e);
      File destFile = new File(path, fileName);
      try (BufferedInputStream is = new BufferedInputStream(zip.getInputStream(e));
           FileOutputStream fos = new FileOutputStream(destFile);
           BufferedOutputStream dest = new BufferedOutputStream(fos, BUFFER)) {
        int currentByte;
        byte data[] = new byte[BUFFER];
        
        while ((currentByte = is.read(data, 0, BUFFER)) != -1) {
          dest.write(data, 0, currentByte);
        }
        dest.flush();
      } catch (IOException e) {
        throw new RuntimeException("Não foi possível extrair!\n" +
          e.getMessage(), e);
      }
    }
    
    private static String extractDirNameFromEntry(ZipEntry entry) {
      String name = entry.getName();
      if (name.lastIndexOf(SEPARATOR) != -1) {
        return name.substring(0, name.lastIndexOf(SEPARATOR)+1);
      }
      return ROOT_DIRECTORY;
    }
    
    private static String extractFilenameFromEntry(ZipEntry entry) {
      String name = entry.getName();
      if (name.lastIndexOf(SEPARATOR) == -1) {
        return name;
      }
      return name.substring(name.lastIndexOf(SEPARATOR)+1);
    }
  }
}

Alguns formas de como executar esse programa (Linux / Windows):
$ java ExtractZipDir /home/user/meu.zip dir
$ java C:\usuario\Documents\meu.zip dir

Compartilhei esse código no github.

@edermag