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

Автор BekzhanKassenov, 12 лет назад, По-русски

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

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

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

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

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

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

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

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

  • Проголосовать: нравится
  • +30
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    По поводу инициализации 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. Как делать правильно?

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

      Забить на warning

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          Rev. 7   Проголосовать: нравится +1 Проголосовать: не нравится

          В Яве нельзя создать массив из 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").

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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

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

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

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

      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):

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

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

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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