Dmitry
1.3 сишная версия. но тут нельзя сравнивать, код всё-таки что-то делает
Dmitry
парсит, хранит, обходит
Dmitry
это что-то да стоит
Кабачок
ада ж померла, или, вернее, и не жила никогда
наверно поэтому писать на ней приятней чем на си
Dmitry
ну код на вид особого отвращения не вызывает, я на розетте видел
Alexander
@voidlizard ты последнюю мою не мерял?
Dmitry
а, да, мерял
Dmitry
1.00s
Alexander
\o/
Dmitry
с другой стороны, когда я ревьювил специальную олимпиаду от фпрога, ада мне вообще тогда не зашла
Dmitry
но там писал чувак, который идентификаторы называл транслитом
Alexander
на си я уже не знаю чего и сделать
Dmitry
ЗАБИТЬ НА НЕГО УЖЕ
Alexander
можно пытаться читать через vsplice какой и писать, а внутри сделать свою структуры где выровняны слова
Alexander
но это уже изврат
Alexander
раст круто, человеческий интерфейс и почти не сливает
Dmitry
но жесть какой вербозный
Alexander
но чхс, что если заниматься совсем low level извратом, то на си проще будет
Dmitry
даже плюсам уступает
Alexander
растеры уже кеш миссы считают
Alexander
похоже если у языка нету тулинга нормального это может быть даже бонусом
Alexander
у нас вроде никто даже core не смотрел?
Aragaer
я смотрел callgrind
Aragaer
на самом деле, реализация "правильной буферизации вывода" на С оказалась значительно более простой, чем я изначально думал
Dmitry
интересно, я привыкну уже к синтаксису раста или нет
Alexander
у кого есть vtune можете продолжать бой
Aragaer
беру идущие подряд N+1 блок достаточно большого размера, одним поинтером в них пишу, когда влетел в последний блок, то дамплю все N, а хвост, который попал в последний, сдвигаю в первый. В конце программы дамплю все, что осталось.
Dmitry
вот нахрен там модули такие '::' ?
Dmitry
вот зачем там замыкания такие
|wtf|
Dmitry
зачем там все эти скобки и запятые и точки, аааа
Alexander
модули т.к. c++?
Alexander
меня кстати :: в этом отношении очень бесят
Кабачок
вот нахрен там модули такие '::' ?
чтобы плюсовики чувствовали себя как дома и не боялись подходить близко, гыгыгы
Dmitry
да уже в плюсах это был фейл
A64m
а что у нас есть как раст, только синтаксис получше?
сейчас авторы языков хорошие синтаксисы не жалуют, во всех этих растах скалах и свифтах как только не извращаются, чтоб только на фя не походить
Dmitry
ну т.е плюсы это вообще фейл, читаешь самую первую книжку Страуса, и делаешь фейспалм по очкам
Dmitry
дед горазд отмазки лепить, конечно
Dmitry
но нафиг это было в расте копировать - это вот вопрос
A64m
А ВО ВСЕМ ВИНОВАТ СЁРЕН КЬЕРКЬЕГОР
Dmitry
@aragaer свифт не особо был мерзкий на первый взгляд, но на второй я его не смтрел
Denis
ast2 // CC @catamorphism мы тебе задачку для ats hello world нашли
Где там условия задачки? Если руки дойдут снова, то можно попробовать.
Denis
Свифт ничего еще. Компилятор так вообще хороший.
A64m
Я другой отмазки такого уровня больше ни у кого ни читал, даже у Леруа
Aragaer
мне свифт не нужен, потому что я к йосам никаким боком не соприкасаюсь. На обжектив си пришлось один раз в жизни писать
Denis
Но вообще на ats писать это фактически на С
Denis
Там ансейф С юзать, поэтому все извраты и оптимизации тоже считаются.
A64m
О том, что Страуструп написал в предисловии "Дизайна и эволюции", что C++ такой потому, что СЁРЕН КЬЕРКЬЕГОР
Dmitry
видимо, еще и Сартр
Dmitry
с Кафкой
Кабачок
таки без второго мягкого знака
Anonymous
А вообще –– Бердяев и Шестов. 🙂 Но это другой чат
Dmitry
я не помню, что там Кьеркегор, но уверен, что это опять отмазки деда и на самом деле Сартр
A64m
существует 256 вариантов написания на русском языке
Dmitry
вот в окамле точно Сартр
Dmitry
прям первый же взгляд на синтаксис и все понятно
Ilya
можно оценку снизу сделать
Сделал. Тут вроде несложно. Задача явно memory-bound. Значит число операций считать не будем, IO тоже считать не будем (уже посчитали с dd)
Парсинг входных данных по времени ничтожен, так как его время линейно зависит от входа, а выход у нас квадратичный.
Что остаётся? Лепка строк.
Для этого мы N^2 раз будем читать suf, и N^2 раз писать (pref + 1 + suf + 1). Итого N^2 * (2suff + pref + 2) оперативной памяти, suff = pref = 5 (в байтах), итого 17N^2 байтов.
Пропускную способность взял 15 гигабайт/с, не знаю сколько сейчас на современных компах на DDR4, но должно быть около того. Для оценки сойдёт.
На длине входа N = 1e4 (что у нас и есть) имеем
17e8 [байт] / 15e8 [байт/c], что примерно равно 1.2 сек.
Ну в общем вывод такой, что вы уже около теоретического значения маячите, что довольно хорошо!
Dmitry
с парсингом может выйти такая фигня, что его время будет расти от размера входа, а тут у нас, конечно, размер входа маленький, но IRL он может расти, в т.ч. бесконечно (генератор)
Dmitry
и на его маленькие размеры закладываться нельзя
Кабачок
если размер входа N будет расти бесконечно, то мы сможем вывести не более N строчек до out of memory
Dmitry
ну, хорошо, размер может вырастать в разы
Кабачок
первый префикс и N суффиксов
Dmitry
сейчас потребление памяти копеечное
Dmitry
т.е есть куда расти до полного краха
Alexander
да, в памяти мы обязаны хранить суффиксы
Alexander
т.к. нету файлов
Alexander
ну или делать самим временный файл
Alexander
вот сюда предложение с mmap норм
Dmitry
sqlite или еще какой-нить kv
Dmitry
чо уж
Dmitry
больше энтерпрайза
Кабачок
а необработанные префиксы разве не нужно хранить?
Dmitry
там каждая строк а- префикс суффикс
Dmitry
таким образом, для всех префиксов нам нужны все суффиксы по условию
Ilya
А блин, делим на 15e9 а не на 15e8, соответственно ответ в 10 раз меньше:) 0.12 сек
Получается, что стадия собственно процессинга должна занимать 0.1-0.2 сек
Ilya
даже с копированием строк