- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
onst addAdjacencies = (
nodes,
) => (
nodes
.map(({
colorId,
id,
x,
y,
}) => ({
color: colors[colorId],
eastId: (
getNodeAtLocation({
nodes,
x: x + 1,
y,
})
),
id,
northId: (
getNodeAtLocation({
nodes,
x,
y: y - 1,
})
),
southId: (
getNodeAtLocation({
nodes,
x,
y: y + 1,
})
),
westId: (
getNodeAtLocation({
nodes,
x: x - 1,
y,
})
),
}))
.map(({
color,
id,
eastId,
northId,
southId,
westId,
}) => ({
adjacentIds: (
[
eastId,
northId,
southId,
westId,
]
.filter((
adjacentId,
) => (
adjacentId !== undefined
))
),
color,
id,
}))
)
https://medium.com/free-code-camp/bet-you-cant-solve-this-google-interview-question-4a6e5a4dc8ee
джаваскриптер натужно пытается решить простейшую задачу "гугл уровня" с обходом, для увеличения кринжа прилагается поехавший кодстайл и решение на RxJS
Follow us!
В кресты тоже завезли RxCpp, так что можно почти дословно переписать...
Но автор похоже в курсе что сишный for лучше и быстрее:
И тут мы приходим к тому, о чём я уже говорил......
Он на полном серьёзе начал замерять пирформанс своей скриптухи.
А в конце подытожил, мол вот ещё пару статей как сделать функцианаьную скриптуху быстрее не такой тормознутой:
>If you wanna read more on JavaScript performance, check out my other articles:
> Speed Up JavaScript Array Processing
> Using Transducers to Speed Up JavaScript Arrays
>>JavaScript
>>performance
Transducers aren’t all peaches and cream. When you have a very small number of items, transducers are a lot slower than either solution. It’s beyond the scope of this article to find the trade-off point for most machines, but let’s redo those performance tests with an array of 3 items.
Скриптух, боролся, боролся, выдумывал питух-структуры, трансдусеры.
Но Царя не читал и не знает, что лучшая структура данных — массив. А лучший цикл — for.
¿¿¿нахуя мне оптимизировать алгоритм для small number of items???
Не поможет. Он же в статье прямо пишет, что его питушарский способ даже в concurrent версиях сливает тупой однопоточной итерации.
Моча в рожи сектантов.
В самом конце статьи анскилябра дала ссылку, на эпопею как она борлоась с царским for.
https://itnext.io/speed-up-javascript-array-processing-8d601c57bb0d
Let’s do a simple performance test with 10 million items using Array.prototype.map:
And then let’s compare that to the native for loop:
I ran each test 7 times and pulled the averages. On my overclocked Intel Core i7–4770K, our array method averaged 1281ms while our for loop averaged 323ms. Incredible right? What a performance improvement! But for loops are so 10 years ago. They’re difficult to write and harder to reason about when doing complex transformations.
Да. Я ещё 6 лет назад заметил:
https://govnokod.ru/16298#comment239238
В начале 00-х когда оно было в зените популярности мне в принципе было очевидно что панацеей оно не является.
Сейчас же лихорадка прошла, появляются языки без ооп и стало модно пинать ооп.
Однако лихорадка сменилась другим сумасшествием - чисто функциональные языки. И это пройдет, останутся только идеи, самые удачные из которых запилят в промышленные императивные язычки (как, например, тоже ооп когда еще было модно, добавили в пыху). Собственно мы видим это уже сейчас.
Ебать дебил.
кто бы мог подумать. Интересно, почему вызовы функций такие медленные?
https://govnokod.ru/17460#comment262105
https://govnokod.ru/17470#comment261947
https://govnokod.ru/16008#comment232669
https://govnokod.ru/13688#comment193518
cyka blyat
https://ideone.com/e7dSAC
Какой пиздец )))
Хахаха. Минут 40 втыкал в код, искал где же «говно».
Ну можно столько MATRIX_AT и не делать.
И сразу early-exit вписать. Нет смысла продолжать, если уже посещали.
Да, точно.
> И сразу early-exit вписать. Нет смысла продолжать, если уже посещали.
У меня в visitNode() идут только непосещённые ноды, там в главном цикле проверка.
На «C» основное говно в неоптимизированности и самописном векторе, ИМХО. Для теста заменил в коде вектора «calloc» на «malloc», увеличил начальную ёмкость до 100, в visitNode сделал vec статическим (с заменой vector_delete на vector_clear) — получил x3 прирост, с 6 секунд до 2 для матрицы 10000*10000. Думаю, если в профилировщике посидеть — можно ещё пару-тройку раз прироста выжать.
Ну да.
Я имел ввиду перенести её в цикл, а лишний MATRIX_AT выкинуть.
Или просто передавать curr аргументом.
Ну и тут
Edit: Я пытался замерять пирфоманс, но код настолько быстрый, даже на 5000x5000, что пирфоманс колеблется в пределах погрешности таймера.
Вот же оно: LCGRand() % COLOR_NUM
> vec_delete
> EXIT_FAILURE
Ну ты понел )
>putchar(MATRIX_AT(matrix, i, j).color + '0');
>putchar('\n');
Только настоящий олд-сишник держит в уме что printf тормозной.
И на тысячах итераций putchar чуток быстрее.
* притом что шланг вроде оптимизирует односимвольные printfы в putchar
И gcc тоже
А вот MSVC — глупая лалка.
>perror("OOM");
>size_t вместо inta
Попытался прикинуться олимпиадником, но руки-то помнят!
Это как маленькая девочка заходит и сообщает: «приффетик ))) я люблю кукол и розофых пони».
А потом пишет обфусцированную программу на Си, которая помимо прочего возвращает ненулевой код ответа в случае ошибочного ввода.
https://govnokod.ru/21037#comment349170
Для удобного чтения треда, введите в консоль регистрационный ключ:
> printf("%c", love [bormand % HACTEHbKA]);
Всё-таки девочки в сишке не очень сильны. gost бы кошерно putchar поставил.
Да и какая разница? Лулзы же.
Бормондяша так мощно кодил на крестах, что пробудил тебя ото сна?
https://pastebin.com/yHXjpAg2
Просто пиздец, насколько же чувак из статьи — анскилльный питух.
> 229.481ms Recursive
> 391.582ms Redux-Observable Concurrent
>js в функцианальном дрисня-стиле, чуть ли не в ДЕСЯТОК раз сливает jsу же в нормальном императивном стиле.
Хм. Перехвалил я скриптуха, откровенно перехвалил. 10x slowdown нужно ещё заслужить.
https://ideone.com/UEJlLeЗ.Ы. Не особо оптимально, но если на пулы пересадить, то будет за O(COLS) по памяти.
Крестовая версия выдаёт 12, наивная — 14, ручной подсчёт присуждает победу наивной.
10111121200121100111102
22112011211021011121121
02101000120120111022110
Именно для этого, кстати, я и запилил самописный рандом.
9 у крестовой, 10 у наивной.
Не учитывается самый левый столбец блока, у которого есть только один элемент нужного цвета, находящийся в самой нижней строке?
По сравнению с немного оптимизированной версией на «C» (https://ideone.com/bd4g1I) производительность снижена примерно в 1.5—2.5 раза: https://ideone.com/mhPokq (на моём компе — ~6500 мс против ~2400).
Подозреваю, что в основном это из-за «шаред_поинтеров».
Кстати, оптимизированный код на «C++» оказался гораздо больше похож на «C», чем код на «C». Какой багор )))
У меня сначала была мысль сделать что-то похожее на борманда.
Но я стремился к царскому решению: побольше массивов, поменьше структур.
Потому я взял за основу твой одномерный массив и заполняшку.
Зато у меня даже входной матрицы нет, можно генерить её на ходу или стримить с диска.
На больших и хитрых матрицах ломается. Плюс второй цикл непонятно как убрать.
Я не смотрел в крестоверсию.
Пока свою не сделал. У меня вышло очень похоже.
Но блин, никак не выходит без третьего вложенного цикла, который топы апдейтит:
>который должен разъебать всё
Слить в хламину же.
Да взять исходный 0xDEADBEAF 100х100.
Недосчитывает.
Я merge заинлайнил, но всё-равно надо вверх идти и топы обновлять.
http://govnokod.ru/26422#comment525770
Фаззилка на «C++»: https://ideone.com/4JphF7;
Фаззилка на «JavaScript»: https://pastebin.com/QD8nBSA2.
З.Ы. Код внизу треда.
поедешь
> Эмпирически, при увеличении размеров матрицы оно растёт как что-то логарифмоподобное.
Думаю вопрос очень сложный. Формулы будут зависеть от числа цветов.
Не факт что при их увеличении, размер больших областей будет расти пропорицонально размерам карты. Вспомним проблему 4х цветов.
5000х5000 Max block size: 106
10kх10k Max block size: 93
А вот МО одноцветной области максимального размера на бесконечной случайной карте явно будет бесконечным.
Возьмём простенькую модельку:
https://ideone.com/dGYGm7
Джва цвета:
Три:
Четыре:
Пять:
Эта ебола очень похожа на какой-то логарифм.
Но всё-равно херня. Никак не выходит без третьего вложенного цикла, который upы обновляет.
https://ideone.com/k37NrXЗ.Ы. Ну теперь то мне позвонят из гугла? UwU
Третий вложенный цикл, от которого я никак не мог избавиться бесил, вышел наружу.
PS
>next = prev = this;
А это зачем? Для чистки памяти?
> max_size = std::max(max_size, size);
Ага. Вкурил, теперь. Мощно.
У меня на ломалось на областях в форме буквы Ш, из-за того что данные в верхних объектах не обновлялись. Линкед-лист очевидно решает эту проблему.
Вот пара тестовых матриц.
000111101
001100101
011000001
010100111
010100100
011111100
000111101
001100110
011000011
010100111
010100100
011111100
На любой картинке с кольцом LinkTo начинает линковать список сам с собой. Но так вышло, что LinkTo ничего не делает если ноды в правильном порядке, а порядок всегда сохраняется.
Ну вот, это теперь практически идиоматический код на «C». Именно поэтому…
Судя по тому, что после прошлогоднего обновления веб-интерфейса их почты он стал жрать одно ядро и отрисовываться с ~10-15 фпс (просто тупой список тем сообщений с парой иконок!) — нет, не возьмут.
К сожалению, я не осилил circular_list_algorithms из буста, чувствую себя мартышкой с очками ;(
А чего ещё ждать от доски объявлений-то?
govno jopa barebuh suka, pidor gopa ⓒ
https://ebanoe.it/2019/07/05/govno-jopa-google/