Обновить

Задачка с собеседования от Яндекса. Скептически отношусь к ценности таких задачек при собеседовании сеньоров в обычный энтерпрайз - они скорее хороши на районном этапе школьной олимпиады. Но может я не прав? Итак задачка - из 4х предложенных над этой я думал дольше других:

В массиве целых чисел нужно найти фрагмент с заданной суммой.

Например, дан массив a = [4, 3, -8, 4, -1, 12, -5, 2] и целевая сумма 5 - тогда ответом будет фрагмент начиная с 3 и заканчивая -5, то есть в синтаксисе Питона sum(a[1:7]) = 5

В чем тут сложность? Сложность во "временной сложности" - требуется чтобы на массиве из миллиона чисел вычисление не занимало минуты. Поэтому наивный вариант не годится:

target = 5
for i in range(len(a)):
    for j in range(i+1, len(a)+1):
        if sum(a[i:j]) == target:
            print(i, j)

Здесь два вложенных цикла - каждый в среднем совершает число итераций сравнимое с длиной массива. Но функция sum(...) внутри тоже бежит по массиву - итого время выполнения пропорционально длине массива в кубе O(N*N*N)

Одно из усовершенствований заключается в том чтобы построить второй массив, в котором хранить сумму от начала массива до i-го элемента. Это позволит считать sum(i, j) не пробегая массив. Улучшение - теперь время пропорционально квадрату.

Можно решить и за "линейное" время - т.е. пропорциональное размеру массива без всякой степени. Когда я сообразил, то сказал "да это же старая задачка на новый лад". Попробуйте - вдруг пригодится на собесе :)

Теги:
Всего голосов 4: ↑4 и ↓0+8
Комментарии14

Как мы запустили Qwen3.8–27B целиком на RTX 5060 8 GB и получили ~30 токенов/с

Наш проект называется ExVRAM Lab. Это открытая исследовательская лаборатория, в которой мы проверяем, насколько большие локальные LLM можно запускать на обычных видеокартах с ограниченным объёмом VRAM, если использовать ultra‑low‑bit quantization, полное размещение весов на GPU и существующие open‑source inference‑технологии.

ExVRAM расшифровывается как Exchange Compute for VRAM. Основная идея проекта — в ряде сценариев выгоднее потратить часть свободной вычислительной мощности GPU на работу с более компактным представлением весов, чем хранить часть модели в оперативной памяти и постоянно передавать данные через PCIe.

Когда мы начинали проект, исходный вопрос был достаточно простой: можно ли запустить dense‑модель примерно на 27 миллиардов параметров на видеокарте всего с 8 ГБ VRAM так, чтобы она не просто «запустилась», а работала полностью на GPU, поддерживала длинный контекст и обеспечивала нормальную интерактивную скорость генерации.

В качестве основной тестовой системы мы используем NVIDIA GeForce RTX 5060 8 GB на архитектуре Blackwell. Основная модель в текущих экспериментах — Qwen3.8–27B.

Сначала результат выглядел не слишком впечатляюще. Модель запускалась, но значительная часть весов оставалась в системной памяти. Около 5,7 GiB весов находилось на GPU, ещё примерно 2,5 GiB — на CPU. Скорость генерации составляла порядка 3,8–5,5 токена в секунду.

При этом сама видеокарта была загружена далеко не полностью.

Это стало одним из первых важных наблюдений проекта. Проблема заключалась не столько в нехватке вычислительной мощности RTX 5060, сколько в том, что часть decoder weights находилась в RAM. Во время autoregressive generation данные приходилось постоянно передавать между CPU и GPU через PCIe.

Как мы запустили Qwen3.8–27B целиком на RTX 5060 8 GB и получили ~30 токенов/с

Публикации