Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > treeMap --> toArray: нарушение сортировки в итоге

Автор: hardfun 25.2.2008, 01:53

hi all.

Имеется большой список названий клиентов в кодировке Win-1251 (в моём примере он составляет 50000 строк).
Этот список был загружен из текстового файла в TreeMap<Integer, String> с компаратором, который при добавлении новых пунктов сортирует их по алфавитному принципу. В результате получился TreeMap-объект, значения которого упорядочены (условно этот объект я называю treeMapObj).

Затем к этому "деревомапу" была применена операция treeMapObj.values().toArray(new String[0]), что дало в результате массив строк. Его элементы (первые 25 строк) был выведен в окне отладчика.
Также значения "деревомапа" были выведены в текстовый файл.

К моему немалому удивлению, значения коллекции, полученной вызовом метода treeMapObj.values().toArray(....), оказались... "не совсем" упорядоченными по алфавиту! То есть, порядок следования элементов в нескольких местах НАРУШАЛСЯ. smile

Просмотр исходника метода values() показал, что этот метод просто возвращает переменную с именем = `values`.
Код метода toArray() в Collection.java  я понять не смог, т.к. в нём записано вот это вот:

    <T> T[] toArray(T[] a);

-- и всё.

ВОПРОС:  по какому принципу java формирует массив строк ? Там что, выполнение идёт в несколько потоков и они, потоки эти, "толкаются" и путают результирующий порядок элементов что ли ?!

ЗЫ. Иллюстрации в виде двух скриншотов прилагаются.
В одном из них - окно отладчика NetBeans с раскрытыми элементами объекта, вычисленного в Evaluate-окне как  treeMapObj.values() .
Во втором окне - фрагмент текстового файла, открытого в FAR'e. Нужные строки (с 16 по 19) выделены. Обратите внимание, что в текстовом файле строки упорядочены ПРАВИЛЬНО, т.е. сам treeMapObj содержит значения в ПРАВИЛЬНОМ порядке следования.

Автор: ivg 25.2.2008, 09:26

Цитата(hardfun @ 25.2.2008, 01:53

)

Этот список был загружен из текстового файла в TreeMap<Integer, String> с компаратором, который при добавлении новых пунктов сортирует их по алфавитному принципу

Здесь сортировка вроде осуществляется по ключу, а не по значению.
Что за компаратор, который сравнивает по алфавитному принципу (я надеюсь я правильно понял, что речь идёт о строках) и как вы его привязали к TreeMap<Integer, String>. Если через конструктор - то он должен быть Comparator<Integer>, а не Comparator<String>

Цитата(hardfun @ 25.2.2008, 01:53

)

К моему немалому удивлению, значения коллекции, полученной вызовом метода treeMapObj.values().toArray(....), оказались... "не совсем" упорядоченными по алфавиту! То есть, порядок следования элементов в нескольких местах НАРУШАЛСЯ.

JavaDoc по методу TreeMap.values();

Код


/**
     * Returns a {@link Collection} view of the values contained in this map.
     * The collection's iterator returns the values in ascending order
     * of the corresponding keys.
...
*/

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

Вобщем если сами не разберётесь, приведите код, который загружает TreeMap<Integer, String>, код компаратора, а так же код вывода в текстовый файл (который в правильном порядке)

Автор: hardfun 27.2.2008, 01:04

2ivg: спасибо Вам за ответ.
Повторные интенсивные тесты эту "странность" не выявили.

Я бы мог признать, что "глаза замылил", но в таких случаях всегда делаю скриншот (который выложил в предыдущем посте: там явно видно, что алфавитная сортирока НЕ соблюдена).
В этот раз был проведен тест загрузки списка в TreeMap-модель и выгрузки в новые текстовые файлы двумя способами:
1) обходом в цикле MAP-коллекции, которая является моделью списка;
2) вызовом метода listMap.values().toArray(new String[0]), который создаёт массив строк. Затем - проход по эому массиву.

Оба файла-результата были сравнены побайтно, их содержимое оказалось идентично.

ЗЫ. Насчет компараторов: я не сразу понял, как они работают. Уже после я выяснил, что после заполнения TreeMap'a данными НЕупорядоченного списка элементы в этом "деревомапе" при доступе к ним через treeMapObj.get(i), где i=0,1,2,... -- возвращаются также в НЕупорядоченном виде.
Для получения упорядоченной последовательности строк надо обходить этот "деревомап" через итератор.

Но всё равно это проще (имхо), чем манипулировать с приведением текущей модели списка к списку СТРОК (через .toArray() и Arrays.asList()), чтобы после передать этот список в Collections.sort().

Или я не прав и данные модели JList'a можно упорядочить каким-то быстрым и, главное, КОРОТКИМ способом ?

Автор: LSD 27.2.2008, 13:15

В TreeMap упорядочиваются не ключи и значения, а пары ключ-значение, причем порядок определяется ключем, значение не оказывает на него никакого влияния.

Код


TreeMap<String, Integer> map = new TreeMap<String, Integer>();
map.put("b", 1);
map.put("d", 2);
map.put("a", 3);
map.put("c", 4);
System.out.println("map.keySet() = " + map.keySet());
System.out.println("map.values() = " + map.values());

на выходе получим:

Код


map.keySet() = [a, b, c, d]
map.values() = [3, 1, 4, 2]

т.е. пары a-3, b-1, c-4, d-2 сохранены, и идут в том порядке в котором идут ключи.