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 и куча опенсурсных уже давно всю работу с матрицами
реализовали и заточили под большинство современных процессоров.
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 раз по сравнению с первоначальной версией...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
просто это вовсе не цельный кусок памяти а адовый венегрет
если исходить из того что объект это только дескриптор а данные где то в куче
то вот применая карта памяти
поэтому достать элемент не так тиривиально как из сплошного куска памяти
int (*ptr)[N];
*(*(ptr + i) + j)
хотя после оптимизатора по скорости должно быть одинаково если только
и будет проигрывать то только из того что обращения к памяти не такие локальные
как для простого массива
17.08.2011 18:12, LaptevVV пишет:
> 1. Почему велосипед с квадратными колесами? Можно обоснование? То, что я > читал, мне понравилось. Тем более, что это и для фортрана сделали.
Просто это область достаточно нетривиальная и не существует в ней
единственного правильного решения. В каждой конкретной ситуации
необходимо выбирать вариант реализации.
Но именно эта часть и есть самая интересная для продвинутых студентов.
Применения различных вариантов параллелизации тоже определяется
предметной областью. Например во многих случаях наиболее узким местом
будет работа с кешами процессора, а не быстродействие и количество
процессоров. Но именно на этой теме очень удобно исследовать особенности
распараллеливания вычислительных задач.
Плюс к этому добавляется проектирование интерфейса этого класса — тут
тоже нет какого единого лучшего решения.
Плюс к этому еще добавляется совместимость с фортраном и др.
Достаточно полезные умения по поиску "узких горлышек" в программах на
этих примерах можно выработать. Корректную работу с памятью — на STL тут
аккуратно полагаться надо.
Ну и еще очень интересный для обучения кусок: разреженные матрицы,
реализация, подходы, операции с ними.
Какую-то литературу не посоветую, да в ней и смысла мало (у AMD на сайте
были статьи по нюансам оптимизации для их процессоров).
Кстати, для тех же студентов будет интересно сравнить(показать),
например, различия в скорости выполнения одного и того же матричного
алгоритма в зависимости от процессора (модели, размера кэшей,
организации) и размера матрицы. Очень оригинальные результаты могут
получаться.
> 2. Совесть здесь причем? Я вообще-то препод и с данной предметной > областью столкнулся первый раз...
Так я и не понял. Ты, как препод этим интересуешься или втюхать кому-то
что-то хочешь.
C>"... в БОЛЬШИНСТВЕ случаев..." — какое такое большинство? Или имеется в ввиду именно работа с матрицами?
Как правило, вектором векторов люди пытаются представить матрицы. Если речь идет о чем-то другом, то вопросов нет.
Здравствуйте, jyuyjiyuijyu, Вы писали:
J>просто это вовсе не цельный кусок памяти а адовый венегрет J>если исходить из того что объект это только дескриптор а данные где то в куче J>то вот применая карта памяти
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 об оптимизации (если с цифрами не наврал зуб не даю)