Обновить
-19
0

Пользователь

Отправить сообщение

Если не заниматься бессмысленными перемещениями данных в памяти, то будет работать значительно быстрее.


Вот-такой код работает в ~60 раз быстрее, чем версия из статьи.


Хотя и стало немного многословнее, да.


import Foundation

// квадрат числа
extension Int {
    func powerOf2() -> Int {
        return self * self
    }
}

// до скольки считаем?
let max = 8_500_000

let startTime = Date()
// заполняем массив
var data = Array(repeating: true, count: max + 1) //(2...max).map{$0}
data[0] = false
data[1] = false
let allocationTime = Date()

// вычисления
for currentPrime in (2...Int(sqrt(Double(max)))) {
    if !data[currentPrime] {
        continue
    }

    for multiple in stride(from:currentPrime.powerOf2(), through: max, by: currentPrime) {
        data[multiple] = false
    }
}
let primes = (2...max).filter{data[$0]}
let overallTime = Date()

// выводим результаты
print("Всего \(primes.count) простых чисел")
print()
print("Выделение массива: \(String(format: "%.2f",(allocationTime.timeIntervalSince(startTime)))) с. ")
print("Вычисления: \(String(format: "%.2f",(overallTime.timeIntervalSince(allocationTime)))) с. ")
print("Всего: \(String(format: "%.2f",(overallTime.timeIntervalSince(startTime)))) с. ")

P.S.


К сожалению, запуск этого кода в плэйграунде на моем Mac Mini Late 2014 (Core i5, 8 ГБ) уже с параметром max = 1 000 000 приводит к диким тормозам, так что будьте осторожны

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

При чем тут какие-то веб-сервисы? Мы вроде как обсуждали конкретно вашу программу. В ней не нужно сортировать числа, структуры или что вы там ещё придумали для этого сервиса. В ней вы именно переизобрели strcmp и ничего больше. И теперь зачем-то требуете того-же от остальных. Или под «приведите код сравнения элементов» вы имеете в виду привести код одного вызова функции из стандартной библиотеки или стандартного оператора «меньше» (в зависимости от языка)?


А если говорить ещё более конкретно, я вас просил привести пример языка, который не умеет лексикографически сравнивать строки байт. Вы там заявили, что не любой язык такое умеет. Подтвердите чем-то свои слова. Приведите пример языка, который не умеет. Будьте программистом, а не балаболом.

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


Все, которые известны мне, это умеют. Вот сравнить их именно как строки (т.е. без учета регистра, с учетом кодировки, разных видов нормализации юникода) — уже не все языки умеют из коробки. И тут часто приходится писать свою реализацию.
А вот вы, судя по всему, зачем-то переизобрели стандартный сишный strcmp (к слову, абсолютно тривиально реализуемый) и жутко собой гордитесь по этому поводу.

У вас какое-то извращенное понимание целей и предназначения программиста и странный повод для гордости. Задача программиста за исключением редких случаев (ваш — не один из них), прежде всего — это писать понятный и поддерживаемый код. А не заниматься самоутверждением путем вываливания каких-то некомпилируемых обрывков кода, написанных не то в соавторстве с обфускатором, не то на компьютере с платными нажатиями клавиш и платным скроллингом (других причин использовать такие аббревиатуры в качестве идентификаторов и такое отвратительное форматирование в 201* году я не вижу).


Ну а касательно вашего вопроса о том, что делает выражение (да, господин программист, то, что вы написали — это не оператор, а выражение) вам уже ответили. Все, что можно понять из вашей строчки — это то, что происходит вызов какой-то функции через таблицу указателей и присваивание результата этого вызова какому-то полю какой-то структуры. Больше ничего из этой строчки узнать не представляется возможным. Если зайти на ваш сайт, то можно найти немного больший (но по-прежнему некомпилируемый и абсолютно бесполезный) огрызок кода, откуда родом эта строчка. Из него уже можно понять, что это часть интерпретатора какой-то виртуальной машины. Ну а почитав соседние страницы можно убедиться, что как и все остальное, к чему вы приложили руку, этот интерпретатор и эта виртуальная машина просто идеальны, лишены всех недостатков, и способны радикально изменить мир в лучшую сторону. Но человечество не понимает. Ибо нет настоящих программистов кроме вас.

Да нет, ввод и вывод все же не имеет никакого отношения к алгоритму. Что в теории, что на практике.


Даже если бы вы топили не за алгоритм, а за вашу сортировальную программку с какой-то конкретной реализацией этого алгоритма и какой-то конкретной реализацией ввода-вывода — ваши измерения и выводы про "худший случай всего в 2 раза медленней лучшего, а значит линейно!" все равно ничего не говорили бы даже о реальной производительности этой программки. Хотя бы в силу того, что история умалчивает, какая машина занималась сортировкой и с какого носителя производилось чтение и запись. Да что там, она даже умалчивает конкретные цифры, сколько времени занимала сортировка разного размера списков.


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


А я — практик

Скажите мне, как практик практику, каким образом я могу на практике убедиться в эффективности вашего алгоритма или хотя бы реализации? Если так жалко кода — дайте хотя бы экзешник. Планируемый онлайн-сервис — задумка бредовая. Во-первых, хоть сколько-нибудь большой объем отсортировать не получится из-за банальных отвалов по таймауту (разве что вы заморочитесь и сделаете каким-то образом асинхронные задачи). Во-вторых, сортирующим и измеряющим по-прежнему будет недоступна информация о железе сервера и его загруженности в момент сортировки. И в-третьих, судя по вашим подходам, время сортировки ваш сервис будет измерять с учетом загрузки и выгрузки данных по сети, так что опять таки окажется, что время работы вообще КОНСТАНТА!1! А для плохого мобильного интернета — так и вообще иногда убывающая функция!

Причём самая длинная часть — это ЗАПИСЬ отсортированного списка в файл. Чуть быстрее работает чтение

Которые не имеют никакого отношения к алгоритму сортировки.


Чтобы говорить о производительности алгоритма сортировки, нужно измерять именно время сортировки, а не время ввода-вывода, время запуска jvm, время прогрева jit-компилятора и т.д.


Иначе с таким же успехом можно говорить, что самая длинная часть — это включение компьютера, а потому "реальная сложность работы программы — константа" (с). Можно даже насортировать ради этого десятки и сотни миллиардов элементов (не забывая перезагружать компьютер перед каждой сортировкой)! Так что РЕАЛЬНАЯ скорость работы получится именно КОНСТАНТНАЯ!

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

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

Во-первых, это не какой-то волшебный шум, который можно незаметно подмешать к любой картинке и тем самым удавить любую нейросеть. Если есть доступ к нейросети и входной картинке — да, можно добавить незаметного шума к конкретной картинке так, чтобы сломалась конкретная нейросеть. Только в случае со Стадией доступа к нейросети нет вообще. И даже доступ к входной картинке очень сильно ограничен хотя-бы в силу того, что она будет пережата видео-кодеком и весь "незаметный" шум бесследно растворится во вполне заметных артефактах сжатия.


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

А* учитывает не только эвристическое расстояние до цели, но и текущую длину пути. Так что как только пройденная часть "длинного обхода аппендикса" станет длиннее, чем путь "шаг в сторону и потом по прямой" — алгоритм переключится на рассмотрение и расширение последнего.


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

Под строгой типизацией как раз имеется ввиду статическая

Кем имеется в виду? Лично вами? Тогда об этом стоило написать под картинкой (если вы не ее автор. Если вы автор, то стоило разобраться с матчастью и использовать на картинке термины в общепринятом смысле). Потому что характеристика "строгая" в отношении типизация всегда была синонимом характеристики "сильная". Никак не "статическая".

Рассказывать алгоритм на графах не через графы — довольно спорный подход. Даже если и удастся так что-то объяснить "через школьную арифметику", то обучающийся в лучшем случае научится просто самостоятельно писать А* для задач, полностью аналогичных примеру. Немного в сторону — и будут большие проблемы. В качестве примеров "отхода в сторону":


  • появление направленных ребер (как в статье — с крыши на землю спрыгнуть можно, обратно — нет)
  • появление ячеек с разной проходимостью (по песку идти медленнее, чем по асфальту)
  • оптимизация по другому параметру (не длина пути, а время в дороге/количество топлива и т.д.)
  • в конце концов, просто задача не связанная с перемещением в пространстве. Для многих игрушек АИ оппонента вполне можно написать через А*, где ребра графа — действия АИ, а узлы — состояния агента либо всей игры.

Эта статья дает намного более фундаментальное понимание, что такое поиск на графе вообще, что такое А* в частности, как он работает и с чем его едят. И если и не дает готовых решений проблем выше, то по крайней мере очень хорошо показывает направление, куда копать. А в случае объяснения на пальцах без графов "через школьную арифметики" у меня большие сомнения, что все будет так просто. Более того, есть ощущение, что как минимум часть из тех проблем покажутся вообще нерелевантными для А*.


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

Ну чесно говоря, причин писать сортировку руками я тоже особо придумать не могу. Параметров key и cmp вполне достаточно для описания любой сортировки.


Разве что это какие-то экзотические ситуации, типа данных, не влезающих в память и требующих сортировки слиянием или каких-то специфических данных, требующих сортировки без сравнений (подсчетом/поразрядной). Но мне кажется, для большинства таких ситуаций python все равно не тот язык, который будет использоваться.

мои предложения грамматики искажения примером являются.

Ну в русском скорее стилистики, а не грамматики. В английском — да, вот такие перестановки слов были бы грамматическими ошибками.

andreyons это упомянул :)


А ещё, слово «like» может означать «подобно». И можно воспринять «Sally like pizza» как неправильный вариант «Sally is like a pizza», что значит «Салли подобна пицце»,

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


В вашем комменте тоже есть куча "ненужных" букв, диакритических знаков и знаков препинания, которые "не несут в себе абсолютно никакого смысла" и без которых коммент останется вполне понятным. Но вы же их почему-то написали.

Вангую, сейчас вам скажут, что если возникла такая ситуация, то робомобиль боковой интервал не соблюдал. Он должен был либо исказить пронстранственно-временной континуум, расширив 3,5-метровую полосу до 20 метров, либо узнать будущее, предсказать выпадение человека из автобуса и снизить скорость заранее. "А иначе зачем такой робомобиль нужен?" (с)

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

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

Это вам тоже показалось. Никто такой цели не ставил.


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

Но выбор все равно делать нужно. Невозможно полностью избежать подобных ситуаций.


первым делом подумал не:… а: ...

Разработчик в любом случае подумает и о первом и о втором. Потому что ДТП с жертвами — это в любом случае репутационные потери. А от того, насколько общественно приемлемое действие предпринял автопилот, зависит объем этих потерь.
Если вас так волнует тот факт, что разработчик задумается об этом не из чистых высоко-моральных побуждений, а по причине банальных и бездуховных потерь денег и репутации — тогда да, вы правы. Стоит запретить робомобили, да и вообще весь бизнес как явление. На всякий случай, там ведь очень часто всем движет отнюдь не мораль.


А штрафы и презумпция виновности — это способ надавить на корпорации

Нет. В вашей радикальной формулировке — это способ уничтожить индустрию.


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

Чем больше вас читаю, тем больше складывается впечатление, что вам важнее наличие возможности быстро найти (или назначить) виноватого, чем более безопасное движение на дороге.


Водитель-человек не в состоянии обеспечить ни одно из ваших условий. "Зачем такой водитель нужен?" (с)
Что дальше? Будем за аварии штрафовать автошколы, в которых водитель учился? Может родителей оштрафовать, которые такого водителя зачали? Врачей, которые вовремя не убедили сделать аборт? Или запретим автомобили в принципе?

Проводя такие исследования компании заранее пытаются

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


мы заранее снимаем с себя ответственность

Ну вы прям правду-матку рубите. Снимать ответственность, которой нет и никогда не было — это сильно. За все, что происходит с автомобилем, отвечает водитель, независимо от того, корректно работает автопилот или нет и есть ли он в машине вообще.

Информация

В рейтинге
Не участвует
Откуда
Украина
Зарегистрирован
Активность