Итераторы

[Igors]

А вообще от этой темы я уже устал. По моему тут уже давно всем всё ясно и дискуссия идёт просто ради дискуссии.

К сожалению да, пустопорожний "подсчет тактов" хотя это даже есть в библии писаной более 10 лет назад.

Если смотреть на первый пост, то речь там вообще шла не о переборе значений, а о "демонстрации мощи итераторов" при удалении элемента. Так что от темы мы тут все уже далеко уклонились

С демонстрацией мощи совсем плохо. Только один показал STL-реализацию которая, увы, проигрывает лобовому решению на С раз в 10. Но он хотя бы показал, а остальные вообще отделываются общими (иногда назидательными) фразами и упорно переводят разговор на такты ("игра в эксперта").  Куда же делась вся "концептуальность" когда появилась простенькая и очень банальная задачка?  

[alex312]

Только один показал STL-реализацию которая, увы, проигрывает лобовому решению на С раз в 10.

Где "эталонное" решение, где тесты производительности ?

[RedDog]

Прошу прощения, мои тесты работают одинаково по скорости, ибо в итераторном тесте вкралась ошибочка begin() надо для первого цикла вызывать каждый раз, А он вызывается только один раз.

[Igors]

Прошу прощения, мои тесты работают одинаково по скорости, ибо в итераторном тесте вкралась ошибочка begin() надо для первого цикла вызывать каждый раз, А он вызывается только один раз.

Ну может и не совсем одинаково, но разница настолько незначительна что нет смысла заниматься такой оптимизацией. То давно известно, тема о другом - вроде использование итераторов "более идейно" и позволяет писать лучший код. Однако пока никакого подтверждения этому я не увидел.

Где "эталонное" решение, где тесты производительности ?

Конечно выложу, не вопрос. Но давайте сравнивать одинаковый функционал (пока у Вас индексы не пересчитаны). Исправьте, тогда сравним

[Alex Custov]

Ну может и не совсем одинаково, но разница настолько незначительна что нет смысла заниматься такой оптимизацией. То давно известно, тема о другом - вроде использование итераторов "более идейно" и позволяет писать лучший код. Однако пока никакого подтверждения этому я не увидел.

Идея простая - идея универсальности. Есть абстрактная коллекция, есть итератор для неё, который начинается с begin() и заканчивается на end(). Во всех случаях ты пишешь один код.

[alex312]

Конечно выложу, не вопрос. Но давайте сравнивать одинаковый функционал (пока у Вас индексы не пересчитаны). Исправьте, тогда сравним

А как их надо пересчитывать? А то из предыдущих постов не совсем понятно 

[Old]

хотя это даже есть в библии писаной более 10 лет назад.

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

Куда же делась вся "концептуальность" когда появилась простенькая и очень банальная задачка?  

Хотите задачку, давайте.
Давайте мы точечки не будем хранить в векторе, а будем их хранить в связанном списочке, что бы можно было их быстро вставлять/удалять.
Будьте любезны, исполните решение на индексах. И сравним с, как вы сказали, лобовым решение на C.

"подсчет тактов"
...
разговор на такты

Классное слово "такт". Еще прикольно произносится "Сигурни Уивер", можете их со словом "такт" чередовать.

[Old]

тема о другом - вроде использование итераторов "более идейно" и позволяет писать лучший код. Однако пока никакого подтверждения этому я не увидел.

Ща, попробую на пальцах показать: Скажите пожалуйста, а какой код из этих более идейный и лучший?

Код

C++ (Qt)
void DoCopy( const int * src, int * dst, int count )
{
 const int * end = src + count;
 while (src != end) {
  *dst = *src;   // *(dst++) = *(src++);
   ++src;
   ++dst;
 }
}

Код

C++ (Qt)
void DoCopy( const int * src, int * dst, int count )
{
  for( size_t i = 0; i < count; ++i )
     dst[ i ] = src[ i ];
}

Вот первый это итераторы, а второй индексы. Не больше не меньше. Никаких скрытых магических свойств (которые вы ждете) у итераторов нет. Грусть.

[xokc]

Ща, попробую на пальцах показать: Скажите пожалуйста, а какой код из этих более идейный и лучший?

Поскольку критериев "идейности" и "лучшести" кода не приведено, значит, используя метод экспертной оценки, и себя в качестве эксперта считаю, что лучше код на индексах - при прочих равных по быстродействию он короче и понятней.

[Old]

Поскольку критериев "идейности" и "лучшести" кода не приведено, значит, используя метод экспертной оценки, и себя в качестве эксперта считаю, что лучше код на индексах - при прочих равных по быстродействию он короче и понятней.

На самом деле эти примеры не равнозначны, то что современные компиляторы сами (за программиста) научились приводить второй пример к первому, это только их заслуга. По моему, надеяться на инструменты не совсем правильно. "Если программа работает медленно, мы лучше подождем новое железо или более умный компилятор, но не будем оптимизировать свой код".

[kamre]

Конечно выложу, не вопрос. Но давайте сравнивать одинаковый функционал (пока у Вас индексы не пересчитаны). Исправьте, тогда сравним

Имеется ввиду что-то вроде такого или без использования дополнительной памяти?

Код

C++ (Qt)
#include <vector>
#include <cstdio>
 
struct Point3D {
  double x, y, z;
};
 
struct Triangle {
  int v[3];
};
 
typedef std::vector<Point3D> Points;
typedef std::vector<Triangle> Triangles;
typedef std::vector<int> Indexes;
 
void remove_points(Points &points, Triangles &triangles, const Indexes &remove)
{
  size_t sz = points.size();
  // create map for points indexes
  Indexes map(sz);
  // mapping to -1 means removed
  for (size_t i = 0; i < remove.size(); ++i) {
    map[remove[i]] = -1;
  }
  // compute mapping and update points
  size_t count = 0;
  for (size_t i = 0; i < sz; ++i) {
     if (map[i] != -1) {
       map[i] = count;
       points[count++] = points[i];
     }
  }
  points.resize(count);
  // update triangles
  count = 0;
  for (size_t i = 0; i < triangles.size(); ++i) {
    Triangle &t = triangles[i];
    bool removed = false;
    for (size_t j = 0; j < 3; ++j) {
      int u = map[t.v[j]];
      if (u == -1) {
        removed = true;
        break;
      }
      t.v[j] = u;
    }
    if (!removed) {
      triangles[count++] = t;
    }
  }
  triangles.resize(count);
}
 
void print(const char* str, const Triangles &triangles)
{
  std::printf("%s:", str);
  for (size_t i = 0; i < triangles.size(); ++i) {
    const Triangle & t = triangles[i];
    std::printf("%s(%d, %d, %d)", (i % 3 ? ", " : "\n  "), t.v[0], t.v[1], t.v[2]);
  }
  std::printf("\n\n");
}
 
int main()
{
  Points pts = { {0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 1}, {1, 1, 1}, {2, 2, 2} };
  Triangles trs = { {{0, 1, 2}}, {{0, 2, 3}}, {{2, 3, 1}}, {{2, 4, 3}},
                   {{4, 3, 1}}, {{4, 2, 3}}, {{0, 2, 4}}, {{0, 1, 4}},
                   {{5, 2, 1}}, {{5, 4, 3}}, {{0, 2, 5}}, {{1, 3, 5}}, };
  Indexes ids = { 0, 2 };
  print("Before", trs);
  remove_points(pts, trs, ids);
  print("After", trs);
}
 

Before:
  (0, 1, 2), (0, 2, 3), (2, 3, 1)
  (2, 4, 3), (4, 3, 1), (4, 2, 3)
  (0, 2, 4), (0, 1, 4), (5, 2, 1)
  (5, 4, 3), (0, 2, 5), (1, 3, 5)

After:
  (2, 1, 0), (3, 2, 1), (0, 1, 3)

[xokc]

По моему, надеяться на инструменты не совсем правильно. "Если программа работает медленно, мы лучше подождем новое железо или более умный компилятор, но не будем оптимизировать свой код".

Если я точно знаю как ведет себя компилятор, зачем я буду работать за него? Его нормочас однозначно дешевле моего. Надеюсь Вы уже не пишите x = y << 1 вместо x = y * 2?

[Old]

Надеюсь Вы уже не пишите x = y << 1 вместо x = y * 2?

А что в этом плохого? Или эта запись вызывает у вас какие-то сложности?

Если я точно знаю как ведет себя компилятор, зачем я буду работать за него?

А вы всегда точно знаете, как будет оптимизировать компилятор? Если вы думаете да, то сильно ошибаетесь. Компилятор частенько перестраховывается.

Как правильно показал Igors, программисты перестали считать такты, они стали считать часы и деньги. Поэтому текстовый редактор сейчас весит сотни мегабайт и для работы требует 4 ядра/4 гига.

[xokc]

А что в этом плохого? Или эта запись вызывает у вас какие-то сложности?

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

А вы всегда точно знаете, как будет оптимизировать компилятор? Если вы думаете да, то сильно ошибаетесь. Компилятор частенько перестраховывается.

Да, я знаю свои инструменты достаточно хорошо, чтобы понять где стоит заморочиться низкоуровневой оптимизацией, а где довериться компилятору. Кроме того, злоупотребление низкоуровневыми конструкциями может и ухудшить результат оптимизации, например, приведет к "неузнаванию" компиляторами ситуаций когда можно применить вектроную арифметику или распараллеливание.

Как правильно показал Igors, программисты перестали считать такты, они стали считать часы и деньги.

Странно, я вроде бы на протяжении всей этой темы старался показать, что "считаю такты". Так что этот камень - не в мой огород. Кроме того мне задачу ставят так: сделай то-то, с таким-то качеством, за такое-то время и такие-то деньги. Если я буду считать только первые 2 пункта я рискую запороть два последних.

[Old]

Кроме того, злоупотребление низкоуровневыми конструкциями может и ухудшить результат оптимизации, например, приведет к "неузнаванию" компиляторами ситуаций когда можно применить вектроную арифметику или распараллеливание.

А я и не предлагаю чем-то злоупотреблять, тем более низкоуровневыми конструкциями. Я начал отказываться от использования ассемблера при выходе Пентиума (хотя активно его использовал начиная с 8086), после появления 64-битной платформы - отказался полностью (на PC).
Но здесь нет низкоуровневых конструкций, здесь есть индексы или указатели.

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

А как компилятор оптимизирует такой код?

Код

C++ (Qt)
std::list<int> src;
MyCollection dst;
 
for( int i = 0; i < src.size(); ++i )
    dst[ i ] = src[ i ];