Para isso, usaremos a IDE Eclipse Ganymede (versão 3.4) com o JDT (Ambiente Java) e CDT (Ambiente C/C++) instalados no eclipse. Criaremos o projeto Java com o nome de "HeapsortJava" e nesse projeto colocaremos a seguinte classe no diretório "src" do projeto "HeapsortJava".
Arquivo "Heapsort.java"
-------------------------------------------------------------------------------------------------
import java.util.Arrays;
public class Heapsort {
static {
System.loadLibrary("JavaC");
}
/**
* @param args
*/
public static void main(String[] args) {
int a[] = Heapsort.geraSequencia(65536);
int a_copy[] = Arrays.copyOf(a, a.length);
/** Ordenação por heapsort em Java. */
long t0J = System.currentTimeMillis();
Heapsort.sort(a);
long t1J = System.currentTimeMillis();
System.out.println("Tempo no heapsort no Java: " + (t1J - t0J));
/** Ordenação por heapsort em C. */
long t0C = System.currentTimeMillis();
Heapsort.sortNative(a_copy);
long t1C = System.currentTimeMillis();
System.out.println("Tempo no heapsort no C: " + (t1C - t0C));
}
public static void sort(int[] array) {
Heapsort.buildMaxHeap(array);
int i = array.length - 1;
int lengthHeap = array.length;
while (i > -1) {
Heapsort.swap(array, 0, i);
lengthHeap = lengthHeap - 1;
Heapsort.maxHeapfy(array, 0, lengthHeap);
i = i - 1;
}
}
public static native void sortNative(int[] array);
private static void buildMaxHeap(int a[]) {
int i = a.length / 2;
while (i > -1) {
Heapsort.maxHeapfy(a, i, a.length);
i--;
}
}
private static void maxHeapfy(int a[], int i, int lengthHeap) {
int left = Heapsort.left(i);
int right = Heapsort.right(i);
int max = 0;
if (left < lengthHeap && a[left] > a[i]) {
max = left;
} else {
max = i;
}
if (right < lengthHeap && a[right] > a[max]) {
max = right;
}
if (max != i) {
Heapsort.swap(a, i, max);
Heapsort.maxHeapfy(a, max, lengthHeap);
}
}
private static int left(int i) {
return i << 1;
}
private static int right(int i) {
return (i << 1) + 1;
}
private static void swap(int x[], int a, int b) {
int t = x[a];
x[a] = x[b];
x[b] = t;
}
public static int[] geraSequencia(int length) {
int[] a = new int[length];
for (int i = 0; i < a.length; i++) {
a[i] = (int) (Math.random() * length);
}
return a;
}
public static void print(int a[]) {
if (a != null) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}
}
-------------------------------------------------------------------------------------------------
Nessa classe, foi definidos dois métodos para ordenação por heapsort, um com o nome de "sort" para ordenação heapsort em Java e o outro com o nome "sortNative" para ordenação heapsort em C que será implementando através do mecanismo JNI (Java Native Interface) a qual permite implementar métodos em Java através das linguagens C/C++, mas nesse exemplo usaremos apenas a linguagem C.
Importante notar nessa classe, o uso da chamada "System.loadLibrary("JavaC");" que tem como finalidade carregar a biblioteca dinâmica libJavaC.so (No Linux) ou libJavaC.dll (No Windows).
E nesta biblioteca dinâmica em C que está a implementação do método nativo "sortNative" que será descrita mais adiante nesse artigo.
Para criarmos a biblioteca dinâmica mencionada anteriormente, precisamos criar o projeto C no eclipse que será mostrado pelas seguintes figuras:
Depois da criação do projeto C chamado "JavaC", precisamos criar o arquivo cabeçalho "Heapsort.h" e o arquivo fonte "Heapsort.c". Para isso, basta usarmos o utilitário do JDK, o javah que gera os cabeçalhos apartir dos métodos nativos definidos nos arquivos compilados Java (".class"). Então, entre no diretório "bin" do projeto Java "HeapsortJava" e execute o seguinte comando:
javah Heapsort
Esse comando gera o arquivo "Heapsort.h" apartir do arquivo "Heapsort.class".
Arquivo "Heapsort.h" gerado
-----------------------------------------------------------------------------------------------
/* DO NOT EDIT THIS FILE - it is machine generated */
#include
/* Header for class Heapsort */
#ifndef _Included_Heapsort
#define _Included_Heapsort
#ifdef __cplusplus
extern "C" {
#endif
/*
* Class: Heapsort
* Method: sortNative
* Signature: ([I)V
*/
JNIEXPORT void JNICALL Java_Heapsort_sortNative
(JNIEnv *, jclass, jintArray);
#ifdef __cplusplus
}
#endif
#endif
-----------------------------------------------------------------------------------------------
Pelo método "sortNative" ser um método estático, então, a função que representa esse método nativo no C, define apenas a classe do método representado pelo tipo jclass. E também, temos uma referência para o array de inteiros como um objeto do tipo jinitArray.
A seguir, temos a implementação em C do método nativo "sortNative" no arquivo "Heapsort.c".
Arquivo "Heapsort.c"
----------------------------------------------------------------------------------------------
#include "Heapsort.h"
// Definindo funções auxiliares.
jint left(jint);
jint right(jint);
void swap(jint *, jint, jint);
void maxHeapfy(jint *, jint, jint);
void buildMaxHeap(jint *, jint);
JNIEXPORT void JNICALL Java_Heapsort_sortNative(JNIEnv *env, jclass c1, jintArray array) {
// Obtêm array de inteiros.
jint* array_aux = (*env)->GetIntArrayElements(env, array, NULL);
// Obtêm o tamanho do array.
jint length = (*env)->GetArrayLength(env, array);
buildMaxHeap(array_aux, length);
jint i = length - 1;
jint lengthHeap = length;
while (i > -1) {
swap(array_aux, 0, i);
lengthHeap = lengthHeap - 1;
maxHeapfy(array_aux, 0, lengthHeap);
i = i - 1;
}
// Libera array de inteiros.
(*env)->ReleaseIntArrayElements(env, array, array_aux, 0);
}
void buildMaxHeap(jint *a, jint length) {
jint i = length / 2;
while (i > -1) {
maxHeapfy(a, i, length);
i--;
}
}
void maxHeapfy(jint *a, jint i, jint lengthHeap) {
jint l = left(i);
jint r = right(i);
jint max = 0;
if (l < lengthHeap && a[l] > a[i]) {
max = l;
} else {
max = i;
}
if (r < lengthHeap && a[r] > a[max]) {
max = r;
}
if (max != i) {
swap(a, i, max);
maxHeapfy(a, max, lengthHeap);
}
}
jint left(jint i) {
return i << 1;
}
jint right(jint i) {
return (i << 1) + 1;
}
void swap(jint *x, jint a, jint b) {
jint t = x[a];
x[a] = x[b];
x[b] = t;
}
----------------------------------------------------------------------------------------------
Agora, precisamos definir os cabeçalhos (os arquivos ".h") a serem usados pelo projeto JavaC, veja na figura abaixo:
Depois disso, compilamos e geramos a biblioteca dinâmica que implementa o método nativo conforme a saída em console abaixo.
---------------------------------------------------------------------------------------------
**** Build of configuration Release for project JavaC ****
make all
Building file: ../src/Heapsort.c
Invoking: GCC C Compiler
gcc -I/usr/lib/jvm/java-6-openjdk/include -O3 -Wall -c -fmessage-length=0 -MMD -MP -MF"src/Heapsort.d" -MT"src/Heapsort.d" -o"src/Heapsort.o" "../src/Heapsort.c"
Finished building: ../src/Heapsort.c
Building target: libJavaC.so
Invoking: GCC C Linker
gcc -shared -o"libJavaC.so" ./src/Heapsort.o
Finished building target: libJavaC.so
---------------------------------------------------------------------------------------------
Com a biblioteca dinâmica criada, precisamos referencia-la no projeto HeapsortJava.
Para isso, basta passar o seguinte parâmetro (VM arguments) no momento de executar o projeto HeapsortJava:
-Djava.library.path=/home/user/workspace/JavaC/Release
Se certifique que o caminho "/home/user/workspace/JavaC/Release" aponta para o diretório no qual está localizado a biblioteca dinâmica libJavaC.so (Linux) ou libJavaC.dll (Windows).
Com isso, já temos o projeto HeapsortJava configurado para localizar e carregar a biblioteca dinâmica cuja saída de console é mostrada a seguir:
---------------------------------------------------------------------------------------------
Tempo no heapsort no Java: 18
Tempo no heapsort no C: 8
---------------------------------------------------------------------------------------------
Isso mostra que a execução do método de ordenação por heapsort no Java leva 18 milisegundos e no método nativo implementado em C leva apenas 8 milisegundos, praticamente a metade do tempo que o código Java puro consegue fazer! Isso mostra umas das vantagens em trabalhar com métodos nativos, que é o aumento do desempenho das aplicações!
Entretanto, o uso de métodos nativos devem ser observados com muita parcimônia, pois o mesmo sacrifica o design em prol do aumento de desempenho. E também, existem casos que o aumento de desempenho proporcionado pelo uso dos métodos nativos é praticamente insignificante em relação ao uso de métodos implementados totalmente em Java. Fora que a portabilidade do código diminui, pois devemos criar bibliotecas dinâmicas para cada sistema operacional, como o linux, windows, solaris e etc.
Referências:
http://en.wikipedia.org/wiki/Java_Native_Interface
http://java.sun.com/docs/books/jni/
