Здравствуй, сообщество Кодфорсес! Как вы уже догадались, я решил найти источник халявной длинки хочу начать учить Java. Под рукой есть хорошая книга — Г. Шилдт, Java, полное руководство — некоторые основы я (надеюсь) изучил. Но эта книга не нацелена помочь олимпиаднику, потому я здесь, со своими вопросами:
1) Как лучше всего хранить графы в Java? Какие структуры, их комбинации наиболее выгодны для использования?
2) Насколько я знаю, Java — язык довольно медленный. Какие хаки используются для ускорения программ? (Про быстрое чтение я знаю)
3) Допустим мне надо n деревьев отрезков, каждое из которых хранится в массиве (т.е. массив деревьев отрезков). Какой вариант будет более выигрышным — описать класс, в котором будут храниться непосредственно деревья и дополнительная информация, и в нем описывать необходимые методы, или же завести двумерный массив, отдельный (static?) метод и просто передавать туда массив, хранящий дерево, в качестве параметра? Что сожрет больше времени и памяти?
4) Убрано (было непонятно)
5) Насколько применимы в олимпиадах HashSet/HashMap? Есть ли вероятность что они упадут? Где можно прочитать о времени работы их методов? (Гугл особо не помог).
6) Решил скачать IDEA и начать работать в ней. Где можно найти русскоязычную документацию?
На этом все, надеюсь я не сильно вам надоел :). Если у вас есть примеры применения чего-либо — буду очень рад вашим исходникам. Заранее спасибо!
5) судя по личному опыту — применимы, если речь идет о числе обращений до пары миллионов. Сложность везде такая же, как у аналогов из C++ — амортизированное О(1). Также есть вероятность взлома — http://codeforces.net/blog/entry/4876
Кстати насчет халявной длинки, ее вроде как хотят реализовать в C++14
Ну до С++14 еще жить и жить :) А где можно почитать теорию об этих структурах данных?
в википедии, там все подробно описано http://en.wikipedia.org/wiki/Hash_table
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: Допустим есть задача, решение которой можно (и логичнее) разбить на несколько классов. Может ли оказаться, что после такого разбиения программа начнет тормозить?
map в с++ основан на rb-tree и дает гарантированную оценку времени работы insert, find и т.д. как O(log N), HashMap в Java основан, как видно из названия, на хеш-таблице и в среднем случае работает за O(1).
ну для тех, кто не понял, я имел ввиду TreeMap.
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
— я написал такой код:Он выдает warning, в котором говорится, что
g = new ArayList [n];
— непроверенное преобразование (unchecked conversion) изArrayList <Integer>[]
вArrayList []
и просит заменить на первое. Если я делаю, как просит компилятор, то он выдает ошибку компиляцииgeneric array creation
. Как делать правильно?Забить на warning
Минусуют те, кто ни разу не писал на джаве.
Ну это несерьезно) Мне интересно что значит этот warning, как его исправить и почему
ArrayList <Integer>[]
дает СЕ.В Яве нельзя создать массив из 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 :-)
Посмотрите здесь http://www8.cs.umu.se/kurser/tdbb24/HT05/jem/download/generics-tutorial.pdf стр. 15-16
Интересная статья. Надо почитать.
1) dalex описал удобный способ, но при наличии проблем с TL/ML стоит использовать способ быстрый. А именно: завести массив массивов ребер, потом считать все ребра, потом создать сами массивы ребер и заполнить их. Краткий пример кода (ориентированный невзвешенный граф, на более сложные случаи обобщается без проблем):
2) Про отказ от объектов уже было упомянуто, также при жестком пропихе асимптотически неоптимального кода стоит отказываться и от лишних мелких функций (вызов функции в Java в сравнении с C++ является крайне дорогостоящей операцией — лично читал исходники Java VM). Также стоит записывать в локальные переменные значения выражений, которые используются несколько раз (пример: стоит кэшировать строки двумерных массивов).
Дисклеймер: пример к ответу на первый вопрос я написал только что, причем вслепую.
Я догадался, что код написан только что — есть косяк в последнем форе. Можно подробней про кэширование строки массива?
Вот лобовое написание алгоритма Флойда:
Вот с кэшированием (да, и я еще избавился от ресурсоемкого вызова функции min):
Как видишь, я уменьшил количество индексаций массивов на каждой итерации цикла по j с 8 до 3-4.
P.S. В чем косяк в последнем форе кода из предыдущего комментария? Я в упор не замечаю...
graph[a[i]][pos[a[i]]++] = b[i]
должно быть. За способы оптимизации — спасибо!Разве во втором примере не нужно обратно присвоить измененные строки?Понял, что не надоЯ видел, что красные заменяют a[n][m] на a[1<<k*m] и обращение a[i][j] на a[i<<k+j], k = [log2m] + 1. Как быстрее?
Вообще достаточно понятно, почему так быстрее, но обычно в таких хаках нет необходимости.
Вроде как так ещё и проще — всё одинаково позаменял и не надо изобретать велосипеды.
Возможно, Вам также будет интересна тема "Представление графа списками смежности в Java"
Да, спасибо большое! А то уже начали появляться мысли сделать так. (Хотя по ссылке предлагается то же :) )