Оптимизация по скорости и размеру

murderer · Регистрация: 06.10.2010

Author24 — интернет-сервис помощи студентам

На асmp.ru есть "задача про XOR"

В рамках подготовки к чемпионату мира Кирилл придумал Ане задачу. Он написал N знаковых 32-битных чисел и попросил вычислить значение некоторого выражения S. Пусть a₁, …, a_N - все эти числа. Тогда выражение это

S = (a₁ xor a₂ xor … xor a_n) xor (b₁ xor b₂ xor … xor b_n-1),

где

b_i = F(a_i, a_i+1) xor F(a_i, a_i+2) xor … xor F(a_i, a_n).

В этой формуле под знаком xor понимается побитовое «исключающее или», а F(a, b) = x - 1, где x - максимальная степень двойки, на которую делится нацело a-b, если a ≠ b, и F(a, b) = -1, если a = b. Все операции xor выполняются слева направо, если скобки не указывают иной порядок.

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

Входные данные
В первой строке входного файла INPUT.TXT содержится число N (1 ≤ N ≤ 10⁵). В следующих N строках содержится N 32-битных знаковых целых чисел a_i по одному на строке.

Выходные данные
В выходной файл OUTPUT.TXT выведите значение выражения.

Моё решение не проходит по скорости на 16 тесте (более 10000 чисел) - вот оно

Delphi

var
  a:   array[1..999999] of integer;
  i,j: integer;
begin
  reset(input,'input.txt');
  rewrite(output,'output.txt');
  read(i);
  for j:=1 to i do
    read(a[j]);
  asm
  pushad
  mov edi,[i]
  dec edi
  mov ebx,dword[a+edi*4]
  jz @c
  @a:mov esi,[i]
     mov ebp,dword[a+edi*4-4]
     xor ebx,ebp
     @b:mov   eax,ebp
        sub   eax,dword[a+esi*4-4]
        cdq
        xor   eax,edx
        sub   eax,edx
        bsf   ecx,eax
        setne al
        movzx eax,al
        shl   eax,cl
        dec   eax
        xor   ebx,eax
        dec   esi
        cmp   esi,edi
     jnz @b
     dec edi
  jnz @a
  @c:
  mov [j],ebx
  popad
  end;
  write(j)
end.

Лучшее решение на Паскале занимает 706 байт, у меня - 407. Подозреваю что нужно оптимизировать чтение из файла, но не уверен, что это поможет.

Какие идеи?

@volvo · 11.07.2015, 01:44

FIL,

255

@FIL · 11.07.2015, 11:24

volvo, 253

@volvo · 11.07.2015, 11:32

Ну, 253-то было просто, попробуй меньше сделать...

@FIL · 11.07.2015, 12:19

Пробую...

Добавлено через 13 минут
Сделал... 251

@volvo · 11.07.2015, 18:39

Ну, 251 я повторил. А вот дальше, похоже, уменьшить не удастся... Скорее всего, это - предел.

@FIL · 11.07.2015, 19:01

Я тоже так считаю. Открываем карты?

@volvo · 11.07.2015, 19:22

Да без проблем:

Кликните здесь для просмотра всего текста

C++

#include <iostream>
#define T int
T I, R, X, W, B[300000];
 
Q(T* Z, T N, T Y, T M)
{
    if(N)
    {
        for(I=X=0; I<N; B[W&M?N+I-X:++X]=W)W=Z[++I+Y];
        R^=X*(Y=N-X)&1||!M&&N&2?M-1:0;
        M?Q(B, X, 0, M+=M):0;
        Q(B, Y, N, M);
    }
}
main()
{
#define C std::cin>>
    for(C X; I<X; R ^= B[++I]=W) C W;
    Q(B, X, 0, 1);
    std::cout << R;
}

@FIL · 11.07.2015, 23:46

Код

C++

#include <iostream>
 
int n, r, z[1 << 22];
 
p(int m, int i, int a)
{
        int b = a + n, x = 0, y = 0;
 
        while (x - y < n)
            z[z[i] & m ? a + x++ : b + --y] = z[i++];
 
        if (x&y&1 || !m && n&2)
            r ^= m - 1;
 
        n = x;
        if (n > 1)
            p(m + m, a, b);
 
        n = -y;
        if (m)
            p(m + m, a + x, b);
}
 
main()
{
    while (std::cin >> z[n])
        r ^= z[n++];
 
    p(1, 1, n--);
 
    std::cout << (r ^ z[0]);
}

(форматирование не удалял)

Добавлено через 2 минуты
Я думал, что у нас нечто похожее должно было получиться...

Добавлено через 7 минут
Даже удивительно, что мы на одном и том же количестве символов остановились.

Добавлено через 4 часа 10 минут
Собрал код с учетом двух имеющихся вариантов:

C++

#include <iostream>
 
int i, x, r, z[1 << 22], w;
 
p(int m, int n, int y)
{
    for (i = x = 0; i < n; z[w&m ? i + n - x : ++x] = w)
        w = z[++i + y];
 
    r ^= (x&(y = n - x)&1 || !m && n&2) ? m - 1 : 0;
 
    m ? p(m += m, x, 0) : 0;
 
    n ? p(m, y, n) : 0;
}
 
main()
{
    while (std::cin >> z[x])
        r ^= z[x++];
 
    p(1, --x, 0);
 
    std::cout << (r ^ z[0]);
}

Получилось 232 символа.

@Ethereal · 12.07.2015, 08:40

Сообщение от volvo

Ничего я не хочу никому доказывать. Много чести. Нужно было бы - сделал бы код и более быстрым и более грамотным.

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

Добавлено через 29 секунд
Но это уже как-бы не актуально. Было в прошлом.

Добавлено через 5 минут

Сообщение от volvo

убрать все освобождения памяти

Ну это будет уже ошибка в программе. За счет ошибок не выигрываем. Если вносить непроявляющие себя ошибки, то можно сделать исходник еще короче. Я нашел пару способов, но не использовал. Программа должна быть корректной. Именно для этого ее и надо выкладывать. Потому-что ошибки в программе не будешь же выкладывать на всеобщее обозрение.

Добавлено через 2 минуты
Рулит битва за алгоритм. Например у этого

Сообщение от Ethereal

If Odd(X*Y) Or (M=0) And (N And 2 = 2) Then R:=M-1 Xor R;

чуток изменим алгоритм :

Pascal

1	If Odd(X*Y) Or (M+2 = N And 2) Then R:=M-1 Xor R;

Вышло короче. Тут используется то, что M = 0,1,2,4,8,16,32 ... 2^31 а N & 2 = 0,2 и подобное равенство может выполниться только при M+2=2, т.е. при M=0

Добавлено через 54 минуты
@volvo
А чем ты компилируешь свой вариант, который выложил ?
У меня он считает неверно, чем я ни компилирую. Просто неверно.

Добавлено через 4 минуты
Херня какая-то. Я повторил твой вариант на Пасквле. Он считает неверно. Но на том сайте прошел все тесты.

@Ethereal · 12.07.2015, 08:46

Я прицепил архив с файлом Input.txt
Твой вариант его обсчитывает
1442522208 = $55FB2460
а правильный ответ
-1468316576 = $A87B4460

@Ethereal · 12.07.2015, 09:20

У меня есть две программы на Паскале. Одна с этим Input.txt выдает первый вариант ответа. Вторая - второй. На том сайте тесты прошли ОБЕ ! А правильная та, что отвечает -1468316576

Добавлено через 9 минут
C++ исходник Фила тоже сыплется на этом Input.txt. Получается, что вы там рекорды набили неправильным решением.

@volvo · 12.07.2015, 12:01

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

@FIL · 12.07.2015, 12:39

Сообщение от Ethereal

Он считает неверно. Но на том сайте прошел все тесты.

Да, я тоже заметил, что мой вариант, вариант volvo и последний комбинированный выдают разные результаты.
Долго пытался найти ошибку в алгоритмах, но все вычисления адресов выглядят правильными. При малых N результаты совпадают, а при больших уже тяжело анализироват.
А когда загрузил на сайт, то он их все принял.
Надо попробовать log-файл записать с инфой о том, что ксорится и при каких условиях, может что-то прояснится.
Кстати, мой С++ вариант выдает одинаковый результат с Паскалевским, я на это ориентировался при написании.

Добавлено через 5 минут
Попробовал просто лишний ксор дописать в алгоритм - сайт валит его уже на первом тесте.

Добавлено через 9 минут

Сообщение от Ethereal

а правильный ответ
-1468316576 = $A87B4460

Мой финальный код С++ выдает: -1468316576

@Ethereal · 12.07.2015, 21:00

Сообщение от volvo

Сферические кони в вакууме, которые должны бы быть правильными с точки зрения Стандарта С++

С точки зрения условия задания, а не стандарта C++. Речь идет о правильном или не правильном решении задачи. У вас реализован алгоритм, который будет считать правильно не при всяких входных данных. Т.е. типичный говнокод, начинающего программиста, который, когда ему на ошибку укажешь, возражает "но ведь работает-же". Так и ты

Добавлено через 59 секунд

Сообщение от volvo

Правильность решения, к счастью, определяет система, которая принимает задания

Очередное "но ведь работает-же". И плевать, что в алгоритме ошибка. Главное, что сейчас сосчитало правильно, а то, что однажды сосчитает неправильно - не волнует.

Добавлено через 1 минуту
А кто-то пальсы гнул

Сообщение от volvo

Нужно было бы - сделал бы код и более быстрым и более грамотным.

Добавлено через 58 секунд
Как тут насчет грамотности.

Добавлено через 5 минут
З.Ы. Они на своем сайте просто плохо составили тесты. Вот поэтому ваши алгоритмы и прошли. А я просто стал генерить данные по Rnd и при первой-же генерации ваши программы выдали что-то не то. Ее я и выложил выше как Input.txt

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

Pascal

Var A:Array [1..300000] Of LongInt;
    I,R,N:LongInt;
 
Procedure Q(N,O,M:LongInt);
Var X,Y:LongInt;
Begin
   If N<2 Then Exit;
   X:=0;
   For I:=1 to N Do
     If A[I+O] And M = 0 Then
        Begin
           X+=1;
           A[X]:=A[I+O]
        End
     Else
       A[N+I-X]:=A[I+O];
   Y:=N-X;
 
   If Odd(X*Y) Or (M=0) And (N And 2 = 2) Then R:=M-1 Xor R;
 
   If M<>0 Then Q(X, 0, M+M); Q(Y, N, M+M)
End;
 
Begin
   Read(N);
   For I:=1 to N Do
     Begin
        Read(A[I]);
        R:=R Xor A[I]
     End;
   Q(N, 0, 1);
   Write(R)
End.

Он и выдает 1442522208 на выложенном выше Input.txt. А должно быть -1468316576.
Он просто тупо неправильный. Хотя на том сайте проходит все тесты.

Кстати, этот неправильный Паскаль-говновариант 349 символов.
Т.е. на том сайте был бы абсолютным Паскаль-говнорекордом.
Только я, когда отправлял его на сайт, специально добавлял в него две ";"
чтобы он говнорекордом не стал. Не надо мне такой чести.

Это Паскаль. Или опять будешь приводить отмазки про стандарт или не стандарт C++ ?

@FIL · 12.07.2015, 21:04

Сообщение от Ethereal

типичный говнокод

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

@Ethereal · 12.07.2015, 21:39

Минимальная длина исходного текста программы при правильном решении задачи.
Вполне корректный критерий.
Ясно, что при этом исходник никак не будет качественным с точки зрения читабельности и оформления текста. Но исходник все равно ДОЛЖЕН содержать правильное решение. Этот критерий должен стоять незыблемо. Исходник может быть сколь угодно некрасивым с точки зрения Дейкстры. В жопу Дейкстру. В жопу структурность, легкую модифицируемость и подобную хрень. Но исходник не должен содержать ошибок. Входные данные в объявленных в условии задачи рамках он должен обсчитывать правильно в любом случае. Иначе он неверный. Иначе вы задачу не решили. Вот о чем речь.

@FIL · 12.07.2015, 22:39

Сообщение от Ethereal

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

С этим я согласен, но не на калькуляторе же обсчитывать 100К эл-тов, а минимум 19 тестов, написанных людьми, которые чему-то учат детей, прошли на ура. Вот в чем для меня основная загадка. Неужели у них нет теста со случайными числами.

Добавлено через 56 минут
В принципе, ошибку устранил, "раздвинув" массивы (n заменил на n*2). Видимо, при определенных условиях возникал перехлест.

C++

1
2
3

    for (i = x = 0; i < n; z[w&m ? i + n*2 - x : ++x] = w)
        ...
    n ? p(m, y, n*2) : 0;

Итого:

C++

#include <iostream>
#include <fstream>
 
ifstream fi("input3.txt");
ofstream fo("output.txt");
 
int i, x, r, z[1 << 22], w;
 
p(int m, int n, int y)
{
    for (i = x = 0; i < n; z[w&m ? i + n*2 - x : ++x] = w)
        w = z[++i + y];
 
    r ^= (x&(y = n - x)&1 || !m && n&2) ? m - 1 : 0;
 
    m ? p(m += m, x, 0) : 0;
 
    n ? p(m, y, n*2) : 0;
}
 
main()
{
//  while (std::cin >> z[x])
    while (fi >> z[x])
        r ^= z[x++];
 
    p(1, --x, 0);
 
//  std::cout << (r ^ z[0]);
    fo << (r ^ z[0]);
    fo.close();
    fi.close();
}

@Ethereal · 12.07.2015, 23:16

Вот проверьте на таких данных.

Код

Тут 6 чисел. Алгоритм volvo дает результат 9. А правильный ответ 15.

Добавлено через 7 минут
Алгоритм Фила, скрещеный с алгоритмом volvo тоже стал неправильным от такого скрещивания.
Я имею ввиду

Сообщение от FIL

Собрал код с учетом двух имеющихся вариантов:

Вот от этой сборки. Хотя до этого был ОК.

@FIL · 12.07.2015, 23:19

Я ж написал выше в чем ошибка и как ее устранить.
С этими правками результат становится правильным.

@Ethereal · 12.07.2015, 23:38

Достаточное условие перехлеста в алгоритме volvo. Пусть было N чисел
Пусть они разделились на X и Y.
Пусть X разделилось на x и y.
Если X+y >= N то кердык.
В моем примере N=6, X=4 Y=2 x=1 y=3 X+y=7>N=6 и кердык.

Добавлено через 10 минут

Сообщение от FIL

Я ж написал выше в чем ошибка и как ее устранить.
С этими правками результат становится правильным.

Ага, -1464621984. А должно быть -1468316576. На том длинном Input.txt

@volvo Супер-модератор 32835 / 21172 / 8148 Регистрация: 22.10.2011 Сообщений: 36,432 Записей в блоге: 8
	11.07.2015, 01:44	61
	FIL, 255 0

@volvo Супер-модератор 32835 / 21172 / 8148 Регистрация: 22.10.2011 Сообщений: 36,432 Записей в блоге: 8
	11.07.2015, 11:32	63
	Ну, 253-то было просто, попробуй меньше сделать... 0

@FIL Модератор 3490 / 2613 / 741 Регистрация: 19.09.2012 Сообщений: 7,974
	11.07.2015, 19:01	66
	Я тоже так считаю. Открываем карты? 0

@Ethereal 6770 / 2739 / 384 Регистрация: 17.02.2013 Сообщений: 4,047
	12.07.2015, 09:20	71
	У меня есть две программы на Паскале. Одна с этим Input.txt выдает первый вариант ответа. Вторая - второй. На том сайте тесты прошли ОБЕ ! А правильная та, что отвечает -1468316576 Добавлено через 9 минут C++ исходник Фила тоже сыплется на этом Input.txt. Получается, что вы там рекорды набили неправильным решением. 1

@volvo Супер-модератор 32835 / 21172 / 8148 Регистрация: 22.10.2011 Сообщений: 36,432 Записей в блоге: 8
	12.07.2015, 12:01	72
	Правильность решения, к счастью, определяет система, которая принимает задания, а не сторонний наблюдатель. Принято - значит для этого сайта решение можно считать правильным. Сферические кони в вакууме, которые должны бы быть правильными с точки зрения Стандарта С++, но не проходящие тест, никого не интересуют. 0

@FIL Модератор 3490 / 2613 / 741 Регистрация: 19.09.2012 Сообщений: 7,974
	11.07.2015, 11:24	62
	volvo, 253 0

@FIL Модератор 3490 / 2613 / 741 Регистрация: 19.09.2012 Сообщений: 7,974
	11.07.2015, 12:19	64
	Пробую... Добавлено через 13 минут Сделал... 251 0

@volvo Супер-модератор 32835 / 21172 / 8148 Регистрация: 22.10.2011 Сообщений: 36,432 Записей в блоге: 8
	11.07.2015, 18:39	65
	Ну, 251 я повторил. А вот дальше, похоже, уменьшить не удастся... Скорее всего, это - предел. 0

@FIL Модератор 3490 / 2613 / 741 Регистрация: 19.09.2012 Сообщений: 7,974
	12.07.2015, 12:39	73
	Сообщение от Ethereal Он считает неверно. Но на том сайте прошел все тесты. Да, я тоже заметил, что мой вариант, вариант volvo и последний комбинированный выдают разные результаты. Долго пытался найти ошибку в алгоритмах, но все вычисления адресов выглядят правильными. При малых N результаты совпадают, а при больших уже тяжело анализироват. А когда загрузил на сайт, то он их все принял. Надо попробовать log-файл записать с инфой о том, что ксорится и при каких условиях, может что-то прояснится. Кстати, мой С++ вариант выдает одинаковый результат с Паскалевским, я на это ориентировался при написании. Добавлено через 5 минут Попробовал просто лишний ксор дописать в алгоритм - сайт валит его уже на первом тесте. Добавлено через 9 минут Сообщение от Ethereal а правильный ответ -1468316576 = $A87B4460 Мой финальный код С++ выдает: -1468316576 0

@FIL Модератор 3490 / 2613 / 741 Регистрация: 19.09.2012 Сообщений: 7,974
	12.07.2015, 21:04	75
	Сообщение от Ethereal типичный говнокод Ethereal, очевидно же, что задача получения наименьшего числа символов, не решается написанием качественного кода, а критерием его "правильности" является прохождение тестов. Поэтому непонятно, зачем к этому придираться. А то, что "неправильный" код прошел тесты, так это вопрос к разработчикам сайта, который, кстати, я там задал. Посмотрим, что ответят. 0

@Ethereal 6770 / 2739 / 384 Регистрация: 17.02.2013 Сообщений: 4,047
	12.07.2015, 21:39	76
	Минимальная длина исходного текста программы при правильном решении задачи. Вполне корректный критерий. Ясно, что при этом исходник никак не будет качественным с точки зрения читабельности и оформления текста. Но исходник все равно ДОЛЖЕН содержать правильное решение. Этот критерий должен стоять незыблемо. Исходник может быть сколь угодно некрасивым с точки зрения Дейкстры. В жопу Дейкстру. В жопу структурность, легкую модифицируемость и подобную хрень. Но исходник не должен содержать ошибок. Входные данные в объявленных в условии задачи рамках он должен обсчитывать правильно в любом случае. Иначе он неверный. Иначе вы задачу не решили. Вот о чем речь. 1

@Ethereal 6770 / 2739 / 384 Регистрация: 17.02.2013 Сообщений: 4,047
	12.07.2015, 23:16	78
	Вот проверьте на таких данных. Код 6 1 3 2 6 10 4 Тут 6 чисел. Алгоритм volvo дает результат 9. А правильный ответ 15. Добавлено через 7 минут Алгоритм Фила, скрещеный с алгоритмом volvo тоже стал неправильным от такого скрещивания. Я имею ввиду Сообщение от FIL Собрал код с учетом двух имеющихся вариантов: Вот от этой сборки. Хотя до этого был ОК. 1

@FIL Модератор 3490 / 2613 / 741 Регистрация: 19.09.2012 Сообщений: 7,974
	12.07.2015, 23:19	79
	Я ж написал выше в чем ошибка и как ее устранить. С этими правками результат становится правильным. 0

@Ethereal 6770 / 2739 / 384 Регистрация: 17.02.2013 Сообщений: 4,047
	12.07.2015, 23:38	80
	Достаточное условие перехлеста в алгоритме volvo. Пусть было N чисел Пусть они разделились на X и Y. Пусть X разделилось на x и y. Если X+y >= N то кердык. В моем примере N=6, X=4 Y=2 x=1 y=3 X+y=7>N=6 и кердык. Добавлено через 10 минут Сообщение от FIL Я ж написал выше в чем ошибка и как ее устранить. С этими правками результат становится правильным. Ага, -1464621984. А должно быть -1468316576. На том длинном Input.txt 0