example - recorrer hashmap java foreach

Encontrar la posición del elemento en un Java TreeMap

Question

Estoy trabajando con un TreeMap de Strings TreeMap<String, String> y usándolo para implementar un Dictionay de palabras.

Luego tengo una colección de archivos y me gustaría crear una representación de cada archivo en el espacio vectorial (espacio de palabras) definido por el diccionario.

Cada archivo debe tener un vector que lo represente con las siguientes propiedades:

• el vector debe tener el mismo tamaño que el diccionario
• para cada palabra contenida en el archivo, el vector debe tener un 1 en la posición correspondiente a la posición de la palabra en el diccionario
• para cada palabra no contenida en el archivo, el vector debe tener un -1 en la posición correspondiente a la posición de la palabra en el diccionario

Entonces mi idea es usar un Vector<Boolean> para implementar estos vectores. (Esta forma de representar documentos en una colección se llama Modelo Booleano - http://www.site.uottawa.ca/~diana/csi4107/L3.pdf )

El problema que estoy enfrentando en el procedimiento para crear este vector es que necesito una forma de encontrar la posición de una palabra en el diccionario, algo como esto:

String key;
int i = get_position_of_key_in_Treemap(key); <--- purely invented method...

1) ¿Hay algún método como este que pueda usar en un TreeMap? De lo contrario, ¿podría proporcionar algún código para ayudarme a implementarlo?

2) ¿Hay un iterador en TreeMap (está ordenado alfabéticamente en las teclas) del cual puedo obtener posición?

3) Eventualmente, ¿debería usar otra clase para implementar el diccionario? (Si crees que con TreeMaps no puedo hacer lo que necesito) En caso afirmativo, ¿cuál?

Gracias por adelantado.

PIEZA AÑADIDA

La solución propuesta por dasblinkenlight se ve bien, pero tiene el problema de la complejidad (lineal con la dimensión del diccionario debido a la copia de claves en una matriz), y la idea de hacerlo para cada archivo no es aceptable.

¿Alguna otra idea para mis preguntas?

Answer 1

Yo tuve el mismo problema. Así que tomé el código fuente de java.util.TreeMap y escribí IndexedTreeMap . Implementa mi propio IndexedNavigableMap :

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

La implementación se basa en actualizar los pesos del nodo en el árbol rojo-negro cuando se cambia. El peso es la cantidad de nodos secundarios debajo de un nodo dado, más uno mismo. Por ejemplo, cuando un árbol se gira hacia la izquierda:

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

updateWeight simplemente actualiza los pesos hasta la raíz:

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

Y cuando necesitamos encontrar el elemento por índice, aquí está la implementación que usa ponderaciones:

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

También resulta muy útil encontrar el índice de una clave:

    public int keyIndex(K key) {
    if (key == null) {
        throw new NullPointerException();
    }
    Entry<K, V> e = getEntry(key);
    if (e == null) {
        throw new NullPointerException();
    }
    if (e == root) {
        return getWeight(e) - getWeight(e.right) - 1;//index to return
    }
    int index = 0;
    int cmp;
    if (e.left != null) {
        index += getWeight(e.left);
    }
    Entry<K, V> p = e.parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        while (p != null) {
            cmp = cpr.compare(key, p.key);
            if (cmp > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        while (p != null) {
            if (k.compareTo(p.key) > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    }
    return index;
}

Implementaré IndexedTreeSet pronto, mientras tanto, puedes usar el conjunto de claves de IndexedTreeMap.

Actualización: IndexedTreeSet se implementa ahora.

Puede encontrar el resultado de este trabajo en https://github.com/geniot/indexed-tree-map

Answer 2

Una vez que haya construido su mapa de árbol, copie las claves ordenadas en una matriz y use Arrays.binarySearch para buscar el índice en la hora O (logN). Si necesita el valor, haga una búsqueda en el mapa original también.

Editar: así es como se copian las claves en una matriz

String[] mapKeys = new String[treeMap.size()];
int pos = 0;
for (String key : treeMap.keySet()) {
    mapKeys[pos++] = key;
}

Answer 3

Estoy de acuerdo con Isolvieira. Quizás el mejor enfoque sería usar una estructura diferente a TreeMap.

Sin embargo, si aún desea utilizar el índice de las claves, una solución sería contar cuántas teclas son más bajas que la clave que está buscando.

Aquí hay un fragmento de código:

    java.util.SortedMap<String, String> treeMap = new java.util.TreeMap<String, String>();
    treeMap.put("d", "content 4");
    treeMap.put("b", "content 2");
    treeMap.put("c", "content 3");
    treeMap.put("a", "content 1");

    String key = "d"; // key to get the index for
    System.out.println( treeMap.keySet() );

    final String firstKey = treeMap.firstKey(); // assuming treeMap structure doesn''t change in the mean time
    System.out.format( "Index of %s is %d %n", key, treeMap.subMap(firstKey, key).size() );

Answer 4

No hay tal implementación en el JDK en sí. Aunque TreeMap itera en el orden natural de las claves, sus estructuras internas de datos están todas basadas en árboles y no en matrices (recuerde que Maps no ordena claves, por definición, a pesar de eso el caso de uso muy común).

Dicho esto, debe hacer una elección, ya que no es posible tener O (1) tiempo de cálculo para sus criterios de comparación tanto para la inserción en el Map como para el indexOf(key) del indexOf(key) . Esto se debe a que el orden lexicográfico no es estable en una estructura de datos mutable (por oposición al orden de inserción, por ejemplo). Un ejemplo: una vez que inserta el primer par clave-valor (entrada) en el mapa, su posición siempre será una. Sin embargo, dependiendo de la segunda clave insertada, esa posición podría cambiar ya que la nueva clave puede ser "mayor" o "menor" que la del Map . Seguramente puede implementar esto manteniendo y actualizando una lista indexada de claves durante la operación de inserción, pero luego tendrá O (n log (n)) para sus operaciones de inserción (ya que tendrá que volver a ordenar una matriz). Eso podría ser deseable o no, según sus patrones de acceso a datos.

ListOrderedMap y LinkedMap en Apache Commons se acercan mucho a lo que necesita pero se basa en el orden de inserción. Puede verificar su implementación y desarrollar su propia solución al problema con poco a moderado esfuerzo, creo (eso debería ser solo una cuestión de reemplazar la matriz de respaldo interno de ListOrderedMap con una lista ordenada - TreeList en Apache Commons, por ejemplo) .

También puede calcular el índice usted mismo, restando la cantidad de elementos que son inferiores a la clave dada (que debería ser más rápido que iterar a través de la lista buscando su elemento, en el caso más frecuente, ya que no está comparando nada) .

Answer 5

Una solución alternativa sería usar el método headMap . Si la palabra existe en TreeMap , entonces el size() de su mapa principal es igual al índice de la palabra en el diccionario. Puede ser un poco inútil en comparación con mi otra respuesta, a través de.

Aquí es cómo lo codifica en Java:

import java.util.*;

class Test {
    public static void main(String[] args) {
        TreeMap<String,String> tm = new TreeMap<String,String>();
        tm.put("quick", "one");
        tm.put("brown", "two");
        tm.put("fox", "three");
        tm.put("jumps", "four");
        tm.put("over", "five");
        tm.put("the", "six");
        tm.put("lazy", "seven");
        tm.put("dog", "eight");
        for (String s : new String[] {
            "quick", "brown", "fox", "jumps", "over",
            "the", "lazy", "dog", "before", "way_after"}
        ) {
            if (tm.containsKey(s)) {
                // Here is the operation you are looking for.
                // It does not work for items not in the dictionary.
                int pos = tm.headMap(s).size();
                System.out.println("Key ''"+s+"'' is at the position "+pos);
            } else {
                System.out.println("Key ''"+s+"'' is not found");
            }
        }
    }
}

Aquí está la salida producida por el programa:

Key ''quick'' is at the position 6
Key ''brown'' is at the position 0
Key ''fox'' is at the position 2
Key ''jumps'' is at the position 3
Key ''over'' is at the position 5
Key ''the'' is at the position 7
Key ''lazy'' is at the position 4
Key ''dog'' is at the position 1
Key ''before'' is not found
Key ''way_after'' is not found

Answer 6

Le sugiero que escriba una lista de exclusión para almacenar su diccionario, ya que esto ofrecerá búsquedas O (log N), inserción y eliminación, y también podrá proporcionar un índice (las implementaciones de árbol generalmente no pueden devolver un índice ya que los nodos no lo sé, y habría un costo para mantenerlos actualizados). Desafortunadamente, la implementación java de ConcurrentSkipListMap no proporciona un índice, por lo que necesitaría implementar su propia versión.

Obtener el índice de un ítem sería O (log N), si quiere tanto el índice como el valor sin hacer 2 búsquedas, entonces debería devolver un objeto envoltorio que contenga ambos.

Answer 7

¿Has pensado hacer que los valores en tu TreeMap contengan la posición en tu diccionario? Estoy usando un BitSet aquí para los detalles de mi archivo.

Esto no funciona tan bien como mi otra idea a continuación.

Map<String,Integer> dictionary = new TreeMap<String,Integer> ();

private void test () {
  // Construct my dictionary.
  buildDictionary();
  // Make my file data.
  String [] file1 = new String[] {
    "1", "3", "5"
  };
  BitSet fileDetails = getFileDetails(file1, dictionary);
  printFileDetails("File1", fileDetails);
}

private void printFileDetails(String fileName, BitSet details) {
  System.out.println("File: "+fileName);
  for ( int i = 0; i < details.length(); i++ ) {
    System.out.print ( details.get(i) ? 1: -1 );
    if ( i < details.length() - 1 ) {
      System.out.print ( "," );
    }
  }
}

private BitSet getFileDetails(String [] file, Map<String, Integer> dictionary ) {
  BitSet details = new BitSet();
  for ( String word : file ) {
    // The value in the dictionary is the index of the word in the dictionary.
    details.set(dictionary.get(word));
  }
  return details;
}

String [] dictionaryWords = new String[] {
  "1", "2", "3", "4", "5"
};

private void buildDictionary () {
  for ( String word : dictionaryWords ) {
    // Initially make the value 0. We will change that later.
    dictionary.put(word, 0);
  }
  // Make the indexes.
  int wordNum = 0;
  for ( String word : dictionary.keySet() ) {
    dictionary.put(word, wordNum++);
  }
}

Aquí la construcción de los detalles del archivo consiste en una búsqueda única en el TreeMap para cada palabra en el archivo.

Si planeaba usar el value en el diccionario TreeMap para otra cosa, siempre podría componerlo con un Integer .

Adicional

Pensando más en eso, si el campo de value del Map está destinado a algo, siempre se pueden usar teclas especiales que calculan su propia posición en el Map y actúan como String para la comparación.

private void test () {
  // Dictionary
  Map<PosKey, String> dictionary = new TreeMap<PosKey, String> ();
  // Fill it with words.
  String[] dictWords = new String[] {
                       "0", "1", "2", "3", "4", "5"};
  for ( String word : dictWords ) {
    dictionary.put( new PosKey( dictionary, word ), word );
  }
  // File
  String[] fileWords = new String[] {
                       "0", "2", "3", "5"};
  int[] file = new int[dictionary.size()];
  // Initially all -1.
  for ( int i = 0; i < file.length; i++ ) {
    file[i] = -1;
  }
  // Temp file words set.
  Set fileSet = new HashSet( Arrays.asList( fileWords ) );
  for ( PosKey key : dictionary.keySet() ) {
    if ( fileSet.contains( key.getKey() ) ) {
      file[key.getPosiion()] = 1;
    }
  }

  // Print out.
  System.out.println( Arrays.toString( file ) );
  // Prints: [1, -1, 1, 1, -1, 1]

}

class PosKey
    implements Comparable {
  final String key;
  // Initially -1
  int position = -1;
  // The map I am keying on.
  Map<PosKey, ?> map;

  public PosKey ( Map<PosKey, ?> map, String word ) {
    this.key = word;
    this.map = map;
  }

  public int getPosiion () {
    if ( position == -1 ) {
      // First access to the key.
      int pos = 0;
      // Calculate all positions in one loop.
      for ( PosKey k : map.keySet() ) {
        k.position = pos++;
      }
    }
    return position;
  }

  public String getKey () {
    return key;
  }

  public int compareTo ( Object it ) {
    return key.compareTo( ( ( PosKey )it ).key );
  }

  public int hashCode () {
    return key.hashCode();
  }
}

NB: se getPosition() que una vez que getPosition() ha sido llamado, el diccionario no se cambia.

Answer 8

Me gustaría agradecer a todos ustedes por el esfuerzo que hicieron al responder mi pregunta, todos fueron muy útiles y tomar lo mejor de cada uno de ellos me hizo llegar a la solución que realmente implementé en mi proyecto.

Lo que creo son las mejores respuestas para mis preguntas únicas son:

2) No hay un iterador definido en TreeMaps como @Isoliveira sais:

There''s no such implementation in the JDK itself. 
Although TreeMap iterates in natural key ordering,
its internal data structures are all based on trees and not arrays
(remember that Maps do not order keys, by definition, 
in spite of that the very common use case).

y como encontré en este SO, ¿cómo iterar sobre un TreeMap? , la única forma de iterar en elementos en un Map es usar map.entrySet() y usar Iterators definidos en Set (o alguna otra clase con Iteradores).

3) Es posible utilizar un TreeMap para implementar Dictionary, pero esto garantizará una complejidad de O (logN) para encontrar el índice de una palabra contenida (costo de una búsqueda en una estructura de datos de árbol).

Usar un HashMap con el mismo procedimiento tendrá complejidad O (1).

1) No existe tal método. La única solución es implementarlo por completo.

Como dijo @Paul

Assumes that once getPosition() has been called, the dictionary is not changed.

la suposición de la solución es que una vez que se crea ese diccionario, no se cambiará después: de esta manera, la posición de una palabra siempre será la misma.

Dando esta suposición encontré una solución que permite construir Diccionario con complejidad O (N) y después de garantizar la posibilidad de obtener el índice de una palabra contenida con el tiempo de constatación O (1) en la búsqueda.

Definí el diccionario como un HashMap como este:

public HashMap<String, WordStruct> dictionary = new HashMap<String, WordStruct>();

• key -> the String representa la palabra contenida en Dictionary
• value -> un Object de una clase creada WordStruct

donde la clase WordStruct se define así:

public class WordStruct {

    private int DictionaryPosition;    // defines the position of word in dictionary once it is alphabetically ordered

    public WordStruct(){

    }

    public SetWordPosition(int pos){
        this.DictionaryPosition = pos;
    }

}

y me permite mantener la memoria de cualquier tipo de atributo que me guste acoplar con la entrada de palabras del Diccionario.

Ahora llené el diccionario iterando sobre todas las palabras contenidas en todos los archivos de mi colección:

THE FOLLOWING IS PSEUDOCODE

for(int i = 0; i < number_of_files ; i++){

        get_file(i);

        while (file_contais_words){

            dictionary.put( word(j) , new LemmaStruct());

        }

}   

Una vez que HashMap se rellena en cualquier orden, uso el procedimiento indicado por @dasblinkenlight para ordenarlo de una vez por todas con la complejidad O (N)

    Object[] dictionaryArray = dictionary.keySet().toArray();
    Arrays.sort(dictionaryArray);

    for(int i = 0; i < dictionaryArray.length; i++){

        String word = (String) dictionaryArray[i];
        dictionary.get(word).SetWordPosition(i);

    }

Y a partir de ahora para tener posición de índice en orden alfabetico de palabra en el diccionario solo lo que se necesita es acceder a su variable DictionaryPosition :

dado que se sabe que solo necesita acceder y esto tiene un costo constante en un HashMap .

¡Gracias de nuevo y les deseo a todos una feliz Navidad!