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: если у меня массив предварительно созданных нод то по логике ведь объекты в нем живут пока идет игра
