Есть у меня квадратная матрица — вектор векторов.

typedef vector<byte> Line;
vector<Line> Grid;                // -- решетка для демонстрации --
Line Mera;                    // -- мера - для поиска --

Пока я бегаю по строкам-векторам, стандартные алгоритмы рулят по полной.
Например:

// -- проверка в доминантном направлении - стандартными алгоритмами --
inline
bool dmCheck(nline ci, npos cj)
{ bool yes = true;
  npos jR = (cj+mera) % L;                       // L - матрица размером L*L 
  if(cj < jR)
  {  Line::iterator Begin = Grid[ci].begin() + cj;
     Line::iterator End   = Begin + mera;
     yes = equal(Begin, End, Mera.begin());
  }
  else yes = dmJoint(ci, cj);                // проверка стыка --
  return yes;
}

Но надо мне и по вертикали делать аналогичные проверки. Пока обхожусь элементарным циклом. Но хотелось бы и тут приспособить стандартные алгоритмы.
Не может ли кто-нить присоветовать, каким образом использовать, например, find_if() по вертикали?
То есть, надо, например, в столбце найти первый ноль.

Размер матрицы — достаточно большой. До пока виртуальной памяти хватает. Например, 20000*20000, 30000*30000, и так далее.
А в стандартных алгоритмах фигурирует pred(*i). Я могу написать соответствующий предикат, но бежать придется, перебирая строки, то вот это *i приводит к копированию всего вектора-строки. Сам вектор вроде и не большой, но 20000 раз его копирования — дороговато выходит. А время — критично.
Поупражняться с указателями на вектор?

Про valarray знаю, но Джосаттис писал, что подсистема заброшена. Поэтому сразу сделал вектор векторов

17.08.2011 16:23, LaptevVV пишет:

> Поупражняться с указателями на вектор?
А вот вектор векторов — это очень плохое решение в большинстве случаев.

>
> Про valarray знаю, но Джосаттис писал, что подсистема заброшена. Поэтому
> сразу сделал вектор векторов
Лучше воспользоваться одной из библиотек для матрицам (boost, armadillo,
cvmlib, it++ ...).

Если для учебных целей, то и разберись с ними и объясни студентам плюсы
и минусы каждой.

Кстати, с матрицами есть очень хорошие развлечения для студентов:
1. Напишите класс для работы с матрицами.
2. Напишите функцию транспонирования матрицы с оптимизацией по
производительности (в т.ч. в многопоточном варианте).
3. Напишите функцию умножения матриц с оптимизацией по
производительности (в т.ч. в многопоточном варианте).
4. Ленивые вычисления.
5. ...

Здравствуйте, Vzhyk, Вы писали:

V>17.08.2011 16:23, LaptevVV пишет:

>> Поупражняться с указателями на вектор?
V>А вот вектор векторов — это очень плохое решение в большинстве случаев.

>>
>> Про valarray знаю, но Джосаттис писал, что подсистема заброшена. Поэтому
>> сразу сделал вектор векторов
V>Лучше воспользоваться одной из библиотек для матрицам (boost, armadillo,
V>cvmlib, it++ ...).
Спасибо за наводки. Но переработка алгоритма — это дело не самого ближайшего будущего. Ближе к новому году затею кардинальную переработку.
V>Если для учебных целей, то и разберись с ними и объясни студентам плюсы
V>и минусы каждой.
V>Кстати, с матрицами есть очень хорошие развлечения для студентов:
V>1. Напишите класс для работы с матрицами.
V>2. Напишите функцию транспонирования матрицы с оптимизацией по
V>производительности (в т.ч. в многопоточном варианте).
V>3. Напишите функцию умножения матриц с оптимизацией по
V>производительности (в т.ч. в многопоточном варианте).
V>4. Ленивые вычисления.
V>5. ...
Да, эт мы примерно так и делаем...

Как вариант — сочинить предикат, который принимает ссылку на аргумент вместо его копии.
Можно заменить вектор векторов (нереально кривое решение в большинстве случаев, кстати) на одномерный вектор, длина которого равно M*N, и сделать свой собственный итератор, который за один инкремент сдвигается на N (длину строки). Все это можно завернуть в специализированный класс.

По поводу кривых решения пока не нужно. Первоначальное решение — требовалось БЫСТРО написать версию реализованного алгоритма (в котором я еще разобраться должен был):
а) работающую в несколько раз быстрее реализованного;
б) понятного челу, реализовавшему первоначальный вариант;
в) понятного его научруку;
г) работающего одинаково в винде и линуксе, в Студии и CodeBlocks.
Сейчас мы начинаем думать над дальнейшими усовершенствованиями... Но это процесс не быстрый...
Например, думаем над переработкой под OpenMP.

17.08.2011 17:03, LaptevVV пишет:

> Сейчас мы начинаем думать над дальнейшими усовершенствованиями... Но это
> процесс не быстрый...
> Например, думаем над переработкой под OpenMP.
Велосипед с квадратными колесами изобретаете.
Слушай, расскажи, как вы умудряетесь так наколоть заказчика, чтобы за
его же деньги велосипед с квадратными колесами ему же и подсунуть?
А совесть? Самому не противно?

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

Здравствуйте, Vamp, Вы писали:

V>вектор векторов (нереально кривое решение в большинстве случаев, кстати) — можно подробнее?

V>>вектор векторов (нереально кривое решение в большинстве случаев, кстати) — можно подробнее?
Если в двух словах, то потому, что вектор векторов — это не матрица. А вектор векторов. А когда ты пытаешься одну сущность представить в виде другой, возникают проблемы — собственно, именно о них и писал Лаптев.
А возможнны и всякие другие. Например, вектор векторов совершенно не обязан быть прямоугольным Невозможно написать генерализированные функции работы с матрицами, невозможно правильно проверять инвариант.

Здравствуйте, Vamp, Вы писали:

V>>>вектор векторов (нереально кривое решение в большинстве случаев, кстати) — можно подробнее?
V>Если в двух словах, то потому, что вектор векторов — это не матрица. А вектор векторов. А когда ты пытаешься одну сущность представить в виде другой, возникают проблемы — собственно, именно о них и писал Лаптев.
V>А возможнны и всякие другие. Например, вектор векторов совершенно не обязан быть прямоугольным Невозможно написать генерализированные функции работы с матрицами, невозможно правильно проверять инвариант.

"... в БОЛЬШИНСТВЕ случаев..." — какое такое большинство? Или имеется в ввиду именно работа с матрицами?

Здравствуйте, Vzhyk, Вы писали:

V>17.08.2011 17:03, LaptevVV пишет:

>> Сейчас мы начинаем думать над дальнейшими усовершенствованиями... Но это
>> процесс не быстрый...
>> Например, думаем над переработкой под OpenMP.
V>Велосипед с квадратными колесами изобретаете.
V>Слушай, расскажи, как вы умудряетесь так наколоть заказчика, чтобы за
V>его же деньги велосипед с квадратными колесами ему же и подсунуть?
V>А совесть? Самому не противно?

V>З.Ы. И intel и amd и куча опенсурсных уже давно всю работу с матрицами
V>реализовали и заточили под большинство современных процессоров.
1. Почему велосипед с квадратными колесами? Можно обоснование? То, что я читал, мне понравилось. Тем более, что это и для фортрана сделали.
2. Совесть здесь причем? Я вообще-то препод и с данной предметной областью столкнулся первый раз...
Лучше конкретные ссылки давайте — будем читать.

Здравствуйте, LaptevVV, Вы писали:

LVV>Есть у меня квадратная матрица — вектор векторов.

в первую очередь вам нужна абстракция Matrix
сначала надо ее обдумать\реализовать
затем делаются внешние алгоритмы
как верно уже все отметили, реализовывать матрицу через вектор векторов — дело гиблое, как по удобству, так и по производительности
проще было взять какую-либо распространенную и обкатанную либу с поддержкой матриц
получили бы нахаляву перформанс и кучку полезных алгоритмов

Здравствуйте, Vzhyk, Вы писали:

V>З.Ы. И intel и amd и куча опенсурсных уже давно всю работу с матрицами
V>реализовали и заточили под большинство современных процессоров.
Тем не менее мне удалось только стандартными средствами повысить быстродействие более, чем в 10 раз по сравнению с первоначальной версией...

просто это вовсе не цельный кусок памяти а адовый венегрет
если исходить из того что объект это только дескриптор а данные где то в куче
то вот применая карта памяти

    -----|
    size |-----
    ptr  |    |
    -----     |
              |
    ----|----|----|----|----|----------------------
    size|size|size|size|size|
    ptr |ptr |ptr |ptr |ptr |
    ------------------------------------------
      |   |    |    |    |data
      |   |    |    |data
      |   |    |data
      |   |data
      |data

поэтому достать элемент не так тиривиально как из сплошного куска памяти
int (*ptr)[N];
*(*(ptr + i) + j)
хотя после оптимизатора по скорости должно быть одинаково если только
и будет проигрывать то только из того что обращения к памяти не такие локальные
как для простого массива

17.08.2011 18:12, LaptevVV пишет:

> 1. Почему велосипед с квадратными колесами? Можно обоснование? То, что я
> читал, мне понравилось. Тем более, что это и для фортрана сделали.
Просто это область достаточно нетривиальная и не существует в ней
единственного правильного решения. В каждой конкретной ситуации
необходимо выбирать вариант реализации.
Но именно эта часть и есть самая интересная для продвинутых студентов.
Применения различных вариантов параллелизации тоже определяется
предметной областью. Например во многих случаях наиболее узким местом
будет работа с кешами процессора, а не быстродействие и количество
процессоров. Но именно на этой теме очень удобно исследовать особенности
распараллеливания вычислительных задач.
Плюс к этому добавляется проектирование интерфейса этого класса — тут
тоже нет какого единого лучшего решения.
Плюс к этому еще добавляется совместимость с фортраном и др.

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

Ну и еще очень интересный для обучения кусок: разреженные матрицы,
реализация, подходы, операции с ними.

Какую-то литературу не посоветую, да в ней и смысла мало (у AMD на сайте
были статьи по нюансам оптимизации для их процессоров).

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

> 2. Совесть здесь причем? Я вообще-то препод и с данной предметной
> областью столкнулся первый раз...
Так я и не понял. Ты, как препод этим интересуешься или втюхать кому-то
что-то хочешь.

C>"... в БОЛЬШИНСТВЕ случаев..." — какое такое большинство? Или имеется в ввиду именно работа с матрицами?
Как правило, вектором векторов люди пытаются представить матрицы. Если речь идет о чем-то другом, то вопросов нет.

Здравствуйте, jyuyjiyuijyu, Вы писали:

J>просто это вовсе не цельный кусок памяти а адовый венегрет
J>если исходить из того что объект это только дескриптор а данные где то в куче
J>то вот применая карта памяти

J>

J>    -----|
J>    size |-----
J>    ptr  |    |
J>    -----     |
J>              |
J>    ----|----|----|----|----|----------------------
J>    size|size|size|size|size|
J>    ptr |ptr |ptr |ptr |ptr |
J>    ------------------------------------------
J>      |   |    |    |    |data
J>      |   |    |    |data
J>      |   |    |data
J>      |   |data
J>      |data
J>

J>поэтому достать элемент не так тиривиально как из сплошного куска памяти
J>int (*ptr)[N];
J>*(*(ptr + i) + j)
J>хотя после оптимизатора по скорости должно быть одинаково если только
J>и будет проигрывать то только из того что обращения к памяти не такие локальные
J>как для простого массива
Да знаю я все это. Могу на встроенном ассемблере ручками реализовать. Меня интересуют стандартные решения... В рамках STL.

17.08.2011 18:13, LaptevVV пишет:

> Тем не менее мне удалось только стандартными средствами повысить
> быстродействие более, чем в 10 раз по сравнению с первоначальной версией...
В конкретном узком случае бывает возможно повысить быстродействие раз в
50 в этих задаче.
Нужно смотреть от оптимизации работы с кешами процессора до
использования всех возможностей последних SSE.
Кстати, можно даже обогнать в узких случаях даже IntelMKL.

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

17.08.2011 18:09, caxaromires пишет:

>
> "... в БОЛЬШИНСТВЕ случаев..." — какое такое большинство? Или имеется в
> ввиду именно работа с матрицами?
Ну как бы это и обсуждают. Именно работы с матрицами.

17.08.2011 17:52, caxaromires пишет:

> V>вектор векторов (нереально кривое решение в большинстве случаев,
> кстати) — можно подробнее?
Легче сказать, когда такое решение не кривое: один раз используемый
объект в совершенно некритичном по памяти и быстродействию месте
программы, который нужно написать за 5 мин и забыть.

ну тоесть обычно 80% кода некритично к скорости а 20% критичных если они вообще есть
(далеко не каждую программу надо оптимизить по скорости а которую надо то критичного кода
малая часть от программы)
можно писать и без вектора векторов (с извращениями и велосипедами)
в на остальных 80% можно использовать любой по скорости код примерно так
привило где то есть 80/20 об оптимизации (если с цифрами не наврал зуб не даю)