Комментарии / Профиль datacompboy / Хабр

Anton Fedorov@datacompboy

Программист / сисадмин (Sr. SRE)

0,1

Рейтинг

298

Подписчики

ПрофильСтатьи44ПостыНовостиКомментарии6.6K

Void me

datacompboy 30 окт 2024 в 13:10

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

Это наблюдаемое частое, а не фундаментальное свойство.
Например, константные строки могут иметь один в могут иметь разный адрес. И сравнение их через сравнение указателей может работать а может нет. И проблема не в компиляторе, когда он сворачивает или нет константы, а в программисте, который полагается на свою логику а не факты

Литкод изи — это просто

datacompboy 30 окт 2024 в 12:17

Не понимаю примера. Можно в цифрах?...

[0,0,0,0,0
,1,1,1,1,1
,2,2,2,2,2
,3,3,3,3,3
,4,4,4,4,4]

вот это -- каждая строка свой цвет. Данная раскладка имеет 14 решений, но первое находится буквально сразу, как первая же возможная расстановка:

W....
..W..
....W
.W...
...W.

Hidden text

((field)=>{
    var N=Math.sqrt(field.length);
    var rw=Array(N);
    var cl=Array(N);
    var cr=Array(N);
    var sol=Array(N*N);
    var psol=()=>{var k=0;var s='';for(var i=0;i<N;++i){for(var j=0;j<N;++j,++k){s+=sol[k]?'W':'.';}s+='\n';}console.log(s)};
    var id=(r,c)=>r*N+c;
    var nei=(r,c)=>(r>0&&c>0&&sol[id(r-1,c-1)])||
                   (r>0&&     sol[id(r-1,c)])||
                   (r>0&&     sol[id(r-1,c+1)])||
                   (     c>0&&sol[id(r  ,c-1)])||
                   (          sol[id(r  ,c)])||
                   (          sol[id(r  ,c+1)])||
                   (     c>0&&sol[id(r+1,c-1)])||
                   (          sol[id(r+1,c)])||
                   (          sol[id(r+1,c+1)]);
    var ok=(r,c)=>!rw[r]&&!cl[c]&&!cr[field[id(r,c)]]&&!nei(r,c);
    var set=(r,c,v)=>{
        sol[id(r,c)]=v;
        rw[r]=v;
        cl[c]=v;
        cr[field[id(r,c)]]=v;
    };
    var solve=(r)=>{
        var sols = 0;
        for(var c=0;c<N;c++) {
            if(ok(r,c)) {
                set(r,c,true);
                if(r==N-1) { sols ++; psol(); }
                else sols += solve(r+1);
                set(r,c,false);
            }
        }
        return sols;
    };
    console.log("Total count of solutions: ", solve(0));
})([0,0,0,0,0
,1,1,1,1,1
,2,2,2,2,2
,3,3,3,3,3
,4,4,4,4,4])

Как Unity отказались от своих строк

datacompboy 30 окт 2024 в 11:56

А зачем работа со строками на каждый фрейм нужна? Я как-то ожидал, что строки -- для удобства программирования, но в рантайме от них должен остаться только запах и указатели, не постоянное генерирование...

Литкод изи — это просто

datacompboy 30 окт 2024 в 11:36

У нас в задаче N строк, N столбцов и N разных цветов. То есть если есть только одна область -- задача представляет собой одну единственную клетку 1*1

Литкод изи — это просто

datacompboy 30 окт 2024 в 10:31

Ну нас интересует не количество валидных расстановок, а поиск какого-либо решения. Мы же не ищем количество решений, ни пытаемся найти какое-то особое решение -- нам устроит любое.

С этой точки зрения, "каждая строка -- отдельный цвет" это лучший, а не худший случай, мы найдём решение практически с первой попытки.

p.s.: ради интересу добавил вывод числа найденных решений в скрипт; сегодня только одно решение. в задаче от 28го (та что в статье) тоже только одно решение. интересно...

Что такое 50% cpu?

datacompboy 30 окт 2024 в 09:59

для VR очень даже надо рендерить два кадра одновременно.

Литкод изи — это просто

datacompboy 30 окт 2024 в 09:17

Хм. Чет я и правда затупил. У нас не дерево, а матрица.

Разверну чуть больше.

Рекурсия используется в качестве программного "цикла циклов", соответственно, эквивалентная схема:

  for( i1 in range(N)):
    for( i2 in range(N)):
      for( i3 in range(N)):
        ..
        for( iN in range(N)):

то есть таки да, это цикл на N^N итераций.

Проверки вертикалей (проверки горизонталей всегда true так как циклы работают каждый на своей выделенной горизонтали) превращают в факториал, так как мы заменяем вызов следующих циклов на константную проверку массива.

Проверок диагоналей у нас нет. Проверка соседей меняет выкидывание одной клетки в строке на выкидывание почти трёх:

 0 1 0 0   =>  0 1 0 0  => 0 1 0 0
 ? ? ? ?       ? x ? ?     x x x 0

Но это только в прямо последующей строке. Фактически, снижает с полного факториала до факториала N-2 что не влияет.

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

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

... что только подтверждает, что решение "в лоб" обычно далеко от эффективности;
... что не меняет того факта, что решатель справляется за практически невидимое для глаза время, так как решение точно существует всегда; задача предполагает решение человеком; и максимальный размер я пока за ~150 дней видел только 15*15.

Литкод изи — это просто

datacompboy 30 окт 2024 в 08:28

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

Российская Java теперь свободно доступна для скачивания

datacompboy 29 окт 2024 в 12:27

25 лет суммарно. 300 интернов с опытом по месяцу

+24

Самая красивая ошибка, которую я нашёл с помощью PVS-Studio в 2024 году

datacompboy 29 окт 2024 в 12:00

удивительно, как странно выглядит код в gcc если добавить -fPIC. clang'овый сразу уже позиционно-независим и не меняется от флага

Самая красивая ошибка, которую я нашёл с помощью PVS-Studio в 2024 году

datacompboy 28 окт 2024 в 12:30

Имеется ввиду любая реализация проверки на число элементов.

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

Самая красивая ошибка, которую я нашёл с помощью PVS-Studio в 2024 году

datacompboy 28 окт 2024 в 12:11

sizeof -- размер в байтах, countof -- размер в элементах. Существует как _countof и в вариациях имени типа array_size, ARRAY_SIZE, std::ranges::size и все прочие. Просто проверяем, на момент компиляции, что размер массива сопадает числу элементов ENUMа.

Самая красивая ошибка, которую я нашёл с помощью PVS-Studio в 2024 году

datacompboy 28 окт 2024 в 11:48

Средствами языка и без накладных расходов:

Когда в массиве элементы перечислены последовательно -- сравнивая countof() в compile-time, мой основной подход;
Мета-макросы, как @RR_Zz упоминул ниже;
unit-testing с перечислением всех вариантов (я считаю форменным издевательством для данного случая, впрочем).

Средствами языка с накладными расходами:

Используя enum class + функцию с case вместо массива;
Проверки assert()'ы или просто if()'s в функциях доступа для проверок или включая проверки на доступ вне массива

Средставми вне языка без накладных расходов в рантайме:

стандартные статические анализаторы;
генератор кода по внешнему источнику (в каком-то смысле вариация x-macro)
ручной валидатор кода заточенный под конкретный случай, например, автогенерация юнит теста.

Это навскидку

Самая красивая ошибка, которую я нашёл с помощью PVS-Studio в 2024 году

datacompboy 28 окт 2024 в 09:42

А это толком и не отследить

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

Лучший способ в данном конкретном случае (и всех аналогичных) -- использовать статический анализатор, который может поймать косвенно (как в статье) по использованию, или попытаться "догадаться" что массивы должны быть 1-в-1 с enum'ом.

Я удивлён, кстати ( @Andrey2008 ), что PVS-Studio не догадывается что это дескриптор для ENUMа и не проверяет на равенство элементов и порядка констант унутре. А ведь косяк в таких массивах часто получается из-за потерянной запятой.