Chat:Ru/2020-06-13

From CG community
Revision as of 11:23, 15 June 2021 by Chat Log (talk | contribs) (Created page with "<img src=/a/13581648321417> ilt: amurushkin это легко проверить <img src=/a/13581648321417> ilt: я контрольную функцию написал <im...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

ilt: amurushkin это легко проверить

ilt: я контрольную функцию написал

ilt: она перед таким таймаутом должна вывести сообщение

ilt: переписал, прикол в том что даже локально теперь стали сыпаться таймауты

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

BorisZ: я не уверен правда что в джаве можно его прям запустить насильно, но какие-то средства должны быть

ilt: нельзя его принудительно запустить

ilt: можно попросить "запусти пожалуйста"

ilt: уже проверил это тупиковый вариант

BorisZ: смутно помню давно читал статью что можно свой сборщик прикручивать вместо стандартного

BorisZ: вроде на хабре была статья, но это давно и не точно

BorisZ: ну и не факт что тут получится

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

BorisZ: и там получалось время выполнения предсказуемое

ilt: я пошел путем как amurushkin и YurkovAS посоветовали

ilt: сейчас еще прикручу локальной прогон реплея из json файла

ilt: и буду дебажить

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

ilt: я также проверяю

vrabosh: какой размер текста можно в редактор загружать?

tomatoes: 100kb

vrabosh: http://chat.codingame.com/pastebin/abc091f4-c80e-47a1-9ba4-4e6a8a84666c

vrabosh: смотрите прикол... допустим ствлю 20 время отккика 20-50 может быть

vrabosh: ставлю range(50) ну или другое чуть больше число, и отклик может быть за 1500

vrabosh: как так?

vrabosh: вот сейчас поставил 40, отклик 61, поставил 45, отклик уже 2300

vrabosh: хотя таймаут не дал

amurushkin: сначала надо инпуты считать

vrabosh: так это я вверху делаю. просто скорость хотел проверить как цикл гоняется

tomatoes: если иногда скачет, то наверное просто еще чтото жрет процессор

vrabosh: я так посмотрел, теоретически если некоторые данные загнать в массив, то можно до 200к цикл прогнать на поверки..

vrabosh: в минимаксе по 100к на каждого игрока, это норм?

tomatoes: ничего не понял

Uljahn: vrabosh: убери round и int

BorisZ: vrabosh а что ты пытаешься измерить то в своем примере?

BorisZ: память то выделяется в первой строке, которая не меряется у тебя никак получается

BorisZ: там может 1мс пройти а может 100 если сборщик запустится

BorisZ: внутри цикла ты как раз ничего не выделяешь

Uljahn: for j in range(50):

   a = 19999 if any(i for i in gfull) else 29999

Uljahn: так разброс поменьше при замерах

Uljahn: чё-то фигню написал, надо же ещё проверку одну добавить, и кофе выпить

Uljahn: или заменить всё одной проверкой последнего элемента :confused:

Uljahn: а то мы тут предсказатель ветвлений замеряем

BorisZ: вряд ли в питоне как-то задействуется предсказатель этот

BorisZ: хотя фиг знает

BorisZ: транслятор же

Uljahn: короче, да, пример ни о чём

BorisZ: гиблое это дело - крестики на питоне

BorisZ: демотивирующее

BorisZ: бросай, Uljahn

BorisZ: завезут JIT - оно и так взлетит

BorisZ: пока не завезли, все впустую

BorisZ: может не взлетит конечно, но будет смысл побороться

BorisZ: сборщик мусора никуда не денется

BorisZ: будет борьба с таймаутами как в джаве

Uljahn: import gc; gc.disable()

Uljahn: частично отключает сборку

Uljahn: ну и если в нумпи всё делать, то и сборки не будет

Uljahn: нашёл всего один таймаут у себя, и то - когда противник даёт фримув :relieved:

Uljahn: можно начать с малого - топ-100 в голде, там ни одного питона

BorisZ: смотря как быстро дерево будет расти

BorisZ: если как у топов, то придется переиспользовать память, не хватит

BorisZ: у меня с 20к ролаутов хватает вроде

Uljahn: 20M нод не хватит?

Uljahn: ну, тогда придётся рут в начало смещать

Uljahn: даже 23М получается выделить, это при том, что ноды можно немного ужать и отключить выравнивание

tomatoes: у меня 4м хватает если в 95мс укладываться. и это при том что родитель и дети могут далеко друг от друга лежать

tomatoes: и 20м за лимит памяти вылезет наверное

tomatoes: в 38 байт хз как ужать :rolling_eyes:

Uljahn: по 4 байта на скор и визиты, один-два байта на индекс хода, 4 байта - индекс первого чайлда, один байт - количество чайлдов, итого 14-15, что я не учёл? :confused:

Uljahn: парентов не храним, отдельным списком при селекшне трекаем для бэкпропа

gybson_samara: 4 байта это 32 бита же, огромное число

vrabosh: как питон без руб прав может положить систему? под линуксом?

vrabosh: причем такоеже и в винде было...

tomatoes: игру ходить при выборке?

Uljahn: а чё было в винде? синий экран?

vrabosh: просто зависает.. и даже клава не работает

Uljahn: точно питон виноват? температуру проца помониторь

vrabosh: я создал массив на 100мбайт, и случайно его запустил вот так aa(fun()) и звисло

vrabosh: а понял, может быть. нагрелся от этого

735487: я тут как то на плюсах память выделял :) 16 гиг быстро кончилось ))

tutubalin: amurushkin а ты логарифм по таблице считаешь?

735487: логарифм кеширую если ты про это

tutubalin: я тут подумал: натуральный логарифм можно заменить на двоичный

tutubalin: а двоичный (не особо точно) можно считать гораздо быстрее

tutubalin: Инструкция LZCNT - Leading zero count.

tutubalin: (32 - LZCNT) примерно равно двоичному логарифму

tutubalin: точнее (31 - LZCNT)

YurkovAS: tutubalin или воспользоваться быстрыми функциями от смитса, он как-то выкладывать в общем чате. там логарифм, корень, обратный корень и рандом без остатка от деления :smiley:

tutubalin: ну рандом без остатка от деления - это вообще правило хорошего тона. так всегда надо поступать

ilt: YurkovAS а у тебя нет кэширования?

YurkovAS: все кешируется

tutubalin: очень многие популярные ГСЧ страдают тем, что младшие биты у них не такие уж и рандомные. если делать через остаток от деления, то могут быть нехорошие корреляции, например, когда делаешь RND%4 или RND%8

ilt: я в этой формуле имею ввиду

YurkovAS: да, в формуле все закешено

YurkovAS: смитс "в обсуждении топов" сказал, что его бот без книги будет на 2-м месте. круто

tutubalin: а как смитс корень быстрее FPU считает?

735487: самое интересное что у него он и с книгой на 2 месте ))

vrabosh: x,g = '2;12S;6R;18S'.split(';',1) g = (j for j in .join([i[-1]*int(i[:-1]) for i in g.split(';')]))


vrabosh: можно как нить это покрасивей написаь, но также в 2 строчки)

vrabosh: надо чтоб был генератор g = ('S','S'..12раз...'R'.. итд)

735487: s 12 раз это 'S'*12

735487: зачем так сложно то? куча разделить - соединить

BorisZ: покрасивей - шрифт поменять на готический )

BorisZ: либо красиво либо в две строчки

BorisZ: x, g = "2;12S;6R;18S".split(";", 1) result_str = "".join(p[-1] * int(p[:-1]) for p in g.split(";"))

BorisZ: вобще весь этот годгольф сомнительный навык какой-то, для людей же пишутся программы, а не для компов

BorisZ: а если человек для которого ты это написал окажется впыльчивый боксер

BorisZ: и с плохим зрением, у которого от скобочек в глазах рябит

tutubalin: vrabosh "S"*12 + "R"*6+"S"*18

vrabosh: tutubalin , посмотри скрипт..

vrabosh: там первое делает как раз [s*12],[r*6] потом это в одномерный массив.

tutubalin: а, ну тогда хз как это красивее сделать. и так красиво вроде

BorisZ: у меня красивее жеж - нет вложенных for

BorisZ: а строка от генератора ничем не отличается с точки зрения использования, еще и удобнее

Uljahn: x, g - за такие имена по рукам надо :)

BorisZ: это видимо из клеша какого-то задачка

BorisZ: тогда в одну строчку можно

tutubalin: может x - это координата, а g - ускорение свободного падения

ilt: если я ставлю HEAP_SIZE = 2 000 000, то секунду только создаю эти все ноды

BorisZ: если нода состоит только из интов, то можно выделять массив из интов

BorisZ: в конструктор ноды передавать индекс следующей свободной ячейки

ilt: нет не только из интов

ilt: пока хватает миллиона

ilt: а если у меня что-то написано типа Node node = nodesHeap[rootIndex]

ilt: от этого тоже надо отказаться?

ilt: эта нода условные три раза обрабатывается

BorisZ: я просто вслух думаю)

vrabosh: у меня переменые длинее 5 символов не бывают)

Uljahn: ilt: а клонировать не пробовал?

BorisZ: вместо класса Node сделать класс, у которого под капотом будет большой массив интов

BorisZ: он будет менеджером памяти как бы

BorisZ: тогда нода будет индекс в этом массиве

BorisZ: а у менеджера будут методы типа getVisits(int node) и так далее

ilt: пробовал тоже время

Uljahn: при создании объектов оверхед конечно выше, чем если просто под массив интов память выделять

Uljahn: а нужны там объекты? может, 2D массивом можно обойтись?

BorisZ: да, странно массив примитивов должен моментально выделяться вроде

gybson_samara: Uljahn +1, поэтому сипипи и выигрывает

gybson_samara: я в пакманах столкнулся с необъяснимым увеличением времени выполнения в нампи с указанием типа, дефолтный риал в разы быстрее оказался

gybson_samara: риал, флоат, не суть =)

Uljahn: gybson_samara: даже в numpy быстро получается, 20 миллионов нод за полсекунды, правда ноды типа struct

Uljahn: а какой указывал?

gybson_samara: Uljahn in8

Uljahn: float16 не родной для numpy, он эмулируется)

Uljahn: int8 должен быстро работать

gybson_samara: ну реально, указал инт и сразу таймаут жесткий

gybson_samara: убрал и в голде

gybson_samara: ну т.е. в серебре, потом до голды допилил

gybson_samara: могу скинуть код, добавишь в создание массива тип и проверишь

Uljahn: давай

gybson_samara: http://chat.codingame.com/pastebin/4130d105-3aac-46c7-a023-0fe4a5ed3873

gybson_samara: не лезет

Uljahn: ой-ой

Uljahn: а только массив если? мне весь бот не нужен)

gybson_samara: self.cross = np.zeros((height,width))

       self.crossvisit = np.zeros((height,width), np.intc)
       self.simfield = np.zeros((height,width))
       self.blocked = np.zeros((height,width))

gybson_samara: щас всем полставлю intc, кстати

gybson_samara: сразу таймаут

gybson_samara: ааа, тут ошибко\

gybson_samara: гребанный гит

gybson_samara: табы похерил

Uljahn: int8 реально тормозит

gybson_samara: ну вот

Uljahn: примерно в 10 раз медленнее при инициализации массива нулей

gybson_samara: я о чем и говорил

gybson_samara: и как я это должен предвидеть?

Uljahn: так это zeros, а попробуй ones))

Uljahn: там всё наоборот

gybson_samara: Uljahn это надо весь код наоборот переписать

Uljahn: я про то, что zeros - это хитрый зверь

Uljahn: нужно сравнивать с np.empty, который только память выделяет

gybson_samara: такс

gybson_samara: а эмпти это не 0?

Uljahn: нет

Uljahn: ничего не обнуляет, просто резервирует область памяти

gybson_samara: логично, но мне надо арифметическую матрицу, без симулякров

Uljahn: ты её потом будешь заполнять же?

Uljahn: или тебе нужна именно матрица нулей?

gybson_samara: потом буду заполнять значениями не ноль

gybson_samara: разумеется мне не нужна мтарица со случайными значениями

BorisZ: вы проверьте время, скорее всего zeros будет совсем ненамного больше чем empty

gybson_samara: Uljahn нампи без указания типа работает быстрее, факт. И это нельзя объяснить тем, что "флоат" ноль быстрее "инт" ноль и точка

BorisZ: там разница в одном вызове memset который должен быть очень быстрый

gybson_samara: Нампи с указанием типа тормозит

Uljahn: ну, потому что нампи оптимизирован под значения типа по умолчанию

Uljahn: кстати, посмотрел, empty нули выделяет

gybson_samara: Uljahn я не против, просто надо учесть

Uljahn: но это вроде не гарантируется

gybson_samara: Uljahn получается питон несколько унижают

gybson_samara: намеренно или нет

Uljahn: в смысле?

ilt: хорошо пошло

Uljahn: угу, что пофиксил?

ilt: я все переписал можно сказать

ilt: на 100 игр 2 таймаута

ilt: во второй части было похуже с таймаутами

ilt: но терпимо

ilt: amurushkin ты здесь?

735487: да

ilt: скажи, а если у меня что-то написано типа Node node = nodesHeap[rootIndex]

ilt: от этого тоже нужно отказаться?

735487: если копирование происходит то да желательно

ilt: node там несколько раз дальше используется

ilt: каждый раз писать nodesHeap[rootIndex]?

YurkovAS: там указатель, 99%, так что без разницы.

YurkovAS: ты же заполняешь в каждую ячейку nodes[0] = new Node(); nodes[1] = new Nodes();

ilt: да

YurkovAS: значит в массиве лежат указатели (адреса) Node node = nodes[1]; не копирует, а node это указатель и содержит адрес. но, это 99%, может ошибаюсь.

YurkovAS: amurushkin правильно?

YurkovAS: http://chat.codingame.com/pastebin/f34b064f-01c6-4158-af9b-38974343d160

ilt: да изменится

YurkovAS: а если бы копировалось, то изменялась бы только копия. в яве все классы указатели.

ilt: часть таймаутов точно имеет баговую причину

ilt: буду искать

MAKMED1337: я могу как-то посмотреть условие что будут в следующих лигах ?

Uljahn: в некоторых мульти полные правила на гитхабе вылодены, а так - нет, но мы можем подсказать

Uljahn: *выложены

ilt: скорость создания объектов это глобальный фейл

ilt: а в плюсах с какой скоростью они создаются?

YurkovAS: не замерял, но очень быстро и на 1-м ходу есть еще 900мс

YurkovAS: хотя, точно не скажу, это у меня тайминг такой.

ilt: а можешь тест сделать?

ilt: там 5 строк

YurkovAS: http://chat.codingame.com/pastebin/ba0daa03-036c-462b-bb99-a088e61842c0

ilt: у меня 400 мс 1 000 000 объектов создается

ilt: печалька

ilt: можно что-то делать до первого ввода и это не входит в время первого хода???

735487: ilt: скорость создания объектов это глобальный фейл, все зависит от конструктора. и на плюсах ловил я таймауты с конструктором

YurkovAS: в общем работает и так Node *nodes = new Node[15mln]; занимает 0мс - без констрактора занимает 2300мс - с конструктором типа: score = 0;

ilt: их ты потом все равно создаешь?

ilt: Смысл иметь массив без объектов

YurkovAS: память выделена, просто там мусор. поэтому потом уже, когда заполняешь данными, то всем полям указываешь значения

ilt: строка nodesHeap = new Node[HEAP_SIZE]; тоже быстро выполняется

YurkovAS: в твоем случае это массив указателей. т.е каждая ячейка занимает адрес (8байт)

ilt: перенос создания объектов во второй и следующие ходы сильно уменьшает количество роллаутов

YurkovAS: до первого импута у меня работает 2-3 сек. можно на это завязаться. потом читаешь импут. и еще 800мс дальше создаешь ноды + 100мс на мктс

ilt: вообще я затупил у меня отсчет начинается после первого ввода тоже

ilt: и я могу спокойно 2 секунды создавать 5м объектов

Uljahn: а на питоне не выделяют дополнительное время, потому что нет компиляции :(

Uljahn: хм, если от самого запуска замерять, то тоже 2.5 секунды получается :upside_down:

Uljahn: вот значит как надо было, теперь у меня тоже под 30кк нод выделяется за 3 секунды и 600МБ

Uljahn: с выравниванием накосячил - 480МБ, можно ещё значит

Uljahn: не понимаю, где косяк - выделяется 100М нод и память не кончается :joy:

Uljahn: нумпай в дебаг пишет - число нод: 1090000000, занято памяти: 17440000000 надо спать идти, Automaton2000

Automaton2000: если у меня массив предварительно созданных нод то по логике ведь объекты в нем живут пока идет игра