Ответы пользователя по тегу Оценка производительности
  • Какая временная сложность у этого алгоритма?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Линейная. O(N+M). Ибо там цикл по i от 0 до startMedianIndex и вся остальная мишура на i вообще никак не влияет. Больше циклов в программе нет. Не понимаю, что тут может быть непонятного.
    Ответ написан
    Комментировать
  • Быстро ли мое решение?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Самый быстрый вариант, конечно, будет изменить вашу программу так, чтобы она могла работать с несколькими кусками, без всяких предварительных подготовок.

    Ваш текущий вариант вносит дополнительное разименовывание указателя на каждое число.
    Вариант с memcpy внесет дополнительное копирование, что помедленнее разыменовывания указателя по идее.

    Но на практике все зависит от кучи факторов. Много ли у вас чисел, попадают ли они в кеш процессора, как далеко лежат две части буффера, как долго идет обработка каждого числа. Проверить это в итоге можно только практикой, но, скорее всего, ваше текущее решение будет быстрее memcpy, потому что единственное приемущество memcopy будет в том, что данные лежат в памяти подряд, что очень дружественно к кешу. Но вашем текущем решении и сами указатели и то, куда они указывают, итак лежат в памяти подряд (кроме одного индекса, где меняются массивы).
    Ответ написан
    Комментировать
  • Какая сложность у такого цикла for?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Так.
    Ответ написан
    Комментировать
  • Почему скорость битовых операций отличается в 1000 раз?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Скорее всего, обращение к массиву тормозит. Там, видимо, еще и проверки на попадание в границы массива происходят.

    Если вы место обращения к массиву будете делать currentByte & (1 << (7-j)), то должно работать почти также быстро.

    P.s. и вообще у вас какой-то странный выбор порядка битов. Обычно сдвигают вправо, к младшему биту. Тогда вместо маски будет тупо 0x1.
    Ответ написан
  • Самая быстрая реализация алгоритма Дейкстры на javascript?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Попробуйте переписать с массивами фиксированной длины. Во всех реализациях по вашим ссылкам вершины нумеруются строками и куча массивов типа distance и visited на самом деле являются словарями, или как это в js называется. Это работает сильно медленнее тупого массива, пронумерованного от 0 до n.

    Вам понадобится один словарь для перенумерации вершин в числа. Потом преобразуйте гарф на массив массивов, вместо этого сложного объекта.

    И уже на нем гоняйте дейкстру. Должно по карйней мере в пару раз ускорится. А то и во все 10.
    Ответ написан