43,3
рейтинг
8 января 2013 в 14:13

Разработка → Одна маленькая оптимизация

Java*
Совсем недавно со мной поделились историей одной оптимизации (привет stanislaw), которая показалась мне довольно забавной.

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

for (A a : arrayListA) { 
    // do something
    for (B b : arrayListB) {
        // do something
        for (C c : arrayListC) {
            // do something
        }
    }
}

Доступа к коду у меня нету, поэтому я передаю лишь суть повествования. Есть некий метод просчета ситуации на карте, в котором происходит много итераций по разного рода циклам. Причём, граф объектов уже создан и изменяется лишь его состояние. То есть новых объектов фактически не создается… Но тем не менее профайлер показывал приблизительно такую картину (картинка из предыдущего топика):

image

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

Проблема оказалась в for циклах. Как известно, компилятор преобразовывает for цикл для коллекций в следующий код:

for (Iterator<A> i = arrayListA.iterator(); i.hasNext();) {
    a = i.next();
}

//смотрим во внутрь метода iterator() ArrayList
public Iterator<E> iterator() {
    return new Itr();
}

//и сам класс итератора. поля которые потребляют память
private class Itr implements Iterator<E> {
	int cursor = 0;
	int lastRet = -1;
	int expectedModCount = modCount;
}

Все бы хорошо, но если у вас несколько вложенных циклов, при чем короткие циклы на самом нижнем уровне вложения, то получается, что просто один лишь проход по циклам создаст тысячи объектов, а если метод постоянно вызывается, то еще и постоянные срабатывания сборщика.
Например, для первого примера — в случае если arrayListA.size() == 1000, arrayListB.size() == 100, arrayListC.size() == 10 за один проход по циклам будет создано около 100 тыс. объектов итераторов…

Решение тут довольно очевидно — получать доступ по индексу:

for (int i = 0; i < arrayListA.size(); i++) {
    A a = arrayListA.get(i);
}


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

Будьте внимательны и с прошедшим Вас Новым годом!
Дмитрий Думанский @doom369
карма
95,5
рейтинг 43,3
Co-Founder в Blynk
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

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

  • +10
    Ужс. Правда все так плохо в Java? В C# компилятор сам делает такие преобразования. И объекты итераторов там обычно структуры и хранятся в стеке.
    • +2
      На самом деле это ожидаемое поведение. Для коллекций свой for, для массивов свой. Ведь возможна ситуация когда на вызов метода iterator() возможна некая логика…
      • +3
        да и в Java должно быть подобное. чем тогда занимается escape analysis?
        Кстати какая версия java?
        • 0
          Да, Вы права. Но это случается не часто. Полагаться на это не стоит.
          Во-первых, escape analysis не всегда возможен в виду ограниченности стека.
          Во-вторых, escape analysis может быть банально отключен.
          • +1
            в 7-ой java он по-моему включён по умолчанию. и его запуск скорее всего зависит только от статистики использования метода.

            wikis.oracle.com/display/HotSpotInternals/EscapeAnalysis

            GlobalEscape — An object escapes the method and thread (stored into a static field or stored into a field of an escaped object or returned as the result of the current method).
            ArgEscape — An object passed as argument or referenced by argument but not globally escape during a call (by analyzing the bytecode of called method).
            NoEscape — A scalar replaceable object.

            After escape analysis C2 eliminates scalar replaceable object allocations and associated locks. C2 also eliminates locks for all non globally escaping objects. C2 does NOT replace a heap allocation with a stack allocation for non globally escaping objects.

            не могу понять что тут хотят сказать в последнем предложении.
            • 0
              Да, включен по умолчанию. Но его можно выключить. Еще — чем больше стек вызовов, переменных в каждом из методов тем меньше памяти остается. Что сводит вероятность создания на стеке к весьма малому числу.

              >>не могу понять что тут хотят сказать в последнем предложении.

              Наверное опечатка, думаю имелось в виду, что объекты, которые выходят за область видимости метода не создаются на стеке.
            • НЛО прилетело и опубликовало эту надпись здесь
              • 0
                non globally escaping object — это объект который убегает из данного метода, но не убегает из цепочки вызовов (и соответственно не убегает из треда). Для такого объекта можно спокойно удалить синхронизацию (не убегает из треда). При этом убегание из метода по цепочке вызовов может быть разное: убегает только вниз по цепочке, убегает только вверх или туда и сюда. Для случая убегания только вниз можно разместить объект на стеке (для остальных так просто нельзя). Так вот, там сказано, что C2 этим не заморачивается. ;)
        • 0
          в джаве нету объектов на стеке
      • –2
        В общем случае это будет смахивать на нарушение LSP. Т.е. если есть какая-то разница между итерированием через индексатор и итератор, то вы что-то делает не так.
        • НЛО прилетело и опубликовало эту надпись здесь
    • +3
      В Java нет структур, которые можно было бы хранить в стеке…
      • +1
        Я знаю
      • 0
        Вы не правы — en.wikipedia.org/wiki/Escape_analysis
        • +1
          Escape analysis, как и любая другая оптимизация, может не сработать из-за магических причин (слишком большой уровень вложенности кода, слишком большое число локальных переменных, и т. п.)

          В C# же итератор можно сделать структурой, которая будет размещаться на стеке всегда (пока ее не приведут к интерфейсу).
          • –2
            Да. Но согласитесь, утверждение
            В Java нет структур, которые можно было бы хранить в стеке…

            Не совсем правдивое.
            • +3
              Оно правдивое.
              Под структурой (struct) я понимаю тип данных, который всегда хранится к стеке.
              Структур в Java нет.

              Что не так?
              • –3
                Что не так?

                Так как речь о java, то Ваши «структуры» воспринимаются исключительно как объекты. А объекты могут быть созданы на стеке (не посредством языка, а виртуальной машиной).
              • 0
                (вздохнул)… Структуры не всегда хранятся в стеке. Это очень популярный миф, но он не верен.
                struct A { int B };
                A a;
                () => Console.Write(a.B);
                

                Где по вашему будет хранится структура A?
                • –3
                  Структура, конечно же, храниться в стеке в таком случае не сможет. Но и отдельного блока памяти выделять также не будет.
                • 0
                  Если вы внимательно читали мой комментарий, который стоит выше по ветке, то я там сказал применительно к итераторам (попробуйте при использовании foreach разместить итератор в куче) и еще там было слово «обычно». Я нигде не говорил «структуры всегда хранятся в стеке», «итераторы всегда структуры» и «итераторы всегда хранятся в стеке».
                  • 0
                    Так я с вами и не спорил.
                    • 0
                      Да, я это понял потом уже. Извините.
          • +2
            Структура не размещается на стеке, например, если она — поле объекта. Или если она используется в каком-нибудь замыкании. blogs.msdn.com/b/ericlippert/archive/2009/04/27/the-stack-is-an-implementation-detail.aspx
            • 0
              весьма очевидно, нет?
            • –2
              Эрик, конечно, грамотный чувак, но в этой статье он гонит откровенную пургу, никак не связанную с реальностью. Ещё ни разу не видел, чтобы кто-то превращал class в struct, чтобы «копирование происходило по значению». Всегда — если требуется избежать лишней работы с кучей.
              • +1
                Про что конкретно он гонит? Держать переменную в стеке или нет, не зависит от типа переменной.
    • 0
      Просто использовать конструкции типа
      for (A a : arrayListA) {
      // some code
      }
      
      не допустимо в серьёзных местах. Лучше просто знать, какой list используется и как лучше его перебирать, а не доверять это for.
      • 0
        [сарказм]Следуя вашему совету уже заменил 5287 for-ов на ручное перебирание.[/сарказм]
        • –2
          Ваш сарказм не к месту, потому что я говорю об использовании
          for(int i = 0; i < arrayList.size(); ++i) {
          
          }
          

          и
          for(Iterator i = linkedList.iterator(); i.hasNext(); ) {
          
          }
          

          вместо
          for (A a : arrayListA) {
          // some code
          }
          
          • +1
            Кстати, просто массивы — это тоже часто не худшее решение. Нужна ли вообще та абстракция и структура данных которая используется?
          • +1
            Я надеюсь вы в реальной жизни не следуете данному совету.
  • 0
    Спасибо. Очевидная вещь, кажется. Но никогда бы не обратил внимание. Было бы здорово посмореть как это конкретно повлияло на производительность процессора и памяти.
    • 0
      Есть предположение, что на производительность процессора и памяти это либо никак не повлияло, либо даже снизило их — если владельцы сервиса на радостях по поводу бесплатной скорости решили перебросить его (сервис) на машинку послабее :)
  • +47
    >узкое место, которое на первый взгляд не вызвало бы ни у кого подозрений

    Угу, 3 вложенных цикла не вызывали ни у кого подозрений. «Ничто не предвещало беды».
    • +3
      Вполне нормальная ситуация, если присутствует сложная иерархия. Я специально описал действие метода, чтобы можно было понять откуда это.
      • 0
        Дело не в том, что ситуация нормальная, а в том, что если иначе никак, лучше сразу думать над оптимизацией.
        • +10
          Зачем сразу думать над оптимизацией? Написано было достаточно понятно и красиво. И сразу всё не заоптимизируешь. Особенно в начале проекта, когда не очевидно какие куски могут стать узким местом. Мне кажется читаемый код важнее, чем кривой, но более быстрый в крайних случаях, код. Если сразу думать над оптимизацией всюду, то можно застрять и не дожить до той поры, когда оптимизация даст плоды.
          • +6
            Вы всё верно говорите, я просто заметил, что с того момента как проблемы с производительностью всё-таки возникли, как-то странно показывая код с тремя вложенным циклами называть его «местом, которое на первый взгляд не вызвало бы ни у кого подозрений».
            • 0
              Ну, если не знать детали реализации, то и не вызовет. В пхп, например, есть два варианта: через внешний итератор и когда класс сам реализует next()/current() и прочие методы итератора. Во втором случае итератор не будет создаваться. А копаться в исходниках всех классов, конечно, полезно — но отнимает время.
    • 0
      В принципе, можно сделать единый итератор по всем трём циклам сразу…
  • +2
    Следует также отметить, что перебор элементов ArrayList через итератор c Sun JVM 1.6.0_05 был медленне чем через get — issues.apache.org/jira/browse/HARMONY-5920 Правда не помню когда пофиксили — толи в 1.7, толи вообще в 1.8. Думаю TheShade может сказать точнее ;)
    • НЛО прилетело и опубликовало эту надпись здесь
  • +9
    Большая просьба к авторам при возникновении проблемы с производительностью или потреблением памяти в Java указывать хотя бы используемые JDK и JVM с указанием версии. Желательно также использованные ключи компиляции и Java-машины.
  • 0
    Почему-то никто не сказал, что коллекции могут спокойно изменяться в других нитях во время итераций по ним. Поэтому правильнее использование итераторов, а не простых счётчиков. Хотя это верно только в случае синхронизированных коллекций (или их мутабельных представителей), иначе — да, имеет смысл оптимизировать доступ к элементам через счётчик, а не через итератор.
    • 0
      Как-то не очень хорошо обобщать в этой ситуации — «коллекции». Если коллекция не гарантирует доступа по индексу за константное время, то такая «оптимизация» может оказаться не совсем оптимизацией. Речь шла об ArrayList, для него да, ваше замечание интересно.
      • –2
        Так, прикладное программирование в том числе строится на обобщении механизмов работы с наборами объектов. Определённые контейнеры (кастомизации) коллекций — лишь частные случаи реализации того или иного механизма хранения/доступа. Итератор является обобщённым представлением паттерна «Визитёр» к коллекциям объектов, замена его счётчиком применительно к контейнеру типа ArrayList (одномерный массив) ведёт, естественно, к локальной оптимизации выполнения кода, но уменьшает абстракцию представления коллекции как таковой — раскрывает детали реализации. Что в будущем может затруднить рефакторинг кода в сторону использования иных коллекций, не имеющих доступа через механизм счётчика на основе целочисленного типа int, но имеющих объектный итератор.
        • 0
          Эм… Какое это всё имеет отношение к моему замечанию? А что такое «обобщённое представление к» чему-либо? Если я вас правильно понимаю, вы (зачем-то) заметили, что паттерн Visitor — частный случай паттерна Iterator. Осмелюсь предположить, что это не так. Я бы даже сказал, совсем не так. Предельно кратко: задача итератора — абстрагировать доступ (в том с числе с целью перебора) к элементам некоторой коллекции; посетителя — обеспечить двойную диспетчеризацию, а также облегчить добавление в систему новых операций над элементами некоторой сложной структуры ценой усложнения добавления новых видов элементов.
          • 0
            Паттерн Iterator реализует стратегию доступа к множеству объектов.
            Паттерн Visitor реализует стратегию действия по отношению к самим объектам множества.
            Улавливаете разницу?
            (А что там про двойную диспетчеризацию и т.д. — это всё частности).
            • +2
              Разницу? Стойкое впечатление, что вы читаете мои сообщения как-то наоборот. Я вам, собственно, про разницу и писал выше. Как и про то, что тема про паттерны совершенно ни к месту тут возникла.
          • –1
            Прошу прощения за грубую неточность в предложении: «Итератор является обобщённым представлением паттерна «Визитёр» к коллекциям объектов». Конечно же, Iterator никак не является обобщённым предствлением паттерна «Визитёр», так как у него несколько другая задача — перечислять объекты коллекции, а не работать с ними.
  • +1
    Стало мне интересно, а насколько медленнее доступ через итератор к элементу, чем по индексу для аналога ArrayList в С++ — для стандартного вектора? Получился вот такой очень простой тест и вот такие результаты.
    • +1
      В общем всё как и должно быть: в релизной сборке разницы нет.
  • 0
    Кстати, если вам все же нужен именно связанный список, а не массив, то я бы посмотрел на специальные gc-эффективные реализации вроде FastList из Javolution.
  • 0
    В принципе код должен быть в первую очередь чистым, читабельным и поддаваться эффективной поддержке. Во вторую очередь уже он должен быть быстрым. То бишь, возможно какое-то место и не будет проблематичным.

    P.S. Поздравляю вас с перформанс фиксом :)
  • 0
    В общем случае (не ArrayList) поможет пул итераторов.
  • –1
    Кто-нибуть может мне объяснить реальные плюсы итераторов перед обращением по индексу.

    Я вот в С++ делаю всегда так (например):

    vector<int> q(magik.size());
    magik.setContentsForVector(q);
    for (unsigned int i = 0; i < q.size(); i++) {
       // тут идут обращения к q[i]
       // или к какому-то const Type var = &q[i]; (как-то так)
    }
    


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

    Да и [ ] это сложение адресов, а с итераторами — создание объектов.
    • +1
      Ну, есть коллекции, доступ к элементам которых по индексу получить нельзя. И если в Ваш метод может прийти одна из таких коллекций на ряду с индексными, то как написать универсальный метод без итератора?
    • 0
      А почему не for each?
      • –3
        Наверное потому что в С++ нету foreaсh, насколько мне известно.
        • +1
          range-based for, C++11.
          • –3
            Ну уж простите, не у всех есть время разбираться с С++11 :) Но в любом случае, спасибо!
          • 0
            И еще костыль foreach в Qt и макрос BOOST_FOREACH (понятно, где)
    • +3
      Если ваша задача — перебрать элементы std::vector<T> с целью их чтения или модификации — разницы действительно нет (почти, см. примечание). А вот дружить с ними стоит. Потому что:

      1. Далеко не для всех коллекций, а вообще говоря, сущностей, содержащих некоторый конечный набор однотипных элементов, эффективен или даже возможен доступ по индексу. В C++ он возможен разве что для std::vector<T> и std::deque<T>, для них же и эффективен (требует константного времени), в Java же и ArrayList<T>, и LinkedList<T>, согласно интерфейсу List<T>, разрешают такой доступ, хотя эффективен он только для первого «списка» (который на самом деле массив ссылок, такой же псевдосписок есть в Qt — QList<T>), для второго требует линейного времени, что простой перебор элементов превращает в алгоритм с квадратичной сложностью. Для таких контейнеров, как множество и отображение (std::map<T>, например), доступ по индексу лишен смысла. Особенно для их unordered_* (в С++11) и Hash* (в Java) версий. И подавно такой доступ бессмысленен для потоков, они предоставляют только итераторы. В C++ STL это будут итераторы категорий InputIterator и OutputIterator (понятие «категория» еще часто именуют как Type Requirements, вещь из мира обобщенного или даже метапрограммирования). Например, std::ostream_iterator<T>. Есть множество потоков, например, в Boost.Spirit вы увидите, что интерфейс, с помощью которого взаимодействуют лексер и парсер — это пара итераторов (в стиле STL, категории ForwardIterator), абстрагирующих доступ к потоку лексем (или токенов). И это очень правильно, потому что резко снижает зависимости между частями системы, например, лексера может и не быть вовсе — а итераторы успешно предоставит, скажем, std::string.

      2. Именно концепция итератора позволяет множеству замечательных алгоритмов STL работать с самыми разными коллекциями обобщенным образом. Алгоритмами этими нужно владеть, их надо знать, а это автоматически потребует от вас дружбы с итераторами.

      3. Итератор — еще и некоторое обобщение ссылки или указателя на объект. Вы можете его сохранить в каком-нибудь другом объекте. Так вы сможете эффективно удалить или изменить какой-то элемент коллекции, не выполняя поиска. Конечно, тут нужно быть осторожным и знать, какие операции инвалидируют итераторы и ссылки, а какие нет, что индивидуально для каждой коллекции (и отдельная история в многопоточном случае). Практически не актуально для Java, так как удаление элемента даже в «настоящм» связном списке в ее случае инвалидирует все ранее созданные итераторы.

      4. Итератор — еще и паттерн проектирования — вы можете использовать его в своих проектах. Тут я не буду останавливаться подробно, а отошлю к GoF.

      Обещанное примечание. Разница все же есть, ибо использование итераторов может более менее существенно уменьшить число изменений, которые придется внести в код в случае изменения типа используемой коллекции. Почему такое изменение — не частый сценарий в реальности, можно почитать у Мейерса, «Эффективное использование STL» (как и о многом другом полезном)

      Также предлагаю два замечания: о том, как стоит итерироваться по коллекциям в C++11 (не забывайте использовать константную ссылку, если не меняете элементы), и, в качестве примера, C++-way вывода на печать массива пользовательских структур (интересны 35-38 и 46 строчки)
      • +1
        Я думаю, вы расставили все точки над i — теперь мне все понятно. Спасибо!
        • 0
          не все так просто. во многих реализациях итератор у вектора это простой указатель, поэтому вставка или удаление элемента в вектор может аннулировать все его итераторы и можно подорваться на внешне безобидном коде
          • 0
            Я об этом предупреждал, посмотрите внимательнее :) Фокус в том, что если вам нужна возможность безопасно удалять элементы по итератору (не инвалидируя остальные), то нужно использовать те коллекции, которые это гарантируют. Единственная условная сложность на этом пути — мне не известен удобный online-ресурс с хорошим поиском, в котором была бы предоставлена настолько детальная информация по стандартной библиотеке C++. А лазать в книжки и стандарты не очень удобно.
    • 0
      Забыл прокомментировать
      Да и [ ] это сложение адресов, а с итераторами — создание объектов.

      А что вас заботит? Эффективность? Как показывает, в частности, маленький тест, проведенный мною выше, разницы в производительности в случае С++ нет никакой. В случае Java, как показывает самый этот пост, по-видимому, есть. Но это едва ли, снова таки, должно вас заботить до этапа профилирования, если в нем вообще возникнет необходимость.
      • +1
        До этапа профилирования

        А как же, «Будь мужиком, пиши качественный код без профилера»?
        • 0
          Тот факт, что преждевременная оптимизация — корень всех (или очень многих) зол, многократно обсуждался и в литературе, и здесь, на хабре. Я не хочу растекаться на эту тему. Замечу лишь, что думая о производительности, важно различать решения, уменьшающие константу в сложности алгоритма, и решения, улучшающие асимптотическую оценку сложности. Если вы себя поймали на том, что пишите кубический алгоритм, работающий с данными, которые предоставляются пользователем, и объем которых, соответственно, диктуется им — то может и стоит задуматься о производительности сразу. Здесь не тот случай.
          • +1
            Да какая преждевременная оптимизация? Если речь идет о узких местах, в них код сразу должен быть максимально быстрым и оптимальным. Каждая новая его модификация должна быть сопровождена соответствующими оптимизациями. Это же узкие места, дядя.

            Если вы знаете, что где-то что-то можно ускорить — его нужно ускорять!
            • 0
              А как вы выясняете, что является узким местом в проекте, до его запуска? Как показывает практика, метод «да ну бросьте, я точно знаю, что это — горячая точка» крайне часто приводит к ошибкам.
              • +1
                Если вы работаете над конкретным модулем (блоком) приложения, вы точно знаете сколько раз что может вызываться.
                • 0
                  Возможно. Наверное, этот спор лучше всего закончить так: зависит от того, что, для какой аудитории и зачем вы пишете.
                  • 0
                    Абсолютно верно.
          • 0
            Вот, в "Стандартах программирования на С++" Саттер и Александреску советуют избегать алгоритмов со сложностью более, чем линейной. За подробностями — к ней, вообще хорошая книга. В той краткой форме, в которой я здесь привел этот совет, он может звучать абсурдно, так что — welcome
            • 0
              Спасибо.
            • 0
              Хороший совет. Особенно в сочетании с тем, что «ясность лучше хитроумия» :)
          • +1
            Если вы себя поймали на том, что пишите кубический алгоритм, работающий с данными, которые предоставляются пользователем, и объем которых, соответственно, диктуется им — то может и стоит задуматься о производительности сразу

            Если выбирать приходится между N^3/32 и N^2*log(N), то думать придётся долго — надо будет прогнозировать, какой объём может предложить этот пользователь в обозримом будущем.
            • 0
              Так как достоверно сравнивать константы у вас появится возможность только после реализации обоих вариантов, то ясно, что до профилировки всего приложения в целом вы или автоматом выберете n^2 * log(n) как подающий большие надежды, либо, что еще более вероятно, тот из них, которых проще в реализации, отладке, модификации, перспективнее с точки зрения переиспользования кода. А уж если возникнет необходимость выжать все, что можно… То вы реализуете оба, начнете сравнивать и… дабы не терять реализованное и отлаженное добро оставите и тот, и другой и будете переключаться между ними в зависимости от размера входных данных :)
            • 0
              Если начать выбирать между N^3/32 и N^2 * log N, то очень скоро станет очевидным, что второй вариант быстрее уже при N > 256.

              Вот выбор между N^5/2^25 и другими вариантами действительно тяжел, особенно когда другие варианты еще не придуманы (кстати, реальный случай на полуфинале ICPC)
    • +2
      в С++ как раз частенько итераторы очень даже нужны
      вот вам пример сходу (извините если вдруг, где-нибудь ошибся)

      std::vector<int> a;
      a.push_back(1);
      a.push_back(2);
      a.push_back(3);
      int b[3] = {4,5,6};
      int* c = new int[3];
      c[0] = 7;
      c[1] = 8;
      c[2] = 9;
      std::map<int, int> d;
      d[1] = 10;
      d[2] = 10;
      d[3] = 10;
      	
      print(a.begin(), a.end());
      print(&b[0], &b[0] + 3);
      print(c, c + 3);
      print(d.begin(), d.end());
      

      где
      std::ostream& operator << (std::ostream& stream, const std::pair<int, int>& element)
      {
          stream << element.first + element.second;
          return stream;
      }
      
      template<class T>
      void print(const T& begin, const T& end)
      {
          for(T current = begin; current!=end;++current)
          {
              std::cout << (*current) << std::endl;
          }
      }
      
    • 0
      И как же ты в Set будешь обрашаться по индексу
      • 0
        А есть итераторы для множеств? Множество — ассоциативный контейнер.
        • 0
          А почему его не должно быть? Списки, множества, очереди, стеки — все это частный вид коллекций, а коллекцию можно проитерировать.
          • –1
            Да нельзя проитерировать множество. Это ассоциативный контейнер. Его элементы не последовательны. А итератор — не зря этот паттерн называют «курсором».

            Если вы со мной не согласны, напишите пример кода, в котором видно, что множество можно итерировать.
            • 0
              В плюсах set — это сбалансированное дерево, то есть множество даже упорядочено. Почему бы его нельзя было итерировать?

              В Java Set — это интерфейс, который может представлять как упорядоченное, так и неупорядоченное множества. Но даже в последнем случае итерация может иметь смысл (например, итерация применяется для копирования элементов между несовместимыми по реализации множествами).

              Пример кода не приведу, но, как видно в docs.oracle.com/javase/6/docs/api/java/util/Set.html, Set наследует от Collection, который наследует от Iterable.
              • 0
                Хм. Почитал www.cplusplus.com/reference/set/set/ — оказалось что был неправ. Я всю жизнь думал, что set, как словарь — не упорядочен.

                Спасибо.
                • 0
                  (извиняюсь, поторопился)
            • +1
              Его элементы не последовательны.
              В теории — да, на практике последовательность зависит от реализации. Если брать яву, то первое что нам приходит на ум это HashSet и TreeSet. Первый испольузет свою хешфункцию для проверки, второй — дерево.

              Упорядоченность множества говорит нам о том, что мы достаем из него элементы не в том порядке в котором положили. К примеру запустив данный код:
              Set<Integer> set = new HashSet<Integer>();
              set.add(2038);
              set.add(2012);
              set.add(1970);
              set.add(1408);
              set.add(1337);
              
              for(int e: set)
                  out.println(e);
              


              На выходе получим:
              1337 1408 1970 2038 2012
              


              Если вместо HashSet будем использовать TreeSet, то результат будет следующим:
              1337 1408 1970 2012 2038
              


              Словарь мы так же можем проитерировать, опять же, То что элементы не последовательны или неупорядочены не означает того, что мы не можем пройтись по всем элементам при помощи итератора. В одном случае это будет простой линейный проход по массву или списку, в другом — еще какая-нибудь хитрая итерация.
            • +2
              Если «элементы не последовательны», то это значит только то, что (физическая) последовательность не специфицирована. Т.е. можно итерировать в любой последовательности, и это будет корректно.
  • 0
    (Вспомнил байку этак 15-летней давности, где какой-то подобный код, будучи скомпилирован новым тогда Intel C++ Compiler, развернулся в константу на стадии компиляции).

    Какие эти императивные языки всё-таки сложные в оптимизации. Чуть повышаешь уровень абстракции — и всё, паттерн оптимизатору уже не виден.
  • 0
    Стоит отметить, что такого рода оптимизация возможна в основном в случае ArrayList.


    Можно оптимизировать и обход других коллекций, если перед циклами элементы записать во временный массив, используя toArray(). Итератор каждой коллекции отработает один раз, а дальше циклы будут просто брать элементы массивов. Тогда выигрыш может быть не только за счет меньшего числа созданных итераторов, но еще и за счет уменьшения overhead'а использования итераторов (взять элемент массива по индексу дешевле, чем get() или next()).

    Но самое главное, конечно — это сидеть с профайлером и смотреть.
  • 0
    Читабельность vs скорость: старая проблема… Зачем тут нужен полноценный ListIterator с hasPrevious() и previous()?
  • 0
    А может просто итерироваться в самом внутреннем цикле по «самой длинной стороне»?
  • 0
    А у итераторов в этом языке нет операции «начать с начала»? Может быть, завести три итератора сразу, а в начале каждого цикла возвращать соответствующий итератор к началу массива?
    • НЛО прилетело и опубликовало эту надпись здесь
      • 0
        Ну, в одном из комментариев я обнаружил строчку «Как известно, компилятор преобразовывает for цикл для коллекций в следующий код...» — а из неё следует, что используемая библиотека неплохо интегрирована с языком, раз компилятор позволяет себе пользоваться её функциями. А кроме того, много ли в наше время есть библиотек, которыми можно пользоваться без специальных ухищрений из более чем одного языка?
    • 0
      А для этого языка, вроде бы, почти всегда достаточно знать, что все, что может объект, можно выяснить исходя из интерфейса. Они документированы и гуглятся хорошо: вот и вот про итераторы. Вот есть же отдельное для списков расширение интерфейса Iterator — ListIterator. Почему нет более развитой иерархии интерфейсов итераторов, среди которых были бы требующие от реализаций методов вроде reset() (из вашего вопроса), мне не известно.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.