Еще один новичок в Java

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Здравствуй, сообщество Кодфорсес! Как вы уже догадались, я ~~решил найти источник халявной длинки~~ хочу начать учить Java. Под рукой есть хорошая книга — Г. Шилдт, Java, полное руководство — некоторые основы я (надеюсь) изучил. Но эта книга не нацелена помочь олимпиаднику, потому я здесь, со своими вопросами:

1) Как лучше всего хранить графы в Java? Какие структуры, их комбинации наиболее выгодны для использования?

2) Насколько я знаю, Java — язык довольно медленный. Какие хаки используются для ускорения программ? (Про быстрое чтение я знаю)

3) Допустим мне надо n деревьев отрезков, каждое из которых хранится в массиве (т.е. массив деревьев отрезков). Какой вариант будет более выигрышным — описать класс, в котором будут храниться непосредственно деревья и дополнительная информация, и в нем описывать необходимые методы, или же завести двумерный массив, отдельный (static?) метод и просто передавать туда массив, хранящий дерево, в качестве параметра? Что сожрет больше времени и памяти?

4) Убрано (было непонятно)

5) Насколько применимы в олимпиадах HashSet/HashMap? Есть ли вероятность что они упадут? Где можно прочитать о времени работы их методов? (Гугл особо не помог).

6) Решил скачать IDEA и начать работать в ней. Где можно найти русскоязычную документацию?

На этом все, надеюсь я не сильно вам надоел :). Если у вас есть примеры применения чего-либо — буду очень рад вашим исходникам. Заранее спасибо!

int n = sc.nextInt(), m = sc.nextInt(); int[][] graph = new int[n][]; int[] a = new int[m], b = new int[m]; int[] deg = new int[n]; int[] pos = new int[n]; for (int i = 0; i < m; i++) { a[i] = sc.nextInt() - 1; b[i] = sc.nextInt() - 1; deg[a[i]]++; } for (int i = 0; i < n; i++) { graph[i] = new int[deg[i]]; } for (int i = 0; i < m; i++) { graph[a[i]][pos[a[i]]++] = b[i]; }

for (int k = 0; k < n; k++) { int[] mk = m[k]; for (int i = 0; i < n; i++) { int[] mi = m[i]; for (int j = 0; j < n; j++) { int newval = mi[k] + mk[j]; if (newval < mi[j]) { mi[j] = newval; } } } }

Комментарии (28)

Написать комментарий?

CountZero

12 лет назад, # |

5) судя по личному опыту — применимы, если речь идет о числе обращений до пары миллионов. Сложность везде такая же, как у аналогов из C++ — амортизированное О(1). Также есть вероятность взлома — http://mirror.codeforces.com/blog/entry/4876

Кстати насчет халявной длинки, ее вроде как хотят реализовать в C++14

→ Ответить

BekzhanKassenov

12 лет назад, # ^ |

← Rev. 3 →

Ну до С++14 еще жить и жить :) А где можно почитать теорию об этих структурах данных?

в википедии, там все подробно описано http://en.wikipedia.org/wiki/Hash_table

pirevitch

← Rev. 2 →

1) Я знаю лишь три варианта, причём всеобщих, не только на Java. Не считая матрицы смежности, аналогично, это ArrayList g[], и граф через самописные списки с помощью нескольких обычных массивов.

2) Я бы не сказал, что он медленный. У него куча медленных аспектов. Например, многомерные массивы, с ними хоть и удобно работать, но это массивы объектов, едят много памяти и времени. Известный хак — размерности должны быть по возрастанию. То есть new int[2][1000000] лучше, чем new int[1000000][2]. А ещё нельзя (особенно на здесь на cfr) сортировать через Arrays.sort() массивы примитивов, есть анти-Java-Sort тесты, нагибающие стандартную сортировку.

3) По моему личному опыту — без разницы.

4) не понял вопроса

5) Во-первых скажу, что (опять же по опыту) они сильно медленнее аналогов в c++, особенно Map. О HashMap ещё уже кое-что писали, его можно тоже нагнуть по TL.

Про 4: Допустим есть задача, решение которой можно (и логичнее) разбить на несколько классов. Может ли оказаться, что после такого разбиения программа начнет тормозить?

andrey_s

map в с++ основан на rb-tree и дает гарантированную оценку времени работы insert, find и т.д. как O(log N), HashMap в Java основан, как видно из названия, на хеш-таблице и в среднем случае работает за O(1).

ну для тех, кто не понял, я имел ввиду TreeMap.

dalex

1) ArrayList<Integer>[] — то же самое, что vector<int> v[100500]. Очень удобно бегать по смежным вершинам: for (int to : graph[from]) { ... }

2) Меньше объектов и все будет нормально.

3) Я бы делал класс, удобнее же. Производительность одинаковая будет.

4) Знатоки терминологии негодуют: создаются объекты, а не классы. Где-нибудь до миллиона объектов обычно влезает в TL.
Наиболее плохо это сказывается в каком-нибудь FFT, где использование класса комплексных чисел раз в 10-15 медленнее, чем два массива double. Все потому, что в FFT O(NlogN) операций с комплексными числами, да еще и с немаленькой константой.

5) На Codeforces, видимо, с недавних пор неприменимы. А на нормальных контестах обычно авторы оказываются нормальными людьми и не делают такие тесты.

6) А зачем? Там и так все понятно. Лучше читать Javadoc у классов из java.util

Про четвертое — я имел ввиду именно классы) Т.е. выгоднее все слить в класс Main и разбить на функции, или поделить на несколько классов?

Ну вот когда бы ты в C++ написал pair<pair<pair<.....>>> или struct, в Java надо писать класс

Уберу-ка этот вопрос из поста) Кажись неправильно я его сформулировал.

По поводу инициализации ArrayList — я написал такой код:

ArrayList <Integer>[] g = new ArayList [n];

for (int i = 0; i < n; i++)
            g[i] = new ArrayList<Integer> ();

Он выдает warning, в котором говорится, что g = new ArayList [n]; — непроверенное преобразование (unchecked conversion) из ArrayList <Integer>[] в ArrayList [] и просит заменить на первое. Если я делаю, как просит компилятор, то он выдает ошибку компиляции generic array creation. Как делать правильно?

-9

Забить на warning

Минусуют те, кто ни разу не писал на джаве.

+11

Ну это несерьезно) Мне интересно что значит этот warning, как его исправить и почему ArrayList <Integer>[] дает СЕ.

OSt

← Rev. 7 →

В Яве нельзя создать массив из ArrayList'оф без предупреждений компилятора, т.к. это не typesafe. Если бы это было иначе — мы могли бы во время выполнения программы получать ClassCastException.

Очень хороший пример ниже

List[] stringLists = new List[1]; // (1)

List intList = Arrays.asList(42); // (2)

Object[] objects = stringLists; // (3)

objects[0] = intList; // (4)

String s = stringLists[0].get(0); // (5)

Допустим, было бы можно делать то, что в (1).

Посмотрите, к чему тогда могли бы мы прийти.

Тип элементов массива вычисляется во время выполнения, а дженерики провеяются во время компиляции и информация о них во время выполнения отсутствует + List < Integer > не является потомком List < Object >.

Очень много интересной информации о дженериках я подчерпнул из Effective Java. Глава "Gegerics".

Чтобы компилятор переставал ругаться лично я в коде создавал примерно такие классы class IntArrayList extends ArrayList{} и потом создавал массив из IntArrayList. Компилятор ругаться вроде переставал :-)

Но иногда даже стараясь убрать все эти предупреждения, компилятор продолжает слегка "тупить" и приходится подавлять его warnings через вставку максимально близкого к месту предупреждения аннотации @SuppressWarnings("unchecked").

Да я понял пример. А как тогда делать typesafe?

С массивами — никак. Дженерики хорошо работают только с дженериками. Можно попробовать использовать вместо массивов ArrayList и в него запихивать другой ArrayList :-)

wistful23

Посмотрите здесь http://www8.cs.umu.se/kurser/tdbb24/HT05/jem/download/generics-tutorial.pdf стр. 15-16

Интересная статья. Надо почитать.

AlexanderBolshakov

1) dalex описал удобный способ, но при наличии проблем с TL/ML стоит использовать способ быстрый. А именно: завести массив массивов ребер, потом считать все ребра, потом создать сами массивы ребер и заполнить их. Краткий пример кода (ориентированный невзвешенный граф, на более сложные случаи обобщается без проблем):

2) Про отказ от объектов уже было упомянуто, также при жестком пропихе асимптотически неоптимального кода стоит отказываться и от лишних мелких функций (вызов функции в Java в сравнении с C++ является крайне дорогостоящей операцией — лично читал исходники Java VM). Также стоит записывать в локальные переменные значения выражений, которые используются несколько раз (пример: стоит кэшировать строки двумерных массивов).

Дисклеймер: пример к ответу на первый вопрос я написал только что, причем вслепую.

Я догадался, что код написан только что — есть косяк в последнем форе. Можно подробней про кэширование строки массива?

Вот лобовое написание алгоритма Флойда:

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            m[i][j] = min(m[i][j], m[i][k] + m[k][j]);
        }
    }
}

Вот с кэшированием (да, и я еще избавился от ресурсоемкого вызова функции min):

Как видишь, я уменьшил количество индексаций массивов на каждой итерации цикла по j с 8 до 3-4.

P.S. В чем косяк в последнем форе кода из предыдущего комментария? Я в упор не замечаю...

graph[a[i]][pos[a[i]]++] = b[i] должно быть. За способы оптимизации — спасибо!

~~Разве во втором примере не нужно обратно присвоить измененные строки?~~ Понял, что не надо

HolyInq

Я видел, что красные заменяют a[n][m] на a[1<<k*m] и обращение a[i][j] на a[i<<k+j], k = [log₂m] + 1. Как быстрее?

Вообще достаточно понятно, почему так быстрее, но обычно в таких хаках нет необходимости.

Вроде как так ещё и проще — всё одинаково позаменял и не надо изобретать велосипеды.

IlyaCk

Возможно, Вам также будет интересна тема "Представление графа списками смежности в Java"

Да, спасибо большое! А то уже начали появляться мысли сделать так. (Хотя по ссылке предлагается то же :) )

Блог пользователя BekzhanKassenov