Как оптимизировать код?

Question

[TheSnegok]

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

const sumNumbers = (maxNumber) => {
    console.time();
    let answer = 0, i = 2;
    next:for(i;i < maxNumber;i++) {
        for(let j = 2; j < i; j++) {
            if(i % j == 0) continue next;
        }
        answer = answer + i;
    }
    return console.log(answer);
    console.timeEnd();
}

sumNumbers(2000000);

Что делает этот код: тык

Comments

[longclaps]

никак

[Ярослав Иванов]

но мне кажется

Покрестились?

Answer 1

[Alexandroppolus]

function sumNumbers(maxNumber) {
    const buf = new Int8Array(maxNumber);
    let answer = maxNumber > 2 ? 2 : 0;
    for(let i = 3; i < maxNumber; i += 2) {
        if (buf[i] === 1) {
            continue;
        }
        answer += i;
        const i2 = i * 2;
        for(let j = i * i; j < maxNumber; j += i2) {
            buf[j] = 1;
        }
    }
    
    return answer;
}

Comments

[TheSnegok]

Можете пожалуйста описать или закомментировать алгоритм работы?

[Alexandroppolus]

TheSnegok, старое доброе решето Эратосфена, ссылка на него есть в комментах к вопросу. На старте в buf все нули, далее "вычеркиваем" (ставим 1) на тех индексах, которые суть непростые числа, остаются только простые, которые суммируем по ходу пьесы. С четными числами не работаем, для пущего ускорения.

[TheSnegok]

Alexandroppolus, Круто, спасибо

Answer 2

[profesor08]

Простые числа это не что-то магическое, они вполне себе известны. Можно просто взять нужный диапазон и работать с ним. Нет нужды каждый раз их генерировать.



P.S. Так как список чисел довольно большой, запихнул его как текст в HTML, чтоб парсер js не подох.

Comments

[WbICHA]

Хороший списочек, на мегабайт. Прекрасная оптимизация...

[Alexandroppolus]

Справедливости ради, в моей функции почти 2 мб вспомогательной памяти. Хотя можно, конечно, ужаться в 16 раз (реально там используется только 1 бит из каждых 16, просто не стал заморачиваться)

[profesor08]

WbICHA, Alexandroppolus, тут придется чем-то пожертвовать, либо памятью ради скорости, либо скоростью ради памяти. Для сравнения, только поиск простых чисел до двух миллионов занимает 7м 46сек, а если работать с готовым набором, то время сокращается до 7 миллисекунд. Разница в 66676 раз. А если надо сделать несколько вызовов функции, то ничего не остается кроме как работать с готовым набором данных.

А если записать данные в файл, и считывать его подходящими кусками, то можно сильно оптимизировать все это дело по памяти, но тогда упрется в скорость IO операций.

[WbICHA]

profesor08, какие ещё 7 минут 46 секунд? Решение Alexandroppolus на 2 миллиона тратит 15+-мс, да даже на 10 миллионов всего 90+-мс.
При этом ничего не мешает кешировать список простых чисел.
Так что на 2 миллиона разница всего в 2 раза, а обьём передаваемых данных отличается на порядки.

[WbICHA]

Alexandroppolus, справедливости ради, 2 мб памяти ─ это ничтожно мало даже для бюджетных телефонов 5-летней давности, а вот 1 мегабайт данных это уже может быть неприятно для слабого интернета (а он может быть слабым просто в дороге).

[WbICHA]

Впрочем, ладно, всё сильно зависит от условий.

[profesor08]

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

При этом ничего не мешает кешировать список простых чисел.

Ничего не мешает, поэтому файлик с сгенерированными данными. При этом памяти будет заниматься, независимо от количества прогонов, примерно одинаково с поправкой на внутреннее выделением чего-то там в самом js.

Так что на 2 миллиона разница всего в 2 раза, а обьём передаваемых данных отличается на порядки.

Не стоит забывать, что загрузка данных происходит асинхронно, эти данные можно поместить в кеш браузера, и таскать оттуда.
Еще можно генерировать данные на клиенте, но браузер может подвиснуть, зависит от реализации. А так-же придется генерировать при каждом обновлении страницы.

[WbICHA]

profesor08,

Каждый раз генерировать нет никакого смысла, все уже сгенерировано.

А зачем тогда сжимают изображения, видео и т.д., если всё уже сгенерированно в высоком качестве?)

При этом памяти будет заниматься, независимо от количества прогонов, примерно одинаково с поправкой на внутреннее выделением чего-то там в самом js.

Ага, при этом по верхней границе, даже если нам нам нужна 10ая часть.

А так-же придется генерировать при каждом обновлении страницы.

А что мешает сохранить массив в локалсторедже после генерации?

На всякий случай проясню, я не против твоего решение, просто оно явно не является лучшим решением на все случаи жизни.

[profesor08]

WbICHA,

А зачем тогда сжимают изображения, видео и т.д., если всё уже сгенерированно в высоком качестве?)

Вот как раз таки затем, чтоб не рисовать их в браузере, а передать готовое. Аналогично и файлик текста в мегабайт сожмется через gzip.

Ага, при этом по верхней границе, даже если нам нам нужна 10ая часть.

1mb для хранения данных будет занят. Зато подсчитывай сумму сколько хочешь.

А что мешает сохранить массив в локалсторедже после генерации?

Ну попробуй сохрани мегабайт в localstorage.

[WbICHA]

profesor08,

Вот как раз таки затем, чтоб не рисовать их в браузере, а передать готовое.

Тебя не смущает, что компрессия и декомпрессия затрачивает ресурсы? Высчитывание всех простых с нуля это тоже своего рода сжатие.

1mb для хранения данных будет занят. Зато подсчитывай сумму сколько хочешь.

Как и в случае высчитывания простых, если кэшировать результат. Причём можно кешировать ещё и результат.

Ну попробуй сохрани мегабайт в localstorage.

Ты это серьёзно написал?
https://www.google.com/search?q=localstorage+max+size

[profesor08]

WbICHA,

компрессия и декомпрессия затрачивает ресурсы?

работает для всего, включена всегда. Ей занимается вебсервер и браузер в момент передачи информации.

Высчитывание всех простых с нуля это тоже своего рода сжатие.

Мартышкин труд.

Как и в случае высчитывания простых, если кэшировать результат. Причём можно кешировать ещё и результат.

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

Ты это серьёзно написал?

5мб на все хранилище, а не на одну запись. Для кеширования есть другие механизмы, доступные только в вебворкерах и то не везде.

[WbICHA]

profesor08,

работает для всего, включена всегда. Ей занимается вебсервер и браузер в момент передачи информации.

Какой ужас. Мартышкин труд.

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

Я не понимаю, ты троллишь или что?

5мб на все хранилище, а не на одну запись.

Вместо тысячи слов:

Ну попробуй сохрани мегабайт в localstorage.

В общем, ладно, я на это закончу, "Куратор тега JavaScript" ─ это уже клеймо некомпетентности, в который раз убеждаюсь.

[Alexandroppolus]

profesor08,

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

учитывая, что он генерится за доли секунды, вряд ли считывание из кэша (то есть с диска) будет намного быстрее. К тому же тут ещё затраты на парсинг раздутого html/js, что тоже не бесплатно.

[profesor08]

WbICHA,

В общем, ладно, я на это закончу, "Куратор тега JavaScript" ─ это уже клеймо некомпетентности, в который раз убеждаюсь.

фыркнуть и слиться

[profesor08]

Alexandroppolus, сложность генерации растет не линейно. Считать файл с диска, распарсить и посчитать сумму будет быстрее, чем генерация налету.

[WbICHA]

profesor08,

фыркнуть и слиться

Куратор во всей красе.

☑ Игнорировать аргументы собеседника.
☑ Забывать про свои же вопросы, на которые собеседник отвечает.
☑ Придерживаться позиции "есть два мнения ─ моё и неправильное".
☑ Когда собеседнику это надоест, сказать, что он слился.

[Alexandroppolus]

profesor08, не линейно.
Из википедии:

Сложность алгоритма составляет O(n * log(log (n))) операций при составлении таблицы простых чисел до n

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

[profesor08]

WbICHA,
☑ хлопать ушами
☑ объявить об уходе публично обвинив всех несогласных в некомпетентности

[profesor08]

example1:
Alexandroppolus 1000 times: 3.477s
142913828922
mem: 0.0791778564453125MB

example2:
prof 1000 times: 113.003ms
142913828922
mem: 2.4878768920898438MB

[WbICHA]

profesor08, ты серьёзно прогнал 1000 раз генерацию без буферизации? Зачем? Для чего? Что ты этим хотел продемонстрировать? То что 1000 генераций будут медленнее, чем 1000 использований готовых ответов? С этим что, кто-то спорил?

Благо ты верно подметил:

☑ хлопать ушами

Забыл включить это в список.

[profesor08]

WbICHA,

example1:
Alexandroppolus 1 times: 12.912ms
142913828922
mem: 0.6602020263671875MB

example2:
prof 1 times: 7.303ms
142913828922
mem: 1.8218231201171875MB

[profesor08]

WbICHA,

example1:
Alexandroppolus 1 times: 12.912ms
142913828922
mem: 0.6602020263671875MB

example2:
prof 1 times: 7.303ms
142913828922
mem: 1.8218231201171875MB

[WbICHA]

profesor08,

profesor08, какие ещё 7 минут 46 секунд? Решение Alexandroppolus на 2 миллиона тратит 15+-мс, да даже на 10 миллионов всего 90+-мс.
При этом ничего не мешает кешировать список простых чисел.
Так что на 2 миллиона разница всего в 2 раза, а обьём передаваемых данных отличается на порядки.

Можешь не отвечать, добавлю тебя в виртуальный чёрный список. Бессмысленно спорить с "Куратором тега JavaScript", который тупо игнорирует слова собеседника чуть более, чем полностью.

[profesor08]

WbICHA, недостаток знаний выливается в язвительные комментарии, классика. А нежелание вникать в результаты бенчмарка, это подтверждает. Считывание файла, парсинг, обработка и подсчет происходит быстрее чем генерация. Даже если полбу бить пруфами, до тебя не доходит.