Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
#1

Скорость выполнения, а так же работа с дв. файлами - C++

24.06.2012, 22:07. Просмотров 1209. Ответов 20
Метки нет (Все метки)

Здравствуйте. У меня есть несколько вопросов, на которые я уже давненько ищу ответы, а именно :

1) Для таких классов, как vector/set/map и прочих, что быстрее - iterator или [] ?

2) Тот же вопрос, но для двумерного vector/set/map, ведь, если даже itearator быстрее [] для одномерного, то, чтобы получить доступ к элементу a[i+1][j+1] через итераторы, придется писать нечто подобное (и не иначе? есть ли возможность другого доступа к i+-N элементов?) :
*((i+1)->begin() + int(j - i->begin() + 1))
В данном случае [] будет гораздо быстрее, так ведь?

3) Есть ли различия в скорости между :
const int MAX = 1000*1000;
vector < vector <int> > a(MAX, vector<int>(MAX));
и
vector < vector <int> > a(MAX);
for (int i=0; i<MAX; i++)
a[i].resize(MAX);
?

4) Недавно работал с двоичными файлами и нужно было не считывая и не записывая ничего в файл (по неизвестному N, которое определяет кол-во элементов в файле), при помощи fseek пробежаться эти N раз с отступом по sizeof и, соответственно, определить его, но вот беда, fseek в упор не видел feof и EOF. Как ни старался, он его проходит и ничего путного о конце файла не говорит, причем не важно - прошел он его мимо или прямо-таки "наступил" на него.. Кто-нибудь сталкивался?

5) Слышал, что функции корня и возведения в степень можно заменить логарифмами и что это, якобы, быстрее, но сколько не шарюсь в гугле, найти чего-то путного по этому поводу не могу.. Можете сказать, как же произвести замену или хотя бы дать ссылку на статейку/заметку?

6) Быстрее ли inline-функция, чем обычная функция? Если да, то на сколько (примерно)? Есть хотя бы 100-200 тактов?

7) Недавно сталкивался с задачкой на оптимизацию и столкнулся с фактом, который не могу объяснить, а именно : цикл от 0 до N работает медленнее, чем цикл от N до 0, причем при больших данных, эта разница была огромной (Задача была в небольшой работе с массивом, был двойной цикл от 0 до (максимум) 2000. При максимальном значении, разница между 0->N и N->0 была в районе 0,3 секунд). Кто-нибудь может пояснить, откуда? Почему такая разница?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.06.2012, 22:07     Скорость выполнения, а так же работа с дв. файлами
Посмотрите здесь:
C++ Скорость выполнения.
Скорость выполнения delete C++
C++ Скорость выполнения операторов
От чего зависит скорость выполнения программы? C++
Как узнать скорость выполнения программы? C++
Влияет ли невыполняющееся условие на скорость выполнения строчки с этим условием? C++
Найти количество счастливых билетов учитывая скорость выполнения программы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
26.06.2012, 12:57  [ТС]     Скорость выполнения, а так же работа с дв. файлами #16
Цитата Сообщение от diagon Посмотреть сообщение
...
Кстати, только что как раз ришал "Числовую последовательность", что у вас в блоге. Было бы интересно увидеть решение динамикой (во всяком случае в "обсуждении" задачи говорят, что есть нерекурсивное решение) или ещё чем-то.
Я, как идиот, забыл, что такое логарифм, и искал уровень двоичным поиском.. >_<"

Добавлено через 1 час 1 минуту
Цитата Сообщение от Evg Посмотреть сообщение
Запусти вот такой код:...
Хах, да уж, искал что-то глубокое, а ведь ответ был на поверхности, спасибо большое : D

Цитата Сообщение от diagon Посмотреть сообщение
Во-первых, замените вектор векторов на обычный статический массив. Дело в том, что у них очень старый компилятор, который, к тому же, запускается в режиме без оптимизаций.
Во-вторых, там очень много ввода, даже scanf с таким не справится. Тут нужно писать свою функцию чтения.
В третьих, в этой задаче есть небольшой чит.
Можно поставить в начале условие
C++
1
2
if ( n > 700 )
   n = 700;
Это в ~3 раза ускорит программу.
1) Т.е. если я использую вектор, то он (у них) быстрее статического массива, а при векторе векторов (и глубже) медленнее, так?
2) Если вы имеете ввиду в прямом смысле "функцию чтения", то странно, что требуется такой глубокий "анализ" на 35%, учитывая сложность таких задач, как "Шаблон" или та же "Числа в последовательности".
Если же вы имеете ввиду разверстку цикла, то разве не будет хуже? Ведь мне каждый раз придется проверять, не считываю ли я слишком много? (Т.е., если я разверну 100 scanf'ов, а у меня осталось 97, то каждую итерацию мне нужно будет проверять n-i <= 100 и уже от него скакать либо scanf'ом 100 к ряду, либо обычным циклом от 1 до 97 без разверстки.
p.s Где-то читал про "дв. разверстку", ту, где при помощи рекурсии каким-то образом можно считать, допустим 100 раз scanf'ом, осталось 97, уменьшили scanf'ы до 50, считали и так далее, но не видел реализации, да и странно это, ведь выделение памяти в рекурсии займет, как я думаю, больше времени, чем обычный цикл? Вы об этом что-нибудь знаете?
3) Не знаю почему, но "чит" не работает. Уже пробовал ;<
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.06.2012, 13:06     Скорость выполнения, а так же работа с дв. файлами #17
Цитата Сообщение от nexen Посмотреть сообщение
1) Т.е. если я использую вектор, то он (у них) быстрее статического массива, а при векторе векторов (и глубже) медленнее, так?
Вектор у них в любом случае медленнее статического массива, т.к. их компилятор не умеет инлайнить.
Итого, для одного обращения к элементу матрицы вызываются две функции, а это довольно сильно тормозит программу.

Цитата Сообщение от nexen Посмотреть сообщение
Если вы имеете ввиду в прямом смысле "функцию чтения", то странно, что требуется такой глубокий "анализ" на 35%
Если бы там стоял нормальный сервер, то сдать эту задачу было бы проще. Но сейчас там стоит какое-то корыто, поэтому приходится извращаться.

Как вариант, можно открыть файл как бинарный, и читать по много байт за раз.
Shandr_71
13 / 13 / 1
Регистрация: 05.12.2011
Сообщений: 84
26.06.2012, 16:35     Скорость выполнения, а так же работа с дв. файлами #18
Цитата Сообщение от nexen Посмотреть сообщение
Хм, а это можно как-то правилами логики объяснить? Или имеется ввиду лишняя проверка, созданная компилятором при трансляции?

p.s Эм, да, что-то я забыл про теги кода :<
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//От 0 до n
    xor rcx, rcx
lo: 
    nop
    inc rcx
    cmp rcx, n
    jb lo
 
//От n до 0
    mov rcx, n
    dec rcx
lo:
    nop
    dec rcx
    jnz lo

Разницу здесь составляет команда
Assembler
1
cmp rcx, n
которая при нахождении n в памяти может занять 100-200 тактов.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
26.06.2012, 16:53     Скорость выполнения, а так же работа с дв. файлами #19
Цитата Сообщение от Shandr_71 Посмотреть сообщение
rcx
О_о
Это на какой архитектуре?
Shandr_71
13 / 13 / 1
Регистрация: 05.12.2011
Сообщений: 84
26.06.2012, 16:55     Скорость выполнения, а так же работа с дв. файлами #20
Цитата Сообщение от Deviaphan Посмотреть сообщение
О_о
Это на какой архитектуре?
Дык на х64.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.06.2012, 17:06     Скорость выполнения, а так же работа с дв. файлами
Еще ссылки по теме:
Организовать работу функции так, чтобы программа не дожидалась окончания её выполнения (многопоточность) C++
C++ Элементарный класс для работы с файлами, компилятор выдает ошибку, что не так с private
работа с файлами C++
C++ работа с файлами на с++
Работа с файлами C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
26.06.2012, 17:06     Скорость выполнения, а так же работа с дв. файлами #21
Цитата Сообщение от Shandr_71 Посмотреть сообщение
Дык на х64.

Я забыл, что ассемблерный код для х64 тоже вывести можно. Извиняйте.)
Yandex
Объявления
26.06.2012, 17:06     Скорость выполнения, а так же работа с дв. файлами
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru