Здравствуйте, FR, Вы писали:

FR>У меня такой вопрос какие задачи ложатся на ФЯ лучше чем на ИЯ. Просто из своего опыта и из тех веток где была задача с простыми числами, у меня сложилось впечатление что даже многие математические задачи проще решаются ИЯ, например у той же задачи про решето Эратосфена сишная реализация намного прозрачнее и ближе к описанию алгоритма на естественном языке.

Задачи, где необходимо работать со сложными типами данных типа деревьев, списков, скорее всего будут более эффективно решаться на ФЯ. Задачи связанные с большим количеством вычислений над простыми типами (int и т.п.), работой с массивами и т.п. будут работать быстрее на ИЯ.
К первым задачам можно отнести всякие системы компьютерной алгебры, символьных вычислений, доказательств теорем, компиляторы с парсерами и т.п. Ко второй — численные задачи с большим объемом вычислений.
Решето Эратосфена как раз императивная задача, поскольку сводится к изменению массива.

Здравствуйте, Gaperton, Вы писали:

G>Здравствуйте, FR, Вы писали:

FR>>Здравствуйте, Gaperton, Вы писали:

FR>>По тестам которые ты выше привел, на другой странице я нашел тест с psyco(jit компилятор питона) у них результаты практически одинаковы с интерпретатором, у меня при включении psyco тест срабатывает в 25 раз быстрее чем интерпретируемый, если они и с остальными языками также намеряли, то доверия к ним нет никакого.
G>Возможно, у них старая версия этого psyco. Возможно, это просто ошибка. Возможно, ты смотришь страницу где включено время старта проги. Если ты им напишешь, они поправят.

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

Здравствуйте, hrg, Вы писали:

hrg>Мне вот интересно, как с помощью ФП пишется бизнес- логика? Как описать
hrg>поведение не_знаю_как_будет_в_ФП_объекты? Такие вот банальные
hrg>сермяжно-прагматические вопросы

Объектов в большинстве ФЯ нет. Там есть свои способы изолировать технические детали реализации от сути программы. В Haskell'е есть монады, например, и классы типов. Классы типов по сути, кстати, есть классы в понимании С++, только поскольку переменных в языке нет, то и нет возможности представить объект как отдельную сущность, т.е. классы в Хаскелле — это классы в С++ без членов-переменных и где все функции статические.

Здравствуйте, VladD2, Вы писали:

VD>Насколько я понял, ОКамл как раз и работает более менее быстро из-за того, что в нем введены императивные средства, на которых и реализованы базовые алгоритмы. И по мне, так очень разумное решение. Вот еще бы более приличный императивный синтаксис. Да и вообще сделать бы синтаксис по ближе к мэйстримным С-подобным языкам. Было бы куда проще осваивать.

В OCaml есть парсер P4, с помощью которого можно сделать свой собственный синтаксис — хочешь императивный, хочешь функциональный.

Здравствуйте, VladD2, Вы писали:


_>>3.Где активно применяется рекурсия например LL — разбор

VD>Но опчему-то для постраения парсеров в ФЯ все равно создают постоители парсеров (вроде Яка/Лекса). А ЛЛ(1) легко делается методом рекурсивного спуска на любом ИЯ.

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

Здесь только часть парсера, чтобы была понятна идея. Думаю, надо написать LL парсер C# на Haskell'e и сравнить с вашей реализацией.

-----------------------------------------------------------
-- GRAMMAR ELEMENTS
-----------------------------------------------------------
compilationUnit :: Parser CompilationUnit
compilationUnit =
    do{ whiteSpace
      ; reserved "package"
      ; name  <- option [""] packageName
      ; decls <- option []   declarations
      ; eof
      ; return $ Package name decls
      }

-----------------------------------------------------------
-- Declarations
-----------------------------------------------------------
declarations =
    braces (semiSep1 declaration)

declaration =
        importDeclaration
    <|> classDeclaration
    <|> variableSignatureDeclaration
    <?> "declaration"

variableSignatureDeclaration =
    do{ name <- variableName
      ; variableDeclaration name <|> signatureDeclaration name
      }

variableDeclaration name =
    do{ symbol "="
      ; expr <- expression
      ; return $ VarDecl name expr
      }
    <?> "variable declaration"

importDeclaration =
    do{ reserved "import"
      ; name <- packageName
      ; star <- option [] (do{ symbol "."
                             ; symbol "*"
                             ; return ["*"]
                             })
      ; return $ ImportDecl (name ++ star)
      }

classDeclaration =
    do{ reserved "class"
      ; name    <- className
      ; extends <- option [] (do{ reserved "extends"
                                ; n <- className
                                ; return [n]
                                })
      ; decls   <- option [] declarations
      ; return $ ClassDecl name extends decls

      }

signatureDeclaration name =
    do{ symbol "::"
      ; texpr  <- typeExpression
      ; return $ SigDecl name texpr
      }
    <?> "type declaration"


-----------------------------------------------------------
-- Expressions
-----------------------------------------------------------
expression :: Parser Expr
expression =
        lambdaExpression
    <|> letExpression
    <|> newExpression
    <|> infixExpression
    <?> "expression"

lambdaExpression =
    do{ symbol "\\"
      ; name <- variableName
      ; symbol "->"
      ; expr <- expression
      ; return $ groupLambdas (Lambda [name] expr)
      }

letExpression =
    do{ reserved "let"
      ; decls <- declarations
      ; reserved "in"
      ; expr <- expression
      ; return $ Let decls expr
      }

newExpression =
    do{ reserved "new"
      ; name  <- className
      ; decls <- option [] declarations
      ; return $ New name decls
      }

Здравствуйте, FR, Вы писали:

FR>Здравствуйте, Gaperton, Вы писали:

FR>По тестам которые ты выше привел, на другой странице я нашел тест с psyco(jit компилятор питона) у них результаты практически одинаковы с интерпретатором, у меня при включении psyco тест срабатывает в 25 раз быстрее чем интерпретируемый, если они и с остальными языками также намеряли, то доверия к ним нет никакого.

Я думаю, они там тестировали только интерпретатор.

Здравствуйте, WolfHound, Вы писали:

WH>До 8192 это даже не смешно. Вот если они сделают тесты до 10'000'000 вот тогда будет понятно кто тут рулит. К стати почему там нет VC++?

Потому что они использовали только свободные компиляторы/интерпретаторы, которые есть в Debian.

Здравствуйте, Gaperton, Вы писали:

G>Он расписался

Автор: Gaperton
Дата: 13.09.04

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

sieve :: [Int] -> [Int]
sieve [] = []
sieve (h:t) = h : sieve [x| x<-t, x`mod`h /= 0]

И что мы видим? А видим мы то что каждое число делится на все простые числа меньше минимального простого делителя те для простых чисел мы получаем что они делятся на все простые числа меньшие данного простого числа.
Для простоты принебрегаем составными числами.
Учитывая что плотность простых чисел примерно N/ln(N) то мы получаем сложность O((N/ln(N))^2) что гораздо хуже чем O(N^(3/2)) у алгоритма в лоб. А если учесть что N/ln(N) это оценка снизу и то что мы забыли про составные числа то картина становится мягко говоря плачевной.

Quintanar -> "Re[4]: ФП: вводная статья" :

Q> Здравствуйте, hrg, Вы писали:

hrg>> Мне вот интересно, как с помощью ФП пишется бизнес- логика? Как
hrg>> описать поведение не_знаю_как_будет_в_ФП_объекты? Такие вот
hrg>> банальные сермяжно-прагматические вопросы

Q> Объектов в большинстве ФЯ нет. Там есть свои способы изолировать
Q> технические детали реализации от сути программы. В Haskell'е есть
Q> монады, например, и классы типов. Классы типов по сути, кстати, есть
Q> классы в понимании С++, только поскольку переменных в языке нет, то и
Q> нет возможности представить объект как отдельную сущность, т.е.
Q> классы в Хаскелле — это классы в С++ без членов-переменных и где все
Q> функции статические.

Спасибо. Интересно, но не понятно

Yury Kopyl aka hrg | http://id.totem.ru | "Спам придумали боги в отместку
за наши молитвы."

Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, Gaperton, Вы писали:

G>>Он расписался

Автор: Gaperton
Дата: 13.09.04

также в том, что заметил лучшую асимптотику твоего алгоритма но не хочет заниматься алгоритмической оптимизацией. Лень ему, понимаешь, и смысла в этом он не видит. Что ты сравнить хочешь, эффективность компиляторов, или что?
WH>Я хочу сравнить компиляторы на алгоритме с одинаковой асимптотикой. И еще хочу увидить реализацию алгоритма на функциональном языке(без императивности)с тойже асимптотикой что и у меня.
Я тоже хочу именно этого. Приступим. Вот дословный перевод твоего алгоритма на Clean.

// фигня всякая...
import StdClass
import StdInt, _SystemArray, StdEnum

/*
Давай мы все-таки не будем меряться скоростью свопа и количеством оперативки, хорошо? :)))
Твоя прога выделяет минимум гигабайт памяти - у меня столько нет.
Так что давай меряться на 100 миллионах, ок? ;)
*/     
Size :== 100000000 

// функция - аналог главного цикла. 
sieve primes i
    | i == Size    = primes // здесь, типа, выходим из цикла
    | primes.[ i ] = sieve { primes & [n] = False \\ n <- [ 2*i, 3*i..(Size - 1) ] } ( i + 1 ) // здесь вычеркиваем
                        = sieve primes ( i + 1 ) // а здесь пустая итерация

// уникальный массив unboxed bool длины Size инициализированный True. Будет меняться деструктивно.
IsPrime:: .{#Bool}
IsPrime = createArray Size True

Start:: Bool
Start =    ( sieve IsPrime 2 ).[31] // ломает меня с вводом-выводом разбираться. Поэтому просто вернем значение ячейки №31.

Как видишь, получилось короче — в основном заслуга array и list comprehensions.

Сами числа не распечатывал, так как ломало ковыряться с Clean-овским вводом-выводом.
Вот exe. http://www.rsdn.ru:80/File/20496/fsieve2.exe

23.59 секунд на моей системе.

WH>Кстати либо я чего не понял либо алгоритм по твоей ссылке имеет асимптотику хуже чем алгоритм "в лоб"
Не, у меня в тот раз была асимптотика O(N*sqrt(N)) — я делал отсечку по sqrt. А перебирал с шагом 4-6-4-6-4-6...

Здравствуйте, hrg, Вы писали:

hrg>Спасибо. Интересно, но не понятно

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

Если посмотреть на стандартные библиотеки в ФЯ, то видно, что близкие по смыслу функции выделяются в отдельные модули типа HashTable, FiniteMap, Tree и т.п.

Есть и другие методы организации вычислений кроме объектного-ориентированного — монады, стрелки, continuation passing style, может еще чего. Все они могут быть реализованы и на С++, только смысла в этом будет немного (исключая CPS).

Гхм, эта... Вот, ассемблер, значить, какой получается...

    .data
m__fsieve:
    .long    6
    .ascii    "fsieve"
    .byte    0,0
    .text
    .globl    _start
_start:
    .globl    ____fsieve__Start
____fsieve__Start:
    cmpl    end_heap,%edi
    jae    i_1
i_2:
    movl    $n3,(%edi)
    movl    %edi,%ecx
    addl    $12,%edi
    jmp    __driver
    .align    4
    .long    0
n3:
    movl    %ecx,(%esi)
    movl    $__cycle__in__spine,(%ecx)
    leal    4(%esi),%esi
    call    ea3
    movl    -4(%esi),%ecx
    movl    $BOOL+2,(%ecx)
    movl    %eax,4(%ecx)
    leal    -4(%esi),%esi
    ret
ea3:
s3:
    call    s2
    movl    $2,%eax
    call    s5
    movzbl    43(%ecx),%eax
    ret
s5:
    cmpl    $100000000,%eax
    jne    else_P1
    ret
else_P1:
    movzbl    12(%ecx,%eax),%ebx
    testl    %ebx,%ebx
    je    else_P2
    cmpl    end_heap,%edi
    jae    i_3
i_4:
    movl    %ecx,(%esi)
    movl    %eax,%ebx
    addl    $1,%ebx
    pushl    %ebx
    pushl    $e_0
    movl    $100000000,%ebx
    subl    $1,%ebx
    pushl    %ebx
    movl    %eax,%ebx
    shl    $1,%ebx
    movl    %eax,%edx
    shl    $1,%edx
    addl    %edx,%eax
    movl    $__cycle__in__spine,(%edi)
    movl    %edi,%ecx
    addl    $12,%edi
    leal    4(%esi),%esi
    jmp    e____SystemEnum__s__from__then__to_I10
e_0:
    movl    -4(%esi),%edx
    leal    -4(%esi),%esi
    call    s6
    popl    %eax
    jmp    s5
else_P2:
    addl    $1,%eax
    jmp    s5
s6:
    xchg    %edx,%ecx
s8:
    cmpl    $__Cons+18,(%edx)
    jne    case_P4
case_P3:
    movl    %ecx,(%esi)
    movl    4(%edx),%ecx
    movl    8(%edx),%edx
    leal    4(%esi),%esi
    testb    $2,(%edx)
    jne    e_1
    movl    %ecx,(%esi)
    addl    $4,%esi
    movl    %edx,%ecx
    call    (%edx)
    movl    %ecx,%edx
    movl    -4(%esi),%ecx
    subl    $4,%esi
e_1:
    testb    $2,(%ecx)
    jne    e_2
    movl    %edx,(%esi)
    addl    $4,%esi
    call    (%ecx)
    movl    -4(%esi),%edx
    subl    $4,%esi
e_2:
    movl    -4(%esi),%eax
    pushl    %eax
    movl    4(%ecx),%eax
    popl    %ebx
    movb    $0,12(%ebx,%eax)
    movl    %edx,%eax
    movl    %ebx,%edx
    movl    %eax,%ecx
    leal    -4(%esi),%esi
    jmp    s6
case_P4:
    ret
s2:
    movl    $1,%eax
    movl    $100000000,%ebx
    call    create_arrayB
    ret
i_1:
    call    collect_0
    jmp    i_2
i_3:
    call    collect_1
    jmp    i_4

Компере ву?

Здравствуйте, FR, Вы писали:

FR>Здравствуйте, Gaperton, Вы писали:


G>>А на самом деле это один из вариантов ZF-нотации, что и есть list comprehensions. В питоне заимствовано из функциональных языков.
G>>ltList = [ y | y <- tail( aList ), y < head( aList ) ]

FR>а я говорю они это из пролога уперли

Из Haskell-а. Ещё в версии 2.0.
Кстати, list comprehensions, мягко говоря, не самая быстрая часть языка (хоть и удобная).
Лично мне больше понравились расширенная семантика итераторов (модуль itertools), которая была введена в 2.3.

Здравствуйте, Gaperton, Вы писали:

G>Как видишь, получилось короче — в основном заслуга array и list comprehensions.
Впрочем нет — получилось совершенно одинаково

Здравствуйте, FR, Вы писали:

FR>Здравствуйте, Gaperton, Вы писали:


G>>А на самом деле это один из вариантов ZF-нотации, что и есть list comprehensions. В питоне заимствовано из функциональных языков.
G>>ltList = [ y | y <- tail( aList ), y < head( aList ) ]
FR>а я говорю они это из пролога уперли
Да ладно тебе

FR>На питоне можно писать и в чисто функциональном стиле, я не спорю, просто тот же list comprehensions в питоне на обычный язык все таки переводится как императивный алгоритм,
Так и в функциональных языках это не святым духом выполняется . Если нет ленивых вычислений, то функциональный код без проблем транслируется в императивный, с цыклами (хвостовая рекурсия переводится в цикл). Что, собственно, и происходит даже в ленивых языках. Смотри, что произошло с моим примером на Clean: http://www.rsdn.ru/Forum/Message.aspx?mid=828170&amp;only=1

Автор: Gaperton
Дата: 28.09.04

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

Здравствуйте, Gaperton, Вы писали:


FR>>На питоне можно писать и в чисто функциональном стиле, я не спорю, просто тот же list comprehensions в питоне на обычный язык все таки переводится как императивный алгоритм,
G>Так и в функциональных языках это не святым духом выполняется . Если нет ленивых вычислений, то функциональный код без проблем транслируется в императивный, с цыклами (хвостовая рекурсия переводится в цикл). Что, собственно, и происходит даже в ленивых языках. Смотри, что произошло с моим примером на Clean: http://www.rsdn.ru/Forum/Message.aspx?mid=828170&amp;only=1

Автор: Gaperton
Дата: 28.09.04

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

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

Угу, к сожалению функциональные языки (я сейчас ocaml ковыряю) оказались не такими удобными, вроде бы и абстракция на самом деле выше, но все равно они кажутся более далекими от человеческого мышления

Здравствуйте, FR, Вы писали:

FR>Угу, к сожалению функциональные языки (я сейчас ocaml ковыряю) оказались не такими удобными, вроде бы и абстракция на самом деле выше, но все равно они кажутся более далекими от человеческого мышления

Это только так кажется на первый взгляд.

Здравствуйте, FR, Вы писали:

FR>Угу, к сожалению функциональные языки (я сейчас ocaml ковыряю) оказались не такими удобными, вроде бы и абстракция на самом деле выше, но все равно они кажутся более далекими от человеческого мышления

Навеяло.

Он обнажил меч и прикинул вес: проделав им несколько пробных взмахов.
— Никудышный баланс, — поморщился он.
— Вы к нему привыкнете.
— Паршивая сталь, — провозгласил он, пристально разглядывая меч.
— Однако с приличной режущей кромкой.
— Ну, мой тренер всегда мне говорил: "Если ты позаботишься о своем
мече, то он позаботится о тебе!"
— Нас, должно быть, обучал один и тот же тренер.
Они улыбнулись друг другу. Я почувствовал себя слегка нехорошо.
— И все же я не знаю. Пятьдесят золотых — большие деньги.
— Да вы только посмотрите на эти камни в рукояти.
— Смотрел. Они фальшивые.
— Ага! Они сделаны так, чтобы выглядеть фальшивыми. Это скрывает их
ценность.
— Безусловно, делает это здорово. Что это за камни?
— Камни Афера.
— Камни Афера?
— Да. Говорят, что они обеспечивают популярность у женщин, если вы
понимаете, что я имею в виду.

http://www.lib.ru/ASPRIN/myth_1.txt

Ну вот опять — обсуждение статьи 5 постов а остальное 'Нужны ли ФЯ.Какая область применимости.Banchmakrs.....'
Было же в двух или трех топиках.Сколько можно.
Что не у кого нет предложений и замечаний по статье.

Здравствуйте, Gaperton, Вы писали:

G>Я тоже хочу именно этого. Приступим. Вот дословный перевод твоего алгоритма на Clean.
Так так... Деструктивное изменение массива... те от функционального языка остался только синтаксис...

G>Давай мы все-таки не будем меряться скоростью свопа и количеством оперативки, хорошо?
А у тебя что меньше ста дватцати метров?
G>Твоя прога выделяет минимум гигабайт памяти — у меня столько нет.
Не она выделяет примеро 120 метров... ибо std::vector<bool> это массив битов по стандарту...
G>Так что давай меряться на 100 миллионах, ок?
Да мне пофигу.
G>ломает меня с вводом-выводом разбираться. Поэтому просто вернем значение ячейки №31.
Ой как все запущено то...
G>Как видишь, получилось короче — в основном заслуга array и list comprehensions.
Да я бы не сказал.

    unsigned size=1000000000;
    std::vector<bool> is_prime(size, true);//помечаем все числа как простые
    for(unsigned i=2;i<size;++i)//ищем очередное не вычеркнутое число
        if(is_prime[i])
            for(unsigned n=i+i;n<size;n+=i)//вычеркиваем все числа кратные данному числу
                is_prime[n]=false;

; 6    :     unsigned size=100000000;
; 7    :     std::vector<bool> is_prime(size, true);    //помечаем все числа как простые

    lea    edx, DWORD PTR $T74423[esp+76]
    push    edx
    xor    esi, esi
    push    3125000                    ; 002faf08H
    lea    ecx, DWORD PTR _is_prime$[esp+88]
    mov    DWORD PTR _is_prime$[esp+84], esi
    mov    DWORD PTR $T74423[esp+84], -1
    call    ?_Construct_n@?$vector@IV?$allocator@I@std@@@std@@QAEXIABI@Z ; std::vector<unsigned int,std::allocator<unsigned int> >::_Construct_n
    push    100000000                ; 05f5e100H
    lea    ecx, DWORD PTR _is_prime$[esp+80]
    mov    DWORD PTR __$EHRec$[esp+88], esi
    call    ?_Trim@?$vector@_NV?$allocator@_N@std@@@std@@IAEXI@Z ; std::vector<bool,std::allocator<bool> >::_Trim

; 9    :         if(is_prime[i])                        //i очередное простое число

    mov    ebx, DWORD PTR _is_prime$[esp+84]
    mov    DWORD PTR __$EHRec$[esp+84], 1
    mov    edi, 2
    push    ebp
$L74729:
    xor    eax, eax
    mov    eax, edi
    mov    ecx, eax
    shr    ecx, 5
    and    eax, 31                    ; 0000001fH
    lea    edx, DWORD PTR [ebx+ecx*4]
    mov    ecx, eax
    mov    eax, DWORD PTR [edx]
    mov    esi, 1
    shl    esi, cl
    test    esi, eax
    je    SHORT $L64774

; 10   :             for(unsigned n=i+i;n<size;n+=i)    //вычеркиваем все числа кратные данному числу

    cmp    edi, 50000000                ; 02faf080H
    lea    edx, DWORD PTR [edi+edi]
    jae    SHORT $L64774

; 11   :                 is_prime[n]=false;

    xor    ebp, ebp
$L64833:
    mov    eax, ebp
    add    eax, edx
    mov    esi, eax
    mov    ecx, ebx
    shr    esi, 5
    lea    esi, DWORD PTR [ecx+esi*4]
    and    eax, 31                    ; 0000001fH
    mov    ecx, 1
    mov    DWORD PTR tv359[esp+80], ecx
    mov    ecx, eax
    mov    eax, DWORD PTR tv359[esp+80]
    shl    eax, cl
    mov    ecx, DWORD PTR [esi]
    add    edx, edi
    not    eax
    and    ecx, eax
    cmp    edx, 100000000                ; 05f5e100H
    mov    DWORD PTR [esi], ecx
    jb    SHORT $L64833
$L64774:

; 8    :     for(unsigned i=2;i<size;++i)            //ищем очередное не вычеркнутое число

    inc    edi
    cmp    edi, 100000000                ; 05f5e100H
    jb    SHORT $L74729

G>23.59 секунд на моей системе.
Execution: 21.31 Garbage collection: 0.21 Total: 21.53 и примерно 290 метров памяти.
Моя программа
8.66727 и примерно 12.8 метров памяти.

Хотя если выкинуть std::vector<bool> и работать с битами ручками то получается лучше хотя и не на много

const unsigned bits=CHAR_BIT*sizeof(unsigned);
void set_bit(unsigned n, unsigned* arr)
{
    unsigned pos=n/bits;
    unsigned ofs=n%bits;
    arr[pos]|=1<<ofs;
}
bool get_bit(unsigned n, unsigned* arr)
{
    unsigned pos=n/bits;
    unsigned ofs=n%bits;
    return arr[pos]&(1<<ofs);
}
int main()
{
    timer_t timer;
    unsigned size=100000000;
    std::vector<unsigned> v(size/bits+1);
    unsigned* arr=&v[0];
    for(unsigned i=2;i<size;++i)//ищем очередное не вычеркнутое число
        if(!get_bit(i, arr))//в i очередное простое число
            for(unsigned n=i+i;n<size;n+=i)//вычеркиваем все кратные данному числу
                set_bit(n, arr);
    std::cout<<timer.time()<<"\n";
    return 0;
}

; 65   :     unsigned size=1000000000;
; 66   :     std::vector<unsigned> v(size/bits+1);

    lea    edx, DWORD PTR $T72444[esp+76]
    push    edx
    xor    esi, esi
    push    31250001                ; 01dcd651H
    lea    ecx, DWORD PTR _v$[esp+84]
    mov    DWORD PTR $T72444[esp+84], esi
    call    ?_Construct_n@?$vector@IV?$allocator@I@std@@@std@@QAEXIABI@Z ; std::vector<unsigned int,std::allocator<unsigned int> >::_Construct_n

; 67   :     unsigned* arr=&v[0];
; 68   :     for(unsigned i=2;i<size;++i)//ищем очередное не вычеркнутое число

    mov    edi, DWORD PTR _v$[esp+80]
    mov    DWORD PTR __$EHRec$[esp+84], esi
    mov    esi, 2
    npad    6
$L72548:

; 69   :         if(!get_bit(i, arr))

    mov    ecx, esi
    and    ecx, 31                    ; 0000001fH
    mov    eax, 1
    shl    eax, cl
    mov    ecx, esi
    shr    ecx, 5
    test    eax, DWORD PTR [edi+ecx*4]
    jne    SHORT $L64574

; 70   :         {
; 71   :             //в i очередное простое число
; 72   :             for(unsigned n=i+i;n<size;n+=i)//вычеркиваем все кратные данному числу

    cmp    esi, 500000000                ; 1dcd6500H
    lea    edx, DWORD PTR [esi+esi]
    jae    SHORT $L64574
$L72547:

; 73   :                 set_bit(n, arr);

    mov    ecx, edx
    and    ecx, 31                    ; 0000001fH
    mov    eax, edx
    mov    ebp, 1
    shl    ebp, cl
    shr    eax, 5
    mov    ecx, DWORD PTR [edi+eax*4]
    add    edx, esi
    or    ecx, ebp
    cmp    edx, 1000000000                ; 3b9aca00H
    mov    DWORD PTR [edi+eax*4], ecx
    jb    SHORT $L72547
$L64574:

; 67   :     unsigned* arr=&v[0];
; 68   :     for(unsigned i=2;i<size;++i)//ищем очередное не вычеркнутое число

    inc    esi
    cmp    esi, 1000000000                ; 3b9aca00H
    jb    SHORT $L72548

8.45668


G>Не, у меня в тот раз была асимптотика O(N*sqrt(N)) — я делал отсечку по sqrt. А перебирал с шагом 4-6-4-6-4-6...
Да я не про твою, а про тот тест который лежит тут