👍

конечно, на плис активно делают ассоциативную память для маршрутизаторов, коды коррекции ошибок, аудио-видео кодеки и всякие микшеры, разные tcp/ip вещи типа SDN, DPI, VoIP шлюзы и мн. др., но паттерн прослеживается. делать на плис сверхбыструю субд или веб-сервер скорее всего глупо. разве-что какую-то небольшую часть задачи ускорить

ну там в любом случае в этих всяких штуках софт кора есть какая никакая - т.е. чистой логикой без программного автомата эти задачи не решаются

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

в реальной задаче обязательно будет процессор с программой. обычно плис/асик обрабатывает большой поток входных данных, уменьшает его до того, что способен съесть процессор, и отдает ему для дальнейшей (менее математичной, более алгоритмичной) обработки

внутри самих плис/асик тоже будет процессор, пусть и специализированный

так проще и быстрей выходит

Алексей если прям достаточно просто вам ответить: ваша задача должна быть очень хорошо преобразуемой в ранг поточный операций с очень малым потреблением памяти, а лучше вообще без неё (т.к. в плис и асиках память внутренняя это прям дорого и её очень мало)

Можете объяснить решение задачи о нахождении треугольников за m√m? Не понимаю

Доказательство через разделение вершин на легкие и тяжелые

Сортировка и почему треугольников не больше m√m понятно. Почему удаляют ребра ведущие в тяжёлые вершины, если мы наоборот сортируем по степени и идём из меньшей в большую?
Последняя часть кода тоже понятна

Типа вот мы перебрали ребро 1-2.
1)
Если вершина 2 легкая, то для таких ребер мы сделаем суммарно m sqrt m работы, ОК.
2)
Если вершина 2 тяжелая, то вершина 1 - тоже тяжелая, но мы сделали M работы по перебору 3.
Оценим кол-во таких комбинаций 123, что вершины 1 и 2 тяжелые.
Давай сначала переберем ребро 23, их всего m штук. Для каждой вершины 2 есть не более чем sqrt(M) вершин 1. То есть таких комбинаций тоже O(M sqrt M)

А, туплю)

Ну мы отсортировали списки смежности. Теперь справа вершины с большой степенью. Мы их и удаляем, чтобы дальше перебер просматривал тройки вершин в порядке убывания степеней. Мне непонятно, в чем проблема?

Убывания? Как я понял из текста выше, по возрастанию.
"Отсортируем вершины по возрастанию степени, ориентируем v->u, v <= u"

По-моему, любой порядок их этих двух сойдет

Потому что реверс просто поменяет все ребра на противоположные, а это не влияет на кол-во путей длины 2

Наверное в контексте имелось ввиду сортировать по убыванию, а я пытаюсь понять что да как...
Просто смотрел разбор задачи с ИОИП 2016-2017, там было по возрастанию, наверное это и сбило с толку