Сказка о потерянном времени

[denismaster]

Вероятно, у вас опечатка, ибо в C# есть Dictionary, а не Directory)
А статья довольно интересная)

[crea7or]

Точно! Писал уже ночью и напутал.

[lookid]

Сказка о потерянном времени на изучение С++

[safinaskar]

lookid прав, время не потеряно, оно ушло на изучение C++

[4e1]

можно было бы использовать GMP вместо буста, я как-то сравнивал скорость boost::rational<boost::multiprecision> с рациональными в GMP (mpq) — буст проигрывал в ~20 раз

[crea7or]

Вряд ли можно сделать проще и быстрее чем два int64. GMP серьёзная вещь и больше подойдёт для серьёзных же задач, а тут таковой не стояло.

[crea7or]

Так у меня хэш таблица и есть один из вариантов. Ну только она самодельная, так как выросла их простого фильтра. Я её в статье map'ом обозвал почему-то. Только любой не линейный поиск упрётся в вылет данных из кэша процессора.

[AnROm]

Гипотеза Эйлера утверждает, что для любого натурального числа n>2 никакую n-ю степень натурального числа нельзя представить в виде суммы (n-1) n-х степеней других натуральных чисел.

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

Круто, что вы взялись за оптимизацию решения задачи.

[PapaBubaDiop]

для k=6 гипотеза Эйлера остаётся открытой

давайте, парни, хватит биткойны майнить

[ilmirus]

Это стандартный шарповый стиль.

[zuborg]

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

[3aicheg]

А потом кто-то возьмёт и добавит:

else
    do_something_else();
    return val2;

И пол-дня будет разбираться, что за хрень происходит, потому что никак не ожидал от себя подобной детсадовской ошибки.

[lgorSL]

Форматирование кода в ide лёгким нажатием клавиш расставит всё по своим местам.

[encyclopedist]

Второе — на каком языке?

[encyclopedist]

Вы заключаете условия на питоне в скобки?

А стиль автора — это один из общепринятых стилей C++. Называется Allman. Он вполне распространённый, и был стандартным стилем Microsoft ещё задолго до появления C#. Его преимущество — сразу видно какая скобка какой соответствует, сканируя взглядом только начала строк.

[trapwalker]

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

— Папа, а что это тут все дяди с синяками и некоторые убитые?
— Это хабр, сынок.

[3aicheg]

[safinaskar]

Стиль без фигурных скобок опасен. Именно из него произошел apple goto fail bug, ищите в инете

[crea7or]

Есть разные правила и именно это мне помогает быстрее понять код. Можно предположить, что границы объектов быстро определяются зрительными отделами и дальше разбирается код внутри уже отделённый чёткими границами(скобками). У других может быть по другому — вариативность устройства мозга огромна. Кому-то и одной скобки на новой строке в конце хватает.

[Fil]

Когда я перешел на новую работу, мне пришлось переучиваться и помещать скобку на новой отдельной строке. И теперь считаю, что так лучше.
1. Открывающая и закрывающая скобки расположены на одном уровне. Это довольно естественно. В GUI, перейдя курсором на закрывающую скобку, легче найти подсвеченную открывающую и глазами визуально выделить блок.
2. Кода влезает меньше, но он не такой плотный, опять же легче ориентироваться в нем. И меньшее количество умещенного кода на экране стимулирует разбивать большие функции.

[3aicheg]

А что, кто-то ещё пишет на С++, не перенося фигурную скобку на новую строку? Глянул щас сорцы нескольких опенсорсных библиотек (boost, OpenCV, VTK, OptiX и т. п.) — везде переносят.

Стайлгайдов, вообще-то, >1, и рекомендации порой сильно отличаются. Из широко известной в узких кругах книги про верёвку и ногу:

Выравнивайте скобки вертикально по левой границе.
Иногда поиск отсутствующей фигурной скобки превращается в крупную проблему. Если вы вынесете скобки туда, где их хорошо видно, то их отсутствие будет сразу же заметно:

while ( some_condition )  
{  
	// внутренний блок  
}  

Я в самом деле не люблю так называемый стиль Кэрнигана и Ричи:

if (condition) {
	code();
}else{
	more_code();
}  

Здесь не только трудно проверить скобки на парность, но и отсутствие зрительного разделения за счет строк, содержащих лишь открытые скобки, ведет к ухудшению читаемости.

Честно, вот не понимаю, как это уродство без переноса скобки вообще могло появиться на свет — единственная теория, что мало было строк на первых терминалах и их пытались экономить всеми силами. Но вот как оно кому-то может нравиться сейчас, когда нет, вроде, никаких проблем уже давно с количеством строк на мониторе??..

[borisko]

Честно, вот не понимаю, как это уродство без переноса скобки вообще могло появиться на свет — единственная теория, что мало было строк на первых терминалах и их пытались экономить всеми силами. Но вот как оно кому-то может нравиться сейчас, когда нет, вроде, никаких проблем уже давно с количеством строк на мониторе??..

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

[3aicheg]

Почему тогда они закрывающую всегда переносят? Тоже оставить на той же строке, ещё больше можно сэкономить.

[zuborg]

Я пользуюсь K&R style, и часто после закрывающей скобки ставлю дополнительную пустую строку — мне так проще группировать код по функциональности. Отдельная открывающая скобка занимает столько же места, сколько пустая строка — и для меня выглядит, что if() стоит одинаково отдельно от кода, что ниже, и от кода, что выше, т.е. строка с if() как бы сама по себе. Дело привычки, наверное, но мне ломает встроенный парсер ).
В любом случае, отступы прекрасно помогают (опять же, лично для меня) выделять уровни кода, дополнительная строка с открывающей скобкой мне ни к чему от слова «вообще».

[masai]

Почему тогда они закрывающую всегда переносят? Тоже оставить на той же строке, ещё больше можно сэкономить.

Вы в полушаге от синтаксиса Python. :)

[3aicheg]

Вот только не надо сюда за уши притягивать Питон — в С++ отступы не несут никакой семантической нагрузки, как бы упоротые адепты египетских скобок не пытались убедить в этом всех подряд, и себя, в том числе :) Поэтому «да какая разница, где скобки, мы всё разобьём на блоки отступами, и будет щасте» — не аргумент, рано или поздно вы облажаетесь с расставлением отступов, и компилятор вам об этом ни слова не скажет.

[masai]

Вообще, это шутка была. А если серьезно, то я довольно много пишу на Python и с ошибками в отступах если и сталкивался, то не помню когда. Точно так же можно ошибиться с расстановкой фигурных скобок. Для решения таких проблем как раз и придуманы тесты. Которые, кстати, стоит писать независимо от языка.

[zuborg]

Не спорю. Мне просто не удалось сразу таких нагуглить

В Go Вы обязаны использовать camel style (K&R) — иначе код не скомпилируется вообще (компилятор считает, что каждая строка заканчивается ';', а компиляция конструкций вида if(..); {… } не предусмотрена). Многие из-за этого сильно ругают Go, кстати ;)

[zuborg]

Точно, Вы правы. Перепутал верблюдов с Египтом

[darkslave]

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

[kdekaluga]

Лично у меня вызывает больше понимания именно такой стиль, когда открывающаяся скобка занимает свою отдельную строку, но тот же самый гугл, например, считает, что надо иначе:

https://google.github.io/styleguide/cppguide.html

Однако, раньше у них было строгое требование — «помещайте открывающуюся скобку в конце строки и никак иначе», сейчас же уже менее строго — «сами решайте, но проект лучше читаем, когда в нем единый стиль» (при этом весь код примеров форматирован K&R).

[TheCalligrapher]

В коде, написанном на С- и С++-подобных языках всенепременнейше рекомендуется писать открывающую фигурную скобку на отдельной строчке: это создает визуальное вертикальное разделение между предшествующим такой скобке кодом (зачастую: заголовок цикла, if с условием и т.п.) и собственно телом compound statement. Наличие такого вертикального разделения астрономически повышает читаемость кода.

Вопрос "вертикального размазывания кода" уже давно не актуален. Код должен содержать огромное количество грамотно расставленного вертикального спейсинга. Преимущества в удобочитаемости кода легко затмевают потери в количестве умещающихся на экране строк.

За "египетские скобки" в современном коде надо бить по рукам так же, как и за явное приведение результата malloc в C.

[vitalick27]

Интересная статья!

PS: Как же легко программисту бросить вызов интересной задачей)
PSS: Понимаю что извращение, но под рукой есть только оракл, запустил на нем вычисления)

[zuborg]

PS: Как же легко программисту бросить вызов интересной задачей)

Загляньте тогда на Project Euler )

[crea7or]

Вот это класс — шикарный проект!

[jknight]

Малость оффтоп, но… Как-то в универе устроили на этом сайте конкурс — кто больше всех задач за неделю нарешает, поедет в любую мат/физ/cs школу на выбор. Поехал участник, нарешавший 81 задачу. У меня 69 было. Вот вроде и давно было, а чувства к этому проекту тееееплые..:)

[crea7or]

Для N=150, UInt128, boost и 27 + 84 + 110 + 133 = 144 (в пятой)
SEARCHRANGE: 0.068 сек. (210 000 i/ms)
SEARCHMAPUSE: 0.141 сек. (78 000 i/ms)
SEARCHBITSETVECTOR: 0.047 сек ( 277 000 i/ms)

Там считается и показывается скорость перебора: i/ms это количество переборов за миллисекунду — это более правильный замер.

N = 86000, UInt128, boost скорость будет такая:
SEARCHRANGE: 250 000 i/ms
SEARCHMAPUSE: 33 000 i/ms
SEARCHBITSETVECTOR: 81 000 i/ms

N = 1000000, UInt128, boost скорость будет такая:
SEARCHRANGE: 330 000 i/ms
SEARCHMAPUSE: 10 000 i/ms
SEARCHBITSETVECTOR: 16 500 i/ms

До полного подсчёта остальных я так и не дошёл.

[crea7or]

Я зациклился именно на скорости, задача найти числа отошла на второй план и потом практически пропала.
Да, ни 6 ни 7 пока нет насколько я знаю.

[crea7or]

Нет, такого не видел. Зато вот нашёл список решений на множестве языков.

[crea7or]

А вот похоже оно.

[zuborg]

Я зациклился именно на скорости

И за какое же время Ваша программа находит все решения (кратные 144^5=...) для N <= 7131 (корень пятой из 2^64, т.е. все числа помещаются в uint64)?

[crea7or]

Эта версия — неприлично долго.

[encyclopedist]

за какое время ваша программа нашла результат

Это плохая метрика для этой задачи. Потому что в такой метрике победит программа которая сразу проверит именно это решение.

[crea7or]

Для 4 есть алгоритм на еллиптических кривых. Но это надо быть математиком.

[Deosis]

На одном из соревнований по спортивному программированию была задача: определить сколько натуральных чисел меньше введенного (ввод ограничен миллиардом) удовлетворяют некоторому условию.
Проблема в том, что честный подсчет не укладывается в лимит времени.
Предполагаемый способ решения: подсчитать список таких чисел заранее (их оказалось немного), забить в табличку и отправить на проверку вариант, который ищет по табличке.

ПС. Сколько потеряно времени на обсуждение скобочек.

[zuborg]

До полного подсчёта остальных я так и не дошёл

В смысле, не дошли до следующих совпадений, таких как
54^5+168^5+220^5+266^5=288^5
?

[crea7or]

Это не следующее значение, это то же самое: 27^5 + 84^5 + 110^5 + 133^5 — только в два раза больше.
Следующее это: 55^5 + 3183^5 + 28969^5 + 85282^5 = 85359^5.

[knotri]

Всброшу интересную задачу. (Сам еще не решил)

Есть бесконечное поле в клеточку — между точками клеточек резистор в 1 Ом.

Какое будет сопротивление между точками
A(0,0) и B(2,1)

[galaxy]

Ответ

Вообще там кроме случая соседних узлов все сложно

[Effolkronium]

Интересно было бы переписать это на компайл-тайм выполнения на С++ с помощью constexpr. Тогда в рантайме оно бы просто выводило результат

[Effolkronium]

Код оставляет желать лучшего. Гора магических чисел и непонятных переменных

[crea7or]

Там только буфер для самописного map'a отдельно определяется — чтобы можно было подстроить/посмотреть.

[crea7or]

Кому интересно, вот тут ещё набор идей по улучшению перебора чтобы не смотреть всё подряд.

[lgorSL]

Странно, что Вы это не использовали. Можно было бы использовать инты и для больших значений — просто забить на переполнение, а всё подошедшее проверять честным расчётом на uint128. Вероятность случайных совпадений очень мала, поэтому "честные" проверки не займут много времени.

[crea7or]

А я его только -только нашёл. Вот тут самый быстрый алгоритм (c++ second version), но до N=10000 ему уже надо 6гб памяти(он там по double переполняется находя неправильно решение 2615 и его ещё надо править, я им там написал про это как раз).

[antonkrechetov]

Глянул вариант от 2Alias и решил попробовать свои силы — реализовать алгоритм для тех же 250 чисел с теми же отсечениями.

Получилось вот что (C++11)

#include <iostream>
#include <algorithm>
#include <chrono>

using std::cout;
using std::endl;

using work_num = long long;
using index_num = unsigned int;

constexpr index_num elements_count = 250;

inline work_num pow5(index_num n) {
  const work_num pow2 = n * n;
  return pow2 * pow2 * n;
}

int main() {
  auto start = std::chrono::steady_clock::now();

  work_num powers[elements_count];
  for (index_num i = 0; i < elements_count; ++i) {
    powers[i] = pow5(i);
  }

  // a^5 + b^5 + c^5 + d^5 = e^5
  for (index_num a = 1; a < elements_count; ++a) {
    for (index_num b = a + 1; b < elements_count; ++b) {
      for (index_num c = b + 1; c < elements_count; ++c) {
        for (index_num d = c + 1; d < elements_count; ++d) {
          work_num sum = powers[a] + powers[b] + powers[c] + powers[d];
          if (std::binary_search(powers, powers + elements_count, sum)) {
            work_num* e_ptr = std::lower_bound(powers, powers + elements_count, sum);

            auto end = std::chrono::steady_clock::now();
            cout << a << " " << b << " " << c << " " << d << " " << (e_ptr - powers) << endl;
            cout << "Time: " << std::chrono::duration<double, std::milli>(end - start).count() << "ms" << endl;

            exit(0);
          }
        }
      }
    }
  }

  auto end = std::chrono::steady_clock::now();
  cout << "Time: " << std::chrono::duration<double, std::milli>(end - start).count() << "ms" << endl;
}

Работает на 28% быстрее оригинала. Вывод — для решения задачи нужно пользоваться наиболее подходящими средствами языка. В данном случае, ни вектор ни map не нужны, а лучше всего подходит бинарный поиск по отсортированном массиву. А рекурсию лучше заменить на вложенные циклы.

[SKolotienko]

Всё ждал в конце этой захватывающей истории, «А потом я заметил, что работаю под Debug и переключился на Release» :)

[crea7or]

Если кому интересно, то в 1966 году искали вот так.

[ProgrammerAlias]

Я 2Alias. Для значений не влезающих в 64 бита, можно искать решения в 64-х битном беззнаковом типе unsigned long long (какбы по модулю 2^64) а когда решение по модулю 2^64 найдено, проверять действительно ли это решение.
Ещё не стоит забывать что это алгоритм почтичто «в лоб», мне думается, что можно придумать гораздо более быстрые варианты.
Когда я терял своё время с этой задачей, мне думались варианты с отсечениями решений по разным модулям. Часть чисел просто не может быть пятой степенью по определённом модулю. т.е. для некоторого числа M и некоторых Y, 0 < Y < M, не существует такого X, что X^5 % M == Y. Для решения уравнения a^5+b^5+c^5+d^4=e^5, можно эффективно перебирарать e, затем a, b, c, а уже d искать в хеш-таблице.

[ProgrammerAlias]

Как-то я неправильно воспроизвёл идею оптимизации с модулями, или может я её и тогда не додумал. Но написал как-то бред, с температурой сижу.

[crea7or]

на rosettacode как раз по модулю 30 и отсекают всё «ненужное». 11 секунд на перебор до N=1000. И, например, дальше отсекать нечётные суммы уже практически не имеет смысла. Выигрыш около 0.2 сек.

[zuborg]

5-я степень по модулю 30 может иметь все возможные остатки — от 0 до 29 включительно. Проверкой по модулю 30 нельзя отсечь ни числа, не являющимися суммой двух пятых степеней (сумма двух пятых степеней может иметь любой остаток по модулю 30), так и ни отсечь одно из слагаемых этой суммы (например, большее число может иметь тоже любой остаток по модулю 30, независимо от значения остатка суммы).

[crea7or]

По модулю 30 двигается pivot, так как число и его степень по модулю 30 равны. Получается в ~30 раз меньше проверок.

Вот их код:

// go straight to the first appropriate x3, mod 30
					if (int err30 = (x0 + x1 + x2 + x3 - rs) % 30)
						x3 += 30 - err30;
					if (x3 >= x2)
						break;
					auto sum = s2 + pow5[x3];

rs это pivot в массиве степеней.

[zuborg]

Что-то я не понял этот код. Они ссылаются на код С, но в С трюк mod-30 используется по другому — там перебирается четыре числа, и проверка 5-го происходит с фильтрацией по остатку mod 30.

А в коде C++ перебираются 3 числа (x0, x1, x2) и затем почему-то делается сдвиг x3 для коррекции остатка, хотя без фиксации пятого числа это не имеет смысла — какой бы остаток mod 30 не был у x3 — всегда найдется 5-я степень с таким же остатком mod 30, как и суммы x0^5+x1^5+x2^5+x3^5, без этой коррекции.

И в чем смысл этого rs, мне совсем не понятно.

[crea7or]

rs это pivot в массиве степеней. Так как мы перебираем только вверх, то и искать в массиве степеней надо только вверх. То есть не надо каждый цикл начинать сначала и бегать с нуля или ещё каким способом чтобы дойти до индекса суммы. В коде на С перебираются уникальные суммы, а в коде на C++ перебираются уникальные сочетания.
В C, например, при 1 2 2 1 и 1 1 2 2 — не появляются в переборе ( 1 2 2 1 будет пропущен), сумма слагаемых ведь от перестановки не меняется (не появится и 1 1 2 2 — так как начинается с 1 2 3 4). А С++ код не будет проверять и 1 2 2 1 — там не появляется одинаковых чисел совсем. То есть 1 2 3 4, 1 2 3 5, 1 2 4 5. 1 3 4 5 и т.д. Из за этого там количество циклов катастрофически меньше. Но мне не очень понятно почему они так сделали. В принципе встречаются равенства со степенями где есть одинаковые слагаемые.
Добавление rs по модулю 30 двигает этот rs к позиции на которой может быть степень числа. То есть он прыгает только по значениям которые могут быть для такой суммы. Суть примерно как у проверки на чётность. Из проверки исключаются все заранее невалидные.

[zuborg]

Пропуск равных слагаемых уменьшит кол-во итераций, но никак не катастрофически.

В коде C++ есть стока

if (pow5[rs] == sum)

Т.е. rs используется для поиска e в уравнении a^5+b^5+c^5+d^5=e^5
Но без фиксации d не получится зафиксировать остаток mod30 для е, и наоборот — пока мы не знаем остаток mod30 для e — мы не знаем какой будет остаток mod30 для d. Мне кажется, что C++ код неправильно использует остаток mod30.

[crea7or]

Я так понимаю, что вы про x3 пишете, но в том примере он уже сложен в общую сумму: auto sum = s2 + pow5[x3];

[zuborg]

Верно, а дальше rs инкрементируется пока rs^5 не достигнет суммы (или превысит её).
Моё замечание касается вставки

if (int err30 = (x0 + x1 + x2 + x3 - rs) % 30)
			x3 += 30 - err30;

до того, как начнется подбираться rs — он участвует в вычислении err30, но значение rs в этот момент не зависит от того, какой окажется итоговая сумма.

[Deosis]

Дельное замечание. Самая простая оптимизация: считать с шагом 2, так как возведение в степень не меняет чётность. Это позволит ускорить перебор в 2 раза. Что гораздо лучше, чем

(boost::unordered_map оказался быстрее std::unordered_map примерно на 10%)

[zuborg]

Допустим, Вы рассматриваете число, потенциально являющееся суммой двух пятых степеней. Если Вы будете перебирать большее из чисел с шагом два (и проверять разницу на предмет того, является ли она пятой степенью), то можете пропустить решение.

[crea7or]

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

[Deosis]

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

[zuborg]

В таком случае, что именно Вы предлагаете перебирать с шагом 2?