как только с \r разберусь

на 40% ускорил

вим в нижней части где-то пишет, что dos

cat -e | head FTW

в выходном должно быть \n

а это точно?

сразу видно кракозябры посторонние

cat -e | head FTW

спасибо. в референсном выводе (от которого хэш) mygfc5tg3e^M$ у меня: mygfc5tg3e$

это значит наоборот \r добавить?

это странно

а не, я перепутал местами

dmz@zen ~/tmp/bsfuck $ cat -e x1 | head mygfc5tg3e$ mygfckwam1$ mygfcebk5k$ mygfcfiyee$

да-да, это у меня лишние \r значит

господа, а есть ли какие-либо известные проблемы со space leaks в Text?

в частности, когда не собираются мусорщиком ByteString и?

либо в Trifecta

Когда делаются маленькие слайсы из больших кусков, они держат весь большой буфер

а можете глянуть тут например, есть ли навскидку очевидные проблемы https://github.com/idris-lang/Idris-dev/blob/master/src/Idris/IdeMode.hs

Так там обычные стринги, которые [Char]

В общем если кому интересно, что тут может дать локальность данных, вот измененный код для pypy #!/usr/bin/env pypy import sys w = [l.split(' ', 1) for l in sys.stdin] pref = [x[0] for x in w] suff = [x[1].rstrip() for x in w] chunk = int(sys.argv[1]) def arrange(pref, suff): if len(pref) > chunk: mid = len(pref)/2 arrange(pref[:mid], suff[:mid]) arrange(pref[:mid], suff[mid:]) arrange(pref[mid:], suff[:mid]) arrange(pref[mid:], suff[mid:]) else: for p in pref: print "\n".join([(p + s) for s in suff]) arrange(pref, suff) Вот такая вещь работает побыстрее оригинала на pypy, у меня примерно на 40%, если задать chunk = 1000 (аргумент программы).

Старался сделать локальность данных, но хз, что тут реально ускоряет

*md5 конечно же не совпадает, если chunk < len(input)

а нельзя как-то сделать, что бы совпадало?

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

FSM + разные блоки фиксированной длины для префиксов и суффиксов. но это ведь уже какое-то навязчивое состояние

а нельзя как-то сделать, что бы совпадало?

Сомневаюсь, но подумаю.

Секта микробенчмарка.

безумие продолжается https://gist.github.com/normalcoder/91839837070a3ac446c9a7dc71aac160

чо, полсекунды челлендж?

пока не дотягивает

тут карта смещений, про которую говорил @qnikst

0.958 уже взяли?

@kcahek хаскельно, dmz@zen ~/tmp/bsfuck $ time ./offset_map < ./49zGQ6Zt.txt > /dev/null real 0m1.646s user 0m1.644s sys 0m0.000s

а какой топовый результат сейчас?

1.008x приблизительно

тут кто-то собирался на окамле писать, как там успехи?

1.008x приблизительно

Это в секундах?

ага

@A64m_qb0 вспоминает окамл, поди

Я вот либы не помню, но я мягко говоря не великий окамлист

а чо-то я пропустил, это какой код 1.008?

ну или предпоследний

а, блин

в смысле, послдений код @qnikst

ада dmz@zen ~/tmp/bsfuck $ time ./special_olimpiade < ./49zGQ6Zt.txt > /dev/null real 1m24.028s user 0m55.284s sys 0m28.736s

у меня получилась в 15 раз медленнее первого пайпай

я сегфолт в Haskell коде починю попробую offset-ы зоделать в haskell

не хочу больше пилить си пока кто-нибудь процентов на 10-20 не обойдет

какие там резервы по оптимизации ещё остались? в сишке

1.008x приблизительно

на си?

выравнивание

@qnikst принято

более эффективное копирование

cache friendly ness

я в это вообще не умею

явное sse какие нибудь сплайсы

@greenest_pig это на чем?

в смысле, послдений код @qnikst

вот этот? https://paste.pound-python.org/show/ghuOtpbzd4KN0R7oc7At/

1.008?

наверное, да. попозже посмотрю точно скажу

да этот

явное sse какие нибудь сплайсы

в этой конкретной задаче непрерывые куски по 5 байт, sse кажется не поможет, даже dword за раз копировать смысла нет

столько энергии потратили, коллективно можно было бы за это время вручную файл рассортировать

а вот важный вопрос

вот этот? https://paste.pound-python.org/show/ghuOtpbzd4KN0R7oc7At/

мой на -O3 быстрее

запилите репу с трависом

💤

гарантируется, что все суффиксы и префиксы одинаковой длины?

между собой, в смысле

это я на си сел писать... сразу такие вопросы и полезли

короче, len(pref1) == ... == len(prefN) ?

короче, len(pref1) == ... == len(prefN) ?

нет

то есть может быть вход типа aa bb aaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbb

?

это плохо

Я смотрю олимпиада продолжается?

мой на -O3 быстрее

обновил свой, теперь мой на -O2 тоже быстрее gist.github.com/yellow-apple/69993c04f8d9afc0d72c56f27e55187f

Пришло время мне делать emerge mlton smlnj (и ждать полчаса). SML for the rescue!

я написал на окамле, это было не сложно

не хочу больше пилить си пока кто-нибудь процентов на 10-20 не обойдет

on my machine, так сказать: 1: https://paste.pound-python.org/show/ghuOtpbzd4KN0R7oc7At/ 2: https://gist.github.com/yellow-apple/69993c04f8d9afc0d72c56f27e55187f 3: https://gist.github.com/normalcoder/91839837070a3ac446c9a7dc71aac160 clang -O3 1.c -o 1 && time ./1 < 49zGQ6Zt.txt > /dev/null real 0m1.158s user 0m1.148s sys 0m0.007s clang -O3 2.c -o 2 && time ./2 < 49zGQ6Zt.txt > /dev/null real 0m1.250s user 0m1.238s sys 0m0.008s clang -O3 3.c -o 3 && time ./3 < 49zGQ6Zt.txt > /dev/null real 0m0.867s user 0m0.859s sys 0m0.005s

https://gist.github.com/yellow-apple/69993c04f8d9afc0d72c56f27e55187f int bufcap = 120000; char *buf = malloc(bufcap); int buflen; // тут нужен = 0