Найти позицию элемента в Java TreeMap

Ответ 1

Я хотел бы поблагодарить всех вас за те усилия, которые вы задали, отвечая на мой вопрос, все они были очень полезны, и каждый из них старался изо всех сил заставить меня подойти к решению, которое я действительно реализовал в своем проекте.

То, что я верю, чтобы быть лучшим ответом на мои вопросы:

2) В TreeMaps нет Итератора как @Isoliveira sais:

There 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).

и, как я нашел в этом ответе SO Как перебирать TreeMap?, единственный способ повторения элементов в Map - использовать map.entrySet() и используйте итераторы, определенные на Set (или какой-либо другой класс с итераторами).

3) Можно использовать TreeMap для реализации Словаря, но это будет гарантировать сложность O (logN) при поиске индекса содержащегося слова (стоимость поиска в структуре данных дерева).

Использование HashMap с той же процедурой будет вместо этого иметь сложность O (1).

1) Такой метод не существует. Единственное решение - полностью реализовать его.

Как сказал @Paul

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

предположение о том, что после создания Словаря он не будет изменен впоследствии: таким образом положение слова всегда будет одинаковым.

Предоставив это предположение, я нашел решение, которое позволяет построить словарь со сложностью O (N) и после того, как garantuees получит возможность получить индекс слова, содержащегося с постоянным временем O (1) в поиске.

Я определил словарь как HashMap следующим образом:

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

• ключ → String, представляющий слово, содержащееся в словаре
• value → a Object созданного класса WordStruct

где класс WordStruct определяется следующим образом:

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;
    }

}

и позволяет сохранять память любого атрибута, который мне нравится связывать со словом в словаре.

Теперь я заполняю словарь, повторяя все слова, содержащиеся во всех файлах моей коллекции:

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());

        }

}   

После того, как HashMap заполняется в любом порядке, я использую процедуру, указанную @dasblinkenlight, чтобы заказать ее раз и навсегда со сложностью 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);

    }

И отныне для того, чтобы иметь индексную позицию в алфавитном порядке слова в словаре, единственное, что нужно, - это использовать его переменную DictionaryPosition:

поскольку слово известно, вам просто нужно получить к нему доступ, и это имеет постоянную стоимость в HashMap.

Еще раз спасибо, и всем вам понравилось С Рождеством!

Ответ 2

Как только вы построили свою древовидную карту, скопируйте ее отсортированные ключи в массив и используйте Arrays.binarySearch для поиска индекса в O (logN). Если вам нужно значение, выполните поиск на исходной карте тоже.

Изменить: так вы копируете ключи в массив

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

Ответ 3

В JDK такой реализации нет. Хотя TreeMap выполняет итерацию в порядке естественного ключа, его внутренние структуры данных основаны на деревьях, а не на массивах (помните, что Maps не упорядочивают ключи по определению, несмотря на то, что это очень распространенный вариант использования).

Тем не менее, вы должны сделать выбор, так как невозможно вычислить время вывода O (1) для ваших критериев сравнения как для вставки в вычисления Map, так и indexOf(key). Это связано с тем, что лексикографический порядок нестабилен в изменяемой структуре данных (в отличие от порядка вставки, например). Пример: как только вы вставляете первую карту-значение (запись) в карту, ее позиция всегда будет одной. Однако в зависимости от введенного второго ключа это положение может измениться, поскольку новый ключ может быть "больше" или "ниже", чем тот, который находится в Map. Вы можете наверняка реализовать это, сохранив и обновив индексированный список ключей во время операции вставки, но тогда у вас будет O (n log (n)) для ваших операций вставки (как это потребуется для переопределения массива). Это может быть желательно или нет, в зависимости от ваших шаблонов доступа к данным.

ListOrderedMap и LinkedMap в Apache Commons приблизились к тому, что вам нужно, но полагайтесь на порядок вставки. Я считаю, что вы можете проверить их реализацию и разработать собственное решение проблемы с небольшими или умеренными усилиями (это должно быть просто заменой массива внутренней поддержки ListOrderedMap отсортированным списком - TreeList в Apache Commons, например).

Вы также можете рассчитать индекс самостоятельно, вычитая количество элементов, которые ниже, чем данный заданный ключ (который должен быть быстрее, чем повторение через список, который ищет ваш элемент, в наиболее частом случае - поскольку вы не сравнение чего-либо).

Ответ 4

Альтернативным решением было бы использовать метод TreeMap headMap. Если слово существует в TreeMap, то size() его главной карты равно индексу слова в словаре. Это может быть немного расточительно по сравнению с моим другим ответом.

Вот как вы его кодируете в 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");
            }
        }
    }
}

Вот результат, полученный программой:

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

Ответ 5

У меня была та же проблема. Поэтому я взял исходный код java.util.TreeMap и написал IndexedTreeMap. Он реализует мою собственную IndexedNavigableMap:

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

Реализация основана на обновлении весов node в красно-черном дереве при его изменении. Вес - это число дочерних узлов ниже заданного node, плюс один. Например, когда дерево поворачивается влево:

    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 просто обновляет весы до корня:

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

И когда нам нужно найти элемент по индексу, это реализация, использующая вес:

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);
}

Также очень удобно найти индекс ключа:

    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;
}

Я скоро буду использовать IndexedTreeSet, тем временем вы можете использовать набор ключей из IndexedTreeMap.

Обновление: Теперь реализован IndexedTreeSet.

Результат этой работы можно найти в https://github.com/geniot/indexed-tree-map

Ответ 6

Я согласен с Isolvieira. Возможно, лучшим подходом было бы использование другой структуры, чем TreeMap.

Однако, если вы все еще хотите использовать индекс ключей, решение будет состоять в том, чтобы подсчитать, сколько ключей меньше, чем тот ключ, который вы ищете.

Вот фрагмент кода:

    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() );

Ответ 7

Считаете ли вы, что значения в вашем TreeMap содержат позицию в словаре? Я использую BitSet здесь для подробностей моего файла.

Это не работает так же хорошо, как моя другая идея ниже.

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++);
  }
}

Здесь информация о файле состоит из одного поиска в TreeMap для каждого слова в файле.

Если вы планируете использовать value в словаре TreeMap для чего-то еще, вы всегда можете составить его с помощью Integer.

Добавлен

Размышляя об этом дальше, если поле value для Map предназначено для чего-то, вы всегда можете использовать специальные клавиши, которые вычисляют свою позицию в Map и действуют как String для сравнения.

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: Предполагается, что после вызова getPosition() словарь не изменяется.

Ответ 8

Я бы предположил, что вы пишете SkipList для хранения своего словаря, поскольку он все равно будет предлагать поиск, вставку и удаление O (log N), а также возможность предоставления индекса (реализация дерева обычно не может возвращать индекс, поскольку узлы этого не знают, и будет стоить их обновление). К сожалению, реализация Java ConcurrentSkipListMap не предоставляет индекс, поэтому вам нужно будет реализовать свою собственную версию.

Получение индекса элемента будет O (log N), если вы хотите как индекс, так и значение без выполнения двух поисков, тогда вам нужно будет вернуть объект-оболочку, содержащий оба.