Очень долго, сдавая задачу Е отсюда, я ловил TL.
В итоге у меня есть 2 посылки (24325463/AC, 1340ms и 24325486/TL10), которые отличаются по времени почти в 2 раза, а по сути лишь порядком индексов в таблице.
И есть вот такие 2 посылки (которые представляют собой тот же код): 24325728/AC, 1652ms и 24325694/TL10, которые отличаются по времени на 450мс, а тексты отличаются лишь количеством пустых строк.
Что я делаю не так?
Auto comment: topic has been translated by HUECTRUM1 (original revision, translated revision, compare)
Нет прав для просмотра посылок.
А вообще, вместо arr[100000][2] рекомендуется использовать arr[2][100000]. Первый случай — это 100000 указателей на 2-элементный массив, а второй — 2 указателя на 100000-элементный массив. Это лучше ложится в кэш, и соответственно доступ к памяти быстрее.
А что значит вариант 2 лучше ложится в кэше? При "правильном" обходе массивов скорость работы отличаться не будет.
Если говорим о статическом массиве, то и первый, и второй случай — цельный кусок памяти без каких-либо указателей. И адресация
a[i][j](по неконстантым индексам) будет работать одинаково быстро. Хотя первый вариант может даже выигрывать за счет того, чтоa + i * 2 + jпосчитать можно без умножения, а дляa + i * 100000 + jнужно умножение.Ну а то, что лучше ляжет в кеш, зависит от того, к каким элементам массива происходит обращение. Если нам нужно часто обращаться вместе к arr[i][0] и arr[i][1], то первый вариант намного быстрее.
Закинул посылки на ideone.
У меня действительно массив [18][MAXN] работает быстрее, чем [MAXN][18]. Впрочем, у меня и абсолютно одинаковые куски почему-то отрабатывают за разное время.